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

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.

Series: Graph Theory Seminar

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.

Series: Graph Theory Seminar

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)

Series: Graph Theory Seminar

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.

Series: Graph Theory Seminar

Suppose that each node of a rooted tree has a message that it wants to
pass up the tree to the root. How can we design a protocol that guarantees
all messages (eventually) reach there without being interfered with by
other messages, if the nodes themselves do not know the underlying
structure of the tree, or even whether their previous messages were
successfully transmitted or not? I will describe (near optimal) answers to
several variations of this problem, based on joint work with Marek Chrobak
(UCR), Laszek Gasieniec (Liverpool) and Dariusz Kowalski (Liverpool).

Series: Graph Theory Seminar

(Alon-Tarsi Conjecture): For even n, the number of even nxn Latin squares
differs from the number of odd nxn Latin squares.
(Stones-Wanless, Kotlar Conjecture): For all n, the number of even nxn
Latin squares with the identity permutation as first row and first column
differs from the number of odd nxn Latin squares of this type.
(Aharoni-Berger Conjecture): Let M and N be two matroids on the same
vertex set, and let A1,...,An be sets
of size n + 1 belonging to both M and N. Then there exists a set belonging
to both M and N and meeting all Ai.
We prove equivalence of the first two conjectures and a special case
of the third one and use these results to show that Alon-Tarsi Conjecture
implies Rota's bases conjecture for odd n and
any system of n non-singular real valued matrices where one of them is
non-negative and the remaining have non-negative inverses.Joint work with Ron Aharoni.

Series: Graph Theory Seminar

In this talk, we discuss our recent progress on the famous directed cycle
double cover conjecture of Jaeger. This conjecture asserts that every
2-connected graph admits a collection of cycles such that each edge is in
exactly two cycles of the collection. In addition, it must be possible to
prescribe an orientation to each cycle so that each edge is traversed in
both ways.
We plan to define the class of weakly robust trigraphs and prove that a
connectivity augmentation conjecture for this class implies general
directed cycle double cover conjecture.
This is joint work with Martin Loebl.

Series: Graph Theory Seminar

This talk is a sequel to the speaker's previous lecture given in
the January 31st Combinatorics Seminar, but attendance at the first talk is
not assumed. We begin by carefully reviewing our generalized cycle-cocyle
reversal system for partial graph orientations. A self contained
description of Baker and Norin's Riemann-Roch formula for graphs is given
using their original chip-firing language. We then explain how to
reinterpret and reprove this theorem using partial graph orientations. In
passing, the Baker-Norin rank of a partial orientation is shown to be one
less than the minimum number of directed paths which need to be reversed in
the generalized cycle-cocycle reversal system to produce an acyclic partial
orientation. We conclude with an overview of how these results extend to
the continuous setting of metric graphs (abstract tropical curves).

Series: Graph Theory Seminar

Consider a graph G and a specified subset A of vertices. An A-path is a path with both ends in A
and no internal vertex in A. Gallai showed that there exists a min-max formula for the maximum number of pairwise disjoint
A-paths. More recent work has extended this result, considering disjoint A-paths which satisfy various additional properties.
We consider the following model. We are given a list of {(s_i, t_i): 0< i < k} of pairs of vertices in A, consider
the question of whether there exist many pairwise disjoint A-paths P_1,..., P_t such that for all j,
the ends of P_j are equal to s_i and t_i for some value i. This generalizes the disjoint paths problem and is NP-hard
if k is not fixed. Thus, we cannot hope for an exact min-max theorem. We further restrict the question, and ask if there
either exist t pairwise disjoint such A-paths or alternatively, a bounded set of f(t) vertices intersecting all such paths. In
general, there exist examples where no such function f(t) exists; we present an exact characterization of
when such a function exists.
This is joint work with Daniel Marx.