Georgia Institute of Technology College of Sciences

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.

Ramsey proved that for every positive integer r, every sufficiently large graph contains as an induced subgraph either a complete graph on r vertices or an independent set with r vertices.  It is well known that every sufficiently large, connected graph contains an induced subgraph isomorphic to one of a large complete graph, a large star, and a long path.  We prove an analogous result for 2-connected graphs.  Similarly, for infinite graphs, every infinite connected graph contains an induced subgraph isomorphic to one of the following: an infinite complete graph, an infinite star, and a ray.  We also prove an analogous result for infinite 2-connected graphs.

Many results in extremal graph theory build on supersaturation of subgraphs. In other words, when a graph is dense enough, it contains many copies of a certain subgraph and these copies are then used as building blocks to force another subgraph of interest. Recently more success is found within this approach where one utilizes not only the large number of copies of a certain subgraph but a well-distributed collection of them to force the desired subgraph. We discuss some recent progress of this nature. The talk is built on joint work with Sean Longbrake, and with Sean Longbrake and Jie Ma.