Seminars and Colloquia by Series

Graham's Conjecture and Rainbow Paths in Graphs

Series
Graph Theory Seminar
Time
Tuesday, March 10, 2026 - 15:30 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Chase Wilson – UCSD

We discuss the recent progress on Graham's Conjecture which states that for any subset $S \subseteq \mathbb{Z}_p \setminus \{0\}$, there exists an ordering of the elements $s_1, \cdots, s_m$ of $S$ such that the partial sums $\sum_{i = 1}^k s_i$ are all distinct. This was very recently proven for all sufficiently large primes by Pham and Sauermann, however our work focuses on the more general setting where $\mathbb{Z}_p$ is replaced by an arbitrary finite group, where the result is also conjectured to hold.

By considering the Cayley Graph, we can translate the problem into the purely graph theoretic problem of finding a rainbow path of length $d - 1$ in any $d$-regular properly edge-colored directed graph. We give an asymptotic result which builds on work by Bucić, Frederickson, Müyesser, Pokrovskiy, and Yepremyan, and shows that we can find a path of length $(1 - o(1)) d$. This corresponds to showing that for any subset $S \subseteq G$, there exists a dense subset $S' \subseteq G$ and an ordering $s'_1, \cdots, s'_m$ of the elements of $S'$ such that the partial products $\prod_{i  = 1}^k s'_i$ are all distinct.

Tree Posets: Supersaturation, Enumeration, and Randomness

Series
Graph Theory Seminar
Time
Tuesday, March 3, 2026 - 15:30 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Sean Longbrake – Emory University

We say a partially ordered set $P$ is a tree poset if its Hasse diagram, the graph drawn by joining $x$ with $y$ if there is no $z$ such that $x > z > y$, is a tree. In this talk, we will be discussing a tool for embedding tree posets $P$ into subsets of the Boolean lattice, and some applications of it to counting copies of $P$ in subsets of the Boolean lattice, counting $P$-free subsets of the Boolean lattice, and largest $P$-free subsets of the Boolean lattice. This talk is based on joint work with Tao Jiang, Sam Spiro, and Liana Yepremyan. 

Truly Subquadratic Time Algorithms for Diameter in Geometric Intersection Graphs and Bounded Distance VC-dimension Graphs

Series
Graph Theory Seminar
Time
Tuesday, February 24, 2026 - 15:30 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Da Zheng – IST Austria

A simple algorithm for computing the diameter of an unweighted $n$-vertex graph is to run a BFS from every vertex of the graph. This leads to quadratic time algorithms for computing diameter in sparse graphs and geometric intersection graphs. There are matching fine-grained lower bounds which show that in many cases, it is not possible to get a truly subquadratic time algorithm for diameter computation.

To contrast, we give the first truly subquadratic time algorithm for computing the diameter of an $n$-vertex unit-disk graph. The algorithm runs in with $O^*(n^{2-1/18})$ time. The result is obtained as an instance of a general framework, applicable for distance problems in any graph with bounded distance VC-dimension. To obtain these results, we exploit bounded VC-dimension of neighborhood balls,  low-diameter decompositions, and geometric data structures.

Based on paper in FOCS 2025, joint work with Timothy M. Chan, Hsien-Chih Chang, Jie Gao, Sándor Kisfaludi-Bak, and Hung Le. Arxiv: https://arxiv.org/abs/2510.16346

Generalized Colouring of Planar Graphs

Series
Graph Theory Seminar
Time
Tuesday, February 17, 2026 - 15:30 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Evelyne Smith-Roberge – Illinois State University

In the mid 1990s, Thomassen proved that planar graphs are 5-list-colourable, and that planar graphs of girth at least five are 3-list-colourable. Moreover, it can be shown via a simple degeneracy argument that planar graphs of girth at least four are 4-list-colourable.  In 2021, Postle and I unified these results, showing that if $G$ is a planar graph and $L$, a list assignment for $G$ where all vertices have size at least three; vertices in 4-cycles have list size at least four; and vertices in triangles have list size at least five, then $G$ is $L$-colourable. In this talk, I will discuss a strengthening of this latter result: that it also holds for correspondence colouring, a generalization of list colouring. In fact, it holds even in the still stronger setting of weak degeneracy. I will also speak briefly on some other weak degeneracy results in the area.

No prior knowledge of correspondence colouring nor list colouring will be assumed.  (Ft. joint work with Ewan Davies, and with Anton Bernshteyn and Eugene Lee.)

Locally chordal graphs and beyond

Series
Graph Theory Seminar
Time
Tuesday, November 18, 2025 - 15:30 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Tara Abrishami – Stanford University

A graph is chordal if each of its cycles of length at least four has a chord. Chordal graphs occupy an extreme end of a trade-off between structure and generalization: they have strong structure and admit many interesting characterizations, but this strong structure makes them a special case, representative of only a few graphs. In this talk, I'll discuss a new class of graphs called locally chordal graphs. Locally chordal graphs are more general than chordal graphs, but still have enough structure to admit interesting characterizations. In particular, most of the major characterizations of chordal graphs generalize to locally chordal graphs in natural and powerful ways. In addition to explaining these characterizations, I’ll discuss some ideas about how locally chordal graphs relate to new width parameters and to results in structural sparsity. This talk is based on joint work with Paul Knappe and Jonas Kobler. 

Lipschitz functions on weak expanders

Series
Graph Theory Seminar
Time
Tuesday, November 4, 2025 - 15:30 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Lina Li – University of Mississippi

