Separation dimension and sparsity

Noga Alon, Manu Basavaraju, L. Sunil Chandran, Rogers Mathew, Deepak RajendraprasadJournal of Graph Theory 2018 · DOI

Abstract

Abstract The separation dimension of a hypergraph G is the smallest natural number k for which the vertices of G can be embedded in so that any pair of disjoint edges in G can be separated by a hyperplane normal to one of the axes. Equivalently, it is the cardinality of a smallest family of total orders of , such that for any two disjoint edges of G , there exists at least one total order in in which all the vertices in one edge precede those in the other. Separation dimension is a monotone parameter; adding more edges cannot reduce the separation dimension of a hypergraph. In this article, we discuss the influence of separation dimension and edge‐density of a graph on one another. On one hand, we show that the maximum separation dimension of a k ‐degenerate graph on n vertices is and that there exists a family of 2‐degenerate graphs with separation dimension . On the other hand, we show that graphs with bounded separation dimension cannot be very dense. Quantitatively, we prove that n ‐vertex graphs with separation dimension s have at most edges. We do not believe that this bound is optimal and give a question and a remark on the optimal bound.
BibTeX
@article{alon2018separation,
  author = {Noga Alon and Manu Basavaraju and L. Sunil Chandran and Rogers Mathew and Deepak Rajendraprasad},
  title = {{Separation dimension and sparsity}},
  journal = {Journal of Graph Theory},
  year = {2018},
  doi = {10.1002/jgt.22236},
}

Loading related content...

Figure