Back to Search
Start Over
LOWER BOUNDS FOR BOXICITY
- Source :
- IndraStra Global.
- Publication Year :
- 2014
- Publisher :
- SPRINGER HEIDELBERG, 2014.
-
Abstract
- An axis-parallel $b$-dimensional box is a Cartesian product $R_1\times R_2\times...\times R_b$ where $R_i$ is a closed interval of the form $[a_i,b_i]$ on the real line. For a graph $G$, its \emph{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 $\delta$ is at least $n/2(n-\delta-1)$. (2) Consider the $\mathcal{G}(n,p)$ model of random graphs. Let $ p \le 1- \frac{40 \log n}{n^2}$. Then, for $G \in \mathcal{G}(n,p)$, almost surely $box(G)=\Omega(np(1-p))$. On setting $p=1/2$ we immediately infer that almost all graphs have boxicity $\Omega(n)$. (3) Spectral lower bounds for the boxicity of $k$-regular graphs. (4) The boxicity of random $k$-regular graphs on $n$ vertices (where $k$ is fixed) is $\Omega(k/\log k)$. (5) There exists a positive constant$c$ such that almost all balanced bipartite graphs on $2n$ vertices with exactly $m$ edges have boxicity at least $c m/n$, for $ m\le c' n^2/3$ for any positive constant $c' < 1$.<br />Comment: 20 pages
- Subjects :
- Random graph
Discrete mathematics
Mathematics::Combinatorics
Cartesian product
Intersection graph
Combinatorics
Computational Mathematics
symbols.namesake
Computer Science::Discrete Mathematics
Bipartite graph
symbols
FOS: Mathematics
Discrete Mathematics and Combinatorics
Mathematics - Combinatorics
Adjacency matrix
Combinatorics (math.CO)
Boxicity
Real line
Eigenvalues and eigenvectors
Computer Science & Automation
Mathematics
Subjects
Details
- Language :
- English
- ISSN :
- 23813652
- Database :
- OpenAIRE
- Journal :
- IndraStra Global
- Accession number :
- edsair.doi.dedup.....05e60aa3ef6585fee6dbdb8a3345c80e