Perfect and nearly perfect separation dimension of complete and random graphs

DOI10.1002/JCD.21802arXiv2108.13662OpenAlexW3196968457MaRDI QIDQ6186984FDOQ6186984

Authors: Raphael Yuster 

Publication date: 5 February 2024

Published in: Journal of Combinatorial Designs (Search for Journal in Brave)

Abstract: The separation dimension of a hypergraph $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 (pairwise nonparallel) hyperplanes. While it is known that for any fixed $rge2$, the separation dimension of any $n$-vertex $r$-graph is $O(logn)$, the perfect separation dimension is much larger. In fact, no polynomial upper-bound for the perfect separation dimension of $r$-uniform hypergraphs is known. In our first result we essentially resolve the case $r=2$, i.e. graphs. We prove that the perfect separation dimension of $K_n$ is linear in $n$, up to a small polylogarithmic factor. In fact, we prove it is at least $n/2-1$ and at most $n(logn{)}^{1+o(1)}$. Our second result proves that the perfect separation dimension of almost all graphs 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/logn)$ for a wide range of values of $p$, including all constant $p$. Finally, we prove that significantly relaxing perfection to just requiring that any pair of disjoint edges of $K_n$ is separated the same number of times up to a difference of $clogn$ for some absolute constant $c$, still requires the dimension to be $Omega(n)$. This is perhaps surprising as it is known that if we allow a difference of $7lo{g}_{2}n$, then the dimension reduces to $O(logn)$.

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

Recommendations

• Separation dimension of graphs and hypergraphs
• Separation dimension and sparsity
• Separation dimension of bounded degree graphs
• Separation dimension and degree
• Boxicity and separation dimension

zbMATH Keywords

random graphcomplete graphseparation dimensionperfect separation

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph representations (geometric and intersection representations, etc.) (05C62) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• On the Shannon capacity of a graph
• The difference between consecutive primes. II
• Separation dimension of bounded degree graphs
• Boxicity of line graphs
• A note on scrambling permutations
• Scrambling permutations and entropy of hypergraphs
• Sequence covering arrays
• Minimal scrambling sets of simple orders
• Concerning a Certain Set of Arrangements
• Perturbed Identity Matrices Have High Rank: Proof and Applications
• Fractional and circular separation dimension of graphs
• Boxicity and separation dimension
• The induced separation dimension of a graph
• The minrank of random graphs over arbitrary fields
• The Minrank of Random Graphs
• On the minimum number of completely 3-scrambling permutations
• Separation dimension and sparsity
• Perfect sequence covering arrays
• Circular separation dimension of a subclass of planar graphs

This page was built for publication: Perfect and nearly perfect separation dimension of complete and random graphs

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