图多项式及其应用国际专题研讨会（International Symposium on Graph Polynomials and their Applications）于6月27日-30日在厦门大学数学科学学院举行。
本次研讨会由厦门大学数学科学学院金贤安教授组织，来自美国、日本、澳大利亚、新加坡、马来西亚、台湾、香港以及中国大陆的30多位专家，厦门三校（厦门大学、集美大学、厦门理工学院）组合与图论领域的教师20多人和研究生20余人参加了研讨会。
6月28日上午8：15，研讨会在海韵园实验楼105报告厅举行。厦门大学张福基教授和新加坡南洋理工大学董峰明教授分别致辞。开幕式后，部分参会教师一起合影留念。
6月28日和29日上午，研讨会安排了17场30分钟报告。研讨会期间，6月29日下午，大连理工大学数学科学学院副院长雷逢春教授和国家杰出青年科学基金获得者、华东师范大学邱瑞锋教授还为我院“拔尖班”学生分别作了题为《庞加莱猜想》和《趣味纽结》的魅力数学讲座。
此次研讨会的主题集中在图多项式和纽结不变量两方面，通过此次会议的举办希望扩大我院组合图论研究团队教师和研究生的学术视野，寻找好的可行的研究课题，吸引更多老师和学生加入到图论和纽结论交叉领域的研究中来，从而推动我院图论和纽结论两个领域的交叉研究向前发展。
Schedule of International Symposium
on Graph Polynomials and their Applications
图多项式及其应用国际(小型)专题研讨会
日程表
Venue：Room 105, Laboratory Building, Haiyun Campus
地 点：海韵园实验楼105室
June 28 am
| 08:15-08:45 | Opening Remarks. Chair: Xian’an Jin Photo. In Haiyun Campus 合影. 海韵园 | |
Chair：Yeong-Nan Yeh | |||
08:45-09:15 | Graham Farr
| A survey of Tutte-Whitney polynomials | |
09:15-09:45 | Beifang Chen
| Values of Tutte polynomial at positive integers | |
09:45-10:15 | Yuanan Diao
| Tutte polynomials, relative Tutte polynomials and virtual knot theory | |
break | |||
Chair：Ruifeng Qiu | |||
10:30-11:00 | Fengchun Lei
| Invariants of 3-manifolds from intersecting kernels of Heegaard splittings | |
11:00-11:30 | Teruhisa Kadokami
| Surface-bracket polynomial of virtual links | |
11:30-12:00 | Zhiqing Yang
| Generalizing Tutte Polynomial | |
June 28 pm
| Chair：Fengming Dong | ||
15:00-15:30 |
Gek Ling Chia
| On the chromatic equivalence classes of graphs | |
15:30-16:00 | Yichao Chen
| Log-concave conjecture for directed genus distribution | |
16:00-16:30 | Jin Xu | TBA | |
Break | |||
Chair：Graham Farr | |||
16:45-17:15 | Yeong-Nan Yeh
| G-parking functions and minimal deletion-contraction sequences of graphs | |
17:15-17:45 | Jun Ma
| A generalization of G-parking functions | |
17:45-18:15 | Boon Leong Ng
| TBA | |
June 29 am
| Chair： Yuanan Diao | ||
08:45-09:15 | Yasuyuki Miyazawa
| On polynomials for virtual links or graphs | |
09:15-09:45 | Bing Wei
| Independence polynomials of some compound graphs | |
09:45-10:15 | Xiaosheng Cheng
| Ear decomposition of 3-regular polyhedral links with applications | |
break | |||
Chair：Beifang Chen | |||
10:30-11:00 | Fengming Dong
| TBA | |
11:00-11:30 | Fuji Zhang
| The computation of the Jones polynomial and its zeros |
Title, speaker and abstract
1. Values of Tutte polynomial at positive integers
Beifang Chen
Hong Kong Polytechnic University, Hong Kong
Abstract: The Tutte polynomial TG(x,y) of a graph G is a common generalization of the chromatic polynomial χ(G,t) and the flow polynomial φ(G,t), and is one of the most important polynomials in graph theory. Unlike definitions of χ by counting proper colorings and of φ by counting nowhere-zero flows, TG is defined by Whitney's rank generating polynomial RG(x,y), rather than by counting certain combinatorial objects. The present talk gives a combinatorial/geometric interpretation for the values of the Tutte polynomial at positive integers.
2. Log-concave conjecture for directed genus distribution
Yichao Chen
Hunan University,China
Abstract: A digraph D is called an {Eulerian digraph} if in(v)=out(v) for each vertex v of D. A 2-cell embedding of an Eulerian digraph D into a closed surface is said to be directed if the boundary of each face is a directed closed walk in D. The directed genus distribution of the digraph D is the sequence g0(D), g1(D), g2(D), …, where gi(D) is the number of cellular directed embeddings of D on the surface Si. A well-known conjecture in topological graph theory, says that all genus distributions of digraphs (graphs) are log-concave. In this talk, we shall present some new results on log-concave conjecture. Our recent results are obtained by the newly developed tool, which are called transfer (or production) matrix.
3. Ear decomposition of 3-regular polyhedral links with applications
Xiaosheng Cheng
Huizhou University,China
Abstract: In this paper, we introduce a notion of ear decomposition of 3-regular polyhedral links based on the ear decomposition of the 3-regular polyhedral graphs. As a result, we obtain an upper bound for the braid index of 3-regular polyhedral links. Our results may be used to characterize and analyze the structure and complexity of protein polyhedra and entanglement in biopolymers.
4. On the chromatic equivalence classes of graphs
Gek Ling Chia
University Malaya,Malaysia
Abstract: Let G be a graph and let P(G;λ) denote its chromatic polynomial. The chromatic equivalence class of G, denoted С(G), is the set of all graphs sharing the same chromatic polynomial with that of G. In the event that С(G)={G}, then G is said to be chromatically unique. While chromatically unique graphs have been the subject of much discussion since 1978, not a great deal has been addressed on the chromatic equivalence classes of graphs. In this talk, we present some known and some new results on chromatic equivalence classes of graphs.
5. Tutte polynomials, relative Tutte polynomials and virtual knot theory
Yuanan Diao
University of North Carolina,USA
Abstract: We introduce the concept of a relative Tutte polynomial of colored graphs. We show that this relative Tutte polynomial can be computed in a way similar to the classical spanning tree expansion used by Tutte in his original paper on this subject. We then apply the relative Tutte polynomial to virtual knot theory. More specifically, we show that the Kauffman bracket polynomial (hence the Jones polynomial) of a virtual knot can be computed from the relative Tutte polynomial of its face (Tait) graph with some suitable variable substitutions. Our method offers an alternative to the ribbon graph approach, using the face graph obtained from the virtual link diagram directly.
6. TBA
Fengming Dong
Nanyang Technological University,Singapore
7. A survey of Tutte-Whitney polynomials
Graham Farr
Monash University,Australia
Abstract: The Tutte-Whitney polynomial of a graph is a two-variable polynomial that contains a lot of interesting information about the graph. It includes, for example, the chromatic, flow and reliability polynomials of a graph, the Ising and Potts model partition functions of statistical mechanics, the weight enumerator of a linear code, and the Jones polynomial of an alternating link. This talk is an introduction to this polynomial and reviews some recent generalisations.
8. Surface-bracket polynomial of virtual links
Teruhisa Kadokami
East China Normal University,China
Abstract：H.A.Dye and L.Kauffman defined a state sum invariant for a virtual link which is situated on a surface. It detects non-triviality of Kishino's knot. We applied the invariant to classify closed virtual 2-braids.
9. Invariants of 3-manifolds from intersecting kernels of Heegaard splittings
Fengchun Lei
Dalian University of Technology,
Abstract: The intersecting kernel of a Heegaard splitting $H\cup_S H'$ for a closed orientable 3-manifold $M$ is the subgroup $K=\text{Ker} i_*\cap \text{Ker} {i'}_*$ of $\pi_1 (S)$, where $i:S\hookrightarrow H$ and $i':S\hookrightarrow H'$ are the inclusion maps, and $i_*$ and $i_*'$ are the induced homomorphisms between the corresponding fundamental groups. In the talk, I will explain how to derive some invariants of 3-manifolds from intersecting kernels of their Heegaard splittings. This is a joint work with Jie Wu and Fengling Li.
10. A generalization of G-parking functions
Jun Ma
Shanghai Jiao Tong University,China
Abstract: Let G be a connected and simple graph. Define to be the set of pairs (f, I) such that f is a G-parking function and I is a subset of the set of all critical-bridge vertices of the G-parking function f. Let be the set of spanning forests of G. In this talk, we will introduce a bijection from to . Let Δ be an integer n×n-matrix which satisfy the conditions: detΔ≠0, Δij≤ 0 for i≠j, and there exists a vector r =(r1,…,rn)>0 such that rΔ≥0. Here the notation r > 0 means that ri>0 for all i and r≥r ' means that ri ≥r'i for every i. In this talk, we will introduce (Δ,r) -parking functions, which is a new generalization of the G-parking functions.
11. On polynomials for virtual links or graphs
Yasuyuki Miyazawa
Yamaguchi University,
Abstract: The speaker defined some polynomial invariants for virtual links or graphs. In this talk, such polynomials and related topics will be briefly introduced.
12. TBA
Boon Leong Ng
Nanyang Technological University,Singapore
Abstract: The chromatic equivalence class of a graph G is the set of graphs that have the same chromatic polynomial as G. We find the chromatic equivalence class of the complete tripartite graphs K(1,n,n+2) for all n≥2. This partially answers a question raised in [G.L. Chia, C.K. Ho. Chromatic equivalence classes of complete tripartite graphs, Discrete Math. 309 (2009), 134-143], which asks for the chromatic equivalence class of the graph K(1,m,n) where 2≤m≤n.
13. Independence polynomials of some compound graphs
Bing Wei
University of Mississippi,USA
Abstract: An independent set of a graph G is a set of pairwise non-adjacent vertices. G is well-covered if all its maximal independent sets have the same size, denoted by α(G). Let fs(G) for 0≤s≤α(G) denote the number of independent sets of s vertices in G. The independence polynomial I(G; x) =introduced by Gutman and Harary has been the focus of considerable research recently. Motivated by a result of Gutman for some compound graphs, we extend his result for more general compound graphs. In particular, we will apply our main results to determine the coeficients fs(G) for somewell-covered graphs and present their exact independence polynomials.
14. TBA
Jin Xu
Peking University,
15. Generalizing Tutte Polynomial
Zhiqing Yang
Dalian University of Technology,China
Abstracts: In this talk, we shall give several techniques to construct graph polynomials which generalize the classical Tutte Polynomial. And we also give examples showing that some of them are more powerful than the classical Tutte Polynomial.
16. G-parking functions and minimal deletion-contraction sequences of graphs
Yeong-Nan Yeh
Academia Sinica,Taiwan
Abstract: In this talk, we give a bijection from the set of minimal deletion-contraction sequences of a connected graph G to the set of G-parking functions. With the benefit of the bijection, we express the universal polynomial of G in terms of weights of G-parking functions.
17. The computation of the Jones polynomial and its zeros
Fuji Zhang
Xiamen University,China
Abstract: It is well known that there is a classical one-to-one correspondence between link diagrams and signed plane graphs. The Kauffman bracket polynomial, the main part of the Jones polynomial, of a link diagram is thus naturally converted to a polynomial of the corresponding signed plane graph which was extended by L. H. Kauffman to general signed graphs in 1989 and called the Tutte polynomial of signed graphs.
In this talk, we first present a formula for computing the Tutte polynomial of the signed graph formed from a labeled graph by edge replacements in terms of the chain polynomial of the labeled graph which was introduced by R. C. Read and E. G. Whitehead Jr. in 1999. Motivated by the connection between the Jones polynomial and statistical mechanics, using the formula obtained above, we then study zeros of the Jones polynomial, presenting two main results: (1) limits of zeros of Jones polynomials of link (diagrams) corresponding to homeomorphic plane graphs are the unit circle centered at the origin and several isolated points; (2) zeros of Jones polynomials of pretzel knots are dense in the whole complex plane. Finally we give two recent results on zeros of Jones polynomials of graphs. We also try to generalize above results to Homfly polynomials.