An entropy proof of the Kahn-Lovász theorem

MaRDI QIDQ625372zbMATH OpenFDO

Authors Jonathan Cutler, Andrew John Radcliffe

Publication date 17 February 2011

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

Full work available at URL https://eudml.org/doc/223259, http://www.emis.de/journals/EJC/Volume_18/Abstracts/v18i1p10.html

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

bipartite graphdegree sequenceperfect matchings

Mathematics Subject Classification ID

Vertex degrees (05C07) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

Summary: \textit{L. M. Brègman} [Sov. Math., Dokl. 14, 945--949 (1973); translation from Dokl. Akad. Nauk SSSR 211, 27--30 (1973; Zbl 0293.15010)], gave a best possible upper bound for the number of perfect matchings in a balanced bipartite graph in terms of its degree sequence. Recently \textit{J. Kahn} and \textit{L. Lovász} (unpublished) extended Brègman's theorem to general graphs. In this paper, we use entropy methods to give a new proof of the Kahn-Lovász theorem. Our methods build on \textit{J. Radhakrishnan}'s [J. Comb. Theory, Ser. A 77, No.\,1, 161--164 (1997; Zbl 0894.15007)] use of entropy to prove Brègman's theorem.

Recommendations

• Entropy bounds for perfect matchings and Hamiltonian cycles
• Matchings and independent sets of a fixed size in regular graphs
• An entropy proof of Bregman's theorem
• scientific article; zbMATH DE number 3308998
• Lower matching conjecture, and a new proof of Schrijver's and Gurvits's theorems

Cited in

(16)

• A proof of the Beyer-Stein-Ulam relation between complexity and entropy
• Proof of an entropy conjecture of Leighton and Moitra
• A proof of the Shepp-Olkin entropy monotonicity conjecture
• Asymptotics for Shamir's problem
• An upper bound on the number of Steiner triple systems
• Permanents of multidimensional matrices: properties and applications
• scientific article; zbMATH DE number 3139246 (Why is no real title available?)
• Asymptotics of the upper matching conjecture
• Entropy of theK-Satisfiability Problem
• A simple proof of Wehrl's conjecture on entropy
• Entropic solution of the innovation conjecture of T. Kailath
• Graphs with the fewest matchings
• Extremal graphs with a given number of perfect matchings
• An entropy proof of Bregman's theorem
• Tight bounds on the coefficients of partition functions via stability
• Entropy bounds for perfect matchings in bipartite hypergraphs

This page was built for publication: An entropy proof of the Kahn-Lovász theorem

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