Seminars and Colloquia by Series

Wednesday, April 13, 2016 - 15:05 , Location: Skiles 005 , Yan Wang , Math, GT , Organizer: Robin Thomas
Let G be a 5-connected nonplanar graph. To show the Kelmans-Seymour conjecture, we keep contracting a connected subgraph on a special vertex z until the following happens: H does not contain K_4^-, and for any subgraph T of H such that z is a vertex in T and T is K_2 or K_3, H/T is not 5-connected. In this talk, we study the structure of these 5-separations and 6-separations, and prove the Kelmans-Seymour conjecture.
Wednesday, April 6, 2016 - 15:05 , Location: Skiles 005 , Yan Wang , Math, GT , Organizer: Robin Thomas
Let G be a 5-connected nonplanar graph. To show the Kelmans-Seymour conjecture, we keep contracting a connected subgraph on a special vertex z until the following happens: H does not contain K_4^-, and for any subgraph T of H such that z is a vertex in T and T is K_2 or K_3, H/T is not 5-connected. In this talk, we prove a lemma using the characterization of three paths with designated ends, which will be used in the proof of the Kelmans-Seymour conjecture.
Wednesday, March 30, 2016 - 15:05 , Location: Skiles 005 , Dawei He , Math, GT , Organizer: Robin Thomas
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.
Wednesday, March 16, 2016 - 15:05 , Location: Skiles 005 , Luke Postle , Department of C&O, University of Waterloo , Organizer: Robin Thomas
In 1998, Reed proved that the chromatic number of a graph is bounded away from its trivial upper bound, its maximum degree plus one, and towards its trivial lower bound, its clique number. Reed also conjectured that the chromatic number is at most halfway in between these two bounds. We prove that for large maximum degree, that the chromatic number is at least 1/25th in between. Joint work with Marthe Bonamy and Tom Perrett.
Wednesday, March 9, 2016 - 15:05 , Location: Skiles 005 , Dawei He , Math, GT , Organizer: Robin Thomas
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.
Wednesday, March 2, 2016 - 15:05 , Location: Skiles 005 , Yan Wang , Math, GT , Organizer: Robin Thomas
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.
Wednesday, February 24, 2016 - 15:05 , Location: Skiles 005 , Yan Wang , Math, GT , Organizer: Robin Thomas
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.
Friday, February 5, 2016 - 15:05 , Location: Skiles 005 , Yan Wang , Math, GT , Organizer: Robin Thomas
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.
Wednesday, January 27, 2016 - 15:05 , Location: Skiles 005 , Yan Wang , Math, GT , Organizer: Robin Thomas
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.
Monday, November 23, 2015 - 15:05 , Location: Skiles 005 , Krzysztof Choromanski , Google Research , Organizer: Robin Thomas
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.