## Seminars and Colloquia by Series

### Progress towards the Burning Number Conjecture

Series
Graph Theory Seminar
Time
Tuesday, October 11, 2022 - 15:45 for 1 hour (actually 50 minutes)
Location
Speaker
Jérémie TurcotteMcGill University

The burning number $b(G)$ of a graph $G$ is the smallest integer $k$ such that $G$ can be covered by $k$ balls of radii respectively $0,\dots,k-1$, and was introduced independently by Brandenburg and Scott at Intel as a transmission problem on processors \cite{alon} and Bonato, Janssen and Roshanbin as a model for the spread of information in social networks.

The Burning Number Conjecture \cite{bonato} claims that $b(G)\leq \left\lceil\sqrt{n}\right\rceil$, where $n$ is the number of vertices of $G$. This bound tight for paths. The previous best bound for this problem, by Bastide et al. \cite{bastide}, was $b(G)\leq \sqrt{\frac{4n}{3}}+1$.

We prove that the Burning Number Conjecture holds asymptotically, that is $b(G)\leq (1+o(1))\sqrt{n}$.

Following a brief introduction to graph burning, this talk will focus on the general ideas behind the proof.

### The complexity of list-5-coloring with forbidden induced substructures

Series
Graph Theory Seminar
Time
Tuesday, October 4, 2022 - 15:45 for 1 hour (actually 50 minutes)
Location
Speaker
Yanjia LiGeorgia Tech

The list-$k$-coloring problem is to decide, given a graph $G$ and a list assignment $L$ of $G$ from $V(G)$ to subsets of $\{1,...,k\}$, whether $G$ has a coloring $f$ such that $f(v)$ in $L(v)$ for all $v$ in $V(G)$. The list-$k$-coloring problem is a generalization of the $k$-coloring problem. Thus for $k\geq 3$, both the $k$-coloring problem and the list-$k$-coloring problem are NP-Hard. This motivates studying the complexity of these problems restricted to graphs with a fixed forbidden induced subgraph $H$, which are called $H$-free graphs.

In this talk, I will present a polynomial-time algorithm to solve the list-5-coloring $H$-free graphs with $H$ being the union of $r$ copies of mutually disjoint 3-vertex paths. Together with known results, it gives a complete complexity dichotomy of the list-5-coloring problem restricted to $H$-free graphs. This is joint work with Sepehr Hajebi and Sophie Spirkl.

### New lift matroids for gain graphs

Series
Graph Theory Seminar
Time
Tuesday, September 20, 2022 - 15:45 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Zach WalshGeorgia Tech

Given a graph G with edges labeled by a group, a construction of Zaslavsky gives a rank-1 lift of the graphic matroid M(G) that respects the group-labeling. For which finite groups can we construct a rank-t lift of M(G) with t > 1 that respects the group-labeling? We show that this is possible if and only if the group is the additive subgroup of a non-prime finite field. We assume no knowledge of matroid theory.

### Unifying and localizing two planar list colouring results of Thomassen

Series
Graph Theory Seminar
Time
Tuesday, September 6, 2022 - 15:45 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Evelyne Smith-RobergeGeorgia Tech

Thomassen famously showed that every planar graph is 5-choosable, and that every planar graph of girth at least five is 3-choosable.  These theorems are best possible for uniform list assignments: Voigt gave a construction of a planar graph that is not 4-choosable, and of a planar graph of girth four that is not 3-choosable. In this talk, I will introduce the concept of a local girth list assignment: a list assignment wherein the list size of each vertex depends not on the girth of the graph, but only on the length of the shortest cycle in which the vertex is contained. I will present a local list colouring theorem that unifies the two theorems of Thomassen mentioned above and discuss some of the highlights and difficulties of the proof. This is joint work with Luke Postle.

### Thresholds for Latin squares and Steiner triple systems

Series
Graph Theory Seminar
Time
Tuesday, August 30, 2022 - 15:45 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Tom KellyGeorgia Tech

