Lower bounds for boxicity

Adiga, A and Chandran, L S and Sivadasan, N (2014) Lower bounds for boxicity. Combinatorica, 34 (6). pp. 631-655. ISSN 0209-9683

Full text not available from this repository. (Request a copy)

Abstract

An axis-parallel b-dimensional box is a Cartesian product R1×-2×...×Rb where Ri is a closed interval of the form [ai; bi] on the real line. For a graph G, its boxicity box(G) is the minimum dimension b, such that G is representable as the intersection graph of boxes in b-dimensional space. Although boxicity was introduced in 1969 and studied extensively, there are no significant results on lower bounds for boxicity. In this paper, we develop two general methods for deriving lower bounds. Applying these methods we give several results, some of which are listed below: 1. The boxicity of a graph on n vertices with no universal vertices and minimum degree δ is at least n/2(n-δ-1). 2. Consider the G(n;p) model of random graphs. Let p ≤ 1 - 40logn/n2. Then with high probability, box(G) = Ω(np(1 - p)). On setting p = 1/2 we immediately infer that almost all graphs have boxicity Ω(n). Another consequence of this result is as follows: For any positive constant c < 1, almost all graphs on n vertices and(Formula presented.)edges have boxicity Ω(m/n). 3. Let G be a connected k-regular graph on n vertices. Let λ be the second largest eigenvalue in absolute value of the adjacency matrix of G. Then, the boxicity of G is at least (Formula presented.). 4. For any positive constant c < 1, almost all balanced bipartite graphs on 2n vertices and m≤cn2 edges have boxicity Ω(m/n).

[error in script]
IITH Creators:
IITH CreatorsORCiD
Sivadasan, NUNSPECIFIED
Item Type: Article
Additional Information: We thank Joel Friedman for personal communication regarding his proof of Alon's conjecture. We thank the anonymous reviewer for the useful com- ments which improved the results as well as the presentation of the paper and in particular for pointing out the approach of Remark 3.9.
Uncontrolled Keywords: 05C62, 05C80
Subjects: Computer science > Big Data Analytics
Divisions: Department of Computer Science & Engineering
Depositing User: Library Staff
Date Deposited: 16 Mar 2015 08:00
Last Modified: 16 Mar 2015 08:00
URI: http://raiith.iith.ac.in/id/eprint/1396
Publisher URL: http://dx.doi.org/10.1007/s00493-011-2981-0
OA policy: http://www.sherpa.ac.uk/romeo/issn/0209-9683/
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 1396 Statistics for this ePrint Item