betaFeedback

WorksMathematics

New bounds on the boxicity of Kneser graphs

Abstract

For a graph G=(V,E)G=(V,E), the boxicity box⁡(G)\operatorname{box}(G) is the least integer dd such that GG is the intersection graph of axis-parallel boxes in Rd\mathbb{R}^d. The Kneser graph K(n,k)K(n,k) is the graph whose vertex set corresponds to the family of kk sized subsets of an nn 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 K(n,k)K(n,k). We first show that for k≥2k\ge 2 and n≥2k+1n\ge 2k+1, box⁡(K(n,k))≥n−2k\operatorname{box}(K(n,k))\ge n-2k, thereby improving the lower bounds of Caoduro and Lichev [Discrete Mathematics 346(5):113333 (2023)] when n≥3k+1n\geq 3k+1 and k≥3k\ge 3. 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 K(n,k)K(n,k). We also show that for k≥2k\ge 2, t≥1t\ge 1 and n=2k+tn=2k+t, box⁡(K(2k+t,k))≤O(t3log⁡(2k+t)).\operatorname{box}(K(2k+t,k)) \leq O( t^3\log(2k+t) ). In particular, for every t=t(k)≥1t=t(k)\ge1 with t3log⁡k=o(k)t^3\log k=o(k), box⁡(K(2k+t,k))=o(k)\operatorname{box}(K(2k+t,k))=o(k). This is the first upper bound on the boxicity of K(n,k)K(n,k) that is sublinear in nn. We also show that for large enough kk, box⁡(K(2k+1,k))≤3ln⁡(2k+1)ln⁡ln⁡(2k+1)\operatorname{box}(K(2k+1,k))\le \frac{3\ln (2k+1)}{\ln\ln (2k+1)}.

Introduction

In this paper all graphs are finite, simple and undirected. We will denote a graph GG defined on the vertex set VV and edge set EE as G=(V,E)G=(V,E).

For a graph G=(V,E)G=(V,E), the boxicity box⁡(G)\operatorname{box}(G) is the least integer dd such that GG is the intersection graph of axis-parallel boxes in Rd\mathbb{R}^{d}. If GG is a complete graph, we take box⁡(G)=0\operatorname{box}(G)=0 by convention.

For a graph GG, several bounds on box⁡(G)\operatorname{box}(G) have been established, notably in terms of its treewidth, vertex cover number, maximum degree, and degeneracy of GG [12, 8, 1]. Bounds have also been derived when GG 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 K(n,k)K(n,k) is the graph whose vertex set corresponds to the family of kk sized subsets of an nn 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 K(n,k)K(n,k) was initiated by Caoduro and Lichev [6] who showed that for n≥2k+1n \ge2k+1, box⁡(K(n,k))≤n−2\operatorname{box}(K(n,k)) \le n-2 and for n≥2k3−2k2+1n \ge2k^3-2k^2+1, box⁡(K(n,k))≥n−12(13k2−11k+16)\operatorname{box}(K(n,k)) \ge n-\frac{1}{2}(13k^2-11k+16). They also showed that box⁡(K(n,k))≥12(n−2k−2)\operatorname{box}(K(n,k)) \ge\frac{1}{2}(n-2k-2) for 2k+1≤n≤3k2k+1 \le n \le3k and box⁡(K(n,k))≥12(n−k−5)\operatorname{box}(K(n,k)) \ge\frac{1}{2}(n-k-5) for n≥3k+1n \ge3k+1. Later Caoduro and Sebő [7] showed that for n≥5n \ge5, box⁡(K(n,2))=n−2\operatorname{box}(K(n,2))=n-2 and conjectured whether for n≥2k+1n \ge2k+1, box⁡(K(n,k))=n−k\operatorname{box}(K(n,k))=n-k. This conjecture was refuted in [11] where the exact boxicity of K(7,3)K(7,3) was computationally shown to be 3.

The lower bound box⁡(K(n,k))≥n−12(13k2−11k+16)\operatorname{box}(K(n,k)) \ge n-\frac{1}{2}(13k^2-11k+16) for n≥2k3−2k2+1n \ge2k^3-2k^2+1 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 box⁡(K(n,k))\operatorname{box}(K(n,k)). 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 ℓ≥0\ell\ge0 and a collection of graphs {Gi=(V,Ei)}1≤i≤ℓ\{G_i=(V,E_i)\}_{1\le i\le\ell}, the graph ⋂1≤i≤ℓGi\bigcap_{1\le i\le\ell}G_i is the graph defined on VV as its set of vertices such that its edge set is ⋂1≤i≤ℓEi\bigcap_{1\le i\le\ell}E_i.

