Đ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: On Multivariate Chromatic Polynomials of Hypergraphs and Hyperedge Elimination. | On Multivariate Chromatic Polynomials of Hypergraphs and Hyperedge Elimination Jacob A. White Mathematical Sciences Research Institute Berkeley California USA jawhite@msri.org Submitted Feb 9 2011 Accepted Jul 22 2011 Published Aug 5 2011 Mathematics Subject Classifications 05C31 05C15 05C65 Abstract In this paper we introduce multivariate hyperedge elimination polynomials and multivariate chromatic polynomials for hypergraphs. The first set of polynomials is defined in terms of a deletion-contraction-extraction recurrence previously investigated for graphs by Averbouch Godlin and Makowsky. The multivariate chromatic polynomial is an equivalent polynomial defined in terms of colorings and generalizes the coboundary polynomial of Crapo and the bivariate chromatic polynomial of Dohmen Ponitz and Tittman. We prove that specializations of these new polynomials recover polynomials which enumerate hyperedge coverings matchings transversals and section hypergraphs all weighted according to certain statistics. We also prove that the polynomials can be defined in terms of Mobius inversion on the partition lattice of a hypergraph and we compute these polynomials for various classes of hypergraphs. We also consider trivariate polynomials which we call the hyperedge elimination polynomial and the trivariate chromatic polynomial. 1 Introduction The chromatic polynomial of a graph enumerates the number of proper k-colorings of a graph. It was originally introduced by Birkhoff BL46 who hoped that understanding this polynomial could lead to a proof of the four-color theorem. The chromatic polynomial was generalized by Tutte to give a two-variable polynomial now called the Tutte polynomial Tut84 Tut47 . The Tutte polynomial was defined for matroids in general The author was partially supported by an NSF grant DMS-0932078 administered by the Mathematical Sciences Research Institute while the author was in residence at MSRI during the Complementary Program Fall 2010. This work began
