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
    0 references
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references