Georgia Institute of Technology School of Mathematics | Georgia Institute of Technology | Atlanta, GA

 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. 

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.

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.

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.