图多项式及其应用国际(小型)专题研讨会日程表

Schedule of International Symposium

on Graph Polynomials and their Applications

图多项式及其应用国际(小型)专题研讨会

VenueRoom 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


AbstractH.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, China

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 ij, 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 rr ' 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, Japan

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 0sα(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, China



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.