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

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.

Series: Graph Theory Seminar

An r-unform n-vertex hypergraph H is said to have the
Manickam-Miklos-Singhi (MMS) property if for every assignment of
weights to
its vertices with nonnegative sum, the number of edges whose total
weight
is nonnegative is at least the minimum degree of H. In this talk I will
show that for n>10r^3, every r-uniform n-vertex hypergraph with equal
codegrees has the MMS property, and the bound on n is essentially
tight up
to a constant factor. An immediate corollary of this result is the
vector
space Manickam-Miklos-Singhi conjecture which states that for n>=4k
and any
weighting on the 1-dimensional subspaces of F_q^n with nonnegative
sum, the
number of nonnegative k-dimensional subspaces is at least ${n-1 \brack
k-1}_q$. I will also discuss two additional generalizations, which
can be
regarded as analogues of the Erdos-Ko-Rado theorem on k-intersecting
families. This is joint work with Benny Sudakov.

Series: Graph Theory Seminar

By the 4-color theorem, every planar graph on n vertices has
an independent set of size at least n/4. Finding a simple
proof of this fact is a long-standing open problem.
Furthermore, no polynomial-time algorithm to decide whether
a planar graph has an independent set of size at least (n+1)/4
is known.
We study the analogous problem for triangle-free planar graphs.
By Grotzsch' theorem, each such graph on n vertices has an
independent set of size at least n/3, and this can be easily
improved to a tight bound of (n+1)/3. We show that for every k,
a triangle-free planar graph of sufficiently large tree-width has
an independent set of size at least (n+k)/3, thus giving a polynomial-time
algorithm to decide the existence of such a set. Furthermore,
we show that there exists a constant c < 3 such that every planar graph
of girth at least five has an independent set of size at least n/c.Joint work with Matthias Mnich.

Series: Graph Theory Seminar

While Robertson and Seymour showed that graphs are
well-quasi-ordered under the minor relation, it is well known
that directed graphs are not. We will present an exact
characterization of the minor-closed sets of directed graphs
which are well-quasi-ordered. This is joint work with M.
Chudnovsky, S. Oum, I. Muzi, and P. Seymour.

Series: Graph Theory Seminar

We prove the dcdc conjecture in a class of lean fork graphs, argue that this
class is substantial and show a path towards the complete solution. Joint work with Andrea Jimenez.

Series: Graph Theory Seminar

A systematic study of large combinatorial objects has recently led
to discovering many connections between discrete mathematics and
analysis. In this talk, we apply analytic methods to permutations.
In particular, we associate every sequence of permutations
with a measure on a unit square and show the following:
if the density of every 4-element subpermutation in a permutation p
is 1/4!+o(1), then the density of every k-element subpermutation
is 1/k!+o(1). This answers a question of Graham whether quasirandomness
of a permutation is captured by densities of its 4-element subpermutations.
The result is based on a joint work with Oleg Pikhurko.

Series: Graph Theory Seminar

Since the foundational results of Thomason and
Chung-Graham-Wilson on quasirandom graphs over 20 years ago, there has
been a lot of effort by many researchers to extend the theory to
hypergraphs. I will present some of this history, and then describe our
recent results that provide such a generalization and unify much of the
previous work. One key new aspect in the theory is a systematic study of
hypergraph eigenvalues first introduced by Friedman and Wigderson. This
is joint work with John Lenz.

Series: Graph Theory Seminar

We show that any internally 4-connected non-planar bipartite graph contains
a subdivision of K3,3 in which each subdivided path contains an even number
of vertices. In addition to being natural, this result has broader
applications in matching theory: for example, finding such a subdivision of
K3,3 is the first step in an algorithm for determining whether or not a
bipartite graph is Pfaffian. This is joint work with Robin Thomas.

Series: Graph Theory Seminar

A recent lower bound on the number of edges in a k-critical n-vertex graph by
Kostochka and Yancey yields a half-page proof of the celebrated Grotzsch
Theorem that every planar triangle-free graph is 3-colorable. We use the same
bound to give short proofs of other known theorems on 3-coloring of planar
graphs, among whose is the Grunbaum-Aksenov Theorem that every planar with at
most three triangles is 3-colorable. We also prove the new result that every
graph obtained from a triangle-free planar graph by adding a vertex of degree
at most four is 3-colorable. Joint work with O. Borodin, A. Kostochka and M. Yancey.

Series: Graph Theory Seminar

We present a dynamic data structure representing a graph G, which allows
addition and removal of edges from G and can determine the number of
appearances of a graph of a bounded size as an induced subgraph of G. The
queries are answered in constant time. When the data structure is used to
represent graphs from a class with bounded expansion (which includes planar
graphs and more generally all proper classes closed on topological minors, as
well as many other natural classes of graphs with bounded average degree), the
amortized time complexity of updates is polylogarithmic. This data structure
is motivated by improving time complexity of graph coloring algorithms and
of random graph generation.