Boxicity and separation dimension
Deepak Rajendraprasad · 2016
A family $$\mathcal {F}$$ of permutations of the vertices of a hypergraph $$H$$ is called pairwise suitable for $$H$$ if, for every pair of disjoint edges in $$H$$ , there exists a permutation in $$\mathcal {F}$$ in which all the vertices in one edge precede those in the other. The cardinality of a smallest such family of permutations for $$H$$ is called the separation dimension of $$H$$ and is denoted by $$\pi (H)$$ . Equivalently, $$\pi (H)$$ is the smallest natural number $$k$$ so that the vertices of $$H$$ can be embedded in $$\mathbb {R}^k$$ such that any two disjoint edges of $$H$$ can be separated by a hyperplane normal to one of the axes. We show that the separation dimension of a hypergraph $$H$$ is equal to the boxicity of the line graph of $$H$$ . This connection helps us in borrowing results and techniques from the extensive literature on boxicity to study the concept of separation dimension.