当前位置:首页 |  学术交流学术交流

新加坡南洋理工大学董峰明教授学术报告

信息来源: 暂无 发布日期: 2017-06-23 浏览次数:

报告人:董峰明,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.