Lower bounds for boxicity (Q2341923)

An (axes-parallel) box is a direct product of intervals \([a_{1},b_{1}]\times [a_{2},b_{2}]\times \cdots \times [a_{k},b_{k}]\) in \(k\)-dimensional space. The boxicity \(\text{box }(G)\) of a graph \(G\) is the smallest \(k\) such that it can be represented as an intersection graph of boxes in \(k\)-dimensional space. Thus for example graphs with boxicity 1 are interval graphs. The paper under review addresses the question, rather neglected in previous literature, of finding lower bounds on boxicity of graphs. Amongst the results proved are the following: The boxicity of a graph on \(n\) vertices with minimum degree \(\delta\) and \(n_{u}\) `universal\'\, vertices (i.e., vertices adjacent to every other vertex) satisfies \[ \text{box }(G)\geq \frac{n-n_{u}}{2(n-\delta-1)}. \] For random graphs \(G(n,p(n))\) with \(p(n)\geq 1-40\log(n)/n^{2}\), we have \[ \mathbb{P}(\text{box }G(n,p(n))=\Omega(p(1-p)n))\geq 1-3/n^{2}. \] In particular, taking \(p=1/2\), almost every graph has boxicity \(\Omega(n)\). Suppose \(G\) is a \(k\)-regular graph on \(n\) vertices with \(\lambda\) being the modulus of the second largest (in modulus) eigenvalue of its adjacency matrix. Then, \[ \text{box }(G)\geq \frac{k^{2}}{\lambda^{2}\log \left(1+k^{2}/\lambda^{2}\right)}\frac{n-k-1}{2n}. \] So again, dense pseudo-random graphs with \(k=\Omega(n)\) and \(\lambda=O(\sqrt{n})\) have large boxicity. The proofs are based on isoperimetric properties of the graphs involved.