Georgia Institute of Technology College of Sciences

Turán-type problems ask for the densest-possible structure which avoids a fixed substructure H. Ramsey-type problems ask for the largest possible "complete" structure which can be decomposed into a fixed number of H-free parts. We discuss some of these problems in the context of vector spaces over finite fields. In the Turán setting, Furstenberg and Katznelson showed that any constant-density subset of the affine space AG(n,q) must contain a k-dimensional affine subspace if n is large enough. On the Ramsey side of things, a classical result of Graham, Leeb, and Rothschild implies that any red-blue coloring of the projective space PG(n-1,q) must contain a monochromatic k-dimensional projective subspace, for n large. We highlight the connection between these results and show how to obtain new bounds in the latter (projective Ramsey) problem from bounds in the former (affine Turán) problem. This is joint work with Liana Yepremyan.

The well-known tree packing conjecture of Gyárfás from 1976 says that, given any sequence of n trees in which the ith tree has i vertices, the trees can be packed edge-disjointly into the complete n-vertex graph. Packing even just the largest trees in such a sequence has proven difficult, with Bollobás drawing attention to this in 1995 by conjecturing that, for each k, if n is sufficiently large then the largest k trees in any such sequence can be packed. This has only been shown for k at most 5, by Zak, despite many partial results and much related work on the full tree packing conjecture.

I will discuss a result which proves Bollobás's conjecture by showing that, moreover, a linear number of the largest trees can be packed in the tree packing conjecture. This is joint work with Barnabás Janzer.

We consider the algorithmic problem of finding large balanced independent sets in sparse random bipartite graphs, and more generally the problem of finding independent sets with specified proportions of vertices on each side of the bipartition. In a bipartite graph it is trivial to find an independent set of density at least half (take one of the partition classes). In contrast, in a random bipartite graph of average degree d, the largest balanced independent sets (containing equal number of vertices from each class) are typically of density (2 + od(1)) log d/d . Can we find such large balanced independent sets in these graphs efficiently? By utilizing the overlap gap property and the low-degree algorithmic framework, we prove that local and low-degree algorithms (even those that know the bipartition) cannot find balanced independent sets of density greater than (1 + ε) log d/d for any ε > 0 fixed and d large but constant.

Fox et al introduced the model of c-closed graphs, a distribution-free model motivated by one of the most universal signatures of social networks, triadic closure. Even though enumerating maximal cliques in an arbitrary network can run in exponential time, it is known that for c-closed graph, enumerating maximal cliques and maximal complete bipartite graphs is always fast, i.e., with complexity being polynomial in the number of vertices in the network. In this work, we investigate further by enumerating maximal blow-ups of an arbitrary graph H in c-closed graphs. We prove that given any finite graph H, the number of maximal blow-ups of H in any c-closed graph on n vertices is always at most polynomial in n. When considering maximal induced blow-ups of a finite graph H, we provide a characterization of graphs H when the bound is always polynomial in n. A similar general theorem is also proved when H is infinite.