Channels, billiards, and perfect matching 2-divisibility

DOI10.37236/9151MaRDI QIDQ2034082zbMATH OpenOpenAlexFDO

Authors Grant T. Barkley, Ricky Ini Liu

Publication date 21 June 2021

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.37236/9151

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

billiardschannelsperfect matching

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

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.

Recommendations

• Billiards, channels, and perfect matching 2-divisibility
• Perfect matchings and perfect squares
• Perfect matchings of cellular graphs
• Generalizing the divisibility property of rectangle domino tilings
• Combinatorics of perfect matchings in plane bipartite graphs and application to tilings.

Cites work

• 2-adic behavior of numbers of domino tilings
• Applications of graphical condensation for enumerating matchings and tilings
• Combinatorial approaches and conjectures for 2-divisibility problems concerning domino tilings of polyominoes
• Dimers, webs, and positroids
• Domino tiling congruence modulo 4
• Enumeration of perfect matchings in graphs with reflective symmetry
• From dimers to webs
• scientific article; zbMATH DE number 487720 (Why is no real title available?)
• scientific article; zbMATH DE number 1405497 (Why is no real title available?)
• Kasteleyn cokernels
• Perfect matchings and perfect powers
• Smith normal form in combinatorics
• The kernel of the adjacency matrix of a rectangular mesh
• The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice
• Tiling parity results and the holey square solution
• Trees and matchings

Cited in

(5)

• Billiards, channels, and perfect matching 2-divisibility
• Powers of 2 in balanced grid colourings
• Homology in combinatorial refraction billiards
• The maximum number of cycles in a triangular-grid billiards system with a given perimeter
• Toric promotion with reflections and refractions

This page was built for publication: Channels, billiards, and perfect matching 2-divisibility

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2034082)