Definition 1.1 ([16]). Let G=(V,E)G=(V,E) be a graph and A\mathcal{A} be a class of graphs that contains the complete graph KnK_n and Kn∖eK_n\setminus e, for an edge ee, ∀n∈N\forall n\in\mathbb{N}. The intersection dimension of GG with respect to A\mathcal{A} (denoted as dim⁡A(G)\dim_{\mathcal{A}}(G)) is defined as follows:

dim⁡A(G)=min⁡{ℓ:∃ a collection of graphs {Gi∈A}1≤i≤ℓ such that G=⋂i=1ℓGi}.\dim_{\mathcal{A}}(G)=\min\left\{\ell:\exists\text{ a collection of graphs }\{G_i\in\mathcal{A}\}_{1\le i\le\ell}\text{ such that }G=\bigcap_{i=1}^{\ell}G_i\right\}.

If GG is a complete graph, we take dim⁡A(G)=0\dim_{\mathcal{A}}(G)=0 by convention.

Our first result optimally represents K(n,k)K(n,k) as the intersection of C4C_4-free graphs. Let C4F be the class of C4C_4-free graphs.

Theorem 1.2. For k≥2k\ge2 and n≥2k+1n\ge2k+1, dim⁡C4F(K(n,k))=n−2k\dim_{\mathrm{C4F}}(K(n,k))=n-2k.

This immediately gives us dim⁡A(K(n,k))≥n−2k\dim_{\mathcal{A}}(K(n,k))\ge n-2k when A\mathcal{A} is the class of chordal graphs, split graphs, threshold graphs or any other graph class that is C4C_4-free. In particular, this gives us a lower bound for boxicity.

