64th KPPY Combinatorics Workshop -- Jun 20, 2014 (Friday)

Date: Jun 20, 2014 (Friday)
Time: 11am - 5pm
Location: KNU
Natural Sciences Building, Room 313

Schedule
11:00 - 11:50 Kang-ju Lee
Seoul National University
The cycle matroid complexes of bi-coned graphs
12:00 Lunch  
1:30 - 2:20 Geňa Hahn
University of Montreal
Cops, robbers, infinite graphs and related problems: Part I
2:30 - 3:20 Geňa Hahn
University of Montreal
Cops, robbers, infinite graphs and related problems: Part II
3:40 - 4:30 Suyoung Choi
Ajou University
The $a$-number of graphs and the topology of small covers
4:40 - 5:30 Yang Da-Wei
Beijing Jiaotong University
Pentavalent symmetric graphs of order two times a prime power
6:00 - 8:00 Banquet  
Program

Abstracts

Kang-ju Lee
The cycle matroid complexes of bi-coned graphs
Matroid complexes are shellable complexes. The $h$-vector of a matroid complex is defined as the coefficients of its shelling polynomial. In 2011, Kook gave a combinatorial interpretation of the terms in the $h$-vector of the cycle matroid of coned graphs whose example is the complete graph. We give a combinatorial interpretation of the terms in the $h$-vector of the cycle matroid of bi-coned graphs whose example is the complete bipartite graph. As an application, we prove Stanley's $M$-vector conjecture for the cycle matroid of bi-coned graphs. Among other cycle matroids, the conjecture was also confirmed for the cycle matroid of planar graphs by Merino in 2001 and for the cycle matroid of coned graphs by Kook in 2012. Our result extends the class of cycle matroids that satisfy Stanley's $M$-vector conjecture. The last term in the $h$-vector of the cycle matroid is called the $\alpha$-invariant of the cycle matroid. This number appears in many fields of mathematics such as topology, commutative algebra, combinatorics, and graph theory. In 2001, D. Bayer, S. Popescu, and B. Sturmfels posed the combinatorial problems to find formulas for the $\alpha$-invariants for graphs. In 2002, I. Novik, A. Postnikov, and B. Sturmfels gave their explicit formulas for the $\alpha$-invariants of complete graphs and complete bipartite graphs. We give a new bijective proof of $\alpha$-invariants of these graphs, using their combinatorial interpretations. Moreover, our solution gives more infomation about what each term of these formulas means. This is a joint work with Woong Kook.
Geňa Hahn
Cops, robbers, infinite graphs and related problems: Part I
We briefly survey the game of cops-and-robbers on graphs and its variants in the finite case and then concenrate on infinite graphs, stressing the difference between the finite and the infinite. Along the way we show (time permitting) how to construct infinite vertex transitive graphs from any graphs and point out some strange properties of the construction. We also suggest several open problems, both finite and infinite. The talk is based on work with A. Bonato, C.Tardif and R.E. Woodrow.
Geňa Hahn
Cops, robbers, infinite graphs and related problems: Part II
Continuation of above.
Suyoung Choi
The $a$-number of graphs and the topology of small covers
Recently, H. Park and I computed the rational Betti number of the canonical real toric variety over a graph associahedron. This computation led us to define an interesting invariant of a simple graph $G$, so called the a-number of $G$. It should be noticed that a graph associahedron is an example of nestohedra which can be produced by hypergraphs, and, hence, it is natural to ask whether similar invariants can be defined for a hypergraph. In this talk, we answer to the above question by using the topology of simplicial complexes related to the real toric variety over a nestohedron.
Yang Da-Wei
Pentavalent symmetric graphs of order two times a prime power
A graph is symmetric if its automorphism group acts transitively on ordered adjacent pairs of vertices of the graph. Let $p$ be a prime, and let $n\geq 2$ be a positive integer. In this talk, all the normal quotients of connected pentavalent symmetric graphs of order $2p^n$ are obtained, and among those normal quotients, basic ones are also determined. As an application, connected pentavalent symmetric graphs of order $2p^2$ and $2p^3$ are classified.