Georgia Institute of Technology College of Sciences

The asymptotic dimension of metric spaces is an important notion in geometric group theory. The metric spaces considered in this talk are the ones whose underlying spaces are the vertex-sets of (edge-)weighted graphs and whose metrics are the distance function in weighted graphs. A standard compactness argument shows that it suffices to consider the asymptotic dimension of classes of finite weighted graphs. We prove that the asymptotic dimension of any minor-closed family of weighted graphs, any class of weighted graphs of bounded tree-width, and any class of graphs of bounded layered tree-width are at most 2, 1,and 2, respectively. The first result solves a question of Fujiwara and Papasoglu; the second and third results solve a number of questions of Bonamy, Bousquet, Esperet, Groenland, Pirot and Scott. These bounds for asymptotic dimension are optimal and generalize and improve some results in the literature, including results for Riemannian surfaces and Cayley graphs of groups with a forbidden minor.

The notion of weak saturation was introduced by Bollobás in 1968. A graph $G$ on $n$ vertices is weakly $F$-saturated if the edges of $E(K_n) \setminus  E(G)$ can be added to $G$, one edge at a time, in such a way that every added edge creates a new copy of $F$. The minimum size of a weakly $F$-saturated graph $G$ of order $n$ is denoted by $\mathrm{wsat}(n, F)$. In this talk, we discuss the weak saturation number of complete bipartite graphs and determine $\mathrm{wsat}(n, K_{t,t})$ whenever $n > 3t-4$. For fixed $1

The following are two classical questions in the area of universal graphs.

1. What is the minimum number of vertices in a graph that contains all $n$-vertex planar graphs as induced subgraphs?

2. What is the minimum number of edges in a graph that contains all $n$-vertex planar graphs as subgraphs?

We give nearly optimal constructions for each problem, i.e. with $n^{1+o(1)}$ vertices for Question 1 and $n^{1+o(1)}$ edges for Question 2. The proofs combine a recent structure theorem for planar graphs (of independent interest) with techniques from data structures.

Joint work with V. Dujmovic, C. Gavoille, G. Joret, P. Micek, and P. Morin.

Erdős, Pach, Pollack and Tuza conjectured that for fixed integers $r$, $\delta \ge 2$, for any connected graph $G$ with minimum degree $\delta$ and order $n$:

(i) If $G$ is $K_{2r}$-free and $\delta$ is a multiple of $(r-1)(3r+2)$, then, as $n$ tends to infinity, the diameter of $G$ is at most $\frac{2(r-1)(3r+2)}{(2r^2-1)} \cdot \frac{n}{\delta} + O(1)$.

(ii) If $G$ is $K_{2r+1}$-free and $\delta$ is a multiple of $3r-1$, then, as $n$ tends to infinity, the diameter of $G$ is at most $\frac{3r-1}{r} \cdot \frac{n}{\delta} + O(1)$.

They created examples that show that the above conjecture, if true, is tight.

No more progress has been reported on this conjecture, except that for $r=2$ in (ii), under a stronger hypothesis ($4$-colorable instead of $K_5$-free), Czabarka, Dankelman and Székely showed that for every connected $4$-colorable graph $G$ of order $n$ and minimum degree $\delta \ge 1$, the diameter of $G$ is at most $\frac{5n}{2\delta} - 1$.

For every $r>1$ and $\delta \ge 2(r-1)$, we create $K_{2r}$-free graphs with minimum degree $\delta$ and diameter $\frac{(6r-5)n}{(2r-1)\delta+2r-3}+O(1)$, which are counterexamples to the conjecture for every $r>1$ and $\delta > 2(r-1)(3r+2)(2r-3)$. We also prove positive results under a stronger hypothesis, $k$-colorability, instead of being $K_{k+1}$-free. We show that the diameter of connected $k$-colorable graphs with minimum degree at least $\delta$ and order $n$ is at most $\left(3-\frac{1}{k-1}\right)\frac{n}{\delta}+O(1)$, while for $k=3$, it is at most $\frac{57n}{23\delta}+O(1)$.

This is joint work with Inne Singgih and László A. Székely.