Georgia Institute of Technology College of Sciences

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.

We will discuss proper q-colourings of sparse, bounded degree graphs when the maximum degree is near the so-called shattering threshold. This threshold, first identified in the statistical physics literature, coincides with the point at which all known efficient colouring algorithms fail and it has been hypothesized that the geometry of the solution space (the space of proper colourings) is responsible. This hypothesis is a cousin of the Overlap-Gap property of Gamarnik ‘21. Significant evidence for this picture was provided by Achlioptos and Coja-Oghlan ‘08, who drew inspiration from statistical physics, but their work only explains the performance of algorithms on random graphs (average-case complexity). We extend their work beyond the random setting by proving that the geometry of the solution space is well behaved for all graphs below the “shattering threshold”. This follows from an original result about the structure of uniformly random colourings of fixed graphs. Joint work with François Pirot.