Given a connected finite graph $G$, an integer-valued function $f$ on $V(G)$ is called $M$-Lipschitz if the value of $f$ changes by at most $M$ along the edges of $G$. In 2013, Peled, Samotij, and Yehudayoff showed that random $M$-Lipschitz functions on graphs with sufficiently good expansion typically exhibit small fluctuations, giving sharp bounds on the typical range of such functions, assuming $M$ is not too large. We prove that the same conclusion holds under a relaxed expansion condition and for larger $M$, (partially) answering questions of Peled et al. Our approach combines Sapozhenko’s graph container method with entropy techniques from information theory.

 

This is joint work with Krueger and Park.

Lower tails for triangles inside the critical window

Series
Graph Theory Seminar
Time
Tuesday, October 28, 2025 - 15:30 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Michael Simkin – MIT

How likely is $G(n;p)$ to have a less-than-typical number of triangles? This is a foundational question in non-linear large deviation theory. When $p >> n^{-1/2}$ or $p >> n^{-1/2}$ the answer is fairly well-understood, with Janson's inequality applying in the former case and regularity- or container-based methods applying in the latter. We study the regime $p = c n^{-1/2}$, with $c>0$ fixed, with the large deviation event having at most $E$ times the expected number of triangles, for a fixed $0 <= E < 1$.

We prove explicit formula for the log-asymptotics of the event in question, for a wide range of pairs $(c,E)$. In particular, we show that for sufficiently small $E$ (including the triangle-free case $E = 0$) there is a phase transition as $c$ increases, in the sense of a non-analytic point in the rate function. On the other hand, if $E > 1/2$, then there is no phase transition.

As corollaries, we obtain analogous results for the $G(n;m)$ model, when $m = C n^{3/2}$. In contrast to the $G(n;p)$ case, we show that a phase transition occurs as $C$ increases for all $E$.

Finally, we show that the probability of $G(n;m)$ being triangle free, where $m = C n^{3/2}$ for a sufficiently small constant $C$, conforms to a Poisson heuristic.

Joint with Matthew Jenssen, Will Perkins, and Aditya Potukuchi.

Nonabelian Sidon sets and extremal problems on digraphs 

Series
Graph Theory Seminar
Time
Tuesday, October 21, 2025 - 15:30 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
John Byrne – University of Delaware

An $S_k$-set is a subset of a group whose $k$-tuples have distinct products. We give explicit constructions of large $S_k$-sets in the groups $\mathrm{Sym}(n)$ and $\mathrm{Alt}(n)$ and of large $S_2$-sets in $\mathrm{Sym}(n)\times\mathrm{Sym}(n)$ and $\mathrm{Alt}(n)\times\mathrm{Alt}(n)$, as well as some probabilistic constructions for 'nice' groups. We show that $k$ is even and $\Gamma$ has a normal abelian subgroup with bounded index then any $S_k$-set has size at most $(1-\varepsilon)|\Gamma|^{1/k}$. We describe some connections between $S_k$-sets and extremal graph theory. We determine up to a constant factor the largest possible minimum outdegree in a digraph with no subgraph in $\{C_{2,2},\ldots,C_{k,k}\}$, where $C_{\ell,\ell}$ is the orientation of $C_{2\ell}$ with two maximal directed $\ell$-paths. Contrasting with undirected cycles, the extremal minimum outdegree for $\{C_{2,2},\ldots,C_{k,k}\}$ is much smaller than that for any $C_{\ell,\ell}$. We count the directed Hamilton cycles in one of our constructions to improve the upper bound for a problem on Hamilton paths introduced by Cohen, Fachini, and Körner. Joint work with Michael Tait.

A new lower bound for the Ramsey numbers R(3,k)

Series
Graph Theory Seminar
Time
Tuesday, October 14, 2025 - 15:30 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Marcus Michelen – Northwestern University

The Ramsey number R(3,k) is the smallest n so that every triangle free graph on n vertices has an independent set of size k.  Upper bounds to R(3,k) consist of finding independent sets in triangle free graphs, while lower bounds consist of constructing triangle free graphs with no large independent set.  The previous best-known lower bound was independently due to works of Bohman-Keevash and Fiz Pontiveros-Griffiths-Morris, both of which analyzed the triangle-free process.  The analysis of the triangle-free process is a delicate dance of demonstrating self-correction and requires tracking a large family of graph statistics simultaneously.  We will discuss a new lower bound to R(3,k) and provide a gentle introduction to the concept of "the Rodl nibble," with an emphasis on which ideas simplify our analysis.  This is based on joint work with Marcelo Campos, Matthew Jenssen and Julian Sahasrabudhe.

Hypergraph Turán Problems

Series
Graph Theory Seminar
Time
Tuesday, September 23, 2025 - 15:30 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Bernard Lidický – Iowa State University

Hypergraph Turán Problems became more approachable due to flag algebras. In this talk we will first focus on tight cycles without an edge. A tight $k$-cycle minus an edge $C_k^-$ is the 3-graph on the vertex set $[k]$, where any three consecutive vertices in the string $123...k1$ form an edge. We show that for every $k \geq 5$, k not divisible by $3$, the extremal density is $1/4$. Moreover, we determine the extremal graph up to $O(n)$ edge edits. The proof is based on flag algebra calculations.

Then we describe new developments in solving large semidefinite programs that allows for improving several other bounds on Turán densities.

This talk is based on joint work with Connor Mattes, Florian Pfender and Jan Volec.

Pages