## Seminars and Colloquia by Series

### The Kelmans-Seymour conjecture III: 3-vertices in K_4^-

Series
Graph Theory Seminar
Time
Wednesday, March 9, 2016 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Dawei HeMath, GT
Let G be a 5-connected graph and let x1, x2,y1,y2 in V(G) be distinct, such that G[{x1, x2, y1, y2}] is isomorphic to K_4^- and y1y2 is not in E(G). We show that G contains a K_4^- in which x1 is of degree 2, or G-x1 contains K_4^-, or G contains a TK_5 in which x1 is not a branch vertex, or {x2, y1, y2} may be chosen so that for any distinct w1,w2 in N(x1) - {x2, y1, y2}, G - {x1v : v is not in {w1, w2, x2, y1,y2} } contains TK_5.

### The Kelmans-Seymour conjecture II: 2-vertices in K_4^- (Intermediate structure and finding TK_5)

Series
Graph Theory Seminar
Time
Wednesday, March 2, 2016 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Yan WangMath, GT
We use K_4^- to denote the graph obtained from K_4 by removing an edge,and use TK_5 to denote a subdivision of K_5. Let G be a 5-connected nonplanar graph and {x_1, x_2, y_1, y_2} \subseteq V (G) such that G[{x_1,x_2, y_1, y_2}] = K_4^- with y_1y_2 \in E(G). Let w_1,w_2,w_3 \in N(y_2)- {x_1,x_2} be distinct. We show that G contains a TK_5 in which y_2 is not a branch vertex, or G - y_2 contains K_4^-, or G has a special 5-separation, or G' := G - {y_2v : v \in {w_1,w_2,w_3, x_1, x_2}} contains TK_5.In this talk, we will obtain a substructure in G' and several additional paths in G', and then use this substructure to find the desired TK_5.

### The Kelmans-Seymour conjecture II: 2-vertices in K_4^- (Non-separating paths)

Series
Graph Theory Seminar
Time
Wednesday, February 24, 2016 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Yan WangMath, GT
We use K_4^- to denote the graph obtained from K_4 by removing an edge,and use TK_5 to denote a subdivision of K_5. Let G be a 5-connected nonplanar graph and {x_1, x_2, y_1, y_2} \subseteq V (G) such that G[{x_1,x_2, y_1, y_2}] = K_4^- with y_1y_2 \in E(G). Let w_1,w_2,w_3 \in N(y_2)- {x_1,x_2} be distinct. We show that G contains a TK_5 in which y_2 is not a branch vertex, or G - y_2 contains K_4^-, or G has a special 5-separation, or G - {y_2v : v \in {w_1,w_2,w_3, x_1, x_2}} contains TK_5.In this talk, we will show the existence of a path X in G whose removal does not affect connectivity too much.

### The Kelmans-Seymour conjecture II: special separations (5-separations containing a triangle)

Series
Graph Theory Seminar
Time
Friday, February 5, 2016 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Yan WangMath, GT
Seymour and, independently, Kelmans conjectured in the 1970s that every 5-connected nonplanar graph contains a subdivision of K_5. This conjecture was proved by Ma and Yu for graphs containing K_4^-. In order to establish the Kelmans-Seymour conjecture for all graphs, we need to consider 5-separations and 6-separations with less restrictive structures. We will talk about special 5-separations and 6-separations whose cut contains a triangle. Results will be used in subsequently to prove the Kelmans-Seymour conjecture.

### The Kelmans-Seymour conjecture I: Special Separations

Series
Graph Theory Seminar
Time
Wednesday, January 27, 2016 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Yan WangMath, GT
Seymour and, independently, Kelmans conjectured in the 1970s that every 5-connected nonplanar graph contains a subdivision of K_5. This conjecture was proved by Ma and Yu for graphs containing K_4^-, and an important step in their proof is to deal with a 5-separation in the graph with a planar side. In order to establish the Kelmans-Seymour conjecture for all graphs, we need to consider 5-separations and 6-separations with less restrictive structures. We will talk about special 5-separations and 6-separations, including those with an apex side. Results will be used in subsequently to prove the Kelmans-Seymour conjecture.

### The Erdos-Hajnal Conjecture and structured non-linear graph-based hashing

