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

Series: Graph Theory Seminar

Let X denote the number of triangles in the random graph G(n, p). The problem of determining the asymptotics of the rate of the upper tail of X, that is, the function f_c(n,p) = log Pr(X > (1+c)E[X]), has attracted considerable attention of both the combinatorics and the probability communities. We shall present a proof of the fact that whenever log(n)/n << p << 1, then f_c(n,p) = (r(c)+o(1)) n^2 p^2 log(p) for an explicit function r(c). This is joint work with Matan Harel and Frank Mousset.

Series: Graph Theory Seminar

We present an algebraic framework which simultaneously
generalizes the notion of linear subspaces, matroids, valuated matroids,
oriented matroids, and regular matroids. To do this, we first
introduce algebraic objects which we call
pastures; they generalize both hyperfields in the sense
of Krasner and partial fields in the sense of Semple and Whittle. We
then define matroids over pastures; in fact, there are at least two
natural notions of matroid in this general context,
which we call weak and strong matroids. We present ``cryptomorphic'’ descriptions of each kind of matroid. To a (classical) rank-$r$ matroid $M$ on $E$, we can associate a
universal pasture (resp. weak universal pasture)
$k_M$ (resp. $k_M^w$). We show that morphisms from the universal
pasture (resp. weak universal pasture) of $M$ to a pasture $F$ are
canonically in bijection with strong (resp. weak) representations
of $M$ over $F$. Similarly, the sub-pasture $k_M^f$ of $k_M^w$
generated by ``cross-ratios'', which we call the
foundation of $M$, parametrizes rescaling classes of
weak $F$-matroid structures on $M$. As a sample application of these
considerations, we give a new proof of the fact that a matroid is
regular if and only if it is both binary and orientable.

Series: Graph Theory Seminar

A
sum of squares of real numbers is always nonnegative. This elementary
observation is quite powerful, and can be used to prove graph density inequalities in
extremal combinatorics, which address so-called Turan problems. This is
the essence of semidefinite method of Lov\'{a}sz and
Szegedy, and also
Cauchy-Schwartz calculus of Razborov. Here multiplication and addition
take place in the gluing algebra of partially
labelled graphs. This
method has been successfully used on many occasions and has also been
extensively studied theoretically. There are two
competing viewpoints
on the power of the sums of squares method. Netzer and Thom refined a
Positivstellensatz of Lovasz and Szegedy by
showing that if f> 0
is a valid graph density inequality, then for any a>0 the inequality
f+a > 0 can be proved via sums of squares. On the other hand,
Hatami and Norine
showed that testing whether a graph density inequality f > 0 is valid
is an undecidable problem, and also provided explicit but
complicated examples
of inequalities that cannot be proved using sums of squares. I will
introduce the sums of squares method, do several
examples of sums of
squares proofs, and then present simple explicit inequalities that show
strong limitations of the sums of squares method. This
is joint work in progress with Annie Raymond, Mohit Singh and Rekha Thomas.

Series: Graph Theory Seminar

Vertex minors are a weakening of the notion of induced subgraphs that
benefit from many additional nice properties. In particular, there is a
vertex minor version of Menger's Theorem proven by Oum. This theorem
gives rise to a natural analog of branch-width called rank-width.
Similarly to the Grid Theorem of Robertson and Seymour, we prove that a
class of graphs has unbounded rank-width if and only if it contains all
"comparability grids'' as vertex minors. This is joint work with Jim
Geelen, O-joung Kwon, and Paul Wollan.

Series: Graph Theory Seminar

Györi and Lovasz independently proved that a k-connected graph can be partitioned into k subgraphs, with each subgraph connected, containing a prescribed vertex, and with a prescribed
vertex count. Lovasz used topological methods, while Györi found a purely graph theoretical approach. Chen et al. later generalized the topological proof to graphs with weighted
vertices, where the subgraphs have prescribed weight sum rather than vertex count. The weighted result was recently proven using Györi's approach by Chandran et al. We will use the
Györi approach to generalize the weighted result slightly further. Joint work with Robin Thomas.

Series: Graph Theory Seminar

A classic theorem of Mader gives the extremal functions for graphs that
do not contain the complete graph on p vertices as a minor for p up to
7. Motivated by the study of linklessly embeddable graphs, we present
some results
on the extremal functions of apex graphs with respect to the number of
triangles, and on triangle-free graphs with excluded minors. Joint work with Robin Thomas.

Series: Graph Theory Seminar

For a graph G, a set of subtrees of G are edge-independent with
root r ∈ V(G) if, for every vertex v ∈ V(G), the paths between v and r
in each tree are edge-disjoint. A set of k such trees represent a set of
redundant
broadcasts from r which can withstand k-1 edge failures. It is easy to
see that k-edge-connectivity is a necessary condition for the existence
of a set of k edge-independent spanning trees for all possible roots.
Itai and Rodeh have conjectured that this condition
is also sufficient. This had previously been proven for k=2, 3. We
prove the case k=4 using a decomposition of the graph similar to an ear
decomposition. Joint work with Robin Thomas.

Series: Graph Theory Seminar

This is Lecture 2 of a series of 3 lectures by the speaker. See the abstract on Tuesday's ACO colloquium of this week. (Please note that this lecture will be 80 minutes' long.)

Series: Graph Theory Seminar

The celebrated Erdos-Hajnal conjecture states that for every graph H, there is a constant c > 0 such that every graph G that does not contain H as an induced subgraph has a clique or stable set of size at least n^c, where n = |V(G)|.
One approach for proving this conjecture is to prove that in every H-free graph G, there are two linear-size sets A and B such that either there are no edges between A and B, or every vertex in A is adjacent to every vertex in B. As is turns out, this is not true unless both H and its complement are trees. In the case when G contains neither H nor its complement as an induced subgraph, the conclusion above was conjectured to be true for all trees (Liebenau & Pilipczuk), and I will discuss a proof of this for a class of tree called "caterpillars".
I will also talk about results and open questions for some variants, including allowing one or both of A and B to have size n^c instead of linear size, and requiring the bipartite graph between A and B to have high or low density instead of being complete or empty. In particular, our results improve the bound on the size of the largest clique or stable that must be present in a graph with no induced five-cycle.
Joint work with Maria Chudnovsky, Jacob Fox, Anita Liebenau, Marcin Pilipczuk, Alex Scott, and Paul Seymour.

Series: Graph Theory Seminar

Let G be a graph containing 5 different vertices a0, a1, a2, b1 and b2.
We say that (G, a0, a1, a2, b1, b2) is feasible if G contains disjoint
connected subgraphs G1, G2, such that {a0, a1, a2}⊆V(G1) and {b1,
b2}⊆V(G2). In
this talk, we will complete a sketch of our arguments for characterizing when (G, a0, a1, a2, b1, b2) is feasible. Joint work with Changong Li, Robin Thomas, and Xingxing Yu.