Workshop

Zoom Link

A $k$-star decomposition of a graph is a partition of the edge set into disjoint $k$-stars. Using the small subgraph conditioning method (SSCM), in 2018 Delcourt and Postle proved that with high probability, a random 4-regular graph has a 3-star decomposition. I will describe work to generalise this result. We have proved, again using the SSCM, that if a certain equation has a unique solution then with high probability, a random $d$-regular graphs has a $k$-star decomposition. We also prove that this sufficient condition holds whenever $k\leq d/2 + \log(d)/6$. There are connections with earlier work on beta-orientations which can be used to prove existence of $k$-star decompositions when $k \leq d/2$, while non-existence results can be obtained using a connection with independent sets in random regular graphs.

Zoom Link

The number of homomorphisms from a graph H to a graph G, denoted by hom(H;G), is the number of maps from V(H) to V(G) that yield a graph homomorphism, i.e., that map every edge of H to an edge of G. Given a fixed collection of finite simple graphs {H_1, ..., H_s}, the graph profile is the set of all vectors (hom(H_1; G), ..., hom(H_s; G)) as G varies over all graphs. We will first discuss graph profiles, which are objects that essentially allow us to understand all polynomial inequalities in homomorphism numbers that are valid on all graphs. Profiles can be extremely complicated; for instance the full profile of any triple of connected graphs is not known. To simplify these objects, we introduce their tropicalization which we show is a closed convex cone that still captures interesting combinatorial information. We explicitly compute these tropicalizations for some sets of graphs, and use those results to answer some questions in extremal graph theory.

Zoom Link

We investigate natural Turán problems for directed graphs (digraphs) and mixed graphs, generalizations of graphs where edges can be either directed or undirected. In both of these situations, far less is known than in the classical Turán setting. We characterize the Turán numbers of several natural families of sparse digraphs that highlight that directed path lengths play a weaker, but analogous role to the chromatic number in the directed setting. In the mixed graph setting, we study a natural Turán density coefficient, establishing an analogue of the Erdős-Stone-Simonovits theorem and showing that Turán density coefficients can be irrational, but are always algebraic.

Zoom Link

Motivated by algorithmic applications, the study of the extremal function ex(n, K_k, K_t-minor), i.e., the number of cliques of order k in K_t-minor free graphs on n vertices, has received much attention. In this talk, we will show essentially sharp bounds on the maximum possible number of cliques of order k in a K_t-minor free graph on n vertices. More precisely, we determine a function C(k,t) such that for each k < t with t-k >> log_2 t, every K_t-minor free graph on n vertices has at most n C(k, t)^{1+o_t(1)} cliques of order k. We also show this bound is sharp by constructing K_t-minor-free graphs on n vertices with C(k, t) n cliques of order k. This bound answers a question of Wood and Fox-Wei asymptotically up to o_t(1) in the exponent except the extreme values when k is very close to t. This talk is based on a joint work with Ruilin Shi.

Zoom Link

This talk requires no prior knowledge and will be suitable for a broad audience. We will meet the chromatic symmetric function, dating from 1995, which is a generalization of the chromatic polynomial. We will also hear about a famed problem regarding it, called the Stanley-Stembridge (3+1)-free problem. This has been the focus of much research lately including resolving another problem of Stanley of whether the (3+1)-free problem can be widened. The resulting paper on the latter problem was recently awarded the 2023 MAA David P. Robbins Prize, and we will hear this story too.