Grid graphs, Gorenstein polytopes, and domino stackings

DOI10.1007/S00373-005-0858-YMaRDI QIDQ844215zbMATH OpenOpenAlexFDO

Authors Matthias Beck, Christian Haase, Steven V. Sam

Publication date 18 January 2010

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0711.4151

zbMATH Keywords

domino tilingsgrid graphsperfect matching polytopes

Mathematics Subject Classification ID

Combinatorial aspects of tessellation and tiling problems (05B45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Abstract: We examine domino tilings of rectangular boards, which are in natural bijection with perfect matchings of grid graphs. This leads to the study of their associated perfect matching polytopes, and we present some of their properties, in particular, when these polytopes are Gorenstein. We also introduce the notion of domino stackings and present some results and several open questions. Our techniques use results from graph theory, polyhedral geometry, and enumerative combinatorics.

Review text

This paper examines the properties of the prefect matching polytopes of grid graphs. In particular, the case where the polytope is Gorenstein is characterized. Perfect matchings of grid graphs are equivalent to domino tilings of rectangular boards. Domino stackings of height \(t\) generlize domino tilings, which are the case \(t=1\). The paper presents several results and open problems concerning domino stackings.

Recommendations

• On the multipacking number of grid graphs
• Gorenstein graphic matroids
• Gorenstein graphic matroids from multigraphs
• scientific article; zbMATH DE number 4008448
• scientific article; zbMATH DE number 7456252
• Graphs, matroids, and geometric lattices
• scientific article; zbMATH DE number 1778131
• On Gorenstein graphs
• Computing the domination number of grid graphs
• A polyhedral theory on graphs

Cites work

• h-vectors of Gorenstein polytopes
• A reciprocity theorem for domino tilings
• Brick decompositions and the matching rank of graphs
• Combinatorial aspects of mirror symmetry
• Combinatorial reciprocity theorems
• Compressed polytopes and statistical disclosure limitation
• Computing the Continuous Discretely
• Convex polytopes all of whose reverse lexicographic initial ideals are squarefree
• Decompositions of Rational Convex Polytopes
• Domino tilings of rectangles with fixed width
• Ehrhart polynomials, simplicial polytopes, magic squares and a conjecture of Stanley
• Generating functions for powers of Fibonacci numbers
• Gorenstein polytopes obtained from bipartite graphs
• scientific article; zbMATH DE number 3163858 (Why is no real title available?)
• scientific article; zbMATH DE number 3983158 (Why is no real title available?)
• Maximum matching and a polyhedron with 0,1-vertices
• On dimer coverings of rectangles of fixed width
• polymake: a framework for analyzing convex polytopes
• Polytopes, Rings, and K-Theory
• The perfect matching polytope and solid bricks
• The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice

Cited in

(6)

• Unconditional reflexive polytopes
• A survey of grid diagrams and a proof of Alexander's theorem
• Gorenstein polytopes obtained from bipartite graphs
• Generalized triangulations and diagonal-free subsets of stack polyominoes
• scientific article; zbMATH DE number 7456252 (Why is no real title available?)
• The Jones polynomials of three-bridge knots via Chebyshev knots and billiard table diagrams

Describes a project that uses

Uses Software

• polymake
• Normaliz

This page was built for publication: Grid graphs, Gorenstein polytopes, and domino stackings

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