Entropy bounds for perfect matchings and Hamiltonian cycles

DOI10.1007/s00493-009-2366-9zbMath1224.05029MaRDI QIDQ624182

Bill Cuckler, Jeffry Kahn

Publication date: 8 February 2011

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00493-009-2366-9

zbMATH Keywords

entropy; matching; Hamiltonian cycles; Dirac graphs

Mathematics Subject Classification ID

05C38: Paths and cycles

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05A16: Asymptotic enumeration

94A17: Measures of information, entropy

05C45: Eulerian and Hamiltonian graphs

Related Items

Extremal Graphs With a Given Number of Perfect Matchings, Asymptotics of the upper matching conjecture, Graphs with the fewest matchings, On the number of matrices and a random matrix with prescribed row and column sums and 0-1 entries, Hamiltonian cycles in Dirac graphs, On prisms, Möbius ladders and the cycle space of dense graphs

Cites Work

• Unnamed Item
• Hamiltonian cycles in Dirac graphs
• The maximum number of perfect matchings in graphs with a given degree sequence
• Some intersection theorems for ordered sets and graphs
• A short proof of Minc's conjecture
• On the number of Hamiltonian cycles in Dirac graphs
• An Entropy Approach to the Hard-Core Model on Bipartite Graphs
• Hamiltonian Cycles in Regular Tournaments
• Some Theorems on Abstract Graphs
• An entropy proof of Bregman's theorem