WorksMathematics
New bounds on the boxicity of Kneser graphs
Abstract
For a graph , the boxicity is the least integer such that is the intersection graph of axis-parallel boxes in . The Kneser graph is the graph whose vertex set corresponds to the family of sized subsets of an sized ground set, and a pair of vertices are adjacent if and only if the corresponding sets are disjoint. In this short paper, we provide new bounds for the boxicity of . We first show that for and , , thereby improving the lower bounds of Caoduro and Lichev [Discrete Mathematics 346(5):113333 (2023)] when and . The proof of this result uses the topological method and follows a strategy similar to Greene's proof of the Kneser's conjecture on the chromatic number of . We also show that for , and , In particular, for every with , . This is the first upper bound on the boxicity of that is sublinear in . We also show that for large enough , .
Introduction
In this paper all graphs are finite, simple and undirected. We will denote a graph defined on the vertex set and edge set as .
For a graph , the boxicity is the least integer such that is the intersection graph of axis-parallel boxes in . If is a complete graph, we take by convention.
For a graph , several bounds on have been established, notably in terms of its treewidth, vertex cover number, maximum degree, and degeneracy of [12, 8, 1]. Bounds have also been derived when belongs to special classes of graphs like planar graphs, chordal graphs, AT-free graphs, and co-comparability graphs [18, 3, 9]. For more on boxicity of graphs, readers are referred to the recent survey [10].
The Kneser graph is the graph whose vertex set corresponds to the family of sized subsets of an sized ground set, and a pair of vertices are adjacent if and only if the corresponding sets are disjoint. The study of the boxicity of the Kneser graph was initiated by Caoduro and Lichev [6] who showed that for , and for , . They also showed that for and for . Later Caoduro and Sebő [7] showed that for , and conjectured whether for , . This conjecture was refuted in [11] where the exact boxicity of was computationally shown to be 3.
The lower bound for established in [6] is achieved by using ideas based on the vertex boundaries of a graph as developed in [2]. Despite its promise, a drawback of this method is that it often involves tedious computations of the vertex boundaries for each subset of vertices. Furthermore, it is a natural question to ask whether or not existing methods can be used to get better bounds for . We answer this question in the positive.
Our results
For ease of presentation, we state below the definition of ‘the intersection dimension’ of a graph, a notion introduced in [16]. For and a collection of graphs , the graph is the graph defined on as its set of vertices such that its edge set is .
Definition 1.1 ([16]). Let be a graph and be a class of graphs that contains the complete graph and , for an edge , . The intersection dimension of with respect to (denoted as ) is defined as follows:
If is a complete graph, we take by convention.
Our first result optimally represents as the intersection of -free graphs. Let C4F be the class of -free graphs.
Theorem 1.2. For and , .
This immediately gives us when is the class of chordal graphs, split graphs, threshold graphs or any other graph class that is -free. In particular, this gives us a lower bound for boxicity.
Corollary 1.3. For and , .
The proof of Theorem 1.2 uses a generalization of a theorem by Lusternik, Schnirelman and Borsuk developed by Greene [13] and bears close similarity to his simplified proof of the Kneser’s conjecture for the chromatic number of (the first proof of this conjecture was given by Lovász [17] and had been simplified once by Bárány [5] before Greene [13]). The strength of this method is illustrated in the clean and unconditional bound obtained, and also in its ease of presentation.
We also show the first upper bounds for the boxicity of when is ‘close’ to , thereby bringing us closer to determining the true behaviour of in this regime. We do this by giving upper bounds for the intersection dimension of with respect to threshold graphs. Let TH be the class of threshold graphs.
Theorem 1.4. For and , we have
In particular, for every with , .
When , we can do much better.
Theorem 1.5. For , . In particular, for large enough , .
Let be the poset of height 2 consisting of the subsets of of size and ordered by the set-inclusion relation. It was observed in Remark 4.11 of [6] that
As result of Theorem 4.5 in [14], there is a positive constant such that
Our upper bounds given in Theorems 1.4 and 1.5 complement the aforementioned lower bounds and are, in fact, the only non-trivial upper bounds for boxicity except for the bound given in [6] for the general case.
Preliminaries
We write for the graph complement of . For a positive integer , we will use the notation to indicate the set with . We will denote an interval graph and its interval representation by the same symbol when there is no confusion. For graphs and , we say that is -free if does not contain as an induced subgraph.
As alluded to earlier, , where is the class of interval graphs. We will use this formulation as the working definition for boxicity instead of the standard definition given earlier.
For ease of understanding of the proofs, we explicitly note down the two criteria that are required to be satisfied for a graph to be an intersection of graphs. For graphs and for some , we have if and only if both the conditions below are satisfied.
for all , i.e., is a supergraph of for all . In other words, if then , .
For distinct vertices , if then there exists a such that .
For graphs for some , we can also define analogously. There is a notion closely related to the intersection dimension of a graph, known as the covering number of the graph.
Definition 2.1 ([16]). Let be a graph and be a class of graphs that contains the empty graph and , for an edge , . The covering number of with respect to (denoted as ) is defined as follows:
If is an empty graph, we take by convention.
It is clear that for a graph and graph class , , where .
The following observation is useful and we state it without a proof.
Observation 2.2. Let be closed under vertex deletion. Then for a graph and an induced subgraph of , .
Recall that we denote the class of threshold graphs as . We formally define this class of graphs.
Definition 2.3. Let and let be a finite set. Let be a function. We define to be the graph such that the vertex set of is and for distinct vertices , is an edge in if and only if . A graph is said to be a threshold graph if for some and , is isomorphic to . In such a case, is said to be a threshold representation of . For a threshold representation of , is called its threshold value, and is called its weight function. Note that we will always implicitly assume that the vertex set of is the same as the domain of .
Let . If for graphs and , we have , then we say that is a TH-representation of .
It is known that . This leads us to the following observation.
Observation 2.4. For any graph , .
It is known that . This gives us the following observation.
Observation 2.5. For any graph , .
Kneser graphs as the intersection of -free graphs
Throughout this section, we assume that and . Let denote the class of -free graphs3. It is clear that . In this section, we will prove Theorem 1.2 by showing that .
Lemma 3.1. For , .
Proof. We show a procedure to generate graphs such that . For any edge in ,
if is non-empty, assign it to , where ;
if is empty, assign it to .
This procedure ensures that . We will show that , is -free. For , let and be distinct edges in . If and are not 4 distinct sets, then they cannot induce a in . So assume they are distinct. Let and be two sets that contain . Then because it contains . Moreover, . Therefore, there is an edge between and in , and consequently does not induce a .
Now suppose and are distinct edges in . If and are not 4 distinct sets, then they cannot induce a in . So assume they are distinct. The sets and cannot be disjoint because if they are, we would have , contradicting the fact that there is no element from in . Therefore, there are sets and such that . Moreover, . Therefore, and are adjacent in .
For a positive integer , we will denote by , the standard unit sphere in . We will use the following generalization of a theorem by Lusternik, Schnirelman and Borsuk, which was proved in [13].
Theorem 3.2 ([13]). If , such that for every , is open or closed, then there is a such that contains two antipodal points.
Lemma 3.3. There is an arrangement of any finite collection of points on the sphere so that no set of many points lies on an equator.
Proof. Take the unit vectors in the direction defined by . Any such point lying on a hyperplane, can be defined by a root of some polynomial of the form . Since a polynomial of degree can have at most roots, there can be at most such points on the hyperplane. Therefore, no set of points generated by this curve lies on an equator (an equator of the sphere is the intersection of the sphere with a hyperplane that passes through the origin).
Lemma 3.4. For , .
Proof. For , the bound is trivially true. Therefore, assume that . We show that any assignment of the edges of to at most many -free graphs leads to a contradiction. Let be a covering of the edges of such that for , is a -free graph.
By Lemma 3.3, there is a way to embed into such that no points lie on an equator. Let be such an embedding. Any edge of is defined by two sets which have a common intersection. Therefore, distinct -sets have an edge between them if and only if .
For each , define , which is an open hemisphere. Define the sets as follows: for , if there is a collection of points , and sets and that satisfy and , then for every for which contains as an edge, put . Note that a point may be put into several sets . Define . It is easy to see that for , is open and that is closed (it is the complement of a union of open sets). Therefore, we have . By Theorem 3.2, there is a such that contains two antipodal points and .
Suppose . Then by definition of , there exist sets and edges and in such that and and . Since, and are antipodal points, . Therefore, . It follows that , and do not exist as edges in . Therefore, the edges and induce a in . This is a contradiction. Therefore, we must have . But this means that and (because for any subset of points of , we can find sets such that ). This means that the equator defined by the plane contains at least points. This contradicts the assumption on our embedding .
The proof of Theorem 1.2 follows from Lemma 3.1 and Lemma 3.4 and the fact that .
Corollary 1.3. For and , .
Proof. By Lemma 3.4 the number of -free graphs needed to cover the edges of is at least . As a consequence, any covering of with at most many co-interval graphs cannot be possible since co-interval graphs are also -free graphs. Hence, it follows that as claimed.
Sublinear upper bounds on when
Recall that is the poset of height consisting of the subsets of of size and ordered by the set-inclusion relation.
Lemma 4.1. For , .
Proof. We will consider to be the subposet of obtained by only retaining sets that contain . It is clear that is order isomorphic to . Let and be a realizer of size for . For and let denote the position of in .
For , let and define the weight functions as follows:
Let be the induced subgraph of obtained by removing all sets that contain . It is clear that . Let and be the TH-representation of . For every and every let
We show that is a TH-representation of . It is clear that the above graphs are super graphs of . We consider the following three cases.
If be such that both of them contain , then they are not adjacent. Clearly for any , .
If be such that both of them do not contain , then they are adjacent in if and only if they are adjacent in . Clearly are adjacent in if and only if , .
If be such contains and does not contain , then they are adjacent if and only if , which holds if and only if , which in turn holds if and only if . Therefore, and are adjacent if and only if .
Note that the bound in Lemma 4.1 is tight up to a constant factor as and . Now we are ready for the proof of Theorem 1.4.
Theorem 1.4. For and , we have
In particular, for every with , .
Proof. Let in the statement of Lemma 4.1. By Corollary 1.12 of [4], . Solving the resulting recursion gives where the last inequality follows by observing that (the graph is a disjoint union of edges). The statement then follows by Observation 2.4.
Theorem 1.5. For , . In particular, for large enough , .
Proof. The proof of this follows exactly as the proof of Theorem 1.4, except that we use Theorem 1 of [15] instead of Corollary 1.12 of [4].
Declaration of AI use: AI tools were not used to write this paper, and all the proofs are due to the authors.
Acknowledgement: The authors thank Rishikesh Gajjala for the fruitful discussions during the initial stages of this work.
References
- [1]Abhijin Adiga, L. Sunil Chandran, and Rogers Mathew. Cubicity, degeneracy, and crossing number. European Journal of Combinatorics, 35:2–12, 2014. Selected Papers of EuroComb’11.
- [2]Abhijin Adiga, L. Sunil Chandran, and Naveen Sivadasan. Lower bounds for boxicity. Combinatorica, 34(6):631–655, 2014.
- [3]Diptendu Bhowmick and L. Sunil Chandran. Boxicity and cubicity of asteroidal triple free graphs. Discrete Mathematics, 310(10-11):1536–1543, 2010.arxiv.org/abs/0812.0894
- [4]Graham R. Brightwell, Henry A. Kierstead, Alexandr V. Kostochka, and William T. Trotter. The dimension of suborders of the Boolean lattice. Order, 11(2):127–134, 1994.DOI
- [5]J. Bárány. A short proof of Kneser’s conjecture. Journal of Combinatorial Theory, Series A, 25(3):325–326, 1978.DOI
- [6]Marco Caoduro and Lyuben Lichev. On the boxicity of Kneser graphs and complements of line graphs. Discrete Mathematics, 346(5):113333, 2023.arxiv.org/abs/2105.02516
- [7]Marco Caoduro and András Sebő. Boxicity and interval-orders: Petersen and the complements of line graphs. In International Symposium on Graph Drawing and Network Visualization, pages 283–295. Springer, 2023.arxiv.org/abs/2309.02062
- [8]L. Sunil Chandran, Anita Das, and Chintan D. Shah. Cubicity, boxicity, and vertex cover. Discrete Mathematics, 309(8):2488–2496, 2009.arxiv.org/abs/0712.2688
- [9]L. Sunil Chandran, Mathew C. Francis, and Rogers Mathew. Boxicity of leaf powers. Graphs and Combinatorics, 27(1):61–72, 2011.
- [10]L. Sunil Chandran, Mathew C. Francis, and Suraj Kumar Sahoo. A survey on the boxicity and cubicity of graphs. Indian Journal of Pure and Applied Mathematics, 57(1):4–38, 2026.DOI
- [11]L. Sunil Chandran, Rishikesh Gajjala, Suraj Kumar Sahoo, and Aatman Supkar. Geometric graph representations via compact SAT encodings. arXiv preprint arXiv:2610.22241, 2026.arxiv.org/abs/2610.22241
- [12]L. Sunil Chandran and Naveen Sivadasan. Boxicity and treewidth. Journal of Combinatorial Theory, Series B, 97(5):733–744, 2007.DOI
- [13]Joshua E. Greene. A new short proof of Kneser’s conjecture. The American Mathematical Monthly, 109(10):918–920, 2002.DOI
- [14]Hal A. Kierstead. The dimension of two levels of the Boolean lattice. Discrete Mathematics, 201(1-3):141–155, 1999.DOI
- [15]Alexandr V. Kostochka. The dimension of neighboring levels of the Boolean lattice. Order, 14(3):267–268, 1997.DOI
- [16]Jan Kratochvíl and Zsolt Tuza. Intersection dimensions of graph classes. Graphs and Combinatorics, 10(2):159–168, 1994.DOI
- [17]L. Lovász. Kneser’s conjecture, chromatic number, and homotopy. Journal of Combinatorial Theory, Series A, 25(3):319–324, 1978.DOI
- [18]Carsten Thomassen. Interval representations of planar graphs. Journal of Combinatorial Theory, Series B, 40(1):9–20, 1986.DOI