Boxicity and separation dimension

DOI10.1007/978-3-319-12340-0_7zbMATH Open1345.05066arXiv1404.4486OpenAlexW2964277984MaRDI QIDQ2945181FDOQ2945181

Authors: Manu Basavaraju, L. Sunil Chandran, Rogers Mathew, Deepak Rajendraprasad, Martin Charles Golumbic 

Publication date: 9 September 2015

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Abstract: A family $mathcalF$ 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 $mathcalF$ 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.

Full work available at URL: https://arxiv.org/abs/1404.4486

Recommendations

• Separation dimension of graphs and hypergraphs
• Separation dimension and sparsity
• Separation dimension and degree
• Separation dimension of bounded degree graphs
• Dimensions of hypergraphs

zbMATH Keywords

line graphboxicityacyclic chromatic numberscrambling permutationseparation dimension

Mathematics Subject Classification ID

Hypergraphs (05C65) Graph operations (line graphs, products, etc.) (05C76)

Cited In (13)

• Box dimension of Neimark–Sacker bifurcation
• The induced separation dimension of a graph
• Separation dimension of graphs and hypergraphs
• Separation dimension and degree
• Fractional and circular separation dimension of graphs
• Lower bounds for boxicity
• Dimensions of hypergraphs
• Perfect and nearly perfect separation dimension of complete and random graphs
• Separation dimension of bounded degree graphs
• Induced separation dimension
• Covering small subgraphs of (hyper)tournaments with spanning acyclic subgraphs
• Sequence Covering Arrays and Linear Extensions
• Separation dimension and sparsity

This page was built for publication: Boxicity and separation dimension

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2945181)