Entropy bounds for perfect matchings and Hamiltonian cycles

DOI10.1007/s00493-009-2366-9zbMath1224.05029OpenAlexW2052478317MaRDI 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

entropymatchingHamiltonian cyclesDirac graphs

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Asymptotic enumeration (05A16) Measures of information, entropy (94A17) Eulerian and Hamiltonian graphs (05C45)

Related Items (8)

Counting Hamilton cycles in Dirac hypergraphs ⋮ Extremal Graphs With a Given Number of Perfect Matchings ⋮ Asymptotics of the upper matching conjecture ⋮ Asymptotics for Shamir's problem ⋮ On prisms, Möbius ladders and the cycle space of dense graphs ⋮ 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

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

This page was built for publication: Entropy bounds for perfect matchings and Hamiltonian cycles