Series
Graph Theory Seminar
Time
Monday, November 23, 2015 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
The goal of this talk is to show recent advances regarding two important mathematical problems. The first one can be straightforwardly formulated in a graph theory language, but can be possibly applied in other fields. The second one was motivated by machine learning applications, but leads to graph theory techniques. The celebrated open conjecture of Erdos and Hajnal from 1989 states that families of graphs not having some given graph H as an induced subgraph contain polynomial-size cliques/stable sets (in the undirected setting) or transitive subsets (in the directed setting). Recent techniques developed over last few years provided the proof of the conjecture for new infinite classes of graphs (in particular the first infinite class of prime graphs). Furthermore, they gave tight asymptotics for the Erdos-Hajnal coefficients for many classes of prime tournaments as well as the proof of the conjecture for all but one tournament on at most six vertices and the proof of the weaker version of the conjecture for trees on at most six vertices. In this part of the talk I will summarize these recent achievements. Structured non-linear graph-based hashing is motivated by applications in neural networks, where matrices of linear projections are constrained to have a specific structured form. This drastically reduces the size of the model and speeds up computations. I will show how the properties of the underlying graph encoding correlations between entries of these matrices (such as its chromatic number) imply the quality of the entire non-linear hashing mechanism. Furthermore, I will explain how general structured matrices that very recently attracted researchers’ attention naturally lead to the underlying graph theory description.

### Cycles lengths in graphs with large minimum degree

Series
Graph Theory Seminar
Time
Thursday, October 1, 2015 - 13:30 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Jie MaUniversity of Science and Technology of China
There has been extensive research on cycle lengths in graphs with large minimum degree. In this talk, we will present several new and tight results in this area. Let G be a graph with minimum degree at least k+1. We prove that if G is bipartite, then there are k cycles in G whose lengths form an arithmetic progression with common difference two. For general graph G, we show that G contains \lfloor k/2\rfloor cycles with consecutive even lengths, and in addition, if G is 2-connected and non-bipartite, then G contains \lfloor k/2\rfloor cycles with consecutive odd lengths. Thomassen (1983) made two conjectures on cycle lengths modulo a fixed integer k: (1) every graph with minimum degree at least k+1 contains cycles of all even lengths modulo k; (2) every 2-connected non-bipartite graph with minimum degree at least $k+1$ contains cycles of all lengths modulo k. These two conjectures, if true, are best possible. Our results confirm both conjectures! when k is even. And when k is odd, we show that minimum degree at least \$+4 suffices. Moreover, our results derive new upper bounds of the chromatic number in terms of the longest sequence of cycles with consecutive (even or odd) lengths. This is a joint work with Chun-Hung Liu.

### Packing and covering topological minors and immersions

Series
Graph Theory Seminar
Time
Thursday, September 10, 2015 - 13:35 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Chun-Hung LiuPrinceton University
A set F of graphs has the Erdos-Posa property if there exists a function f such that every graph either contains k disjoint subgraphs each isomorphic to a member in F or contains at most f(k) vertices intersecting all such subgraphs. In this talk I will address the Erdos-Posa property with respect to three closely related graph containment relations: minor, topological minor, and immersion. We denote the set of graphs containing H as a minor, topological minor and immersion by M(H),T(H) and I(H), respectively. Robertson and Seymour in 1980's proved that M(H) has the Erdos-Posa property if and only if H is planar. And they left the question for characterizing H in which T(H) has the Erdos-Posa property in the same paper. This characterization is expected to be complicated as T(H) has no Erdos-Posa property even for some tree H. In this talk, I will present joint work with Postle and Wollan for providing such a characterization. For immersions, it is more reasonable to consider an edge-variant of the Erdos-Posa property: packing edge-disjoint subgraphs and covering them by edges. I(H) has no this edge-variant of the Erdos-Posa property even for some tree H. However, I will prove that I(H) has the edge-variant of the Erdos-Posa property for every graph H if the host graphs are restricted to be 4-edge-connected. The 4-edge-connectivity cannot be replaced by the 3-edge-connectivity.

Series
Graph Theory Seminar
Time
Thursday, April 16, 2015 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Luke PostleUniversity of Waterloo
We discuss the relationship between the chromatic number (Chi), the clique number (Omega) and maximum average degree (MAD).

### Bipartite Kneser graphs are Hamiltonian

Series
Graph Theory Seminar
Time
Thursday, April 9, 2015 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Torsten MuetzeSchool of Mathematics, Georgia Tech and ETH Zurich
For integers k>=1 and n>=2k+1, the bipartite Kneser graph H(n,k) is defined as the graph that has as vertices all k-element and all (n-k)-element subsets of {1,2,...,n}, with an edge between any two vertices (=sets) where one is a subset of the other. It has long been conjectured that all bipartite Kneser graphs have a Hamilton cycle. The special case of this conjecture concerning the Hamiltonicity of the graph H(2k+1,k) became known as the 'middle levels conjecture' or 'revolving door conjecture', and has attracted particular attention over the last 30 years. One of the motivations for tackling these problems is an even more general conjecture due to Lovasz, which asserts that in fact every connected vertex-transitive graph (as e.g. H(n,k)) has a Hamilton cycle (apart from five exceptional graphs). Last week I presented a (rather technical) proof of the middle levels conjecture. In this talk I present a simple and short proof that all bipartite Kneser graphs H(n,k) have a Hamilton cycle (assuming that H(2k+1,k) has one). No prior knowledge will be assumed for this talk (having attended the first talk is not a prerequisite). This is joint work with Pascal Su (ETH Zurich).