Separation dimension and sparsity

No Thumbnail Available

Date

2018

Authors

Alon, N.
Basavaraju, M.
Chandran, L.S.
Mathew, R.
Rajendraprasad, D.

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

The separation dimension 𝜋?(G) of a hypergraph G is the smallest natural number k for which the vertices of G can be embedded in Rk 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 F of total orders of V(G), such that for any two disjoint edges of G, there exists at least one total order in F 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 O(k lg lg n) and that there exists a family of 2-degenerate graphs with separation dimension ?(lg lg n). 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 3(4 lg n)s?2 edges. We do not believe that this bound is optimal and give a question and a remark on the optimal bound. 2018 Wiley Periodicals, Inc.

Description

Keywords

Citation

Journal of Graph Theory, 2018, Vol.89, 1, pp.14-25

Endorsement

Review

Supplemented By

Referenced By