Browsing by Author "Rajendraprasad, D."

Now showing 1 - 4 of 4

Separation dimension and sparsity
(2018) Alon, N.; Basavaraju, M.; Chandran, L.S.; Mathew, R.; Rajendraprasad, D.
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.
Separation dimension and sparsity
(Wiley-Liss Inc. info@wiley.com, 2018) Alon, N.; Basavaraju, M.; Sunil Chandran, L.S.; Mathew, R.; Rajendraprasad, D.
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.
Separation Dimension of Graphs and Hypergraphs
(2016) Basavaraju, M.; Chandran, L.S.; Golumbic, M.C.; Mathew, R.; Rajendraprasad, D.
Separation dimension of a hypergraph H, denoted by ?( 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. In this paper, we study the separation dimension of hypergraphs and graphs. 2015, Springer Science+Business Media New York.
Separation Dimension of Graphs and Hypergraphs
(Springer New York LLC barbara.b.bertram@gsk.com, 2016) Basavaraju, M.; Sunil Chandran, L.S.; Golumbic, M.C.; Mathew, R.; Rajendraprasad, D.
Separation dimension of a hypergraph H, denoted by ?( 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. In this paper, we study the separation dimension of hypergraphs and graphs. © 2015, Springer Science+Business Media New York.