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

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.

Series: Graph Theory Seminar

Every subcubic triangle-free graph on n vertices contains an independent
set of size at least 5n/14 (Staton'79). We strengthen this result by showing
that all such graphs have fractional chromatic number at most 14/5,
thus confirming a conjecture by Heckman and Thomas. (Joint work with J.-S. Sereni and J. Volec)

Series: Graph Theory Seminar

The online matching problem has received significant attention in recent years because of its connections to allocation problems in internet advertising, crowd sourcing, etc. In these real-world applications, the typical goal is not to maximize the number of allocations; rather it is to maximize the number of “successful” allocations, where success of an allocation is governed by a stochastic event that comes after the allocation. These applications motivate us to introduce stochastic rewards in the online matching problem. In this talk, I will formally define this problem, point out its connections to previously studied allocation problems, give a deterministic algorithm that is close to optimal in its competitive ratio, and describe some directions of future research in this line of work. (Based on joint work with Aranyak Mehta.)

Series: Graph Theory Seminar

The Weak Structure Theorem of Robertson and Seymour is the cornerstone of
many of the algorithmic applications of graph minors techniques. The
theorem states that any graph which has both large tree-width and excludes
a fixed size clique minor contains a large, nearly planar subgraph. In
this talk, we will discuss a new proof of this result which is
significantly simpler than the original proof of Robertson and Seymour. As
a testament to the simplicity of the proof, one can extract explicit
constants to the bounds given in the theorem. We will assume no previous
knowledge about graph minors or tree-width.
This is joint work with Ken Kawarabayashi and Robin Thomas

Series: Graph Theory Seminar

A (5,2)-configuration in a graph G is a function which maps the
vertices of G into 2-element subsets of {1,2,3,4,5} in such a way that
for every vertex u, the union of the 2-element subsets assigned to u and
all its neighbors is {1,2,3,4,5}. This notion is motivated by a problem in robotics. Fujita, Yamashita and Kameda showed
that every 3-regular graph has a (5,2)-configuration. In this talk, we will prove that except for four graphs, every
graph of minimum degree at least two which does not contain K_{1,6} as
an induced subgraph has a (5,2)-configuration. This is joint work with Waseem Abbas, Magnus Egerstedt, Robin Thomas, and Peter Whalen.