2012/12/30 by Manu Basavaraju, L. Sunil Chandran, Basavaraju, Manu +5 · 3 citations
Computer Science · Engineering · Mathematics · #05C62 #05C65 #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Mathematics and Applications #graph theory and CDMA systems #math.CO #msc:05C62 #msc:05C65
paper · pdf · doi:10.48550/arxiv.1212.6756
28 pages
arxiv created 2012/12/30 · openalex publication_date 2012/12/30 · arxiv updated 2013/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A family 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 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 π(H). Equivalently, π(H) is the smallest natural number k so that the vertices of H can be embedded in Rk 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.