TAU Combinatorics Seminar 2020/21

When: Sunday, October 18, 10am
Speaker: Raphy Yuster, University of Haifa
Title: Perfect and nearly perfect separation dimension of complete and random graphs


The separation dimension of a graph $G$ is the smallest natural number $d$ for which there is an embedding of $G$ into $\mathbb{R}^d$, such that any pair of disjoint edges is separated by some hyperplane normal to one of the axes. The perfect separation dimension further requires that any pair of disjoint edges is separated by the same amount of such hyperplanes. While it is known that the separation dimension of $K_n$ is $\Theta(\log n)$, the perfect separation dimension is much larger. We prove that:

1) The perfect separation dimension of $K_n$ is linear in $n$, up to a small polylogarithmic factor. In fact, it is at least $n/2-1$ and at most $n(\log n)^{1+o(1)}$.

2) For almost all graphs, the separation dimension is also linear in $n$, up to a logarithmic factor. This follows as a special case of a more general result showing that the perfect separation dimension of the random graph $G(n,p)$ is w.h.p. $\Omega(np/\log n)$ for a wide range of values of $p$, including all constant $p$.

3) Significantly relaxing perfection to just requiring that any pair of disjoint edges is separated the same number of times up to a difference of $c\log n$ for some absolute constant $c$, still requires the dimension for $K_n$ to be $\Omega(n)$. This is perhaps surprising as it is known that if we allow a difference of $7\log n$, then the dimension reduces to only $\Theta(\log n)$.