An order-n Latin square is an $n \times n$ matrix with entries from a set of $n$ symbols, such that each row and each column contains each symbol exactly once.  Suppose that $L_{i,j} \subseteq [n]$ is a random subset of $[n]$ where each $k \in [n]$ is included in $L_{i,j}$ independently with probability $p$ for each $i,j\in[n]$.  How likely does there exist an order-$n$ Latin square where the entry in the $i$th row and $j$th column lies in $L_{i,j}$?  This question was initially raised by Johansson in 2006, and later Casselgren and H{\"a}ggkvist and independently Luria and Simkin conjectured that $\log n / n$ is the threshold for this property.  In joint work with Dong-yeap Kang, Daniela K\"{u}hn, Abhishek Methuku, and Deryk Osthus, we proved that for some absolute constant $C$, if $p > C \log^2 n / n$, then asymptotically almost surely there exists such a Latin square.  We also prove analogous results for Steiner triple systems and $1$-factorizations of complete graphs.

### Concentration of the Chromatic Number of Random Graphs

Series
Graph Theory Seminar
Time
Tuesday, May 17, 2022 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Lutz WarnkeUCSD
What can we say about the chromatic number \chi(G_{n,p}) of an n-vertex binomial random graph G_{n,p}? From a combinatorial perspective, it is natural to ask about the typical value of \chi(G_{n,p}), i.e., upper and lower bounds that are close to each other. From a probabilistic combinatorics perspective, it is also natural to ask about the concentration of \chi(G_{n,p}), i.e., how much this random variable varies. Among these two fundamental questions, significantly less is known about the concentration question that we shall discuss in this talk. In terms of previous work, in the 1980s Shamir and Spencer proved that the chromatic number of the binomial random graph G_{n,p} is concentrated in an interval of length at most \omega\sqrt{n}, and in the 1990s Alon showed that an interval of length \omega\sqrt{n}/\log n suffices for constant edge-probabilities p\in (0,1). In this talk, we prove a similar logarithmic improvement of the Shamir-Spencer concentration results for the sparse case p=p(n) \to 0, and also discuss several intriguing questions about the chromatic number \chi(G_{n,p}) that remain open. Based on joint work with Erlang Surya; see https://arxiv.org/abs/2201.00906

### On the size Ramsey number of graphs

Series
Graph Theory Seminar
Time
Tuesday, April 26, 2022 - 11:00 for 1 hour (actually 50 minutes)
Location
Skiles 005/Zoom (hybrid)
Speaker
Meysam MiralaeiInstitute for Research in Fundamental Sciences, Iran

Please Note: Note the unusual time!

For given graphs $G$ and $H$ and a graph $F$, we say that $F$ is Ramsey for $(G, H)$ and we write $F \longrightarrow (G,H)$, if for every $2$-edge coloring of $F$, with colors red and blue, the graph $F$ contains either a red copy of $G$ or a blue copy of $H$. A natural question is how few vertices can a graph $F$ have, such that $F \longrightarrow (G,H)$? Frank P. Ramsey studied this question and proved that for given graphs $G$ and $H$, there exists a positive integer $n$ such that for the complete graph $K_n$ we have $K_n \longrightarrow (G,H)$. The smallest such $n$ is known as the Ramsey number of $G$, $H$ and is denoted by $R(G, H)$. Instead of minimizing the number of vertices, one can ask for the minimum number of  edges of such a graph, i.e. can we find a graph which possibly has more vertices than $R(G, H)$, but has fewer edges and still is Ramsey for $(G,H)$? How many edges suffice to construct a graph which is Ramsey for $(G,H)$? The attempts at answering the last question give rise to the notion of size-Ramsey number of graphs. In 1978, Erdős, Faudree, Rousseau and Schelp pioneered the study of the size-Ramsey number to be the minimum number of edges in a graph $F$, such that $F$ is Ramsey for $(G,H)$. In this talk, first I will give a short history about the size Ramsey number of graphs with a special focus on sparse graphs. Moreover, I will talk about the multicolor case of the size Ramsey number of cycles with more details.

### A min-max theorem for circuit decompositions of group-labelled graphs

Series
Graph Theory Seminar
Time
Tuesday, April 19, 2022 - 15:45 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Rose McCartyUniversity of Warsaw

This talk focuses on Eulerian graphs whose arcs are directed and labelled in a group. Each circuit yields a word over the group, and we say that a circuit is non-zero if this word does not evaluate to 0. We give a precise min-max theorem for the following problem. Given a vertex $v$, what is the maximum number of non-zero circuits in a circuit decomposition where each circuit begins and ends at $v$? This is joint work with Jim Geelen and Paul Wollan. Our main motivation is a surprising connection with vertex-minors which is due to Bouchet and Kotzig.

### Fast algorithms for $(\Delta+1)$-edge-coloring

Series
Graph Theory Seminar
Time
Tuesday, April 12, 2022 - 15:45 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Abhishek DhawanGeorgia Institute of Technology

Vizing's Theorem states that simple graphs can be edge-colored using $\Delta+1$ colors. The problem of developing efficient $(\Delta+1)$-edge-coloring algorithms has been a major challenge. The algorithms involve iteratively finding small subgraphs $H$ such that one can extend a partial coloring by modifying the colors of the edges in $H$. In a recent paper, Bernshteyn showed one can find $H$ such that $e(H) = \mathrm{poly}(\Delta)(\log n)^2$.  With this result, he defines a $(\Delta+1)$-edge-coloring algorithm which runs in $\mathrm{poly}(\Delta, \log n)$ rounds. We improve on this by showing we can find $H$ such that $e(H) = \mathrm{poly}(\Delta)\log n$. As a result, we define a distributed algorithm that improves on Bernshteyn's by a factor of $\mathrm{poly}(\log n)$. We further apply the idea to define a randomized sequential algorithm which computes a proper $(\Delta+1)$-edge-coloring in $\mathrm{poly}(\Delta)n$ time. Under the assumption that $\Delta$ is a constant, the previous best bound is $O(n\log n)$ due to Sinnamon.

### Recent advances in Ramsey theory

Series
Graph Theory Seminar
Time
Tuesday, March 29, 2022 - 15:45 for 1 hour (actually 50 minutes)
Location
ONLINE
Speaker
Dhruv MubayiUniversity of Illinois at Chicago

Ramsey theory studies the paradigm that every sufficiently large system contains a well-structured subsystem. Within graph theory, this translates to the following statement: for every positive integer $s$, there exists a positive integer $n$ such that for every partition of the edges of the complete graph on $n$ vertices into two classes, one of the classes must contain a complete subgraph on $s$ vertices. Beginning with the foundational work of Ramsey in 1928, the main question in the area is to determine the smallest $n$ that satisfies this property.

For many decades, randomness has proved to be the central idea used to address this question. Very recently, we proved a theorem which suggests that "pseudo-randomness" and not complete randomness may in fact be a more important concept in this area. This new connection opens the possibility to use tools from algebra, geometry, and number theory to address the most fundamental questions in Ramsey theory. This is joint work with Jacques Verstraete.