An entropy proof of the Kahn-Lovász theorem (Q625372)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An entropy proof of the Kahn-Lovász theorem |
scientific article |
Statements
An entropy proof of the Kahn-Lovász theorem (English)
0 references
17 February 2011
0 references
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.
0 references
perfect matchings
0 references
bipartite graph
0 references
degree sequence
0 references