Corollary 1.3. For k≥2k\ge2 and n≥2k+1n\ge2k+1, box⁡(K(n,k))≥n−2k\operatorname{box}(K(n,k))\ge n-2k.

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 K(n,k)K(n,k) (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 K(n,k)K(n,k) when nn is ‘close’ to 2k2k, thereby bringing us closer to determining the true behaviour of box⁡(K(n,k))\operatorname{box}(K(n,k)) in this regime. We do this by giving upper bounds for the intersection dimension of K(n,k)K(n,k) with respect to threshold graphs. Let TH be the class of threshold graphs.

Theorem 1.4. For k≥2k\ge2 and t≥1t\ge1, we have

box⁡(K(2k+t,k))≤dim⁡TH(K(2k+t,k))≤O(t3log⁡(2k+t)).\operatorname{box}(K(2k+t,k))\le\dim_{\mathrm{TH}}(K(2k+t,k))\le O(t^3\log(2k+t)).

In particular, for every t=t(k)≥1t=t(k)\ge1 with t3log⁡k=o(k)t^3\log k=o(k), box⁡(K(2k+t,k))≤dim⁡TH(K(2k+t,k))=o(k)\operatorname{box}(K(2k+t,k))\le\dim_{\mathrm{TH}}(K(2k+t,k))=o(k).

When n=2k+1n=2k+1, we can do much better.

Theorem 1.5. For k≥2k \ge2, box⁡(K(2k+1,k))≤dim⁡TH(K(2k+1,k))≤2min⁡{j:j!≥k}+2\operatorname{box}(K(2k+1,k)) \le\dim_{\mathrm{TH}}(K(2k+1,k)) \le2\min\{j:j! \ge k\}+2. In particular, for large enough kk, box⁡(K(2k+1,k))≤3ln⁡(2k+1)ln⁡ln⁡(2k+1)\operatorname{box}(K(2k+1,k)) \le\frac{3\ln(2k+1)}{\ln\ln(2k+1)}.

Let B(a,b;c)B(a,b;c) be the poset of height 2 consisting of the subsets of [c][c] of size aa and bb ordered by the set-inclusion relation. It was observed in Remark 4.11 of [6] that

box⁡(K(n,k))≥12dim⁡(B(k−1,n−k−1;n−1))−2≥12dim⁡(B(1,n−2k+1;n−k+1))−2.\operatorname{box}(K(n,k)) \ge\frac{1}{2}\dim(B(k-1,n-k-1;n-1))-2 \ge\frac{1}{2}\dim(B(1,n-2k+1;n-k+1))-2.

As result of Theorem 4.5 in [14], there is a positive constant cc such that

box⁡(K(2k+t,k))≥{c2t+1log⁡log⁡(k+t+1)−2if 1≤t≤log⁡log⁡(k+t+1)−log⁡log⁡log⁡(k+t+1)−1,c(t+1)2⋅log⁡(t+k+1)log⁡(t+1)−2if 1+log⁡log⁡(k+t+1)≤t≤1+2k+t+1.\operatorname{box}(K(2k+t,k)) \ge\begin{cases} c2^{t+1}\log\log(k+t+1)-2 & \text{if }1 \le t \le\log\log(k+t+1)-\log\log\log(k+t+1)-1, \\ c(t+1)^2\cdot\frac{\log(t+k+1)}{\log(t+1)}-2 & \text{if }1+\log\log(k+t+1) \le t \le1+2\sqrt{k+t+1}. \end{cases}

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 n−2n-2 bound given in [6] for the general case.

Preliminaries

We write G‾\overline{G} for the graph complement of GG. For a positive integer xx, we will use the notation [x][x] to indicate the set {1,2,…,x}\{1,2,\ldots,x\} with [0]=∅[0]=\varnothing. We will denote an interval graph and its interval representation by the same symbol when there is no confusion. For graphs GG and HH, we say that GG is HH-free if GG does not contain HH as an induced subgraph.

As alluded to earlier, box⁡(G)=dim⁡INT(G)\operatorname{box}(G)=\dim_{\mathrm{INT}}(G), where INT\mathrm{INT} 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 G=(V,E)G=(V,E) and {Gi=(V,Ei)}i∈[ℓ]\{G_i=(V,E_i)\}_{i\in[\ell]} for some ℓ≥0\ell\ge0, we have G=G1∩G2∩⋯∩GℓG=G_1\cap G_2\cap\cdots\cap G_\ell if and only if both the conditions below are satisfied.

  1. E⊆EiE \subseteq E_i for all i∈[ℓ]i\in[\ell], i.e., GiG_i is a supergraph of GG for all i∈[ℓ]i\in[\ell]. In other words, if uv∈Euv\in E then uv∈Eiuv\in E_i, ∀i∈[ℓ]\forall i\in[\ell].

  1. For distinct vertices u,v∈Vu,v\in V, if uv∉Euv\notin E then there exists a j∈[ℓ]j\in[\ell] such that uv∉Ejuv\notin E_j.

For graphs {Gi=(V,Ei)}i∈[ℓ]\{G_i=(V,E_i)\}_{i\in[\ell]} for some ℓ≥0\ell\ge0, we can also define ⋃i∈[ℓ]Gi\bigcup_{i\in[\ell]}G_i 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 G=(V,E)G=(V,E) be a graph and A\mathcal{A} be a class of graphs that contains the empty graph KnK_n and Kn∪eK_n\cup e, for an edge ee, ∀n∈N\forall n\in\mathbb{N}. The covering number of GG with respect to A\mathcal{A} (denoted as cov⁡A(G)\operatorname{cov}_{\mathcal{A}}(G)) is defined as follows:

cov⁡A(G)=min⁡{ℓ:∃ a collection of graphs {Gi∈A}i∈[ℓ] such that G=⋃i=1ℓGi}.\operatorname{cov}_{\mathcal{A}}(G)=\min\left\{\ell:\exists\text{ a collection of graphs }\{G_i\in\mathcal{A}\}_{i\in[\ell]}\text{ such that }G=\bigcup_{i=1}^{\ell}G_i\right\}.

If GG is an empty graph, we take cov⁡A(G)=0\operatorname{cov}_{\mathcal{A}}(G)=0 by convention.

It is clear that for a graph GG and graph class A\mathcal{A}, cov⁡A(G)=dim⁡co⁡−A(G‾)\operatorname{cov}_{\mathcal{A}}(G)=\operatorname{dim}_{\operatorname{co}-\mathcal{A}}(\overline{G}), where co⁡−A={H:H‾∈A}\operatorname{co}-\mathcal{A}=\{H:\overline{H}\in\mathcal{A}\}.

The following observation is useful and we state it without a proof.

Observation 2.2. Let A\mathcal{A} be closed under vertex deletion. Then for a graph GG and an induced subgraph HH of GG, dim⁡A(G)≥dim⁡A(H)\operatorname{dim}_{\mathcal{A}}(G)\geq\operatorname{dim}_{\mathcal{A}}(H).

Recall that we denote the class of threshold graphs as TH\mathrm{TH}. We formally define this class of graphs.

Definition 2.3. Let s∈R≥0s\in\mathbb{R}_{\geq0} and let VV be a finite set. Let w:V→R≥0w:V\to\mathbb{R}_{\geq0} be a function. We define Γ(s,w)\Gamma(s,w) to be the graph such that the vertex set of Γ(s,w)\Gamma(s,w) is VV and for distinct vertices u,v∈Vu,v\in V, uvuv is an edge in Γ(s,w)\Gamma(s,w) if and only if w(u)+w(v)≥sw(u)+w(v)\geq s. A graph G=(V,E)G=(V,E) is said to be a threshold graph if for some s∈R≥0s\in\mathbb{R}_{\geq0} and w:V→R≥0w:V\to\mathbb{R}_{\geq0}, GG is isomorphic to Γ(s,w)\Gamma(s,w). In such a case, Γ(s,w)\Gamma(s,w) is said to be a threshold representation of GG. For a threshold representation Γ(s,w)\Gamma(s,w) of GG, ss is called its threshold value, and ww is called its weight function. Note that we will always implicitly assume that the vertex set of Γ(s,w)\Gamma(s,w) is the same as the domain of ww.

Let ℓ≥0\ell\geq0. If for graphs GG and {Gi∈TH}i∈[ℓ]\{G_i\in\mathrm{TH}\}_{i\in[\ell]}, we have G=⋂i=1ℓGiG=\bigcap_{i=1}^{\ell}G_i, then we say that {Gi∈TH}i∈[ℓ]\{G_i\in\mathrm{TH}\}_{i\in[\ell]} is a TH-representation of GG.

It is known that TH⊂INT\mathrm{TH}\subset\mathrm{INT}. This leads us to the following observation.

Observation 2.4. For any graph GG, dim⁡TH(G)≥box⁡(G)\operatorname{dim}_{\mathrm{TH}}(G)\geq\operatorname{box}(G).

It is known that co⁡−TH=TH\operatorname{co}-\mathrm{TH}=\mathrm{TH}. This gives us the following observation.

Observation 2.5. For any graph GG, cov⁡TH(G)=dim⁡TH(G‾)\operatorname{cov}_{\mathrm{TH}}(G)=\operatorname{dim}_{\mathrm{TH}}(\overline{G}).

Kneser graphs as the intersection of C4C_4-free graphs

Throughout this section, we assume that n≥2k+1n\geq2k+1 and k≥2k\geq2. Let 2K2F2K_2\mathrm{F} denote the class of 2K22K_2-free graphs3. It is clear that 2K2F=co⁡−C4F2K_2\mathrm{F}=\operatorname{co}-C_4\mathrm{F}. In this section, we will prove Theorem 1.2 by showing that cov⁡2K2F(K(n,k)‾)=n−2k\operatorname{cov}_{2K_2\mathrm{F}}(\overline{K(n,k)})=n-2k.

Lemma 3.1. For n≥2k+1n\geq2k+1, cov⁡2K2F(K(n,k)‾)≤n−2k\operatorname{cov}_{2K_2\mathrm{F}}(\overline{K(n,k)})\leq n-2k.

Proof. We show a procedure to generate graphs {Gi}i∈[n−2k]\{G_i\}_{i\in[n-2k]} such that K(n,k)‾=⋃i∈[n−2k]Gi\overline{K(n,k)}=\bigcup_{i\in[n-2k]}G_i. For any edge {A,B}\{A,B\} in K(n,k)‾\overline{K(n,k)},

  • if (A∪B)∩[n−2k−1](A\cup B)\cap[n-2k-1] is non-empty, assign it to GjG_j, where j=min⁡((A∪B)∩[n−2k−1])j=\min((A\cup B)\cap[n-2k-1]);

  • if (A∪B)∩[n−2k−1](A\cup B)\cap[n-2k-1] is empty, assign it to Gn−2kG_{n-2k}.

This procedure ensures that K(n,k)‾=⋃i∈[n−2k]Gi\overline{K(n,k)}=\bigcup_{i\in[n-2k]}G_i. We will show that ∀i∈[n−2k]\forall i\in[n-2k], GiG_i is 2K22K_2-free. For i∈[n−2k−1]i\in[n-2k-1], let {A1,B1}\{A_1,B_1\} and {A2,B2}\{A_2,B_2\} be distinct edges in GiG_i. If A1,B1,A2A_1,B_1,A_2 and B2B_2 are not 4 distinct sets, then they cannot induce a 2K22K_2 in GiG_i. So assume they are distinct. Let X1∈{A1,B1}X_1\in\{A_1,B_1\} and X2∈{A2,B2}X_2\in\{A_2,B_2\} be two sets that contain ii. Then X1∩X2≠∅X_1\cap X_2\ne\varnothing because it contains ii. Moreover, i=min⁡((X1∪X2)∩[n−2k−1])i=\min((X_1\cup X_2)\cap[n-2k-1]). Therefore, there is an edge between X1X_1 and X2X_2 in GiG_i, and consequently {A1,B1,A2,B2}\{A_1,B_1,A_2,B_2\} does not induce a 2K22K_2.

Now suppose {A1,B1}\{A_1,B_1\} and {A2,B2}\{A_2,B_2\} are distinct edges in Gn−2kG_{n-2k}. If A1,B1,A2A_1,B_1,A_2 and B2B_2 are not 4 distinct sets, then they cannot induce a 2K22K_2 in Gn−2kG_{n-2k}. So assume they are distinct. The sets A1∪B1A_1 \cup B_1 and A2∪B2A_2 \cup B_2 cannot be disjoint because if they are, we would have ∣(A1∪B1)∪(A2∪B2)∣≥2k+2\lvert(A_1 \cup B_1) \cup(A_2 \cup B_2) \rvert\ge2k+2, contradicting the fact that there is no element from [n−2k−1][n-2k-1] in (A1∪B1)∪(A2∪B2)(A_1 \cup B_1) \cup(A_2 \cup B_2). Therefore, there are sets X1∈{A1,B1}X_1 \in\{A_1,B_1\} and X2∈{A2,B2}X_2 \in\{A_2,B_2\} such that X1∩X2≠∅X_1 \cap X_2 \ne\varnothing. Moreover, X1∪X2⊆[n]∖[n−2k−1]X_1 \cup X_2 \subseteq[n] \setminus[n-2k-1]. Therefore, X1X_1 and X2X_2 are adjacent in Gn−2kG_{n-2k}.

For a positive integer dd, we will denote by Sd−1S^{d-1}, the standard unit sphere in Rd\mathbb{R}^d. We will use the following generalization of a theorem by Lusternik, Schnirelman and Borsuk, which was proved in [13].

Theorem 3.2 ([13]). If Sd−1=C0∪C1∪C2∪⋯∪Cd−1S^{d-1}=C_0\cup C_1\cup C_2\cup\cdots\cup C_{d-1}, such that for every 0≤i≤d−10\le i\le d-1, CiC_i is open or closed, then there is a 0≤j≤d−10\le j\le d-1 such that CjC_j contains two antipodal points.

Lemma 3.3. There is an arrangement of any finite collection of points on the sphere Sd−1S^{d-1} so that no set of dd many points lies on an equator.

Proof. Take the unit vectors in the direction defined by (1,x,x2,…,xd−1)(1,x,x^2,\ldots,x^{d-1}). Any such point lying on a hyperplane, can be defined by a root of some polynomial of the form c0+c1x+c2x2+⋯+cd−1xd−1c_0+c_1x+c_2x^2+\cdots+c_{d-1}x^{d-1}. Since a polynomial of degree d−1d-1 can have at most d−1d-1 roots, there can be at most d−1d-1 such points on the hyperplane. Therefore, no set of dd 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 n≥2k+1n\ge2k+1, cov⁡2K2F(K(n,k)‾)≥n−2k\operatorname{cov}_{2K_2F}(\overline{K(n,k)})\ge n-2k.

Proof. For n=2k+1n=2k+1, the bound is trivially true. Therefore, assume that n≥2k+2n\ge2k+2. We show that any assignment of the edges of K(n,k)‾\overline{K(n,k)} to at most n−2k−1n-2k-1 many 2K22K_2-free graphs leads to a contradiction. Let G1,G2,…,Gn−2k−1G_1,G_2,\ldots,G_{n-2k-1} be a covering of the edges of K(n,k)‾\overline{K(n,k)} such that for i∈[n−2k−1]i\in[n-2k-1], GiG_i is a 2K22K_2-free graph.

By Lemma 3.3, there is a way to embed [n][n] into Sn−2k−1S^{n-2k-1} such that no n−2kn-2k points lie on an equator. Let ff be such an embedding. Any edge of K(n,k)‾\overline{K(n,k)} is defined by two sets which have a common intersection. Therefore, distinct kk-sets A,B∈([n]k)A,B\in\binom{[n]}{k} have an edge between them if and only if k+1≤∣A∪B∣≤2k−1k+1\le\lvert A\cup B\rvert\le2k-1.

For each v∈Sn−2k−1v\in S^{n-2k-1}, define Hv={x∈Sn−2k−1:⟨x,v⟩>0}H_v=\{x\in S^{n-2k-1}:\langle x,v\rangle>0\}, which is an open hemisphere. Define the sets C0,C1,C2,…,Cn−2k−1C_0,C_1,C_2,\ldots,C_{n-2k-1} as follows: for v∈Sn−2k−1v\in S^{n-2k-1}, if there is a collection of points T⊂f([n])∩HvT\subset f([n])\cap H_v, and sets AA and BB that satisfy k+1≤∣T∣≤2k−1k+1\le\lvert T\rvert\le2k-1 and T=f(A)∪f(B)T=f(A)\cup f(B), then for every ii for which GiG_i contains {A,B}\{A,B\} as an edge, put v∈Civ\in C_i. Note that a point v∈Sn−2k−1v\in S^{n-2k-1} may be put into several sets CiC_i. Define C0=Sn−2k−1∖⋃i∈[n−2k−1]CiC_0=S^{n-2k-1}\setminus\bigcup_{i\in[n-2k-1]}C_i. It is easy to see that for i∈[n−2k−1]i\in[n-2k-1], CiC_i is open and that C0C_0 is closed (it is the complement of a union of open sets). Therefore, we have Sn−2k−1=C0∪⋃i∈[n−2k−1]CiS^{n-2k-1}=C_0\cup\bigcup_{i\in[n-2k-1]}C_i. By Theorem 3.2, there is a 0≤j≤n−2k−10\le j\le n-2k-1 such that CjC_j contains two antipodal points x1x_1 and x2x_2.

Suppose j∈[n−2k−1]j\in[n-2k-1]. Then by definition of CjC_j, there exist sets T1⊂f([n])∩Hx1,T2⊂f([n])∩Hx2T_1\subset f([n])\cap H_{x_1},T_2\subset f([n])\cap H_{x_2} and edges {A1,B1}\{A_1,B_1\} and {A2,B2}\{A_2,B_2\} in GjG_j such that k+1≤∣T1∣,∣T2∣≤2k−1k+1\le\lvert T_1\rvert,\lvert T_2\rvert\le2k-1 and T1=f(A1)∪f(B1)T_1=f(A_1)\cup f(B_1) and T2=f(A2)∪f(B2)T_2=f(A_2)\cup f(B_2). Since, x1x_1 and x2x_2 are antipodal points, Hx1∩Hx2=∅H_{x_1}\cap H_{x_2}=\varnothing. Therefore, (A1∪B1)∩(A2∪B2)=∅(A_1\cup B_1)\cap(A_2\cup B_2)=\varnothing. It follows that {A1,B1},{A1,A2},{B1,B2}\{A_1,B_1\},\{A_1,A_2\},\{B_1,B_2\}, and {B1,A2}\{B_1,A_2\} do not exist as edges in K(n,k)‾\overline{K(n,k)}. Therefore, the edges {A1,B1}\{A_1,B_1\} and {A2,B2}\{A_2,B_2\} induce a 2K22K_2 in GjG_j. This is a contradiction. Therefore, we must have j=0j=0. But this means that ∣Hx1∩f([n])∣≤k\lvert H_{x_1}\cap f([n])\rvert\le k and ∣Hx2∩f([n])∣≤k\lvert H_{x_2}\cap f([n])\rvert\le k (because for any TT subset of k+1k+1 points of f([n])f([n]), we can find sets A,B∈([n]k)A,B\in\binom{[n]}{k} such that T=f(A)∪f(B)T=f(A)\cup f(B)). This means that the equator defined by the plane ⟨x,x1⟩=0\langle x,x_1\rangle=0 contains at least n−2kn-2k points. This contradicts the assumption on our embedding ff.

The proof of Theorem 1.2 follows from Lemma 3.1 and Lemma 3.4 and the fact that dim⁡C4F(K(n,k))=cov⁡2K2F(K(n,k)‾)\operatorname{dim}_{C_4F}(K(n,k))=\operatorname{cov}_{2K_2F}(\overline{K(n,k)}).

Corollary 1.3. For k≥2k\geq2 and n≥2k+1n\geq2k+1, box⁡(K(n,k))≥n−2k\operatorname{box}(K(n,k))\geq n-2k.

Proof. By Lemma 3.4 the number of 2K22K_2-free graphs needed to cover the edges of K(n,k)K(n,k) is at least n−2kn-2k. As a consequence, any covering of K(n,k)K(n,k) with at most n−2k−1n-2k-1 many co-interval graphs cannot be possible since co-interval graphs are also 2K22K_2-free graphs. Hence, it follows that box⁡(K(n,k))=dim⁡INT(K(n,k))=cov⁡co−INT(K(n,k)‾)≥n−2k\operatorname{box}(K(n,k))=\operatorname{dim}_{\mathrm{INT}}(K(n,k))=\operatorname{cov}_{\mathrm{co-INT}}(\overline{K(n,k)})\geq n-2k as claimed. □\square

Sublinear upper bounds on box⁡(K(n,k))\operatorname{box}(K(n,k)) when n≈2k+1n\approx2k+1

Recall that B(a,b;c)B(a,b;c) is the poset of height 22 consisting of the subsets of [c][c] of size aa and bb ordered by the set-inclusion relation.

Lemma 4.1. For n≥2k+1n\geq2k+1, dim⁡TH(K(n,k))≤dim⁡(B(k−1,n−k−1;n−1))+dim⁡TH(K(n−1,k))\operatorname{dim}_{\mathrm{TH}}(K(n,k))\leq\operatorname{dim}(B(k-1,n-k-1;n-1))+\operatorname{dim}_{\mathrm{TH}}(K(n-1,k)).

Proof. We will consider B0B_0 to be the subposet of B(k,n−k;n)B(k,n-k;n) obtained by only retaining sets that contain 11. It is clear that B0B_0 is order isomorphic to B(k−1,n−k−1;n−1)B(k-1,n-k-1;n-1). Let dim⁡(B0)=t1\operatorname{dim}(B_0)=t_1 and L={Li}i∈[t1]\mathcal{L}=\{L_i\}_{i\in[t_1]} be a realizer of size t1t_1 for B0B_0. For i∈[t1]i\in[t_1] and X∈B0X\in B_0 let pi(X)p_i(X) denote the position of XX in LiL_i.

For i∈[t1]i\in[t_1], let si=2(nk)s_i=2\binom{n}{k} and define the weight functions wi:([n]k)→Z≥0w_i:\binom{[n]}{k}\to\mathbb{Z}_{\geq0} as follows:

wi(Y)={(nk)+pi([n]∖Y),if Y does not contain 1,(nk)−pi(Y),if Y contains 1.w_i(Y)= \begin{cases} \binom{n}{k}+p_i([n]\setminus Y), & \text{if }Y\text{ does not contain }1,\\ \binom{n}{k}-p_i(Y), & \text{if }Y\text{ contains }1. \end{cases}

Let G0G_0 be the induced subgraph of K(n,k)K(n,k) obtained by removing all sets that contain 11. It is clear that G0≅K(n−1,k)G_0\cong K(n-1,k). Let dim⁡TH(G0)=t2\operatorname{dim}_{\mathrm{TH}}(G_0)=t_2 and {Γ(sj,wj′)}j∈[t2]\{ \Gamma(s_j,w'_j)\}_{j\in[t_2]} be the TH-representation of G0G_0. For every j∈[t2]j\in[t_2] and every Y∈([n]k)Y\in\binom{[n]}{k} let

wj(Y)={wj′(Y),if Y does not contain 1,sj,if Y contains 1.w_j(Y)= \begin{cases} w'_j(Y), & \text{if }Y\text{ does not contain }1,\\ s_j, & \text{if }Y\text{ contains }1. \end{cases}

We show that {Γ(si,wi)}i∈[t1+t2]\{\Gamma(s_i,w_i)\}_{i\in[t_1+t_2]} is a TH-representation of K(n,k)K(n,k). It is clear that the above graphs are super graphs of K(n,k)K(n,k). We consider the following three cases.

  • If Y1,Y2∈([n]k)Y_1,Y_2\in\binom{[n]}{k} be such that both of them contain 11, then they are not adjacent. Clearly for any i∈[t1]i\in[t_1], wi(Y1)+wi(Y2)=(nk)−pi(Y1)+(nk)−pi(Y2)<2(nk)w_i(Y_1)+w_i(Y_2)=\binom{n}{k}-p_i(Y_1)+\binom{n}{k}-p_i(Y_2)<2\binom{n}{k}.

  • If Y1,Y2∈([n]k)Y_1,Y_2\in\binom{[n]}{k} be such that both of them do not contain 11, then they are adjacent in K(n,k)K(n,k) if and only if they are adjacent in G0G_0. Clearly Y1,Y2Y_1,Y_2 are adjacent in G0G_0 if and only if ∀j∈[t2]\forall j\in[t_2], wj(Y1)+wj(Y2)=wj′(Y1)+wj′(Y2)≥sjw_j(Y_1)+w_j(Y_2)=w'_j(Y_1)+w'_j(Y_2)\geq s_j.

  • If Y1,Y2∈([n]k)Y_1,Y_2\in\binom{[n]}{k} be such Y1Y_1 contains 11 and Y2Y_2 does not contain 11, then they are adjacent if and only if Y1⊂[n]∖Y2Y_1\subset[n]\setminus Y_2, which holds if and only if ∀i∈[t1]\forall i\in[t_1], pi(Y1)<pi([n]∖Y2)p_i(Y_1)<p_i([n]\setminus Y_2) which in turn holds if and only if (nk)−pi(Y1)+(nk)+pi([n]∖Y2)≥2(nk)\binom{n}{k}-p_i(Y_1)+\binom{n}{k}+p_i([n]\setminus Y_2)\geq2\binom{n}{k}. Therefore, Y1Y_1 and Y2Y_2 are adjacent if and only if ∀i∈[t1]\forall i\in[t_1] wi(Y1)+wi(Y2)≥siw_i(Y_1)+w_i(Y_2)\geq s_i.

□\square

Note that the bound in Lemma 4.1 is tight up to a constant factor as dim⁡TH(K(n,k))≥dim⁡TH(K(n−1,k))\operatorname{dim}_{\mathrm{TH}}(K(n,k))\geq\operatorname{dim}_{\mathrm{TH}}(K(n-1,k)) and dim⁡TH(K(n,k))≥box⁡(K(n,k))≥12dim⁡(B(k−1,n−k−1;n−1))−2\operatorname{dim}_{\mathrm{TH}}(K(n,k))\geq\operatorname{box}(K(n,k))\geq\frac{1}{2}\operatorname{dim}(B(k-1,n-k-1;n-1))-2. Now we are ready for the proof of Theorem 1.4.

Theorem 1.4. For k≥2k \ge2 and t≥1t \ge1, we have

box⁡(K(2k+t,k))≤dim⁡TH(K(2k+t,k))≤O(t3log⁡(2k+t)).\operatorname{box}(K(2k+t,k)) \le\dim_{\mathrm{TH}}(K(2k+t,k)) \le O(t^{3}\log(2k+t)).

In particular, for every t=t(k)≥1t=t(k) \ge1 with t3log⁡k=o(k)t^{3}\log k=o(k), box⁡(K(2k+t,k))≤dim⁡TH(K(2k+t,k))=o(k)\operatorname{box}(K(2k+t,k)) \le\dim_{\mathrm{TH}}(K(2k+t,k))=o(k).

Proof. Let n=2k+tn=2k+t in the statement of Lemma 4.1. By Corollary 1.12 of [4], dim⁡(B(k−1,k+t−1;2k+t−1))≤O(t2log⁡(2k+t−1))\dim(B(k-1,k+t-1;2k+t-1)) \le O(t^{2}\log(2k+t-1)). Solving the resulting recursion gives dim⁡TH(K(2k+t,k))≤O(t3log⁡(2k+t))+dim⁡TH(K(2k,k))≤O(t3log⁡(2k+t))\dim_{\mathrm{TH}}(K(2k+t,k)) \le O(t^{3}\log(2k+t))+\dim_{\mathrm{TH}}(K(2k,k)) \le O(t^{3}\log(2k+t)) where the last inequality follows by observing that dim⁡TH(K(2k,k))≤2\dim_{\mathrm{TH}}(K(2k,k)) \le2 (the graph K(2k,k)K(2k,k) is a disjoint union of edges). The statement then follows by Observation 2.4.

Theorem 1.5. For k≥2k \ge2, box⁡(K(2k+1,k))≤dim⁡TH(K(2k+1,k))≤2min⁡{j:j!≥k}+2\operatorname{box}(K(2k+1,k)) \le\dim_{\mathrm{TH}}(K(2k+1,k)) \le2\min\{j:j! \ge k\}+2. In particular, for large enough kk, box⁡(K(2k+1,k))≤3ln⁡(2k+1)ln⁡ln⁡(2k+1)\operatorname{box}(K(2k+1,k)) \le\frac{3\ln(2k+1)}{\ln\ln(2k+1)}.

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. [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. [2]Abhijin Adiga, L. Sunil Chandran, and Naveen Sivadasan. Lower bounds for boxicity. Combinatorica, 34(6):631–655, 2014.
  3. [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. [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. [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. [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. [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. [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. [9]L. Sunil Chandran, Mathew C. Francis, and Rogers Mathew. Boxicity of leaf powers. Graphs and Combinatorics, 27(1):61–72, 2011.
  10. [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. [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. [12]L. Sunil Chandran and Naveen Sivadasan. Boxicity and treewidth. Journal of Combinatorial Theory, Series B, 97(5):733–744, 2007.DOI
  13. [13]Joshua E. Greene. A new short proof of Kneser’s conjecture. The American Mathematical Monthly, 109(10):918–920, 2002.DOI
  14. [14]Hal A. Kierstead. The dimension of two levels of the Boolean lattice. Discrete Mathematics, 201(1-3):141–155, 1999.DOI
  15. [15]Alexandr V. Kostochka. The dimension of neighboring levels of the Boolean lattice. Order, 14(3):267–268, 1997.DOI
  16. [16]Jan Kratochvíl and Zsolt Tuza. Intersection dimensions of graph classes. Graphs and Combinatorics, 10(2):159–168, 1994.DOI
  17. [17]L. Lovász. Kneser’s conjecture, chromatic number, and homotopy. Journal of Combinatorial Theory, Series A, 25(3):319–324, 1978.DOI
  18. [18]Carsten Thomassen. Interval representations of planar graphs. Journal of Combinatorial Theory, Series B, 40(1):9–20, 1986.DOI

Paper details

vlnc:W_cawxhm4e
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 6

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents