Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "An entropy proof of the Kahn-Lov´sz theorem a"
Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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 A.J. Radcliffe Montclair State University University of Nebraska-Lincoln jonathan.cutler@montclair.edu aradcliffe1@math.unl.edu 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 e.g. 5 . In the following definition and throughout this