## SFU Discrete Math Seminar: David R. Wood

• Date: 03/10/2020
• Time: 13:30
Lecturer(s):
David R. Wood, Monash University
Location:

Simon Fraser University

Topic:

Graph and Poset Dimension Parameters

Description:

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.

Other Information:

SCK 9509