An entropy proof of the Kahn-Lovász theorem
type: Item
instance of: scholarly article
title: An entropy proof of the Kahn-Lovász theorem
zbMATH Open document ID: 1229.05137
author: Jonathan Cutler
author: Andrew John Radcliffe
published in: The Electronic Journal of Combinatorics
publication date: 2011-02-17T00:00:00Z
full work available at URL: https://eudml.org/doc/223259
full work available at URL: v18i1p10.html
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.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C07
zbMATH DE Number: 5852460
zbMATH Keywords: perfect matchings
zbMATH Keywords: bipartite graph
zbMATH Keywords: degree sequence
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 5852460