Channels, billiards, and perfect matching 2-divisibility (Q2034082)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Channels, billiards, and perfect matching 2-divisibility |
scientific article |
Statements
Channels, billiards, and perfect matching 2-divisibility (English)
0 references
21 June 2021
0 references
In this paper, the authors study channels, billiards, and perfect matching of a graph modulo 2. They introduce a number of combinatorial tools for determining the parity of perfect matchings and for giving a lower bound to the power of 2 dividing perfect matching numbers. Moreover, they study the channels which correspond to elements in the kernel of the adjacency matrix of a graph modulo 2, they give a new combinatorial proof of this result and strengthen it by showing that the number of channels gives a lower bound to the power of 2 dividing the perfect matching number when \(G\) is a planar graph, and describe a number of local graph operations which preserve the number of channels. Finally, they establish a surprising connection between 2-divisibility of the perfect matching number and dynamical systems by showing an equivalency between channels and billiard paths, and use billiard paths to give a fast algorithm for counting channels in simply connected regions of the square grid.
0 references
channels
0 references
billiards
0 references
perfect matching
0 references
0 references