# Better bounds for poset dimension and boxicity

Scott, A
Wood

18 October 2019

## Journal:

Transactions of the American Mathematical Society

## Last Updated:

2020-10-23T18:55:59.88+01:00

## DOI:

10.1090/tran/7962

1-1

## abstract:

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 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 and is tight up to a constant factor.

1070387

Submitted

Journal Article