





















We prove that the dimension of every poset whose comparability graph has maximum degree $Δ$ is at most $Δ\log^{1+o(1)} Δ$. This result improves on a 30-year old bound of Füredi and Kahn, and is within a $\log^{o(1)}Δ$ 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 $Δ$ has boxicity at most $Δ\log^{1+o(1)} Δ$, which is also within a $\log^{o(1)}Δ$ factor of optimal. We also show that the maximum boxicity of graphs with Euler genus $g$ is $Θ(\sqrt{g \log g})$, which solves an open problem of Esperet and Joret and is tight up to a $O(1)$ factor.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。