tailieunhanh - Báo cáo toán học: "An entropy proof of the Kahn-Lov´sz theorem a"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: An entropy proof of the Kahn-Lov´sz theorem a. | An entropy proof of the Kahn-Lovasz theorem Jonathan Cutler . Radcliffe Montclair State University University of Nebraska-Lincoln aradcliffe1@ Submitted Jun 9 2010 Accepted Dec 16 2010 Published Jan 5 2011 Mathematics Subject Classification 05C35 Abstract Bregman 2 gave a best possible upper bound for the number of perfect matchings in a balanced bipartite graph in terms of its degree sequence. Recently Kahn and Lovasz 8 extended Bregman s theorem to general graphs. In this paper we use entropy methods to give a new proof of the Kahn-Lovasz theorem. Our methods build on Radhakrishnan s 9 use of entropy to prove Bregman s theorem. 1 Introduction Entropy has recently emerged as a powerful tool in combinatorics see for instance 3 6 7 . Radhakrishnan 9 used entropy to give a new proof of Bregman s theorem. While Bregman s theorem is usually stated in terms of the permanent of a square 0 1 -matrix the equivalent version we state uses graph theoretic notation. If G is a graph we let T G be the set of perfect matchings of G and Ộ G G . Also if v G V G we denote the degree of v by d v . Theorem 1 Bregman 2 . If G G L R is a bipartite graph such that L R then HG n d v 1 d v . veL The extension of Bregman s theorem to general graphs was achieved by Kahn and Lovasz 8 and independently proved by Friedland 4 . Theorem 2 Kahn-Lovasz 8 . For G an arbitrary graph d G n d v 1 2d v . vev THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P10 1 The original proof of Kahn and Lovasz was never published see 3 . Friedland s proof is based on an extension of Schrijver s 10 proof of the Bregman inequality. A short proof deducing the result for general graphs from Bregman s theorem was given by Alon and Friedland 1 . This paper presents a new proof of Theorem 2 using entropy methods. We introduce the basics of entropy that will be used in this paper. For a more comprehensive introduction see . 5 . In the following definition and throughout this