We prove that the dimension of every poset whose comparability graph has maximum degree $\Delta$ is at most $\Delta\log^{1+o(1)} \Delta$. This result improves on a 30-year old bound of F\"uredi and Kahn, and is within a $\log^{o(1)}\Delta$ factor of optimal. We prove this result via the notion of boxicity. The \emph{boxicity} of a graph $G$ is the minimum integer $d$ such that $G$ is the intersection graph of $d$-dimensional axis-aligned boxes. We prove that every graph with maximum degree $\Delta$ has boxicity at most $\Delta\log^{1+o(1)} \Delta$, which is also within a $\log^{o(1)}\Delta$ factor of optimal. We also show that the maximum boxicity of graphs with Euler genus $g$ is $\Theta(\sqrt{g \log g})$, which solves an open problem of Esperet and Joret and is tight up to a $O(1)$ factor. This is joint work with Alex Scott (arXiv:1804.03271).

# Combinatorial Theory Seminar

Please note that the list below only shows forthcoming events, which may not include regular events that have not yet been entered for the forthcoming term. Please see the past events page for a list of all seminar series that the department has on offer.

The last remaining open problem from Erdős and Rényi's original paper on random graphs is the following: for q at least 3, what is the largest d so that the random graph G(n,d/n) is q-colorable with high probability? A lot of interesting work in probabilistic combinatorics has gone into proving better and better bounds on this q-coloring threshold, but the full answer remains elusive. However, a non-rigorous method from the statistical physics of glasses - the cavity method - gives a precise prediction for the threshold. I will give an introduction to the cavity method, with random graph coloring as the running example, and describe recent progress in making parts of the method rigorous, emphasizing the role played by tools from extremal combinatorics. Based on joint work with Amin Coja-Oghlan, Florent Krzakala, and Lenka Zdeborová.