Seminars and Colloquia by Series

Chi, Omega, MAD

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).

Dimension and matchings in comparability and incomparability graphs

Series
Graph Theory Seminar
Time
Thursday, March 5, 2015 - 00:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Ruidong WangMath, GT
In the combinatorics of posets, many theorems are in pairs, one for chains and one for antichains. Typically, the statements are exactly the same when roles are reversed, but the proofs are quite different. The classic pair of theorems due to Dilworth and Mirsky were the starting point for this pattern, followed by the more general pair known respectively as the Greene-Kleitman and Greene theorems dealing with saturated partitions. More recently, a new pair has been discovered dealing with matchings in the comparability and incomparability graphs of a poset. We show that if the dimension of a poset P is d and d is at least 3, then there is a matching of size d in the comparability graph of P, and a matching of size d in the incomparability graph of P.

Binary linear codes via 4D discrete Ihara-Selberg function

Series
Graph Theory Seminar
Time
Tuesday, January 20, 2015 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Martin LoeblCharles University
We express weight enumerator of each binary linear code as a product. An analogous result was obtain by R. Feynman in the beginning of 60's for the speacial case of the cycle space of the planar graphs.

Groundstates of the Ising Model on antiferromagnetic triangulations

Series
Graph Theory Seminar
Time
Thursday, January 8, 2015 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Andrea JimenezGT and University of São Paulo
We discuss a dual version of a problem about perfect matchings in cubic graphs posed by Lovász and Plummer. The dual version is formulated as follows: "Every triangulation of an orientable surface has exponentially many groundstates"; we consider groundstates of the antiferromagnetic Ising Model. According to physicist, the dual formulation holds. In this talk, I plan to show a counterexample to the dual formulation (**), a method to count groundstates which gives a better bound (for the original problem) on the class of Klee-graphs, the complexity of the related problems and if time allows, some open problems. (**): After that physicists came up with an explanation to such an unexpected behaviour!! We are able to construct triangulations where their explanation fails again. I plan to show you this too. (This is joint work with Marcos Kiwi)

Towards dichotomy for planar boolean CSP

Series
Graph Theory Seminar
Time
Wednesday, December 3, 2014 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Zdenek DvorakCharles University
For relations {R_1,..., R_k} on a finite set D, the {R_1,...,R_k}-CSP is a computational problem specified as follows: Input: a set of constraints C_1, ..., C_m on variables x_1, ..., x_n, where each constraint C_t is of form R_{i_t}(x_{j_{t,1}}, x_{j_{t,2}}, ...) for some i_t in {1, ..., k} Output: decide whether it is possible to assign values from D to all the variables so that all the constraints are satisfied. The CSP problem is boolean when |D|=2. Schaefer gave a sufficient condition on the relations in a boolean CSP problem guaranteeing its polynomial-time solvability, and proved that all other boolean CSP problems are NP-complete. In the planar variant of the problem, we additionally restrict the inputs only to those whose incidence graph (with vertices C_1, ..., C_m, x_1, ..., x_m and edges joining the constraints with their variables) is planar. It is known that the complexities of the planar and general variants of CSP do not always coincide. For example, let NAE={(0,0,1),(0,1,0),(1,0,0),(1,1,0),(1,0,1),(0,1,1)}). Then {NAE}-CSP is NP-complete, while planar {NAE}-CSP is polynomial-time solvable. We give some partial progress towards showing a characterization of the complexity of planar boolean CSP similar to Schaefer's dichotomy theorem.Joint work with Martin Kupec.

Minors and dimension

Series
Graph Theory Seminar
Time
Thursday, August 28, 2014 - 13:30 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Bartosz WalczakGT, Math and Jagiellonian University in Krakow
The dimension of a poset P is the minimum number of linear extensions of P whose intersection is equal to P. This parameter plays a similar role for posets as the chromatic number does for graphs. A lot of research has been carried out in order to understand when and why the dimension is bounded. There are constructions of posets with height 2 (but very dense cover graphs) or with planar cover graphs (but unbounded height) that have unbounded dimension. Streib and Trotter proved in 2012 that posets with bounded height and with planar cover graphs have bounded dimension. Recently, Joret et al. proved that the dimension is bounded for posets with bounded height whose cover graphs have bounded tree-width. My current work generalizes both these results, showing that the dimension is bounded for posets of bounded height whose cover graphs exclude a fixed (topological) minor. The proof is based on the Robertson-Seymour and Grohe-Marx structural decomposition theorems. I will survey results relating the dimension of a poset to structural properties of its cover graph and present some ideas behind the proof of the result on excluded minors.

Graph structures and well-quasi-ordering

Series
Graph Theory Seminar
Time
Thursday, August 21, 2014 - 13:30 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Chun-Hung LiuMath, GT and Princeton University
Robertson and Seymour proved that graphs are well-quasi-ordered by the minor relation and the weak immersion relation. In other words, given infinitely many graphs, one graph contains another as a minor (or a weak immersion, respectively). Unlike the relation of minor and weak immersion, the topological minor relation does not well-quasi-order graphs in general. However, Robertson conjectured in the late 1980s that for every positive integer k, the topological minor relation well-quasi-orders graphs that do not contain a topological minor isomorphic to the path of length k with each edge duplicated. We will sketch the idea of our recent proof of this conjecture. In addition, we will give a structure theorem for excluding a fixed graph as a topological minor. Such structure theorems were previously obtained by Grohe and Marx and by Dvorak, but we push one of the bounds in their theorems to the optimal value. This improvement is needed for our proof of Robertson's conjecture. This work is joint with Robin Thomas.

Fractional chromatic number of planar graphs

Series
Graph Theory Seminar
Time
Monday, April 28, 2014 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Zdenek DvorakCharles University
Grötzsch's theorem implies that every planar triangle-free graph is 3-colorable. It is natural to ask whether this can be improved. We prove that every planar triangle-free graph on n vertices has fractional chromatic number at most 3-1/(n+1/3), while Jones constructed planar triangle-free n-vertex graphs with fractional chromatic number 3-3/(n+1). We also investigate additional conditions under that triangle-free planar graphs have fractional chromatic number smaller than 3-epsilon for some fixed epsilon > 0.(joint work with J.-S. Sereni and J. Volec)

Turan Number of the Generalized Triangle

Series
Graph Theory Seminar
Time
Thursday, April 17, 2014 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Liana YepremyanMcGill University (Montreal) and Georgia Tech
Generalized triangle T_r is an r-graph with edges {1,2,…,r}, {1,2,…,r-1, r+1} and {r,r+1, r+2, …,2r-2}. The family \Sigma_r consists of all r-graphs with three edges D_1, D_2, D_3 such that |D_1\cap D_2|=r-1 and D_1\triangle D_2\subset D_3. In 1989 it was conjectured by Frankl and Furedi that ex(n,T_r) = ex(n,\Sigma_r) for large enough n, where ex(n,F) is the Tur\'{a}n function. The conjecture was proven to be true for r=3, 4 by Frankl, Furedi and Pikhurko respectively. We settle the conjecture for r=5,6 and show that extremal graphs are blow-ups of the unique (11, 5, 4) and (12, 6, 5) Steiner systems. The proof is based on a technique for deriving exact results for the Tur\'{a}n function from “local stability" results, which has other applications. This is joint work with Sergey Norin.

Pages