An entropy proof of the Kahn-Lovász theorem

zbMATH Open1229.05137MaRDI QIDQ625372FDOQ625372

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

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

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

zbMATH Keywords

bipartite graphperfect matchingsdegree sequence

Mathematics Subject Classification ID

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

Cited In (15)

• Proof of an entropy conjecture of Leighton and Moitra
• Entropy of theK-Satisfiability Problem
• A simple proof of Wehrl's conjecture on entropy
• Extremal Graphs With a Given Number of Perfect Matchings
• Permanents of multidimensional matrices: Properties and applications
• An entropy proof of Bregman's theorem
• A proof of the Beyer-Stein-Ulam relation between complexity and entropy
• A proof of the Shepp-Olkin entropy monotonicity conjecture
• Title not available (Why is that?)
• An upper bound on the number of Steiner triple systems
• Tight bounds on the coefficients of partition functions via stability
• Entropic solution of the innovation conjecture of T. Kailath
• Asymptotics for Shamir's problem
• Asymptotics of the upper matching conjecture
• Graphs with the fewest matchings

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)