报告人：董峰明，Nanyang Technological University, Singapore
报告时间：2017年6月27日16:00-18:00
报告地点：数计学院4号楼229室
报告题目：Chromatic polynomials of hypergraphs
报告摘要：For any graph G, the chromatic polynomial of G is a function P(G; \lambda) such that P(G; k) is the number of proper k-colourings of G for any positive integer k. This graph-function for planar graphs was originally introduced by George David Birkho in 1912 to attack the four color problem. Hassler Whitney generalised it from the planar case to general graphs in 1932. In 1968 Read asked which polynomials are the chromatic polynomials of some graphs, a question that remains open, and some other questions. Today, chromatic polynomial is one of the central objects of algebraic graph theory.
The graph-function P(G; \lambda) for graphs was extended to the case for hypergraphs in 1970s. A (simple) hypergraph \mathcal{H}=(\mathcal{V}, \mathcal{E}) consists of a vertex-set \mathcal{V}= \{v_1,...,v_n\} and an edge-set \mathcal{E} =\{e_1,...,e_m\} where e_i\subseteq \mathcal{V} and e_i\neq e_j for all 1\le i\le j. If |e_i|= 2 holds for each e_i\in\mathcal{E} , then \mathcal{H} is a simple graph. A (weak) proper\lambda-colouring of a hypergraph \mathcal{H} is a mapping f : \mathcal{V}\rightarrow \{1,...,\lambda\} such that |\{f(u) : u \in e\}|\ge 2 holds for each e\in \mathcal{E}. Let P(\mathcal{H}; \lambda) be the number of perper \lambda-colourings of \mathcal{H}. This graph-function P(\mathcal{H}; \lambda) is a polynomial of \lambda with degree |\mathcal{V}| and is called the chromatic polynomial of \mathcal{H}. Clearly P(\mathcal{H}; \lambda) is an extension of chromatic polynomials of simple graphs. In this talk, we will present our latest results on some properties of P(H; ) which are different from properties of chromatic polynomials of graphs. We will also introduce some open problems on the study of P(\mathcal{H}; \lambda).
Joint work with Zhang Ruixue, Nanyang Technological University, Singapore.
