- You are here:
- GT Home
- Home
- News & Events

Series: Graph Theory Seminar

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.

Series: Graph Theory Seminar

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.

Series: Graph Theory Seminar

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

We discuss the relationship between the chromatic number (Chi),
the clique number (Omega) and maximum average degree (MAD).

Series: Graph Theory Seminar

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

Series: Graph Theory Seminar

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.

Series: Graph Theory Seminar

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.

Series: Graph Theory Seminar

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)

Series: Graph Theory Seminar

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.

Series: Graph Theory Seminar

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.