..
This connects to Erdős’s classical 1958 theorem that graphs with arbitrarily large girth and chromatic number exist. A natural question is whether this persists for unit-distance graphs: graphs whose vertices can be embedded into $\mathbb R^d$ so that the endpoints of each edge are at distance $1$. The best known lower bound on the chromatic number in this setting is due to Raigorodskii (2000), who showed that $\chi(G)\ge (1.239+o(1))^d$ is achievable. Kupavskii (2012) proved that for every $g$ there exists $c_g>1$ such that there exist unit-distance graphs in $\mathbb{R}^d$ with girth at least $g$ and $\chi(G)\ge (c_g+o(1))^d$, although known estimates of $c_g$ tend to 1 as $g$ grows.
In this talk I present a recent paper by Matija Bucić and James Davies in which they prove the existence of unit-distance graphs in $\mathbb R^d$ with chromatic number at least $(1.074+o(1))^d$ that have arbitrarily large girth. The same construction also yields graphs with large chromatic number and high girth in other geometric settings, namely diameter graphs and orthogonality graphs.
In this talk I will present a proof of the theorem due to Stevo Todorčević, following a recent exposition by Spencer Unger, which was explained to me by Jan Hubička. If time permits, I will also show how the Halpern–Läuchli theorem implies Milliken's tree theorem, a Ramsey-style theorem in which Halpern–Läuchli plays the role of the pigeonhole principle.
Past Talks
2026/3/27: Geometric graphs with exponential chromatic number and arbitrary girth
Given at: Seminar on Combinatorics
Materials: notes
Abstract
The Hadwiger–Nelson problem asks for the chromatic number of the plane — the minimum number of colors needed to color $\mathbb{R}^2$ so that no two points at distance $1$ receive the same color. While unit-distance graphs with chromatic number $4$ are easy to construct, Erdős (1975) asked whether such graphs can avoid triangles, i.e., have girth (the length of a shortest cycle) at least $4$. This was answered affirmatively by subsequent constructions, culminating in O’Donnell’s 1999 result showing the existence of $4$-chromatic unit-distance graphs with arbitrary girth.This connects to Erdős’s classical 1958 theorem that graphs with arbitrarily large girth and chromatic number exist. A natural question is whether this persists for unit-distance graphs: graphs whose vertices can be embedded into $\mathbb R^d$ so that the endpoints of each edge are at distance $1$. The best known lower bound on the chromatic number in this setting is due to Raigorodskii (2000), who showed that $\chi(G)\ge (1.239+o(1))^d$ is achievable. Kupavskii (2012) proved that for every $g$ there exists $c_g>1$ such that there exist unit-distance graphs in $\mathbb{R}^d$ with girth at least $g$ and $\chi(G)\ge (c_g+o(1))^d$, although known estimates of $c_g$ tend to 1 as $g$ grows.
In this talk I present a recent paper by Matija Bucić and James Davies in which they prove the existence of unit-distance graphs in $\mathbb R^d$ with chromatic number at least $(1.074+o(1))^d$ that have arbitrarily large girth. The same construction also yields graphs with large chromatic number and high girth in other geometric settings, namely diameter graphs and orthogonality graphs.
2026/3/18: A short proof of the Halpern–Läuchli theorem
Given at: Seminar on Reckoning
Abstract
A classical product Ramsey theorem states that for every $n$ there exists $N$ such that every $2$-coloring of the edges of $K_{N,N}$ contains a monochromatic copy of $K_{n,n}$. The most direct infinite analogue fails: one can easily construct a $2$-coloring of the product $\omega\times\omega$ that contains no monochromatic copy of $\omega\times\omega$. This raises the question whether a meaningful infinite product Ramsey theorem exists. The Halpern–Läuchli theorem provides such a result for level products of finitely branching trees of height $\omega$ with no leaves. It guarantees the existence of monochromatic strong subtrees (subtrees preserving part of the branching structure of the original trees) of height $\omega$.In this talk I will present a proof of the theorem due to Stevo Todorčević, following a recent exposition by Spencer Unger, which was explained to me by Jan Hubička. If time permits, I will also show how the Halpern–Läuchli theorem implies Milliken's tree theorem, a Ramsey-style theorem in which Halpern–Läuchli plays the role of the pigeonhole principle.