SFU Discrete Math Seminar: David R. Wood

The dimension of a poset P is the minimum number of total orders whose intersection is P. 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üredi and Kahn [Order, 1986], and is within a $log^{o(1)} \Delta$ factor of optimal. We prove this result via the notion of boxicity. The 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 [Graphs Combin. 2013] and is tight up to a constant factor. The separation dimension of a graph G is the minimum positive integer d for which there is an embedding of G into $\mathbb{R}^d$, such that every pair of disjoint edges are separated by some axis-parallel hyperplane. We prove a conjecture of Alon et al. [SIAM J. Discrete Math. 2015] by showing that every graph with maximum degree $\Delta$ has separation dimension less than $20\Delta$, which is best possible up to a constant factor. We also prove that graphs with separation dimension 3 have bounded average degree and bounded chromatic number, partially resolving open problems by Alon et al. [J. Graph Theory 2018]. Joint work with Alex Scott.