## Seminars and Colloquia by Series

### Progress towards Nash-Williams' conjecture on triangle decompositions

Series
Graph Theory Seminar
Time
Tuesday, February 9, 2021 - 12:30 for 1 hour (actually 50 minutes)
Location
Speaker
Michelle DelcourtRyerson University

Please Note: Note the unusual time!

Partitioning the edges of a graph into edge disjoint triangles forms a triangle decomposition of the graph. A famous conjecture by Nash-Williams from 1970 asserts that any sufficiently large, triangle divisible graph on $n$ vertices with minimum degree at least $0.75 n$ admits a triangle decomposition. In the light of recent results, the fractional version of this problem is of central importance. A fractional triangle decomposition is an assignment of non-negative weights to each triangle in a graph such that the sum of the weights along each edge is precisely one.

We show that for any graph on n vertices with minimum degree at least $0.827327 n$ admits a fractional triangle decomposition. Combined with results of Barber, Kühn, Lo, and Osthus, this implies that for every sufficiently large triangle divisible graph on $n$ vertices with minimum degree at least $0.82733 n$ admits a triangle decomposition. This is a significant improvement over the previous asymptotic result of Dross showing the existence of fractional triangle decompositions of sufficiently large graphs with minimum degree more than $0.9 n$. This is joint work with Luke Postle.

### Prague dimension of random graphs

Series
Graph Theory Seminar
Time
Tuesday, January 26, 2021 - 15:45 for 1 hour (actually 50 minutes)
Location
Speaker
He GuoGeorgia Institute of Technology

The Prague dimension of graphs was introduced by Nešetřil, Pultr and Rödl in the 1970s. Proving a conjecture of Füredi and Kantor, we show that the Prague dimension of the binomial random graph is typically of order $n/\log n$ for constant edge-probabilities. The main new proof ingredient is a Pippenger–Spencer type edge-coloring result for random hypergraphs with large uniformities, i.e., edges of size $O(\log n)$. Based on joint work with Kalen Patton and Lutz Warnke.

### Asymptotic dimension of minor-closed families and beyond

Series
Graph Theory Seminar
Time
Tuesday, December 8, 2020 - 15:45 for 1 hour (actually 50 minutes)
Location
Speaker
Chun-Hung LiuTexas A&amp;M University

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.

### Embedding spanning structures into vertex-ordered graphs

Series
Graph Theory Seminar
Time
Tuesday, December 1, 2020 - 15:45 for 1 hour (actually 50 minutes)
Location
Speaker
Andrew TreglownUniversity of Birmingham

Over recent years there has been much interest in both Turán and Ramsey properties of vertex ordered graphs (i.e., graphs equipped with an ordering of their vertex set). In a recent paper, József Balogh, Lina Li and I initiated the study of embedding spanning structures into vertex ordered graphs. In particular, we introduced a general framework for approaching the problem of determining the minimum degree threshold for forcing a perfect $H$-tiling in an ordered graph. In this talk I will discuss this work, in particular emphasizing how we adapt the regularity and absorbing methods to be applicable in the ordered setting.

### Weak saturation numbers of complete bipartite graphs

Series
Graph Theory Seminar
Time
Tuesday, November 24, 2020 - 15:45 for 1 hour (actually 50 minutes)
Location