Introduction
All graphs in this paper are finite, simple and undirected. A d d d -dimensional box representation of a graph is a function f f f that maps the vertices of the graph to axis-parallel boxes in R d \mathbb{R}^{d} R d , such that two distinct vertices u u u and v v v in the graph are adjacent if and only if f ( u ) ∩ f ( v ) ≠ ∅ f(u)\cap f(v)\ne\varnothing f ( u ) ∩ f ( v ) = ∅ .
Definition 1.1. The boxicity of a graph Γ \Gamma Γ , denoted as box ( Γ ) \operatorname{box}(\Gamma) box ( Γ ) , is the minimum d ≥ 0 d\ge0 d ≥ 0 such that there is a d d d -dimensional box representation of $\Gamma.
By convention, we assume that a complete graph has boxicity 0. Note that interval graphs are precisely the graphs that have boxicity at most 1.
The notion of boxicity was introduced by Roberts [34 ] , who showed that any graph on n n n vertices has a ⌊ n / 2 ⌋ \lfloor n/2\rfloor ⌊ n /2 ⌋ -dimensional box representation. Boxicity has found applications in areas such as ecology [35 ] and operations research [33 ] .
The boxicity of several important graph classes has been studied. It is known that boxicity can be arbitrarily large even for restrictive classes like chordal bipartite graphs [18 ] , split graphs [23 ] , line graphs [4 , 20 ] and strongly chordal graphs [19 ] . On the other hand, it is known that planar graphs and strictly chordal graphs have boxicity at most 3 [19 , 44 ] and that planar bipartite graphs and outerplanar graphs have boxicity at most 2 [27 , 38 ] . The boxicity of asteroidal triple-free graphs, circular arc graphs, Kneser graphs and the complement of line graphs has also been studied [7 , 8 , 10 , 12 ] . For more on the boxicity of graphs, the reader may refer to [21 ] .
Adiga, Bhowmick, and Chandran [3 ] have examined the relationship between poset dimension, an order-theoretic concept, and boxicity, prompting investigations into boxicity within subclasses of comparability graphs and poset dimensions in the corresponding partial orders [14 , 22 ] . Recently, Chandran and Ghosh [15 ] studied the boxicity of an algebraically defined subclass of comparability graphs, called power graphs . Outside of power graphs, the only other study of the boxicity of an algebraically defined graph class has been that of zero-divisor graphs. [11 , 16 , 17 , 28 ] .
The power graph of a finite group G G G , denoted as Pow ( G ) \operatorname{Pow}(G) Pow ( G ) , is a graph defined on the group G G G such that two group elements are adjacent in Pow ( G ) \operatorname{Pow}(G) Pow ( G ) if and only if one is the power of the other. Power graphs were introduced by Chakrabarty, Ghosh and Sen [13 ] . For more on power graphs, the readers may refer to [2 , 29 ] .
Chandran and Ghosh [15 ] studied Pow ( G ) \operatorname{Pow}(G) Pow ( G ) when G G G is a cyclic group. They showed the following.
Theorem 1.2 ([15 ] ). Let 1 ≤ m 1 ≤ m 2 ≤ … ≤ m d 1 \le m_1 \le m_2 \le\ldots\le m_d 1 ≤ m 1 ≤ m 2 ≤ … ≤ m d be positive integers and d ≥ 2 d \ge2 d ≥ 2 . Let n = p 1 m 1 p 2 m 2 ⋯ p d m d n = p_1^{m_1}p_2^{m_2}\cdots p_d^{m_d} n = p 1 m 1 p 2 m 2 ⋯ p d m d , where p 1 , p 2 , … , p d p_1,p_2,\ldots,p_d p 1 , p 2 , … , p d are pairwise distinct primes. Then
(a) box ( Pow ( Z n ) ) ≤ m 1 + m 2 + ⋯ + m d − 1 \operatorname{box}(\operatorname{Pow}(\mathbb{Z}_n)) \le m_1 + m_2 + \cdots+ m_{d-1} box ( Pow ( Z n )) ≤ m 1 + m 2 + ⋯ + m d − 1 .
(b) When d d d is odd, box ( Pow ( Z n ) ) ≥ ∑ 1 ≤ j ≤ d − 1 2 m 2 j − 1 + m d − 1 \operatorname{box}(\operatorname{Pow}(\mathbb{Z}_n)) \ge\sum_{1 \le j \le\frac{d-1}{2}} m_{2j-1} + m_{d-1} box ( Pow ( Z n )) ≥ ∑ 1 ≤ j ≤ 2 d − 1 m 2 j − 1 + m d − 1 .
(c) When d d d is even, box ( Pow ( Z n ) ) ≥ ∑ 1 ≤ j ≤ d − 2 2 m 2 j + m d − 1 \operatorname{box}(\operatorname{Pow}(\mathbb{Z}_n)) \ge\sum_{1 \le j \le\frac{d-2}{2}} m_{2j} + m_{d-1} box ( Pow ( Z n )) ≥ ∑ 1 ≤ j ≤ 2 d − 2 m 2 j + m d − 1 .
Moreover, in [15 ] , an open question was posed: ”What is the exact value of the boxicity of the power graph of the cyclic group?” In this paper, we address this question. Additionally, the inquiry regarding the boxicity of power graphs of arbitrary groups was raised in [15 ] . We provide a partial answer by determining the exact boxicity of the power graph associated with a finite nilpotent group.
Our Results
Exact boxicity of the power graph of a cyclic group
Chandran and Ghosh [15 ] posed the question of determining the exact boxicity of power graphs of finite cyclic groups. In this paper, we address this question by establishing a lower bound for the boxicity that matches the upper bound provided in Theorem 1.2 . We prove the following:
Theorem 1.3. Let n = p 1 m 1 p 2 m 2 ⋯ p d m d n = p_1^{m_1}p_2^{m_2}\cdots p_d^{m_d} n = p 1 m 1 p 2 m 2 ⋯ p d m d , where p 1 , p 2 , … , p d p_1,p_2,\ldots,p_d p 1 , p 2 , … , p d are pairwise distinct primes and d ≥ 2 d \ge2 d ≥ 2 . Then box ( Pow ( Z n ) ) = ∑ i = 1 d m i − max i ∈ [ d ] m i \operatorname{box}(\operatorname{Pow}(\mathbb{Z}_n)) = \sum_{i=1}^{d} m_i - \max_{i \in[d]} m_i box ( Pow ( Z n )) = ∑ i = 1 d m i − max i ∈ [ d ] m i .
Exact boxicity of the power graph of a nilpotent group
Our second result is the exact boxicity of the power graph of any nilpotent group (Theorem 1.5 ). To state the result, we need to give a few notations and definitions. Let G G G be a finite nilpotent group. It is well known that the Sylow subgroups of G G G are normal and that G G G can be written as a direct product of its Sylow subgroups, i.e,
G = ∏ p is a prime factor of ∣ G ∣ S p , (1) G = \prod_{\substack{p\text{ is a prime factor of }|G|}} S_p, \tag*{(1)} G = p is a prime factor of ∣ G ∣ ∏ S p , (1)
where S p S_p S p is the Sylow p p p -subgroup of G G G .
Let s ( G ) = { p : S p is noncyclic } s(G)=\{p:S_p\text{ is noncyclic}\} s ( G ) = { p : S p is noncyclic } and t ( G ) = { p odd : S p is noncyclic } t(G)=\{p\text{ odd}:S_p\text{ is noncyclic}\} t ( G ) = { p odd : S p is noncyclic } . Note that, when ∣ G ∣ |G| ∣ G ∣ is odd, we have t ( G ) = s ( G ) t(G)=s(G) t ( G ) = s ( G ) .
For a finite group H H H , we define the function exp ( H ) \operatorname{exp}(H) exp ( H ) to be the exponent of H H H , i.e., the smallest positive integer k k k such that h k = e h^k=e h k = e , for every h ∈ H h\in H h ∈ H . We write C ( H ) C(H) C ( H ) to denote the poset of cyclic subgroups of a finite group H H H , ordered by inclusion. If H H H is a p p p -group, then the cover graph of C ( H ) C(H) C ( H ) is a rooted tree whose root is the trivial subgroup. We prove this later in Lemma 5.2 . We need the following definition to state our results.
Definition 1.4. Let T T T be a finite rooted tree poset (see Definition 2.1 ). For u ∈ T u\in T u ∈ T , let depth ( u ) \operatorname{depth}(u) depth ( u ) be the distance of u u u from the root in the cover graph of T T T . For k ≥ 2 k\ge2 k ≥ 2 , define h k ( T ) = max { depth ( u ) : u has k pairwise incomparable strict descendants in T } h_k(T)=\max\{\operatorname{depth}(u):u\text{ has }k\text{ pairwise incomparable strict descendants in }T\} h k ( T ) = max { depth ( u ) : u has k pairwise incomparable strict descendants in T } . The maximum of the empty set is − ∞ -\infty − ∞ . For a p p p -group H H H , we write h k ( H ) = h k ( C ( H ) ) h_k(H)=h_k(C(H)) h k ( H ) = h k ( C ( H )) .
The descendants in this definition need not cover u u u . The following theorem is our second main result.
Theorem 1.5. Let G G G be a finite nilpotent group as expressed in Equation (1) . Let n = exp ( G ) n=\operatorname{exp}(G) n = exp ( G ) .
(i) If S 2 S_2 S 2 is absent or cyclic, then box ( Pow ( G ) ) = box ( Pow ( Z n ) ) + t ( G ) \operatorname{box}(\operatorname{Pow}(G))=\operatorname{box}(\operatorname{Pow}(\mathbb{Z}_n))+t(G) box ( Pow ( G )) = box ( Pow ( Z n )) + t ( G ) .
(ii) Suppose S 2 S_2 S 2 is noncyclic and the odd part of G G G is nontrivial. Let exp ( S p ) = p e p \operatorname{exp}(S_p)=p^{e_p} exp ( S p ) = p e p , a = e 2 a=e_2 a = e 2 , m = max p ≠ 2 e p m=\max_{p\ne2}e_p m = max p = 2 e p , q = min { a , m } q=\min\{a,m\} q = min { a , m } . Then
box ( Pow ( G ) ) = { box ( Pow ( Z n ) ) + t ( G ) + 1 , h 3 ( S 2 ) ≥ q − 1 , box ( Pow ( Z n ) ) + t ( G ) , h 3 ( S 2 ) ≤ q − 2. \operatorname{box}(\operatorname{Pow}(G))=
\begin{cases}
\operatorname{box}(\operatorname{Pow}(\mathbb{Z}_n))+t(G)+1, & h_3(S_2)\ge q-1,\\
\operatorname{box}(\operatorname{Pow}(\mathbb{Z}_n))+t(G), & h_3(S_2)\le q-2.
\end{cases} box ( Pow ( G )) = { box ( Pow ( Z n )) + t ( G ) + 1 , box ( Pow ( Z n )) + t ( G ) , h 3 ( S 2 ) ≥ q − 1 , h 3 ( S 2 ) ≤ q − 2. (iii) If G = S p G=S_p G = S p is a noncyclic p p p -group, then box ( Pow ( G ) ) = 1 \operatorname{box}(\operatorname{Pow}(G))=1 box ( Pow ( G )) = 1 .
Because h 3 ( S 2 ) h_3(S_2) h 3 ( S 2 ) is an integer or − ∞ -\infty − ∞ , the alternatives in Theorem 1.5 exhaust all cases.
Overview of the methods used: To achieve the results, we have combined order-theoretic, geometric, topological, and group-theoretic arguments. We first replace the power graph by the comparability graph of the poset of cyclic subgroups, preserving boxicity. For a finite nilpotent group, the Sylow subgroup decomposition expresses this poset as a product of rooted tree posets, whose heights are determined by the exponents of the Sylow subgroups of the nilpotent group. Explicit interval constructions provide upper bounds for adding chain factors and replacing chains by rooted tree posets.
For the lower bounds, we use topological concepts, in particular a combination of the Van Kampen obstruction and Tancer’s nonrepresentability theorem with the 2-Helly property of axis-parallel boxes. This yields a boxicity obstruction for comparability graphs of certain kinds of product posets. In particular, we determine the exact boxicity of the Boolean lattice and thereby settle the cyclic case. For more general products, we select layers that form an induced graph join and use the additivity of boxicity under joins. Group-theoretic arguments provide special subgroup structures in the corresponding poset of cyclic subgroups, particularly terminal ternary forks in each noncyclic odd Sylow factor.
Organisation of the paper
In Section 2, we write the necessary preliminaries on posets, groups, and boxicity. In Section 3, we establish the topological obstruction used for our lower bounds, after providing the necessary background. Section 4 develops bounds for comparability graphs of product posets and determines the exact values for mixed products of chains and stars. Further, we apply these tools to finite cyclic groups in Section 5.2 and to nilpotent groups in Section 5. Appendix A gives an alternative combinatorial proof of the Boolean-lattice result, while Appendix B contains an omitted proof.
Preliminaries
Definitions on Posets
A chain is a poset where all elements are pairwise comparable. We denote a chain of length e e e as C e = { 0 < 1 < 2 < ⋯ < e } C_e = \{0 < 1 < 2 < \cdots< e\} C e = { 0 < 1 < 2 < ⋯ < e } .
Definition 2.1. A rooted tree poset is a finite poset ( T , ≤ ) (T, \le) ( T , ≤ ) with a unique minimum element ρ \rho ρ , called its root , such that, for every v ∈ T v \in T v ∈ T , the set { u ∈ T : u < v } \{u \in T : u < v\} { u ∈ T : u < v } is a chain. So, ρ ≤ v \rho\le v ρ ≤ v for all v ∈ T v \in T v ∈ T . The depth of a node v v v is defined by depth ( v ) = ∣ { u ∈ T : u < v } ∣ \operatorname{depth}(v) = |\{u \in T : u < v\}| depth ( v ) = ∣ { u ∈ T : u < v } ∣ , i.e., the distance of v v v from the root ρ \rho ρ in the cover graph of T T T .
The height of a rooted tree poset T T T is the maximum length of the path from the root to a node, or the length of an induced longest chain in T T T . For two elements u , v ∈ T u, v \in T u , v ∈ T , if u ≤ v u \le v u ≤ v , then we say that u u u is an ancestor of v v v and v v v is a descendant of u u u . A strict descendant (or, ancestor ) of u u u is an element v v v satisfying u < v u < v u < v (or, v < u v < u v < u ). An immediate descendant of u u u is an element v v v satisfying u < v u < v u < v and there is no w w w such that u < w < v u < w < v u < w < v . The notion of immediate ancestor of an element in the rooted tree poset T T T should be clear. Maximal members (if any) of a rooted tree are called leaves , and maximal chains as induced subposets are called branches . Note that the cover graph of a rooted tree poset T T T is a tree. Every non-root element in T T T has a unique immediate ancestor.
We define a star poset as a rooted tree poset when the cover graph is a star. In this paper, we use S S S to denote the four-element star poset consisting of a root element ρ \rho ρ and three leaves a 1 , a 2 , a 3 a_1,a_2,a_3 a 1 , a 2 , a 3 , where the relations in the poset are given by ρ < a j \rho< a_j ρ < a j , j = 1 , 2 , 3 j = 1,2,3 j = 1 , 2 , 3 , with the leaves pairwise incomparable.
A broom of height e ≥ 1 e \ge1 e ≥ 1 is a rooted tree poset with elements c 0 , … , c e − 1 , x 1 , x 2 , x 3 c_0, \ldots, c_{e-1}, x_1, x_2, x_3 c 0 , … , c e − 1 , x 1 , x 2 , x 3 , whose order is determined by c 0 < c 1 < ⋯ < c e − 1 < x i c_0 < c_1 < \cdots< c_{e-1} < x_i c 0 < c 1 < ⋯ < c e − 1 < x i for i ∈ { 1 , 2 , 3 } i \in\{1,2,3\} i ∈ { 1 , 2 , 3 } with x 1 , x 2 , x 3 x_1,x_2,x_3 x 1 , x 2 , x 3 pairwise incomparable.
For k ≥ 2 k \ge2 k ≥ 2 , an element u u u of a poset P P P is said to have a k k k -ary fork if u u u has k k k pairwise incomparable strict descendants in P P P .
A poset P P P is called the product poset of two posets ( P 1 , ≤ 1 ) (P_1,\le_1) ( P 1 , ≤ 1 ) and ( P 2 , ≤ 2 ) (P_2,\le_2) ( P 2 , ≤ 2 ) , if P = P 1 × P 2 P = P_1 \times P_2 P = P 1 × P 2 and ∀ ( x 1 , x 2 ) , ( y 1 , y 2 ) ∈ P \forall(x_1,x_2),(y_1,y_2) \in P ∀ ( x 1 , x 2 ) , ( y 1 , y 2 ) ∈ P , we have ( x 1 , x 2 ) ≤ ( y 1 , y 2 ) ⟺ x 1 ≤ 1 y 1 (x_1,x_2) \le(y_1,y_2) \Longleftrightarrow x_1 \le_1 y_1 ( x 1 , x 2 ) ≤ ( y 1 , y 2 ) ⟺ x 1 ≤ 1 y 1 and x 2 ≤ 2 y 2 x_2 \le_2 y_2 x 2 ≤ 2 y 2 . The comparability graph Comp ( P ) \operatorname{Comp}(P) Comp ( P ) of a poset ( P , ≤ ) (P,\le) ( P , ≤ ) is a simple undirected graph with vertex set P P P ; two distinct vertices x x x and y y y are adjacent in Comp ( P ) \operatorname{Comp}(P) Comp ( P ) if and only if x x x and y y y are comparable in ( P , ≤ ) (P,\le) ( P , ≤ ) , i.e., x ≤ y x \le y x ≤ y , or y ≤ x y \le x y ≤ x .
Basics on Group Theory and Power Graphs
In this paper, we only consider finite groups. An interested reader can refer to any standard book (e.g., [36 ] ) for the basic definitions and facts on group theory. The subgroup H H H of a group G G G is denoted by H ≤ G H \le G H ≤ G . The order of a group G G G , denoted by ∣ G ∣ |G| ∣ G ∣ , is the number of elements in G G G . The order of an element g g g in G G G , denoted by o ( g ) o(g) o ( g ) , is the smallest positive integer k k k such that g k = e g^k=e g k = e , where e e e is the identity element of the group G G G . The exponent of a finite group G G G , denoted by exp ( G ) \exp(G) exp ( G ) , is the least common multiple of the orders of all elements of G G G .
The direct product of two groups G 1 , G 2 G_1,G_2 G 1 , G 2 , denoted by G 1 × G 2 G_1 \times G_2 G 1 × G 2 , is the group on the elements ( g 1 , g 2 ) (g_1,g_2) ( g 1 , g 2 ) , g 1 ∈ G 1 g_1 \in G_1 g 1 ∈ G 1 , g 2 ∈ G 2 g_2 \in G_2 g 2 ∈ G 2 and the group operation on G 1 × G 2 G_1 \times G_2 G 1 × G 2 is given as follows: ( g 1 , g 2 ) ( g 1 ′ , g 2 ′ ) = ( g 1 g 1 ′ , g 2 g 2 ′ ) (g_1,g_2)(g'_1,g'_2)=(g_1g'_1,g_2g'_2) ( g 1 , g 2 ) ( g 1 ′ , g 2 ′ ) = ( g 1 g 1 ′ , g 2 g 2 ′ ) where the co-ordinate wise binary operations are the group operations of G 1 G_1 G 1 and G 2 G_2 G 2 respectively. A subset T T T of elements of a group G G G is said to generate a subgroup H ≤ G H \le G H ≤ G if H H H is the set of all finite products of elements of T T T . The set T T T is called a set of generators of H H H , and we write H = ⟨ T ⟩ H=\langle T\rangle H = ⟨ T ⟩ . When S S S is a singleton set { g } \{g\} { g } , then the subgroup ⟨ g ⟩ \langle g\rangle ⟨ g ⟩ generated by { g } \{g\} { g } is called the *cyclic subgroup generated by g g g . A cyclic group of order n n n is isomorphic to Z n \mathbb{Z}_n Z n , the additive group of integers modulo n n n .
A group G G G is called a p p p -group if the order of G G G is a power of a prime p p p . It is common to refer to a group as a p p p -group whenever its order is a power of some prime, where the symbol p p p denotes an arbitrary prime. Note that the exponent exp ( G ) \exp(G) exp ( G ) of a p p p -group G G G is the maximum order of an element in G G G . If p m p^m p m is the highest power of a prime p p p such that p m p^m p m divides ∣ G ∣ |G| ∣ G ∣ , then there is at least one subgroup of order p m p^m p m in G G G , and such a subgroup is called a Sylow p p p -subgroup of G G G . A finite group is a nilpotent group 4 if and only if it is a direct product of its Sylow subgroups. Moreover, for each prime factor p p p of G G G , the Sylow p p p -subgroup is unique in a finite nilpotent group G G G .
Definition 2.2. The power graph Pow ( G ) \operatorname{Pow}(G) Pow ( G ) of a finite group G G G is a simple, undirected graph with vertex set G G G . Two distinct elements x x x and y y y are adjacent in Pow ( G ) \operatorname{Pow}(G) Pow ( G ) if and only if x = y k x=y^k x = y k or y = x k y=x^k y = x k for some positive integer k k k .
The following observation is straightforward from the definition.
Observation 2.3. For two distinct elements x , y ∈ G x,y \in G x , y ∈ G , { x , y } \{x,y\} { x , y } is an edge in Pow ( G ) \operatorname{Pow}(G) Pow ( G ) if and only if ⟨ x ⟩ ≤ ⟨ y ⟩ \langle x\rangle\le\langle y\rangle ⟨ x ⟩ ≤ ⟨ y ⟩ or ⟨ y ⟩ ≤ ⟨ x ⟩ \langle y\rangle\le\langle x\rangle ⟨ y ⟩ ≤ ⟨ x ⟩ in G G G .
A power graph is a comparability graph [1 ] . The relation between these two graphs, in terms of boxicity, is also supported by [15 Observation 3] . The key idea behind this is a fundamental observation concerning the relationships among cyclic subgroups of a group, which provides a poset structure. Note that this poset structure is indeed the poset C ( G ) \mathcal{C}(G) C ( G ) of cyclic subgroups of a group G G G , ordered by inclusion. The next lemma serves as a bridge between these two graphs.
Lemma 2.4. For every finite group G G G , box ( Pow ( G ) ) = box ( Comp ( C ( G ) ) ) \operatorname{box}(\operatorname{Pow}(G))=\operatorname{box}(\operatorname{Comp}(\mathcal{C}(G))) box ( Pow ( G )) = box ( Comp ( C ( G ))) .
Basics on Boxicity
An equivalent formulation of boxicity was given by Roberts [34 ] and will be used throughout the paper.
Theorem 2.5 [34 ] . A non-complete graph G G G has boxicity at most l > 0 l > 0 l > 0 , if and only if it can be represented as the intersection of l l l many interval graphs, i.e., there exist interval supergraphs { I 1 , I 2 , … , I l } \{I_1,I_2,\ldots,I_l\} { I 1 , I 2 , … , I l } of G G G such that ∀ i ∈ [ l ] \forall i \in[l] ∀ i ∈ [ l ] , V ( I i ) = V ( G ) V(I_i)=V(G) V ( I i ) = V ( G ) and E ( G ) = E ( I 1 ) ∩ E ( I 2 ) ∩ ⋯ ∩ E ( I l ) E(G)=E(I_1)\cap E(I_2)\cap\cdots\cap E(I_l) E ( G ) = E ( I 1 ) ∩ E ( I 2 ) ∩ ⋯ ∩ E ( I l ) .
For vertex-disjoint graphs Γ 1 \Gamma_1 Γ 1 and Γ 2 \Gamma_2 Γ 2 , their join Γ 1 ∨ Γ 2 \Gamma_1 \vee\Gamma_2 Γ 1 ∨ Γ 2 is obtained from their disjoint union by adding every edge between V ( Γ 1 ) V(\Gamma_1) V ( Γ 1 ) and V ( Γ 2 ) V(\Gamma_2) V ( Γ 2 ) .
Lemma 2.6 [21 ] . For vertex-disjoint graphs Γ 1 \Gamma_1 Γ 1 and Γ 2 \Gamma_2 Γ 2 , box ( Γ 1 ∨ Γ 2 ) = box ( Γ 1 ) + box ( Γ 2 ) \operatorname{box}(\Gamma_1 \vee\Gamma_2)=\operatorname{box}(\Gamma_1)+\operatorname{box}(\Gamma_2) box ( Γ 1 ∨ Γ 2 ) = box ( Γ 1 ) + box ( Γ 2 ) .
The following lemma is straightforward, and we state it without a proof.
Lemma 2.7 [21 ] . Let d ≥ 1 d \ge1 d ≥ 1 . Let Γ 1 \Gamma_1 Γ 1 and Γ 2 \Gamma_2 Γ 2 be vertex-disjoint graphs with boxicity at most d d d . Then Γ 1 ⊔ Γ 2 \Gamma_1 \sqcup\Gamma_2 Γ 1 ⊔ Γ 2 has a d d d -box representation.
The Topological Tool
A ‘topological obstruction’ will be crucial in our lower bound proofs. This subsection discusses the tool and provides the necessary definitions to build the background for the reader.
Simplicial Complex, Nerve, and the Topological Obstruction
In this subsection, we discuss the topological terminologies used in our paper. An interested reader can refer to any standard textbook on topology, such as [31 ] , for more detailed information.
Definition 3.1. Let V V V be a finite set. A simplicial complex on V V V is a family K K K of subsets of V V V such that the following properties hold: (i) ∅ ∈ K \emptyset\in K ∅ ∈ K ; and (ii) whenever σ ∈ K \sigma\in K σ ∈ K and τ ⊆ σ \tau\subseteq\sigma τ ⊆ σ , one has τ ∈ K \tau\in K τ ∈ K . The members of K K K are called faces or simplices .
By definition, a face σ ∈ K \sigma\in K σ ∈ K containing s s s vertices has dimension s − 1 s-1 s − 1 , and dim K = max σ ∈ K dim σ \dim K=\max_{\sigma\in K}\dim\sigma dim K = max σ ∈ K dim σ . Thus, a zero-dimensional complex consists of isolated vertices together with the empty face. The face poset or nonempty face poset of a simplicial complex K K K is P ( K ) = K ∖ { ∅ } P(K)=K\setminus\{\emptyset\} P ( K ) = K ∖ { ∅ } , ordered by set inclusion. The order complex Δ ( P ) \Delta(P) Δ ( P ) of a finite poset P P P is the simplicial complex whose vertex set is P P P and whose faces are the finite chains of P P P .
Definition 3.2. The barycentric subdivision of a simplicial complex K K K , denoted by sd K \operatorname{sd}K sd K , is defined abstractly as follows: sd K = Δ ( P ( K ) ) \operatorname{sd}K=\Delta(P(K)) sd K = Δ ( P ( K )) . Consequently, the following hold:
a vertex of sd K \operatorname{sd}K sd K is a nonempty face of K K K ; and
a collection of such vertices is a face of sd K \operatorname{sd}K sd K precisely when the corresponding faces of K K K form an inclusion chain.
Definition 3.3. Let A = { A i } i ∈ I \mathcal{A}=\{A_i\}_{i\in I} A = { A i } i ∈ I be a family of sets indexed on the finite set I I I . The nerve of A \mathcal{A} A , denoted by Nerve ( A ) \operatorname{Nerve}(\mathcal{A}) Nerve ( A ) is the simplicial complex Nerve ( A ) = { σ ⊆ I : ⋂ i ∈ σ A i ≠ ∅ } \operatorname{Nerve}(\mathcal{A})=\{\sigma\subseteq I:\bigcap_{i\in\sigma}A_i\ne\emptyset\} Nerve ( A ) = { σ ⊆ I : ⋂ i ∈ σ A i = ∅ } . By convention, the empty set is included as a face in the nerve to satisfy the definition of a simplicial complex.
A non-empty set σ ⊆ I \sigma\subseteq I σ ⊆ I is considered a face of the nerve if and only if the subfamily of A \mathcal{A} A indexed by σ \sigma σ has a non-empty intersection. Note that the nerve of a family records intersections of arbitrary subfamilies, not merely pairwise intersections.
Definition 3.4. A finite simplicial complex K K K is d d d -representable if there is a finite family A = { A i } i ∈ I \mathcal{A}=\{A_i\}_{i\in I} A = { A i } i ∈ I of convex sets in R d \mathbb{R}^d R d such that K ≅ Nerve ( A ) K\cong\operatorname{Nerve}(\mathcal{A}) K ≅ Nerve ( A ) , i.e., the faces of K K K can be identified with the index sets of subfamilies of A = { A i } i ∈ I \mathcal{A}=\{A_i\}_{i\in I} A = { A i } i ∈ I having a non-empty total intersection.
Definition 3.5. Let K K K and L L L be two simplicial complexes with disjoint vertex sets. Then their simplicial join , denoted by K ∗ L K * L K ∗ L , is defined as follows: K ∗ L = { σ ∪ τ : σ ∈ K , τ ∈ L } K * L=\{\sigma\cup\tau:\sigma\in K,\tau\in L\} K ∗ L = { σ ∪ τ : σ ∈ K , τ ∈ L } . This means, every face of K ∗ L K * L K ∗ L is obtained by independently choosing a face of K K K and a face of L L L .
From the above definition, it is easy to see that dim ( K ∗ L ) = dim K + dim L + 1 \dim(K * L)=\dim K+\dim L+1 dim ( K ∗ L ) = dim K + dim L + 1 , whenever both complexes have a vertex.
To design tools to establish lower bounds on the boxicity of power graphs, we examine a specific simplicial complex D 3 D_3 D 3 , the zero-dimensional complex on three vertices: D 3 = { ∅ , { 1 } , { 2 } , { 3 } } D_3=\{\emptyset,\{1\},\{2\},\{3\}\} D 3 = { ∅ , { 1 } , { 2 } , { 3 }} . For r ≥ 1 r\geq1 r ≥ 1 , we then take the simplicial join D 3 ∗ r D_3^{*r} D 3 ∗ r of r r r disjoint copies of D 3 D_3 D 3 . Note that a face of D 3 ∗ r D_3^{*r} D 3 ∗ r has at most one of the three vertices from each copy of D 3 D_3 D 3 . Moreover, a maximal face contains one vertex from each of the r r r copies of D 3 D_3 D 3 and hence each maximal face has r r r vertices. So, dim D 3 ∗ r = r − 1 \dim D_3^{*r}=r-1 dim D 3 ∗ r = r − 1 .
We use the following theorem by Tancer [42 ] as a black box in our paper.
Theorem 3.6 ([42 ] ). If K K K is an s s s -dimensional simplicial complex with a non-vanishing Van Kampen obstruction, then the barycentric subdivision sd K \operatorname{sd}K sd K of K K K is not 2 s 2s 2 s -representable.
The Van Kampen obstruction is a certain obstruction for the embeddability of d d d -dimensional simplicial complexes into R 2 d \mathbb{R}^{2d} R 2 d . Defining this obstruction precisely would require extensive preliminaries, and since no definition or calculation is necessary later, we avoid mentioning the details here and direct interested readers to [5 Section 2] and [32 Appendix D] for an introductory explanation. From the discussion in [5 Section 2.2 and Lemma 9] , it is clear that the D 3 ∗ r D_3^{*r} D 3 ∗ r has a non-vanishing Van Kampen obstruction in target dimension 2 r − 2 2r-2 2 r − 2 . Combining this fact with Theorem 3.6 , one can derive the following corollary easily.
Corollary 3.7. For every r ≥ 2 r\geq2 r ≥ 2 , the barycentric subdivision sd ( D 3 ∗ r ) \operatorname{sd}(D_3^{*r}) sd ( D 3 ∗ r ) is not ( 2 r − 2 ) (2r-2) ( 2 r − 2 ) -representable.
The above corollary serves as the primary tool for establishing the lower bounds discussed in this paper.
The Comparability Graph of the Face Poset of D 3 ∗ r D_3^{*r} D 3 ∗ r
In this subsection, we establish a lower bound for the boxicity of the comparability graph of the face poset of D 3 ∗ r D_3^{*r} D 3 ∗ r . The proof utilises Corollary 3.7. Observe that Corollary 3.7 concerns nerves of convex sets and boxicity is defined using axis-parallel boxes, which are examples of convex sets. We now discuss why an axis-parallel box representation produces exactly the nerve needed above.
Before going into further details, we state the 2-Helly property for axis-parallel boxes : Let S \mathcal{S} S be a nonempty finite family of axis-parallel boxes in R d \mathbb{R}^d R d . Then ⋂ S ∈ S S ≠ ∅ ⟺ S ∩ S ′ ≠ ∅ \bigcap_{S\in\mathcal{S}}S\ne\emptyset\Longleftrightarrow S\cap S'\ne\emptyset ⋂ S ∈ S S = ∅ ⟺ S ∩ S ′ = ∅ for every S , S ′ ∈ S S,S'\in\mathcal{S} S , S ′ ∈ S . Note that the preceding statement is stronger than Helly’s theorem for general convex sets in R d \mathbb{R}^d R d . It holds because an axis-parallel box is a Cartesian product of intervals, and Helly’s theorem applies for intervals in R \mathbb{R} R .
We can now derive the main result of this subsection.
Lemma 3.8. Suppose Γ r = Comp ( P ( D 3 ∗ r ) ) \Gamma_r = \operatorname{Comp}(P(D_3^{*r})) Γ r = Comp ( P ( D 3 ∗ r )) . For every r ≥ 1 r \ge1 r ≥ 1 , box ( Γ r ) ≥ 2 r − 1 \operatorname{box}(\Gamma_r) \ge2r - 1 box ( Γ r ) ≥ 2 r − 1 .
Proof. For r = 1 r = 1 r = 1 , it is easy to see that Γ 1 \Gamma_1 Γ 1 is the empty graph on three vertices. Hence, box ( Γ 1 ) = 1 \operatorname{box}(\Gamma_1) = 1 box ( Γ 1 ) = 1 .
Now assume r ≥ 2 r \ge2 r ≥ 2 . For a contradiction, suppose that box ( Γ r ) ≤ 2 r − 2 \operatorname{box}(\Gamma_r) \le2r - 2 box ( Γ r ) ≤ 2 r − 2 . So we consider a ( 2 r − 2 ) (2r - 2) ( 2 r − 2 ) -box representation B = { B σ : σ ∈ P ( D 3 ∗ r ) } \mathcal{B} = \{B_\sigma: \sigma\in P(D_3^{*r})\} B = { B σ : σ ∈ P ( D 3 ∗ r )} of Γ r \Gamma_r Γ r , where each B σ B_\sigma B σ is an axis-parallel box in R 2 r − 2 \mathbb{R}^{2r-2} R 2 r − 2 . Note that a vertex of Γ r \Gamma_r Γ r is an element of the poset P ( D 3 ∗ r ) P(D_3^{*r}) P ( D 3 ∗ r ) and so a non-empty face of D 3 ∗ r D_3^{*r} D 3 ∗ r .
We now take the nerve of the family B = { B σ : σ ∈ P ( D 3 ∗ r ) } \mathcal{B} = \{B_\sigma: \sigma\in P(D_3^{*r})\} B = { B σ : σ ∈ P ( D 3 ∗ r )} . We first prove the following claim:
Claim 3.9. Nerve ( B ) = Δ ( P ( D 3 ∗ r ) ) = sd D 3 ∗ r \operatorname{Nerve}(\mathcal{B}) = \Delta(P(D_3^{*r})) = \operatorname{sd} D_3^{*r} Nerve ( B ) = Δ ( P ( D 3 ∗ r )) = sd D 3 ∗ r .
Proof. Let us take a face F = { σ 1 , σ 2 , … , σ t } F = \{\sigma_1,\sigma_2,\ldots,\sigma_t\} F = { σ 1 , σ 2 , … , σ t } from Nerve ( B ) \operatorname{Nerve}(\mathcal{B}) Nerve ( B ) . We show that this face F F F corresponds to a face in Δ ( P ( D 3 ∗ r ) ) \Delta(P(D_3^{*r})) Δ ( P ( D 3 ∗ r )) , i.e., to a finite chain in P ( D 3 ∗ r ) P(D_3^{*r}) P ( D 3 ∗ r ) . Note that F = { σ 1 , σ 2 , … , σ t } ⊆ P ( D 3 ∗ r ) F = \{\sigma_1,\sigma_2,\ldots,\sigma_t\} \subseteq P(D_3^{*r}) F = { σ 1 , σ 2 , … , σ t } ⊆ P ( D 3 ∗ r ) and ⋂ i = 1 t B σ i ≠ ∅ \bigcap_{i=1}^{t} B_{\sigma_i} \ne\varnothing ⋂ i = 1 t B σ i = ∅ . This means that { σ i } i = 1 t \{\sigma_i\}_{i=1}^{t} { σ i } i = 1 t forms a clique in Γ r \Gamma_r Γ r and { σ i } i = 1 t \{\sigma_i\}_{i=1}^{t} { σ i } i = 1 t forms a chain (in some order) in P ( D 3 ∗ r ) P(D_3^{*r}) P ( D 3 ∗ r ) . This, in turn, implies that { σ i } i = 1 t \{\sigma_i\}_{i=1}^{t} { σ i } i = 1 t is a face in Δ ( P ( D 3 ∗ r ) ) = sd D 3 ∗ r \Delta(P(D_3^{*r})) = \operatorname{sd} D_3^{*r} Δ ( P ( D 3 ∗ r )) = sd D 3 ∗ r .
For the opposite direction, we consider a face F ′ = { τ i } i = 1 s F' = \{\tau_i\}_{i=1}^{s} F ′ = { τ i } i = 1 s in Δ ( P ( D 3 ∗ r ) ) \Delta(P(D_3^{*r})) Δ ( P ( D 3 ∗ r )) . This corresponds to a finite chain in P ( D 3 ∗ r ) P(D_3^{*r}) P ( D 3 ∗ r ) . Our goal is to show that there is a corresponding face F F F in Nerve ( B ) \operatorname{Nerve}(\mathcal{B}) Nerve ( B ) . By construction, { τ i } i = 1 s \{\tau_i\}_{i=1}^{s} { τ i } i = 1 s induces a clique in Γ r \Gamma_r Γ r . So, B τ i ∩ B τ j ≠ ∅ B_{\tau_i} \cap B_{\tau_j} \ne\varnothing B τ i ∩ B τ j = ∅ , for each $1 \le i < j \le s$. By Helly’s property of axis-parallel boxes, we have ⋂ i = 1 s B τ i ≠ ∅ \bigcap_{i=1}^{s} B_{\tau_i} \ne\varnothing ⋂ i = 1 s B τ i = ∅ . Hence, the set { τ i } i = 1 s \{\tau_i\}_{i=1}^{s} { τ i } i = 1 s is a face in Nerve ( { B σ : σ ∈ P ( D 3 ∗ r ) } ) \operatorname{Nerve}(\{B_\sigma: \sigma\in P(D_3^{*r})\}) Nerve ({ B σ : σ ∈ P ( D 3 ∗ r )}) .
Since an axis-parallel box is a convex set, the above claim implies that B \mathcal{B} B is a convex set representation of sd D 3 ∗ r \operatorname{sd} D_3^{*r} sd D 3 ∗ r in R 2 r − 2 \mathbb{R}^{2r-2} R 2 r − 2 ; equivalently, sd D 3 ∗ r \operatorname{sd} D_3^{*r} sd D 3 ∗ r is ( 2 r − 2 ) (2r - 2) ( 2 r − 2 ) -representable. This contradicts Corollary 3.7 and therefore, our assumption is wrong and hence box ( Γ r ) > 2 r − 2 \operatorname{box}(\Gamma_r) > 2r - 2 box ( Γ r ) > 2 r − 2 .
Note that the equality between the nerve and the barycentric subdivision mentioned in Claim 3.9 does not hold in general. This is because pairwise intersections need not always guarantee a common point. However, in this context, equality holds because we are dealing with a box representation of a comparability graph, and the Helly property for axis-parallel boxes guarantees the required result.
The Boxicity of Comparability Graph of Product of Posets
In this section, we develop some tools that will eventually help us bound the boxicity of a particular product of posets by breaking it down into more basic units, such as chains and rooted tree posets.
The comparability graph of a rooted tree poset
Lemma 4.1. Let T T T be a finite rooted tree poset. Then Comp ( T ) \operatorname{Comp}(T) Comp ( T ) is an interval graph.
Proof. We first traverse the cover graph of T T T in depth-first order and list its leaves from left to right during the traversal. For every vertex v v v , let l ( v ) l(v) l ( v ) and r ( v ) r(v) r ( v ) be the positions in the depth-first order of the first and last leaves below v v v , possibly including v v v if it is itself a leaf.
Assign the interval J ( v ) = [ l ( v ) , r ( v ) ] J(v)=[l(v),r(v)] J ( v ) = [ l ( v ) , r ( v )] . All leaves below a fixed node occur consecutively in a depth-first order. Note that if v v v is a leaf, then l ( v ) = r ( v ) l(v)=r(v) l ( v ) = r ( v ) and J ( v ) J(v) J ( v ) is a point interval.
Let u u u be an ancestor of v v v . If v v v is a leaf, then clearly J ( v ) ⊆ J ( u ) J(v)\subseteq J(u) J ( v ) ⊆ J ( u ) . If v v v is a non-leaf vertex, then every leaf below v v v is also below u u u , so J ( v ) ⊆ J ( u ) J(v)\subseteq J(u) J ( v ) ⊆ J ( u ) . If u u u and v v v are incomparable, their rooted subtrees are disjoint and occupy disjoint blocks of leaves, so J ( u ) ∩ J ( v ) = ∅ J(u)\cap J(v)=\varnothing J ( u ) ∩ J ( v ) = ∅ . Thus, intervals meet exactly for ancestor-comparable nodes. Therefore, the intersection graph of these intervals is isomorphic to the interval graph Comp ( T ) \operatorname{Comp}(T) Comp ( T ) .
Adding a chain coordinate
Recall that C e C_e C e denotes a chain { 0 < 1 < 2 < ⋯ < e } \{0<1<2<\cdots<e\} { 0 < 1 < 2 < ⋯ < e } of length/height e e e .
Lemma 4.2. For every finite poset P P P and every e ≥ 0 e\geq0 e ≥ 0 , box ( Comp ( P × C e ) ) ≤ box ( Comp ( P ) ) + e \operatorname{box}(\operatorname{Comp}(P\times C_e))\leq\operatorname{box}(\operatorname{Comp}(P))+e box ( Comp ( P × C e )) ≤ box ( Comp ( P )) + e .
Proof. Let d = box ( Comp ( P ) ) d=\operatorname{box}(\operatorname{Comp}(P)) d = box ( Comp ( P )) and let J 1 , J 2 , … , J d J_1,J_2,\ldots,J_d J 1 , J 2 , … , J d be a collection of interval graphs that form a d d d -box representation of Comp ( P ) \operatorname{Comp}(P) Comp ( P ) .
Consider an arbitrary linear extension of P P P and for an element x ∈ P x\in P x ∈ P , let λ ( x ) \lambda(x) λ ( x ) be the position of x x x in the linear extension. Let r ∈ P r\in P r ∈ P be the element appearing last in this linear order.
We define interval graphs I 1 , I 2 , … , I d + e I_1,I_2,\ldots,I_{d+e} I 1 , I 2 , … , I d + e such that ∀ ( x , j ) ∈ P × C e \forall(x,j)\in P\times C_e ∀ ( x , j ) ∈ P × C e , we have
∀ i ∈ [ d ] , I i ( x , j ) = J i ( x ) \forall i\in[d],\ I_i(x,j)=J_i(x) ∀ i ∈ [ d ] , I i ( x , j ) = J i ( x )
and
∀ i ∈ [ d + e ] ∖ [ d ] , I i ( x , j ) = { [ λ ( x ) , λ ( r ) ] , j < i − d , [ 0 , λ ( x ) ] , j ≥ i − d . \forall i\in[d+e]\setminus[d],\ I_i(x,j)=
\begin{cases}
[\lambda(x),\lambda(r)], & j<i-d,\\
[0,\lambda(x)], & j\geq i-d.
\end{cases} ∀ i ∈ [ d + e ] ∖ [ d ] , I i ( x , j ) = { [ λ ( x ) , λ ( r )] , [ 0 , λ ( x )] , j < i − d , j ≥ i − d .
Note that when two elements x x x and y y y of P P P are incomparable, there exists k ∈ [ d ] k\in[d] k ∈ [ d ] , such that J k ( x ) ∩ J k ( y ) = ∅ J_k(x)\cap J_k(y)=\varnothing J k ( x ) ∩ J k ( y ) = ∅ . Consequently, for any j 1 , j 2 ∈ C e j_1,j_2\in C_e j 1 , j 2 ∈ C e , I k ( x , j 1 ) ∩ I k ( y , j 2 ) = ∅ I_k(x,j_1)\cap I_k(y,j_2)=\varnothing I k ( x , j 1 ) ∩ I k ( y , j 2 ) = ∅ .
Therefore, we only need to check the case when two elements x x x and y y y of P P P are comparable.
Suppose ( x , j 1 ) ≤ ( y , j 2 ) (x,j_1)\leq(y,j_2) ( x , j 1 ) ≤ ( y , j 2 ) in the product, so x ≤ y x\leq y x ≤ y and j 1 ≤ j 2 j_1\leq j_2 j 1 ≤ j 2 . It is clear that for i ∈ [ d ] i\in[d] i ∈ [ d ] , I i ( x , j 1 ) ∩ I i ( y , j 2 ) ≠ ∅ I_i(x,j_1)\cap I_i(y,j_2)\neq\varnothing I i ( x , j 1 ) ∩ I i ( y , j 2 ) = ∅ . For i ∈ [ d + e ] ∖ [ d ] i\in[d+e]\setminus[d] i ∈ [ d + e ] ∖ [ d ] , there are three possibilities:
j 1 , j 2 < i − d j_1,j_2<i-d j 1 , j 2 < i − d : we have λ ( r ) ∈ I i ( x , j 1 ) ∩ I i ( y , j 2 ) \lambda(r)\in I_i(x,j_1)\cap I_i(y,j_2) λ ( r ) ∈ I i ( x , j 1 ) ∩ I i ( y , j 2 ) ;
i − d ≤ j 1 , j 2 i-d\leq j_1,j_2 i − d ≤ j 1 , j 2 : we have 0 ∈ I i ( x , j 1 ) ∩ I i ( y , j 2 ) 0\in I_i(x,j_1)\cap I_i(y,j_2) 0 ∈ I i ( x , j 1 ) ∩ I i ( y , j 2 ) ;
j 1 < i − d ≤ j 2 j_1<i-d\leq j_2 j 1 < i − d ≤ j 2 : the intervals are [ λ ( x ) , λ ( r ) ] [\lambda(x),\lambda(r)] [ λ ( x ) , λ ( r )] and [ 0 , λ ( y ) ] [0,\lambda(y)] [ 0 , λ ( y )] , which meet because λ ( x ) ≤ λ ( y ) \lambda(x)\leq\lambda(y) λ ( x ) ≤ λ ( y ) .
Hence, every such pair remains adjacent.
Now suppose x < y x<y x < y but j 1 > j 2 j_1>j_2 j 1 > j 2 . Choose k k k with j 2 < k ≤ j 1 j_2<k\leq j_1 j 2 < k ≤ j 1 . Then I d + k ( x , j 1 ) = [ 0 , λ ( x ) ] I_{d+k}(x,j_1)=[0,\lambda(x)] I d + k ( x , j 1 ) = [ 0 , λ ( x )] , I d + k ( y , j 2 ) = [ λ ( y ) , λ ( r ) ] I_{d+k}(y,j_2)=[\lambda(y),\lambda(r)] I d + k ( y , j 2 ) = [ λ ( y ) , λ ( r )] , and these intervals are disjoint because λ ( x ) < λ ( y ) \lambda(x)<\lambda(y) λ ( x ) < λ ( y ) . The case y < x y<x y < x and j 2 > j 1 j_2>j_1 j 2 > j 1 is symmetric. These are precisely the remaining pairs in the product.
Replacing a chain by a rooted tree poset
Lemma 4.3. Let P P P be a finite poset and let T T T be a rooted tree poset of height e e e . Then box ( Comp ( P × T ) ) ≤ box ( Comp ( P × C e ) ) + 1 \operatorname{box}(\operatorname{Comp}(P\times T))\leq\operatorname{box}(\operatorname{Comp}(P\times C_e))+1 box ( Comp ( P × T )) ≤ box ( Comp ( P × C e )) + 1 .
Proof. Take a box representation of Comp ( P × C ℓ ) \operatorname{Comp}(P \times C_{\ell}) Comp ( P × C ℓ ) , where the vertex ( x , j ) (x,j) ( x , j ) is given the box B ~ x , j \widetilde{B}_{x,j} B x , j . Assign the vertex ( x , v ) ∈ P × T (x,v) \in P \times T ( x , v ) ∈ P × T the box B x , v : = B ~ x , depth ( v ) B_{x,v} := \widetilde{B}_{x,\operatorname{depth}(v)} B x , v := B x , depth ( v ) . By the proof of Lemma 4.1, there is an interval representation J J J of T T T such that for a vertex v ∈ T v \in T v ∈ T , the interval J ( v ) J(v) J ( v ) is determined by the depth-first order of the leaves of v v v .
We will show that the intersection graph of the boxes { B x , v × J ( v ) } ( x , v ) ∈ P × T \{B_{x,v} \times J(v)\}_{(x,v)\in P \times T} { B x , v × J ( v ) } ( x , v ) ∈ P × T is isomorphic to Comp ( P × T ) \operatorname{Comp}(P \times T) Comp ( P × T ) .
Suppose ( x , u ) , ( y , v ) ∈ P × T (x,u),(y,v) \in P \times T ( x , u ) , ( y , v ) ∈ P × T are comparable. Then ( x , u ) ≤ ( y , v ) (x,u) \le(y,v) ( x , u ) ≤ ( y , v ) and so ( x , depth ( u ) ) ≤ ( y , depth ( v ) ) (x,\operatorname{depth}(u)) \le(y,\operatorname{depth}(v)) ( x , depth ( u )) ≤ ( y , depth ( v )) . Hence, B x , u × J ( u ) ∩ B y , v × J ( v ) ≠ ∅ B_{x,u} \times J(u) \cap B_{y,v} \times J(v) \ne\varnothing B x , u × J ( u ) ∩ B y , v × J ( v ) = ∅
Conversely, suppose ( x , u ) , ( y , v ) ∈ P × T (x,u),(y,v) \in P \times T ( x , u ) , ( y , v ) ∈ P × T are incomparable. If ( x , depth ( u ) ) (x,\operatorname{depth}(u)) ( x , depth ( u )) and ( y , depth ( v ) ) (y,\operatorname{depth}(v)) ( y , depth ( v )) are incomparable in P × C ℓ P \times C_{\ell} P × C ℓ , then B ~ x , depth ( u ) ∩ B ~ y , depth ( v ) = ∅ \widetilde{B}_{x,\operatorname{depth}(u)} \cap\widetilde{B}_{y,\operatorname{depth}(v)} = \varnothing B x , depth ( u ) ∩ B y , depth ( v ) = ∅ and consequently, B x , u ∩ B y , v = ∅ B_{x,u} \cap B_{y,v} = \varnothing B x , u ∩ B y , v = ∅ . On the other hand, if ( x , depth ( u ) ) (x,\operatorname{depth}(u)) ( x , depth ( u )) and ( y , depth ( v ) ) (y,\operatorname{depth}(v)) ( y , depth ( v )) are comparable in P × C ℓ P \times C_{\ell} P × C ℓ , then the incomparability of ( x , u ) (x,u) ( x , u ) and ( y , v ) (y,v) ( y , v ) forces u u u and v v v to lie on different branches of T T T . In that case J ( u ) ∩ J ( v ) = ∅ J(u) \cap J(v) = \varnothing J ( u ) ∩ J ( v ) = ∅ . In either case, B x , u × J ( u ) ∩ B y , v × J ( v ) = ∅ B_{x,u} \times J(u) \cap B_{y,v} \times J(v) = \varnothing B x , u × J ( u ) ∩ B y , v × J ( v ) = ∅
The Comparability Graph of Product of Star Posets
Recall that the star poset S S S is defined as follows: S S S is the four-element star poset consisting of a root element ρ \rho ρ and three leaves a 1 , a 2 , a 3 a_1,a_2,a_3 a 1 , a 2 , a 3 , where the relations in the poset are given by ρ < a j \rho< a_j ρ < a j , j = 1 , 2 , 3 j = 1,2,3 j = 1 , 2 , 3 , with the leaves pairwise incomparable. This poset is the face poset of D 3 D_3 D 3 when the empty face is retained: the root ρ \rho ρ of S S S refers to the empty face of D 3 D_3 D 3 , and each leaf a j a_j a j refers to the singleton face { j } \{j\} { j } . Note that by this definition of S S S , the product poset S r S^r S r explicitly corresponds to the full face poset of D 3 ∗ r D_3^{*r} D 3 ∗ r , i.e., the face poset of D 3 ∗ r D_3^{*r} D 3 ∗ r including the empty face as well. Hence, the following observation is straightforward. The proof is included in Section B.1
Observation 4.4. Γ r = Comp ( P ( D 3 ∗ r ) ) \Gamma_r = \operatorname{Comp}(P(D_3^{*r})) Γ r = Comp ( P ( D 3 ∗ r )) is an induced subgraph of Comp ( S r ) \operatorname{Comp}(S^r) Comp ( S r ) . This in turn implies that box ( Comp ( S r ) ) ≥ 2 r − 1 \operatorname{box}(\operatorname{Comp}(S^r)) \ge2r - 1 box ( Comp ( S r )) ≥ 2 r − 1 .
The Comparability Graph of a Mixed Product of Chains and Star Posets
Let C 1 r C_1^r C 1 r denote the product of r r r copies of the poset chain C 1 = { 0 < 1 } C_1 = \{0 < 1\} C 1 = { 0 < 1 } . Hence, an element of C 1 r C_1^r C 1 r is a tuple x = ( x 1 , … , x r ) \mathbf{x} = (x_1,\ldots,x_r) x = ( x 1 , … , x r ) , x i ∈ { 0 , 1 } x_i \in\{0,1\} x i ∈ { 0 , 1 } , and the product order is coordinate-wise: x ≤ y \mathbf{x} \le\mathbf{y} x ≤ y if and only if x i ≤ y i x_i \le y_i x i ≤ y i for every i i i . The map x ↦ { i ∈ [ r ] : x i = 1 } x \mapsto\{i \in[r] : x_i = 1\} x ↦ { i ∈ [ r ] : x i = 1 } is an order isomorphism from C 1 r C_1^r C 1 r to the Boolean lattice of all subsets of [ r ] [r] [ r ] , ordered by inclusion. This comparability graph Comp ( C 1 r ) \operatorname{Comp}(C_1^r) Comp ( C 1 r ) was referred to in [15 ] as the transitive closure of the hypercube of dimension r r r , denoted by the notation T C ( H r ) TC(H_r) T C ( H r ) . They used the function f ( r ) f(r) f ( r ) to represent the boxicity box ( T C ( H r ) ) \operatorname{box}(TC(H_r)) box ( T C ( H r )) and we retain this notation, i.e., we define f ( r ) = box ( T C ( H r ) ) = box ( Comp ( C 1 r ) ) f(r) = \operatorname{box}(TC(H_r)) = \operatorname{box}(\operatorname{Comp}(C_1^r)) f ( r ) = box ( T C ( H r )) = box ( Comp ( C 1 r )) .
The following observation is stated in [15 ] , Corollary 3 in terms of T C ( H r ) TC(H_r) T C ( H r ) . But we note here for completeness, as it is essential for our discussions in this section and throughout the remainder of the paper. This observation is easy to see from combining the fact box ( Comp ( C 1 ) ) = 0 \operatorname{box}(\operatorname{Comp}(C_1)) = 0 box ( Comp ( C 1 )) = 0 and Lemma 4.2.
Observation 4.5. box ( Comp ( C 1 r ) ) ≤ r − 1 \operatorname{box}(\operatorname{Comp}(C_1^r)) \le r - 1 box ( Comp ( C 1 r )) ≤ r − 1 , r ≥ 1 r \ge1 r ≥ 1 .
Proof. The comparability graph Comp ( C 1 ) \operatorname{Comp}(C_1) Comp ( C 1 ) is complete and, under our convention, f ( 1 ) = 0 f(1) = 0 f ( 1 ) = 0 . For r ≥ 2 r \ge2 r ≥ 2 , write C 1 r = C 1 r − 1 × C 1 C_1^r = C_1^{r-1} \times C_1 C 1 r = C 1 r − 1 × C 1 . Lemma 4.2 gives f ( r ) ≤ f ( r − 1 ) + 1 f(r) \le f(r - 1) + 1 f ( r ) ≤ f ( r − 1 ) + 1 , since the height of the chain is 1. Iterating this inequality from f ( 1 ) = 0 f(1) = 0 f ( 1 ) = 0 yields f ( r ) ≤ r − 1 f(r) \le r - 1 f ( r ) ≤ r − 1 .
A poset construction: We consider the product of posets R r , j = S j × C 1 r − j R_{r,j}=S^j\times C_1^{r-j} R r , j = S j × C 1 r − j for j = 0 , 1 , … , r j=0,1,\ldots,r j = 0 , 1 , … , r . In particular, this is a product of multiple copies of two types of posets: j j j copies of a star poset S S S and r − j r-j r − j copies of a chain. It is important to note that R r , 0 = C 1 r R_{r,0}=C_1^r R r , 0 = C 1 r and R r , r = S r R_{r,r}=S^r R r , r = S r .
In the next lemma (Lemma 4.6), we will demonstrate the boxicity of the comparability graph of the poset R r , j R_{r,j} R r , j for 0 ≤ j ≤ r 0\le j\le r 0 ≤ j ≤ r .
Lemma 4.6. For r ≥ 1 r\ge1 r ≥ 1 , box ( Comp ( R r , j ) ) = r + j − 1 \operatorname{box}(\operatorname{Comp}(R_{r,j}))=r+j-1 box ( Comp ( R r , j )) = r + j − 1 , for 0 ≤ j ≤ r 0\le j\le r 0 ≤ j ≤ r .
Proof. The strategy is to go from R r , j − 1 R_{r,j-1} R r , j − 1 to R r , j R_{r,j} R r , j by replacing one factor C 1 C_1 C 1 with S S S and applying Lemma 4.3. Both C 1 C_1 C 1 and S S S have height 1, and hence using Lemma 4.3 we have the following inequality: box ( Comp ( S j − 1 × C 1 r − j × S ) ) ≤ box ( Comp ( S j − 1 × C 1 r − j × C 1 ) ) + 1 \operatorname{box}(\operatorname{Comp}(S^{j-1}\times C_1^{r-j}\times S))\le\operatorname{box}(\operatorname{Comp}(S^{j-1}\times C_1^{r-j}\times C_1))+1 box ( Comp ( S j − 1 × C 1 r − j × S )) ≤ box ( Comp ( S j − 1 × C 1 r − j × C 1 )) + 1 . Since permuting the positions of the factors does not change the final product up to isomorphism, the above inequality can be rewritten as follows:
box ( Comp ( R r , j ) ) ≤ box ( Comp ( R r , j − 1 ) ) + 1. (2) \operatorname{box}(\operatorname{Comp}(R_{r,j}))\le\operatorname{box}(\operatorname{Comp}(R_{r,j-1}))+1. \tag*{(2)} box ( Comp ( R r , j )) ≤ box ( Comp ( R r , j − 1 )) + 1. (2)
By repeatedly applying Lemma 4.3 to the right-hand side of the inequality in Equation (2) until we reach j = 0 j=0 j = 0 (which requires applying Lemma 4.3 a total of j j j times), we obtain the following result: box ( Comp ( R r , j ) ) ≤ box ( Comp ( C 1 r ) ) + j \operatorname{box}(\operatorname{Comp}(R_{r,j}))\le\operatorname{box}(\operatorname{Comp}(C_1^r))+j box ( Comp ( R r , j )) ≤ box ( Comp ( C 1 r )) + j . Next, by using Observation 4.5, we arrive at the desired upper bound: box ( Comp ( R r , j ) ) ≤ r − 1 + j \operatorname{box}(\operatorname{Comp}(R_{r,j}))\le r-1+j box ( Comp ( R r , j )) ≤ r − 1 + j .
For the lower bound, we apply Equation (2) successively for ℓ = j + 1 , j + 2 , … , r \ell=j+1,j+2,\ldots,r ℓ = j + 1 , j + 2 , … , r . Thus, we have box ( Comp ( R r , r ) ) ≤ box ( Comp ( R r , j ) ) + r − j \operatorname{box}(\operatorname{Comp}(R_{r,r}))\le\operatorname{box}(\operatorname{Comp}(R_{r,j}))+r-j box ( Comp ( R r , r )) ≤ box ( Comp ( R r , j )) + r − j . Since R r , r = S r R_{r,r}=S^r R r , r = S r , by Observation 4.4 the last mentioned inequality yields the following: 2 r − 1 ≤ box ( Comp ( R r , j ) ) + r − j 2r-1\le\operatorname{box}(\operatorname{Comp}(R_{r,j}))+r-j 2 r − 1 ≤ box ( Comp ( R r , j )) + r − j . Thus, we have box ( Comp ( R r , j ) ) ≥ r + j − 1 \operatorname{box}(\operatorname{Comp}(R_{r,j}))\ge r+j-1 box ( Comp ( R r , j )) ≥ r + j − 1 .
As a direct consequence of the previous lemma, we will now determine the exact boxicity of the comparability graph of the Boolean lattice C 1 r C_1^r C 1 r . As discussed earlier, this result also provides the precise value of the boxicity of the power graph of the cyclic group, which was an open question in [15 ] .
Corollary 4.7. For every r ≥ 1 r\ge1 r ≥ 1 , f ( r ) = box ( Comp ( C 1 r ) ) = r − 1 f(r)=\operatorname{box}(\operatorname{Comp}(C_1^r))=r-1 f ( r ) = box ( Comp ( C 1 r )) = r − 1 .
Proof. Putting j = 0 j=0 j = 0 in Lemma 4.6, we have the lemma.
To ensure uniformity in exposition, the proof of Corollary 4.7 has been presented in its current form as a consequence of Lemma 3.8. However, there is a more direct and combinatorial proof of this lemma, which may be of independent interest. We present this alternate proof in the Appendix A.
The Comparability Graph of Product of Some Special Types of Rooted Tree Posets
In this subsection, we establish a lower bound for the boxicity of the comparability graph of a product of posets, in particular a product of rooted tree posets with special properties. The proof of this lemma uses the strategy for establishing the lower bound in [15 ] .
Lemma 4.8. Let d ≥ 1 d\ge1 d ≥ 1 , and let T 1 , … , T d T_1,\ldots,T_d T 1 , … , T d be finite rooted tree posets of heights e 1 , … , e d e_1,\ldots,e_d e 1 , … , e d , respectively, where e i ≥ 1 e_i\ge1 e i ≥ 1 for every i ∈ [ d ] i\in[d] i ∈ [ d ] . Suppose that for every i i i in a specified set R R R , the rooted tree poset T i T_i T i satisfies h 3 ( T i ) = e i − 1 h_3(T_i)=e_i-1 h 3 ( T i ) = e i − 1 . Then
box ( Comp ( ∏ i = 1 d T i ) ) ≥ ∑ i = 1 d e i − max i e i + ∣ R ∣ . (3) \operatorname{box}\left(\operatorname{Comp}\left(\prod_{i=1}^{d}T_i\right)\right)\ge\sum_{i=1}^{d}e_i-\max_i e_i+|R|. \tag*{(3)} box ( Comp ( i = 1 ∏ d T i ) ) ≥ i = 1 ∑ d e i − i max e i + ∣ R ∣. (3) :::♀♀♀♀♀♀
Proof. Put M = max i e i M = \max_i e_i M = max i e i . We first choose a small induced subposet P i P_i P i in every factor rooted tree poset T i T_i T i . For i ∉ R i \notin R i ∈ / R , choose in T i T_i T i a root-to-leaf chain P i P_i P i of height e i e_i e i , so P i ≅ C e i P_i \cong C_{e_i} P i ≅ C e i . For i ∈ R i \in R i ∈ R , choose a node c i c_i c i of depth e i − 1 e_i - 1 e i − 1 having three pairwise incomparable strict descendants; these descendants have depth e i e_i e i , since T i T_i T i has height e i e_i e i . In this case, i.e., for i ∈ R i \in R i ∈ R , let P i P_i P i consist of the root-to-c i c_i c i chain together with three such descendants. Thus P i P_i P i is an induced subposet of T i T_i T i , and consequently ∏ i = 1 d P i \prod_{i=1}^{d} P_i ∏ i = 1 d P i is an induced subposet of ∏ i = 1 d T i \prod_{i=1}^{d} T_i ∏ i = 1 d T i . It is therefore enough to prove the required lower bound for Comp ( ∏ i P i ) \operatorname{Comp}(\prod_i P_i) Comp ( ∏ i P i ) .
We consider the dual order Q = ( ∏ i = 1 d P i ) o p = ∏ i = 1 d P i o p Q = \left(\prod_{i=1}^{d} P_i\right)^{\mathrm{op}} = \prod_{i=1}^{d} P_i^{\mathrm{op}} Q = ( ∏ i = 1 d P i ) op = ∏ i = 1 d P i op . Since the dual order P o p P^{\mathrm{op}} P op of a poset P P P is defined to be the same set, but with the inverse order, i.e. x ≤ y x \le y x ≤ y holds in P o p P^{\mathrm{op}} P op if and only if y ≤ x y \le x y ≤ x holds in P P P , taking the duality does not change the comparability graph. We list the different e i + 1 e_i+1 e i + 1 levels of a subposet P i o p P_i^{\mathrm{op}} P i op from bottom to top as L i , 0 , L i , 1 , … , L i , e i L_{i,0}, L_{i,1}, \ldots, L_{i,e_i} L i , 0 , L i , 1 , … , L i , e i . For i ∉ R i \notin R i ∈ / R , these levels of P i o p P_i^{\mathrm{op}} P i op are singleton sets. For i ∈ R i \in R i ∈ R , the bottom most level L i , 0 L_{i,0} L i , 0 has three elements, every L i , j L_{i,j} L i , j with 1 ≤ j ≤ e i 1 \le j \le e_i 1 ≤ j ≤ e i is a singleton, and every element of L i , 0 L_{i,0} L i , 0 lies below the element of L i , 1 L_{i,1} L i , 1 . In either case, every element at a lower-indexed level lies below every element at a higher-indexed level.
For 1 ≤ k ≤ M 1 \le k \le M 1 ≤ k ≤ M , we set A k = { i : e i ≥ k } A_k = \{i : e_i \ge k\} A k = { i : e i ≥ k } and r k = ∣ A k ∣ r_k = |A_k| r k = ∣ A k ∣ . Since every e i ≥ 1 e_i \ge1 e i ≥ 1 , we have A 1 = { 1 , … , d } A_1 = \{1,\ldots,d\} A 1 = { 1 , … , d } and r 1 = d r_1 = d r 1 = d . Also note that, A M ⊆ A M − 1 ⊆ ⋯ ⊆ A 2 ⊆ A 1 A_M \subseteq A_{M-1} \subseteq\cdots\subseteq A_2 \subseteq A_1 A M ⊆ A M − 1 ⊆ ⋯ ⊆ A 2 ⊆ A 1 . Let V k ⊆ Q V_k \subseteq Q V k ⊆ Q consist of the tuples x = ( x 1 , … , x d ) x = (x_1,\ldots,x_d) x = ( x 1 , … , x d ) satisfying
{ x i ∈ L i , k − 1 ∪ L i , k , i ∈ A k , x i ∈ L i , e i , i ∉ A k . \begin{cases}
x_i \in L_{i,k-1} \cup L_{i,k}, & i \in A_k,\\
x_i \in L_{i,e_i}, & i \notin A_k.
\end{cases} { x i ∈ L i , k − 1 ∪ L i , k , x i ∈ L i , e i , i ∈ A k , i ∈ / A k .
Let m k m_k m k be the unique maximum of V k V_k V k , obtained by taking the element of L i , k L_{i,k} L i , k when i ∈ A k i \in A_k i ∈ A k and that of L i , e i L_{i,e_i} L i , e i otherwise, and put V k ∗ = V k ∖ { m k } V_k^* = V_k \setminus\{m_k\} V k ∗ = V k ∖ { m k } . We use the elementary fact that deleting a universal vertex does not change boxicity. After permuting the factors, ( V 1 ) o p ≅ S ∣ R ∣ × C 1 d − ∣ R ∣ = R d , ∣ R ∣ (V_1)^{\mathrm{op}} \cong S^{|R|} \times C_1^{d-|R|} = R_{d,|R|} ( V 1 ) op ≅ S ∣ R ∣ × C 1 d − ∣ R ∣ = R d , ∣ R ∣ (See the construction of R r , j R_{r,j} R r , j in § 4.5 .). Under this isomorphism, m 1 m_1 m 1 corresponds to the unique minimum of R d , ∣ R ∣ R_{d,|R|} R d , ∣ R ∣ , which is universal in its comparability graph. Therefore Lemma 4.6 gives
box ( Comp ( V 1 ∗ ) ) = d + ∣ R ∣ − 1. (4) \operatorname{box}(\operatorname{Comp}(V_1^*)) = d + |R| - 1. \tag*{(4)} box ( Comp ( V 1 ∗ )) = d + ∣ R ∣ − 1. (4)
For k ≥ 2 k \ge2 k ≥ 2 , both levels L i , k − 1 L_{i,k-1} L i , k − 1 and L i , k L_{i,k} L i , k are singletons for every i ∈ A k i \in A_k i ∈ A k . Hence ( V k ) o p ≅ C 1 r k (V_k)^{\mathrm{op}} \cong C_1^{r_k} ( V k ) op ≅ C 1 r k . Since V k ∗ V_k^* V k ∗ is obtained by deleting the unique maximum of V k V_k V k , Corollary 4.7 gives
box ( Comp ( V k ∗ ) ) = r k − 1 ( 2 ≤ k ≤ M ) . (5) \operatorname{box}(\operatorname{Comp}(V_k^*)) = r_k - 1 \qquad(2 \le k \le M). \tag*{(5)} box ( Comp ( V k ∗ )) = r k − 1 ( 2 ≤ k ≤ M ) . (5)
We now verify that these layers form an induced join.
Claim 4.9. The subgraph induced by ⋃ k = 1 M V k ∗ \bigcup_{k=1}^{M} V_k^* ⋃ k = 1 M V k ∗ is Comp ( V 1 ∗ ) ∨ Comp ( V 2 ∗ ) ∨ ⋯ ∨ Comp ( V M ∗ ) \operatorname{Comp}(V_1^*) \vee\operatorname{Comp}(V_2^*) \vee\cdots\vee\operatorname{Comp}(V_M^*) Comp ( V 1 ∗ ) ∨ Comp ( V 2 ∗ ) ∨ ⋯ ∨ Comp ( V M ∗ ) .
Proof. The vertex sets V 1 ∗ , V 2 ∗ , … , V M ∗ V_1^*, V_2^*, \ldots, V_M^* V 1 ∗ , V 2 ∗ , … , V M ∗ are pairwise disjoint. If l ≥ k + 2 l \ge k+2 l ≥ k + 2 , choose i ∈ A l i \in A_l i ∈ A l ; the i i i -th coordinates of V k V_k V k and V l V_l V l lie in disjoint sets of levels. If l = k + 1 l = k+1 l = k + 1 , a tuple belonging to both V k V_k V k and V k + 1 V_{k+1} V k + 1 must lie in L i , k L_{i,k} L i , k for every i ∈ A k i \in A_k i ∈ A k and in L i , e i L_{i,e_i} L i , e i for every i ∉ A k i \notin A_k i ∈ / A k . It is therefore m k m_k m k , which does not belong to V k ∗ V_k^* V k ∗ .
Now let k < l k < l k < l , x ∈ V k ∗ x \in V_k^* x ∈ V k ∗ , and y ∈ V l y \in V_l y ∈ V l . For each i i i , if e i < l e_i < l e i < l , then y i y_i y i is the maximum element of P i o p P_i^{\mathrm{op}} P i op , so x i ≤ y i x_i \le y_i x i ≤ y i . If e i ≥ l e_i \ge l e i ≥ l , then x i ∈ L i , k − 1 ∪ L i , k x_i \in L_{i,k-1} \cup L_{i,k} x i ∈ L i , k − 1 ∪ L i , k , y i ∈ L i , l − 1 ∪ L i , l y_i \in L_{i,l-1} \cup L_{i,l} y i ∈ L i , l − 1 ∪ L i , l , and k ≤ l − 1 k \le l - 1 k ≤ l − 1 , so again x i ≤ y i x_i \le y_i x i ≤ y i . Hence x ≤ y x \le y x ≤ y in Q Q Q . Thus the subgraph of Comp ( Q ) \operatorname{Comp}(Q) Comp ( Q ) induced by the set ⋃ k = 1 M V k ∗ \bigcup_{k=1}^{M} V_k^* ⋃ k = 1 M V k ∗ is the join ⋁ k = 1 M Comp ( V k ∗ ) \bigvee_{k=1}^{M} \operatorname{Comp}(V_k^*) ⋁ k = 1 M Comp ( V k ∗ ) .
By Lemma 2.6, (4), and (5),
box ( Comp ( Q ) ) ≥ d + ∣ R ∣ − 1 + ∑ k = 2 M ( r k − 1 ) = ∑ k = 1 M r k − M + ∣ R ∣ = ∑ i = 1 d e i − M + ∣ R ∣ . \begin{aligned}
\operatorname{box}(\operatorname{Comp}(Q)) &\ge d + |R| - 1 + \sum_{k=2}^{M}(r_k - 1) \\
&= \sum_{k=1}^{M} r_k - M + |R| \\
&= \sum_{i=1}^{d} e_i - M + |R|.
\end{aligned} box ( Comp ( Q )) ≥ d + ∣ R ∣ − 1 + k = 2 ∑ M ( r k − 1 ) = k = 1 ∑ M r k − M + ∣ R ∣ = i = 1 ∑ d e i − M + ∣ R ∣.
The last equality holds because i ∈ A k i \in A_k i ∈ A k for exactly e i e_i e i values of k k k . Finally, Comp ( Q ) = Comp ( ∏ i P i ) \operatorname{Comp}(Q) = \operatorname{Comp}(\prod_i P_i) Comp ( Q ) = Comp ( ∏ i P i ) is an induced subgraph of Comp ( ∏ i T i ) \operatorname{Comp}(\prod_i T_i) Comp ( ∏ i T i ) , which proves the lemma.
The Comparability Graph of Mixed Product of a Chain and a Special type of Rooted Tree Poset
For later use, observe that if T T T is any rooted tree poset of height b b b , then Lemma 4.3 and Lemma 4.2 give
box ( Comp ( T × C n ) ) ≤ min { b , n } + 1. (6) \operatorname{box}(\operatorname{Comp}(T \times C_n)) \le\min\{b,n\} + 1. \tag*{(6)} box ( Comp ( T × C n )) ≤ min { b , n } + 1. (6)
Lemma 4.10. Let T T T be a finite rooted tree poset of height a ≥ 1 a \ge1 a ≥ 1 , let m ≥ 1 m \ge1 m ≥ 1 , and put
q = min { a , m } . q = \min\{a,m\}. q = min { a , m } . If h 3 ( T ) ≤ q − 2 h_3(T) \le q - 2 h 3 ( T ) ≤ q − 2 and h 2 ( T ) ≤ q − 1 h_2(T) \le q - 1 h 2 ( T ) ≤ q − 1 , then
box ( Comp ( T × C m ) ) = q . (7) \operatorname{box}(\operatorname{Comp}(T \times C_m)) = q. \tag*{(7)} box ( Comp ( T × C m )) = q . (7)
Proof. Choose a leaf of maximum depth a a a , and let C a C_a C a be the induced chain of its ancestors, including the leaf. Its product with C m C_m C m is an induced C a × C m C_a \times C_m C a × C m , whose comparability graph has boxicity at least q q q by Lemma 5.5. This proves the lower bound.
We now construct a q q q -box representation by induction on q q q .
Base case 1: q = 1 q = 1 q = 1 and a = 1 ≤ m a = 1 \le m a = 1 ≤ m . The rooted tree poset T T T consists of its root ρ \rho ρ and at most two leaves because h 3 ( T ) ≤ q − 2 h_3(T) \le q - 2 h 3 ( T ) ≤ q − 2 forbids three incomparable descendants of the root. If T T T consists of only one leaf, T = C 1 T = C_1 T = C 1 and so, box ( Comp ( T × C m ) ) = 1 = q \operatorname{box}(\operatorname{Comp}(T \times C_m)) = 1 = q box ( Comp ( T × C m )) = 1 = q . Therefore, assume that T T T consists of exactly 2 leaves, say x x x and y y y .
For 0 ≤ i , j ≤ m 0 \le i,j \le m 0 ≤ i , j ≤ m , assign
I ( ρ , i ) = [ i , 2 m + 2 − i ] , I ( x , j ) = [ − 1 , j ] , I ( y , j ) = [ 2 m + 2 − j , 2 m + 3 ] . \begin{aligned}
I(\rho,i) &= [i,2m+2-i],\\
I(x,j) &= [-1,j],\\
I(y,j) &= [2m+2-j,2m+3].
\end{aligned} I ( ρ , i ) I ( x , j ) I ( y , j ) = [ i , 2 m + 2 − i ] , = [ − 1 , j ] , = [ 2 m + 2 − j , 2 m + 3 ] .
We show that this is an interval representation of Comp ( T × C m ) \operatorname{Comp}(T \times C_m) Comp ( T × C m ) .
Suppose two of its vertices ( u 1 , j 1 ) (u_1,j_1) ( u 1 , j 1 ) and ( u 2 , j 2 ) (u_2,j_2) ( u 2 , j 2 ) are adjacent; then they form a chain of length 1. Without loss of generality, assume u 1 ≤ u 2 u_1 \le u_2 u 1 ≤ u 2 and j 1 ≤ j 2 j_1 \le j_2 j 1 ≤ j 2 . If u 1 = x u_1 = x u 1 = x then u 2 u_2 u 2 must be x x x . It is clear that − 1 ∈ I ( x , j 1 ) ∩ I ( x , j 2 ) -1 \in I(x,j_1) \cap I(x,j_2) − 1 ∈ I ( x , j 1 ) ∩ I ( x , j 2 ) . Similarly, if u 1 = y u_1 = y u 1 = y then u 2 u_2 u 2 must be y y y and so, 2 m + 3 ∈ I ( y , j 1 ) ∩ I ( y , j 2 ) 2m+3 \in I(y,j_1) \cap I(y,j_2) 2 m + 3 ∈ I ( y , j 1 ) ∩ I ( y , j 2 ) . Therefore, assume u 1 = ρ u_1 = \rho u 1 = ρ . If u 2 = ρ u_2 = \rho u 2 = ρ , then m + 1 ∈ I ( ρ , j 1 ) ∩ I ( ρ , j 2 ) m+1 \in I(\rho,j_1) \cap I(\rho,j_2) m + 1 ∈ I ( ρ , j 1 ) ∩ I ( ρ , j 2 ) . If u 2 = x u_2=x u 2 = x , then I ( ρ , j 1 ) ∩ I ( x , j 2 ) ≠ ∅ I(\rho,j_1)\cap I(x,j_2)\ne\varnothing I ( ρ , j 1 ) ∩ I ( x , j 2 ) = ∅ as j 1 ≤ j 2 j_1\le j_2 j 1 ≤ j 2 . Similarly, if u 2 = y u_2=y u 2 = y , then I ( ρ , j 1 ) ∩ I ( y , j 2 ) ≠ ∅ I(\rho,j_1)\cap I(y,j_2)\ne\varnothing I ( ρ , j 1 ) ∩ I ( y , j 2 ) = ∅ as 2 m + 2 − j 2 ≤ 2 m + 2 − j 1 2m+2-j_2\le2m+2-j_1 2 m + 2 − j 2 ≤ 2 m + 2 − j 1 (since j 1 ≤ j 2 j_1\le j_2 j 1 ≤ j 2 ).
Now suppose ( u 1 , j 1 ) (u_1,j_1) ( u 1 , j 1 ) and ( u 2 , j 2 ) (u_2,j_2) ( u 2 , j 2 ) are not adjacent. Then it must be that they are incomparable. If { u 1 , u 2 } = { x , y } \{u_1,u_2\}=\{x,y\} { u 1 , u 2 } = { x , y } , the corresponding intervals are disjoint, since every x x x -interval ends at most at m m m , whereas every y y y -interval starts at least at m + 2 m+2 m + 2 . Otherwise, without loss of generality, assume that u 1 < u 2 u_1<u_2 u 1 < u 2 and j 1 > j 2 j_1>j_2 j 1 > j 2 . This forces u 1 = ρ u_1=\rho u 1 = ρ . If u 2 = x u_2=x u 2 = x , I ( ρ , j 1 ) ∩ I ( x , j 2 ) = ∅ I(\rho,j_1)\cap I(x,j_2)=\varnothing I ( ρ , j 1 ) ∩ I ( x , j 2 ) = ∅ as j 1 > j 2 j_1>j_2 j 1 > j 2 . If u 2 = y u_2=y u 2 = y , I ( ρ , j 1 ) ∩ I ( y , j 2 ) = ∅ I(\rho,j_1)\cap I(y,j_2)=\varnothing I ( ρ , j 1 ) ∩ I ( y , j 2 ) = ∅ as 2 m + 2 − j 2 > 2 m + 2 − j 1 2m+2-j_2>2m+2-j_1 2 m + 2 − j 2 > 2 m + 2 − j 1 (since j 1 > j 2 j_1>j_2 j 1 > j 2 ).
Base case 2: q = 1 q=1 q = 1 and m = 1 < a m=1<a m = 1 < a . h 2 ( T ) ≤ q − 1 h_2(T)\le q-1 h 2 ( T ) ≤ q − 1 forbids two-way branching at every positive depth, while property h 3 ( T ) ≤ q − 2 h_3(T)\le q-2 h 3 ( T ) ≤ q − 2 permits at most two branches from the root. Consequently, T T T is one root-to-leaf chain or the union of two such chains meeting only at the root.
Write v d v_d v d for the vertex at depth d d d on the first branch and w d w_d w d for the vertex at depth d d d on the second branch. Put K = a + 2 K=a+2 K = a + 2 and define
I ( ρ , 0 ) = [ − K , K ] , I ( ρ , 1 ) = [ − 1 , 1 ] I ( v d , 0 ) = [ − K , − d − 1 ] , I ( v d , 1 ) = [ − d − 1 , − 1 ] , I ( w d , 0 ) = [ d + 1 , K ] , I ( w d , 1 ) = [ 1 , d + 1 ] . \begin{aligned}
I(\rho,0)&=[-K,K], & I(\rho,1)&=[-1,1]\\
I(v_d,0)&=[-K,-d-1], & I(v_d,1)&=[-d-1,-1],\\
I(w_d,0)&=[d+1,K], & I(w_d,1)&=[1,d+1].
\end{aligned} I ( ρ , 0 ) I ( v d , 0 ) I ( w d , 0 ) = [ − K , K ] , = [ − K , − d − 1 ] , = [ d + 1 , K ] , I ( ρ , 1 ) I ( v d , 1 ) I ( w d , 1 ) = [ − 1 , 1 ] = [ − d − 1 , − 1 ] , = [ 1 , d + 1 ] .
We will show that this is an interval representation of Comp ( T × C m ) \operatorname{Comp}(T\times C_m) Comp ( T × C m ) .
If two vertices of Comp ( T × C m ) \operatorname{Comp}(T\times C_m) Comp ( T × C m ) are adjacent then their first coordinate should be from the same branch of the T T T (including the root). For convenience, we will take v 0 = w 0 = ρ v_0=w_0=\rho v 0 = w 0 = ρ . Let the two vertices adjacent in Comp ( T × C m ) \operatorname{Comp}(T\times C_m) Comp ( T × C m ) be on the first branch, say ( v d 1 , j 1 ) (v_{d_1},j_1) ( v d 1 , j 1 ) and ( v d 2 , j 2 ) (v_{d_2},j_2) ( v d 2 , j 2 ) . Then these two vertices form a chain of length 1. Without loss of generality, assume that ( v d 1 , j 1 ) ≤ ( v d 2 , j 2 ) (v_{d_1},j_1)\le(v_{d_2},j_2) ( v d 1 , j 1 ) ≤ ( v d 2 , j 2 ) . If j 1 = 1 j_1=1 j 1 = 1 , then j 2 = 1 j_2=1 j 2 = 1 . It follows that − 1 ∈ I ( v d 1 , 1 ) ∩ I ( v d 2 , 1 ) -1\in I(v_{d_1},1)\cap I(v_{d_2},1) − 1 ∈ I ( v d 1 , 1 ) ∩ I ( v d 2 , 1 ) . Therefore, assume j 1 = 0 j_1=0 j 1 = 0 . If j 2 = 0 j_2=0 j 2 = 0 , then − K ∈ I ( v d 1 , 0 ) ∩ I ( v d 2 , 0 ) -K\in I(v_{d_1},0)\cap I(v_{d_2},0) − K ∈ I ( v d 1 , 0 ) ∩ I ( v d 2 , 0 ) . Otherwise j 2 = 1 j_2=1 j 2 = 1 . If d 1 = 0 d_1=0 d 1 = 0 , then ( v d 1 , 0 ) = ( ρ , 0 ) (v_{d_1},0)=(\rho,0) ( v d 1 , 0 ) = ( ρ , 0 ) is universal and hence we are done. So d 1 ≥ 1 d_1\ge1 d 1 ≥ 1 . This forces, d 2 ≥ 1 d_2\ge1 d 2 ≥ 1 . It follows that I ( v d 1 , 0 ) ∩ I ( v d 2 , 1 ) ≠ ∅ I(v_{d_1},0)\cap I(v_{d_2},1)\ne\varnothing I ( v d 1 , 0 ) ∩ I ( v d 2 , 1 ) = ∅ since − d 2 − 1 ≤ − d 1 − 1 -d_2-1\le-d_1-1 − d 2 − 1 ≤ − d 1 − 1 (since d 1 ≤ d 2 d_1\le d_2 d 1 ≤ d 2 ). A similar argument works when the first coordinate of the vertices belong to the second branch of T T T as the endpoints of the intervals are symmetric around the origin.
If two vertices of Comp ( T × C m ) \operatorname{Comp}(T\times C_m) Comp ( T × C m ) are not adjacent then they are not comparable. The first case is when their first coordinate belongs to the same branch of T T T . Without loss of generality, suppose the vertices are of the kind ( v d 1 , j 1 ) (v_{d_1},j_1) ( v d 1 , j 1 ) and ( v d 2 , j 2 ) (v_{d_2},j_2) ( v d 2 , j 2 ) and suppose d 1 < d 2 d_1<d_2 d 1 < d 2 , j 1 > j 2 j_1>j_2 j 1 > j 2 . This forces j 1 = 1 j_1=1 j 1 = 1 and j 2 = 0 j_2=0 j 2 = 0 . Since, ( ρ , 0 ) (\rho,0) ( ρ , 0 ) is universal, we can assume v d 2 ≠ ρ v_{d_2}\ne\rho v d 2 = ρ , i.e., d 2 ≥ 1 d_2\ge1 d 2 ≥ 1 . But then, I ( v d 1 , 1 ) ∩ I ( v d 2 , 0 ) = ∅ I(v_{d_1},1)\cap I(v_{d_2},0)=\varnothing I ( v d 1 , 1 ) ∩ I ( v d 2 , 0 ) = ∅ as − d 2 − 1 < − d 1 − 1 -d_2-1<-d_1-1 − d 2 − 1 < − d 1 − 1 . A similar argument works when the first coordinate of the vertices belong to the second branch of T T T as the endpoints of the intervals are symmetric around the origin. The second case is when the first coordinate of one vertex is from the first branch and that of the other is from the second branch (none of them have first coordinate equal to ρ \rho ρ ). In this case, observe that ⋃ d ≠ 0 I ( v d , 0 ) ∪ I ( v d , 1 ) = [ − K , − 1 ] \bigcup_{d\ne0}I(v_d,0)\cup I(v_d,1)=[-K,-1] ⋃ d = 0 I ( v d , 0 ) ∪ I ( v d , 1 ) = [ − K , − 1 ] and ⋃ d ≠ 0 I ( w d , 0 ) ∪ I ( w d , 1 ) = [ 1 , K ] \bigcup_{d\ne0}I(w_d,0)\cup I(w_d,1)=[1,K] ⋃ d = 0 I ( w d , 0 ) ∪ I ( w d , 1 ) = [ 1 , K ] . Therefore, the two intervals corresponding to the two vertices do not intersect.
Induction step 1: a ≤ m a\le m a ≤ m . Here q = a ≥ 2 q=a\ge2 q = a ≥ 2 . Let ρ \rho ρ be the root, and let T 1 , … , T s T_1,\ldots,T_s T 1 , … , T s be the rooted subtree posets whose roots are the children of ρ \rho ρ . Removing the root row from T × C m T\times C_m T × C m leaves the disjoint union ⨆ i = 1 s Comp ( T i × C m ) \bigsqcup_{i=1}^{s}\operatorname{Comp}(T_i\times C_m) ⨆ i = 1 s Comp ( T i × C m ) . If T i T_i T i has height at most a − 2 a-2 a − 2 , box ( Comp ( T i × C m ) ) ≤ a − 1 \operatorname{box}(\operatorname{Comp}(T_i\times C_m))\le a-1 box ( Comp ( T i × C m )) ≤ a − 1 by (6) .
On the other hand, if T i T_i T i has height a − 1 a-1 a − 1 , h 2 ( T i ) ≤ a − 2 h_2(T_i)\le a-2 h 2 ( T i ) ≤ a − 2 and h 3 ( T i ) ≤ a − 3 h_3(T_i)\le a-3 h 3 ( T i ) ≤ a − 3 . The induction hypothesis represents Comp ( T i × C m ) \operatorname{Comp}(T_i\times C_m) Comp ( T i × C m ) in a − 1 a-1 a − 1 dimensions.
Lemma 2.7 therefore represents the entire displayed disjoint union in a − 1 a-1 a − 1 dimensions. Let I 2 , I 3 , … , I a I_2,I_3,\ldots,I_a I 2 , I 3 , … , I a be the set of interval graphs representing Comp ( ⨆ i = 1 s ( T i × C m ) ) \operatorname{Comp}(\bigsqcup_{i=1}^{s}(T_i\times C_m)) Comp ( ⨆ i = 1 s ( T i × C m )) .
For every integer 0 ≤ k ≤ m 0 \le k \le m 0 ≤ k ≤ m , make the vertex ( ρ , k ) (\rho,k) ( ρ , k ) universal in the interval graphs I 2 , I 3 , … , I a I_2,I_3,\ldots,I_a I 2 , I 3 , … , I a . Define interval graph I 1 I_1 I 1 by the assignment given as follows.
I 1 ( v , j ) = { [ 0 , j ] if v ≠ ρ , [ j , m ] if v = ρ . I_1(v,j)=
\begin{cases}
[0,j] & \text{if } v \ne\rho,\\
[j,m] & \text{if } v=\rho.
\end{cases} I 1 ( v , j ) = { [ 0 , j ] [ j , m ] if v = ρ , if v = ρ .
All nonroot intervals contain 0 0 0 , so this interval graph changes no adjacency among the nonroot vertices. Moreover, for v ≠ ρ v \ne\rho v = ρ , 1 ≤ k ≤ m 1 \le k \le m 1 ≤ k ≤ m , and 0 ≤ j ≤ m 0 \le j \le m 0 ≤ j ≤ m
I 1 ( ρ , k ) ∩ I 1 ( v , j ) ≠ ∅ ⟺ k ≤ j , I_1(\rho,k) \cap I_1(v,j) \ne\varnothing\quad\Longleftrightarrow\quad k \le j, I 1 ( ρ , k ) ∩ I 1 ( v , j ) = ∅ ⟺ k ≤ j ,
which is precisely the condition ( ρ , k ) ≤ ( v , j ) (\rho,k) \le(v,j) ( ρ , k ) ≤ ( v , j ) . We obtain an a = q a=q a = q dimensional representation.
Induction step 2: m < a m<a m < a . Here q = m ≥ 2 q=m\ge2 q = m ≥ 2 . Consider the following induced subgraph H = { ( v , j ) : v ≠ ρ , 1 ≤ j ≤ m } H=\{(v,j):v\ne\rho,\ 1\le j\le m\} H = {( v , j ) : v = ρ , 1 ≤ j ≤ m } . After replacing j j j by j − 1 j-1 j − 1 , it is the disjoint union
H ≅ ⨆ i = 1 s Comp ( T i × C m − 1 ) . H \cong\bigsqcup_{i=1}^{s} \operatorname{Comp}(T_i \times C_{m-1}). H ≅ i = 1 ⨆ s Comp ( T i × C m − 1 ) .
If T i T_i T i has smaller height, Comp ( T i × C m − 1 ) \operatorname{Comp}(T_i \times C_{m-1}) Comp ( T i × C m − 1 ) uses at most m − 1 m-1 m − 1 dimensions by (6) . On the other hand, if T i T_i T i has height at least m − 1 m-1 m − 1 , then h 2 ( T i ) ≤ m − 2 h_2(T_i)\le m-2 h 2 ( T i ) ≤ m − 2 and h 3 ( T i ) ≤ m − 3 h_3(T_i)\le m-3 h 3 ( T i ) ≤ m − 3 . Therefore, the induction hypothesis gives an ( m − 1 ) (m-1) ( m − 1 ) -box representation.
By Lemma 2.7, we have m − 1 m-1 m − 1 interval graphs I 2 , I 3 , … , I m I_2,I_3,\ldots,I_m I 2 , I 3 , … , I m whose intersection give H H H .
For 2 ≤ i ≤ m 2\le i\le m 2 ≤ i ≤ m and v ≠ ρ v\ne\rho v = ρ , define I i ( v , 0 ) = I i ( v , 1 ) I_i(v,0)=I_i(v,1) I i ( v , 0 ) = I i ( v , 1 ) . For every integer k k k with 0 ≤ k ≤ m 0\le k\le m 0 ≤ k ≤ m , make the vertex ( ρ , k ) (\rho,k) ( ρ , k ) universal in each of the interval graphs I 2 , I 3 , … , I m I_2,I_3,\ldots,I_m I 2 , I 3 , … , I m . Let d ( v ) = depth T ( v ) d(v)=\operatorname{depth}_T(v) d ( v ) = depth T ( v ) and put K = a + 1 K=a+1 K = a + 1 . Define the interval graph I 1 I_1 I 1 by the following assignment
I 1 ( v , j ) = { [ − K , − d ( v ) ] if v ≠ ρ and j = 0 , [ − d ( v ) , K ] if v ≠ ρ and j = 1 , [ − K , j K ] if v ≠ ρ and j ≥ 2 , [ − K , m K ] if v = ρ and j = 0 , [ j K , m K ] if v = ρ and j ≥ 1. I_1(v,j)=
\begin{cases}
[-K,-d(v)] & \text{if } v\ne\rho\text{ and } j=0,\\
[-d(v),K] & \text{if } v\ne\rho\text{ and } j=1,\\
[-K,jK] & \text{if } v\ne\rho\text{ and } j\ge2,\\
[-K,mK] & \text{if } v=\rho\text{ and } j=0,\\
[jK,mK] & \text{if } v=\rho\text{ and } j\ge1.
\end{cases} I 1 ( v , j ) = ⎩ ⎨ ⎧ [ − K , − d ( v )] [ − d ( v ) , K ] [ − K , j K ] [ − K , m K ] [ j K , m K ] if v = ρ and j = 0 , if v = ρ and j = 1 , if v = ρ and j ≥ 2 , if v = ρ and j = 0 , if v = ρ and j ≥ 1.
It only remains to check the adjacency and non-adjacency of pairs involving newly attached vertices.
Two vertices ( v , 0 ) , ( w , 0 ) (v,0),(w,0) ( v , 0 ) , ( w , 0 ) with v ≠ ρ v\ne\rho v = ρ and w ≠ ρ w\ne\rho w = ρ are adjacent in I 1 I_1 I 1 as − K ∈ I 1 ( v , 0 ) ∩ I 1 ( w , 0 ) -K\in I_1(v,0)\cap I_1(w,0) − K ∈ I 1 ( v , 0 ) ∩ I 1 ( w , 0 ) . Therefore, ( v , 0 ) (v,0) ( v , 0 ) and ( w , 0 ) (w,0) ( w , 0 ) are adjacent in I 1 ∩ I 2 ∩ ⋯ I m I_1\cap I_2\cap\cdots I_m I 1 ∩ I 2 ∩ ⋯ I m if and only if ( v , 1 ) (v,1) ( v , 1 ) and ( w , 1 ) (w,1) ( w , 1 ) are adjacent in I 2 ∩ I 3 ∩ ⋯ I m I_2\cap I_3\cap\cdots I_m I 2 ∩ I 3 ∩ ⋯ I m , which is true if and only if v v v and w w w are comparable in T T T . This is exactly the requirement for the adjacency of ( v , 0 ) (v,0) ( v , 0 ) and ( w , 0 ) (w,0) ( w , 0 ) .
Two vertices ( v , 0 ) (v,0) ( v , 0 ) and ( w , 1 ) (w,1) ( w , 1 ) with v ≠ ρ v\ne\rho v = ρ and w ≠ ρ w\ne\rho w = ρ are adjacent in I 1 I_1 I 1 if and only if − d ( w ) ≤ − d ( v ) -d(w)\le-d(v) − d ( w ) ≤ − d ( v ) , i.e., d ( v ) ≤ d ( w ) d(v)\le d(w) d ( v ) ≤ d ( w ) . Moreover, since I i ( v , 0 ) = I i ( v , 1 ) I_i(v,0)=I_i(v,1) I i ( v , 0 ) = I i ( v , 1 ) for every 2 ≤ i ≤ m 2\le i\le m 2 ≤ i ≤ m , the vertices ( v , 0 ) (v,0) ( v , 0 ) and ( w , 1 ) (w,1) ( w , 1 ) are adjacent in I 2 ∩ ⋯ ∩ I m I_2\cap\cdots\cap I_m I 2 ∩ ⋯ ∩ I m if and only if v v v and w w w are comparable in T T T . Combining this with the condition d ( v ) ≤ d ( w ) d(v)\le d(w) d ( v ) ≤ d ( w ) imposed by I 1 I_1 I 1 , we conclude that ( v , 0 ) (v,0) ( v , 0 ) and ( w , 1 ) (w,1) ( w , 1 ) are adjacent in I 1 ∩ ⋯ ∩ I m I_1\cap\cdots\cap I_m I 1 ∩ ⋯ ∩ I m if and only if v ≤ w v\le w v ≤ w . This is precisely the condition for ( v , 0 ) (v,0) ( v , 0 ) and ( w , 1 ) (w,1) ( w , 1 ) to be comparable in T × C m T\times C_m T × C m .
If j ≥ 2 j\ge2 j ≥ 2 , v ≠ ρ v\ne\rho v = ρ and w ≠ ρ w\ne\rho w = ρ the adjacency of ( v , 0 ) (v,0) ( v , 0 ) and ( w , j ) (w,j) ( w , j ) is completely determined by I 2 , I 3 , … , I m I_2,I_3,\ldots,I_m I 2 , I 3 , … , I m .
The vertex ( ρ , 0 ) (\rho,0) ( ρ , 0 ) is universal. For v ≠ ρ v\ne\rho v = ρ , 0 ≤ j ≤ m 0\le j\le m 0 ≤ j ≤ m , and 1 ≤ k ≤ m 1\le k\le m 1 ≤ k ≤ m , we have,
I 1 ( ρ , k ) ∩ I 1 ( v , j ) ≠ ∅ ⟺ k ≤ j . I_1(\rho,k)\cap I_1(v,j)\ne\varnothing\quad\Longleftrightarrow\quad k\le j. I 1 ( ρ , k ) ∩ I 1 ( v , j ) = ∅ ⟺ k ≤ j .
Moreover, I 1 ( ρ , k 1 ) ∩ I 1 ( ρ , k 2 ) ≠ ∅ I_1(\rho,k_1)\cap I_1(\rho,k_2)\ne\varnothing I 1 ( ρ , k 1 ) ∩ I 1 ( ρ , k 2 ) = ∅ for 0 ≤ k 1 , k 2 ≤ m 0\le k_1,k_2\le m 0 ≤ k 1 , k 2 ≤ m .
Thus, I 1 , I 2 , … , I m I_1,I_2,\ldots,I_m I 1 , I 2 , … , I m gives an m = q m=q m = q dimensional representation. This completes the induction. □
The Boxicity of Power Graphs of Nilpotent Groups
We will now explore the boxicity of power graphs associated with nilpotent groups. In the first subsection § 5.1 , we will examine the structure of power graphs that arise from finite nilpotent groups, specifically in relation to the cyclic subgroup poset. The next subsection (§ 5.2 ) focuses on cyclic groups, a specific subclass of finite nilpotent groups. The findings in this subsection primarily rely on § 4.5 and previously established results from [15 ] . In the subsequent sections, we will extend these results to encompass all finite nilpotent groups. We will first present an upper bound applicable to all finite nilpotent groups (§ 5.3 ), and then we will proceed to determine the exact boxicity based on the structural characteristics of the nilpotent group (§ 5.5 ).
Structure of Power Graphs of Finite Nilpotent Groups
In this section, we explore the structure of the power graph associated with a finite nilpotent group G G G , focusing specifically on the poset C ( G ) \mathcal{C}(G) C ( G ) of cyclic subgroups of G G G . Our objective is to investigate the boxicity of these graphs, and Lemma 2.4 suggests that a thorough analysis of the poset structure suffices for our purposes. Although Equation (1) provides the final expression, it is essential to first write the preliminary lemma. This lemma follows almost immediately as a corollary from the discussion of subgroup lattice of direct products of groups in [39 Lemma 1.6.4] . By doing their arguments for the cyclic subgroups, we get Lemma 5.1. A more general statement is mentioned in [26 Section 2] in terms of the number of cyclic subgroups of the direct product of two groups with coprime order.
Lemma 5.1. Let G G G be a finite nilpotent group and G = ∏ i S p i G = \prod_i S_{p_i} G = ∏ i S p i , where S p i S_{p_i} S p i denotes the Sylow p i p_i p i -subgroup of G G G . Then C ( G ) ≅ ∏ i C ( S p i ) \mathcal{C}(G) \cong\prod_i \mathcal{C}(S_{p_i}) C ( G ) ≅ ∏ i C ( S p i ) as the product of posets.
The following lemma collects standard facts about the cyclic-subgroup poset of a finite p p p -group. The tree property is explicitly noted in the proof of Proposition 4.1 of Leifman and Muzychuk [30 ] ; it also follows from the edge-counting formula in Lemma 2.2 of Tărnăuceanu [43 ] , as illustrated in the proof of his Theorem 1.1. Cameron, Reddy and Sharma [9 Theorems 2.6 and 2.4(2)] give tree and path characterisations for cyclic subgroup graphs , which yield the corresponding tree and chain assertions here. We include a self-contained proof for completeness and to record the relation between the height of the poset and the exponent of the group explicitly.
Lemma 5.2. Let S p S_p S p be a finite p p p -group of exponent p e p^e p e .
(a) C ( S p ) \mathcal{C}(S_p) C ( S p ) is a rooted tree poset of height e e e .
(b) C ( S p ) \mathcal{C}(S_p) C ( S p ) is a chain if and only if S p S_p S p is cyclic.
Proof. (a) Let U = ⟨ u ⟩ U = \langle u\rangle U = ⟨ u ⟩ be cyclic of order p k p^k p k , where k ≥ 1 k \ge1 k ≥ 1 . A cyclic group of order p k p^k p k has exactly one subgroup of order p k − 1 p^{k-1} p k − 1 , namely ⟨ u p ⟩ \langle u^p\rangle ⟨ u p ⟩ . Therefore, every non-root node of C ( S p ) \mathcal{C}(S_p) C ( S p ) has a unique element strictly below it in the cover graph. Repeatedly taking the lower cover reaches the trivial subgroup, so the cover graph is a rooted tree.
Because S p S_p S p has exponent p e p^e p e , it contains an element of order p e p^e p e and no element of larger order. The maximum root-to-node distance is therefore e e e .
(b) If S p S_p S p is cyclic, it has exactly one subgroup of each order 1 , p , … , p e 1,p,\ldots,p^e 1 , p , … , p e , so C ( S p ) \mathcal{C}(S_p) C ( S p ) is a chain. Conversely, suppose C ( S p ) \mathcal{C}(S_p) C ( S p ) is a chain. Let U U U be its largest member. For every x ∈ S p x \in S_p x ∈ S p , the cyclic subgroup ⟨ x ⟩ \langle x\rangle ⟨ x ⟩ is comparable with and hence contained in U U U . Thus, every element of S p S_p S p lies in U U U , so S p = U S_p = U S p = U is cyclic. ∎
Combining Lemmas 2.4, 5.1, and 5.2, we obtain the following formulation, when G = ∏ i S p i G = \prod_i S_{p_i} G = ∏ i S p i is a finite nilpotent group:
box ( Pow ( G ) ) = box ( Comp ( ∏ i T i ) ) , T i = C ( S p i ) , (8) \operatorname{box}(\operatorname{Pow}(G)) = \operatorname{box}\left(\operatorname{Comp}\left(\prod_i T_i\right)\right), \qquad T_i = \mathcal{C}(S_{p_i}), \tag*{(8)} box ( Pow ( G )) = box ( Comp ( i ∏ T i ) ) , T i = C ( S p i ) , (8)
where T i T_i T i is a rooted tree poset of height e i e_i e i (where exp ( S p i ) = p i e i \exp(S_{p_i}) = p_i^{e_i} exp ( S p i ) = p i e i ) and is a chain exactly when S p i S_{p_i} S p i is cyclic. In particular, we have the following for the power graph of the cyclic group Z n \mathbb{Z}_n Z n , where n = ∏ i p i e i n = \prod_i p_i^{e_i} n = ∏ i p i e i :
box ( Pow ( Z n ) ) = box ( Comp ( ∏ i C i ) ) , (9) \operatorname{box}(\operatorname{Pow}(\mathbb{Z}_n)) = \operatorname{box}\left(\operatorname{Comp}\left(\prod_i C_i\right)\right), \tag*{(9)} box ( Pow ( Z n )) = box ( Comp ( i ∏ C i ) ) , (9)
where C i C_i C i is a chain of length e i e_i e i .
The Boxicity for Power Graphs of Cyclic Groups
For a cyclic group Z n \mathbb{Z}_n Z n of order n = ∏ i p i e i n = \prod_i p_i^{e_i} n = ∏ i p i e i , (8) gives the following: box ( Pow ( Z n ) ) = box ( Comp ( ∏ i C e i ) ) \operatorname{box}(\operatorname{Pow}(\mathbb{Z}_n)) = \operatorname{box}(\operatorname{Comp}(\prod_i C_{e_i})) box ( Pow ( Z n )) = box ( Comp ( ∏ i C e i )) , where C e i C_{e_i} C e i denotes the chain poset of length e i e_i e i . Recall that Chandran and Ghosh [15 ] established the following upper bound, which is also stated in (a) of Theorem 1.2 .
Lemma 5.3. [15 Cor. 1] Let n = ∏ i = 1 d p i e i n = \prod_{i=1}^{d} p_i^{e_i} n = ∏ i = 1 d p i e i . Then box ( Pow ( Z n ) ) ≤ E − M \operatorname{box}(\operatorname{Pow}(\mathbb{Z}_n)) \le E - M box ( Pow ( Z n )) ≤ E − M , where E = ∑ i e i E = \sum_i e_i E = ∑ i e i and M = max i e i M = \max_i e_i M = max i e i .
Chandran and Ghosh [15 ] showed the following lemma.
Lemma 5.4 ([15 ] ). Let 1 ≤ e 1 ≤ e 2 ≤ ⋯ ≤ e d 1 \le e_1 \le e_2 \le\cdots\le e_d 1 ≤ e 1 ≤ e 2 ≤ ⋯ ≤ e d be d d d natural numbers, where d ≥ 2 d \ge2 d ≥ 2 . Let n = p 1 e 1 p 2 e 2 ⋯ p d e d n = p_1^{e_1}p_2^{e_2}\cdots p_d^{e_d} n = p 1 e 1 p 2 e 2 ⋯ p d e d , where p 1 , p 2 , … , p d p_1,p_2,\ldots,p_d p 1 , p 2 , … , p d are pairwise distinct primes. Then box ( Pow ( Z n ) ) ≥ e 1 f ( d ) + ( e 2 − e 1 ) f ( d − 1 ) + ( e 3 − e 2 ) f ( d − 2 ) + ⋯ + ( e d − 1 − e d − 2 ) f ( 2 ) \operatorname{box}(\operatorname{Pow}(\mathbb{Z}_n)) \ge e_1f(d) + (e_2-e_1)f(d-1) + (e_3-e_2)f(d-2) + \cdots+ (e_{d-1}-e_{d-2})f(2) box ( Pow ( Z n )) ≥ e 1 f ( d ) + ( e 2 − e 1 ) f ( d − 1 ) + ( e 3 − e 2 ) f ( d − 2 ) + ⋯ + ( e d − 1 − e d − 2 ) f ( 2 ) .
In fact, parts (b) and (c) of Theorem 1.2 are a consequence of Lemma 5.4 and the fact that for r ≥ 2 r \ge2 r ≥ 2 , f ( r ) ≥ ⌈ r 2 ⌉ f(r) \ge\left\lceil\frac{r}{2} \right\rceil f ( r ) ≥ ⌈ 2 r ⌉ . Consequently, an improvement of the lower bound on f ( r ) f(r) f ( r ) gives an improved lower bound for box ( Pow ( Z n ) ) \operatorname{box}(\operatorname{Pow}(\mathbb{Z}_n)) box ( Pow ( Z n )) for free. Substituting the optimal value of f ( r ) f(r) f ( r ) , which is f ( r ) = r − 1 f(r) = r-1 f ( r ) = r − 1 (obtained in Corollary 4.7, and also in Lemma A.6 ) for r = d , d − 1 , … , 2 r = d,d-1,\ldots,2 r = d , d − 1 , … , 2 , in the above formula of Lemma 5.4, we get the following lower bound. Note that this lower bound matches the upper bound proved by Chandran and Ghosh [15 ] , stated in Lemma 5.3.
Lemma 5.5. Let e 1 , … , e d ≥ 1 e_1,\ldots,e_d \ge1 e 1 , … , e d ≥ 1 . Then box ( Comp ( ∏ i = 1 d C e i ) ) ≥ E − M \operatorname{box}(\operatorname{Comp}(\prod_{i=1}^{d} C_{e_i})) \ge E-M box ( Comp ( ∏ i = 1 d C e i )) ≥ E − M .
Now we are ready to prove our first main theorem, Theorem 1.3 .
Proof of Theorem 1.3. Combining Lemma 5.5, (8) and Lemma 5.3, we have the following: if n = ∏ i = 1 d p i e i n = \prod_{i=1}^{d} p_i^{e_i} n = ∏ i = 1 d p i e i , then box ( Pow ( Z n ) ) = box ( Comp ( ∏ i C e i ) ) = E − M \operatorname{box}(\operatorname{Pow}(\mathbb{Z}_n)) = \operatorname{box}(\operatorname{Comp}(\prod_i C_{e_i})) = E-M box ( Pow ( Z n )) = box ( Comp ( ∏ i C e i )) = E − M . □
The Universal Upper Bound for Arbitrary Nilpotent Groups
We now extend the cyclic upper bound to arbitrary finite nilpotent groups. The proof is relatively straightforward and can be easily derived from the lemmas and tools we have previously discussed.
Lemma 5.6. Let G = S p 1 × S p 2 × ⋯ × S p k G = S_{p_1} \times S_{p_2} \times\cdots\times S_{p_k} G = S p 1 × S p 2 × ⋯ × S p k be a finite nilpotent group. Then box ( Pow ( G ) ) ≤ box ( Pow ( Z exp ( G ) ) ) + s ( G ) \operatorname{box}(\operatorname{Pow}(G)) \le\operatorname{box}(\operatorname{Pow}(\mathbb{Z}_{\exp(G)})) + s(G) box ( Pow ( G )) ≤ box ( Pow ( Z e x p ( G ) )) + s ( G ) , where s ( G ) s(G) s ( G ) is the number of non-cyclic Sylow subgroups of G G G .
Proof. Suppose exp ( S p i ) = p e i \exp(S_{p_i})=p^{e_i} exp ( S p i ) = p e i . Note that exp ( G ) = ∏ i p i e i \exp(G)=\prod_i p_i^{e_i} exp ( G ) = ∏ i p i e i (by using Lemma 5.1 ). Due to Equation (8) , it is enough to prove the upper bound of box ( Comp ( ∏ i T i ) ) \operatorname{box}(\operatorname{Comp}(\prod_i T_i)) box ( Comp ( ∏ i T i )) , where T i T_i T i denotes the rooted tree poset arising from the Sylow p i p_i p i -subgroup S p i S_{p_i} S p i . Since exp ( S p i ) = p e i \exp(S_{p_i})=p^{e_i} exp ( S p i ) = p e i , height of the rooted tree poset T i T_i T i is e i e_i e i . Let S ( G ) = { i ∈ [ k ] : S p i is non-cyclic } S(G)=\{i\in[k]:S_{p_i}\text{ is non-cyclic}\} S ( G ) = { i ∈ [ k ] : S p i is non-cyclic } . Then s ( G ) = ∣ S ( G ) ∣ s(G)=|S(G)| s ( G ) = ∣ S ( G ) ∣ . Hence, from Equation (8) , it is clear that for i ∉ S ( G ) i\notin S(G) i ∈ / S ( G ) , the rooted tree poset T i T_i T i is indeed a chain of height/length e i e_i e i .
box ( Comp ( ∏ i T i ) ) = box ( Comp ( ∏ i ∈ S ( G ) T i × ∏ i ∉ S ( G ) C e i ) ) ≤ box ( Comp ( ∏ i C e i ) ) + s ( G ) (Lemma 4.3) = box ( Pow ( Z exp ( G ) ) ) + s ( G ) . (10) \begin{aligned}
\operatorname{box}\left(\operatorname{Comp}\left(\prod_i T_i\right)\right)
=
\operatorname{box}\left(\operatorname{Comp}\left(\prod_{i\in S(G)}T_i\times\prod_{i\notin S(G)}C_{e_i}\right)\right) \\
&\leq\operatorname{box}\left(\operatorname{Comp}\left(\prod_i C_{e_i}\right)\right)+s(G)
\qquad\text{(Lemma 4.3)} \\
&= \operatorname{box}\left(\operatorname{Pow}\left(\mathbb{Z}_{\exp(G)}\right)\right)+s(G). \tag*{(10)}
\end{aligned} box ( Comp ( i ∏ T i ) ) = box Comp i ∈ S ( G ) ∏ T i × i ∈ / S ( G ) ∏ C e i ≤ box ( Comp ( i ∏ C e i ) ) + s ( G ) (Lemma 4.3) = box ( Pow ( Z e x p ( G ) ) ) + s ( G ) . (10)
Lower Bound Due to Odd Order Non-Cyclic Sylow Subgroups
The previous upper bound of box ( Pow ( G ) ) \operatorname{box}(\operatorname{Pow}(G)) box ( Pow ( G )) for an arbitrary nilpotent group G G G treats each rooted tree poset T i T_i T i , which arises from a non-cyclic Sylow subgroup S p i S_{p_i} S p i of G G G , uniformly. For the lower bound, we observe that the structure of a rooted tree poset necessitates the introduction of an additional dimension, coordinate, or interval. We also show that for odd primes, there is sufficient branching at the terminal level of the rooted tree posets associated with the corresponding Sylow subgroups.
For this, we establish a property of the cyclic subgroup poset of a noncyclic p p p -group with odd p p p (in Lemma 5.9 ), which is used to establish our lower bound in Corollary 5.10. First, we recall the standard normalizer condition for finite p p p -groups, stated in the next lemma; see, for example, [24 Sec 6.1, Th 1] . Let g A g − 1 = { g a g − 1 : a ∈ A } gAg^{-1}=\{gag^{-1}:a\in A\} g A g − 1 = { g a g − 1 : a ∈ A } . The normalizer of A A A in G G G to be the set N G ( A ) = { g ∈ G : g A g − 1 = A } N_G(A)=\{g\in G:gAg^{-1}=A\} N G ( A ) = { g ∈ G : g A g − 1 = A } .
Lemma 5.7. [24 ] Let G G G be a finite p p p -group and let H < G H<G H < G . Then H < N G ( H ) H<N_G(H) H < N G ( H ) .
We will now discuss the main observation (see Lemma 5.9 ) of this subsection. For the argument concerning the non-abelian case, we refer to the following statement from Suzuki’s classification theorem [41 Theorem 4.1] . Here, G = ⟨ T ∣ R ⟩ G=\langle T\mid R\rangle G = ⟨ T ∣ R ⟩ denotes a generator-relation presentation of a group G G G , where the set T T T generates the group G G G and R R R contains the relations that the elements of T T T satisfy.
Lemma 5.8. [41 ] Let p p p be odd and G G G be a finite nonabelian p p p -group of order p n p^n p n possessing a cyclic maximal subgroup. Then G ≅ M ( p n ) G\cong M(p^n) G ≅ M ( p n ) , where, for n ≥ 3 n\geq3 n ≥ 3 , M ( p n ) = ⟨ a , b ∣ a p n − 1 = b p = 1 , b − 1 a b = a 1 + p n − 2 ⟩ M(p^n)=\left\langle a,b\mid a^{p^{n-1}}=b^p=1,\ b^{-1}ab=a^{1+p^{n-2}}\right\rangle M ( p n ) = ⟨ a , b ∣ a p n − 1 = b p = 1 , b − 1 ab = a 1 + p n − 2 ⟩ .
We acknowledge that the following lemma is not a new result, and while it may have been noted by some group theorists, we have not found it stated verbatim. Therefore, we present the proof here.
Lemma 5.9. Let p p p be an odd prime, and let G G G be a finite noncyclic p p p -group of exponent p e p^e p e . Then there exists a cyclic subgroup U ≤ G U\leq G U ≤ G of order p e − 1 p^{e-1} p e − 1 that is contained in at least three distinct cyclic subgroups of order p e p^e p e .
Proof. The case e = 1 e=1 e = 1 is trivial. Then every nonidentity element of G G G has order p p p . Distinct subgroups of order p p p intersect only in the identity, and each such subgroup contains exactly p − 1 p-1 p − 1 nonidentity elements. Hence, the number of subgroups of order p p p is ∣ G ∣ − 1 p − 1 \frac{|G|-1}{p-1} p − 1 ∣ G ∣ − 1 . Since G G G is noncyclic, ∣ G ∣ ≥ p 2 |G| \ge p^2 ∣ G ∣ ≥ p 2 , and therefore ∣ G ∣ − 1 p − 1 ≥ p 2 − 1 p − 1 = p + 1 ≥ 4 \frac{|G|-1}{p-1} \ge\frac{p^2-1}{p-1}=p+1\ge4 p − 1 ∣ G ∣ − 1 ≥ p − 1 p 2 − 1 = p + 1 ≥ 4 . Thus the trivial subgroup U = { 1 } U=\{1\} U = { 1 } , of order p e − 1 = 1 p^{e-1}=1 p e − 1 = 1 , is contained in at least three cyclic subgroups of order p p p . This proves the lemma when e = 1 e=1 e = 1 .
For the rest of our discussion, we assume that e ≥ 2 e\ge2 e ≥ 2 . Since G G G is a finite group, exp ( G ) = p e \exp(G)=p^e exp ( G ) = p e implies that some element g ∈ G g\in G g ∈ G has order exactly p e p^e p e . Let A = ⟨ g ⟩ A=\langle g\rangle A = ⟨ g ⟩ . Then ∣ A ∣ = p e |A|=p^e ∣ A ∣ = p e . Since G G G is noncyclic, A < G A<G A < G . By Lemma 5.7 A < N G ( A ) A<N_G(A) A < N G ( A ) . By the definition of the normaliser, A ⊴ N G ( A ) A\unlhd N_G(A) A ⊴ N G ( A ) , so N G ( A ) / A N_G(A)/A N G ( A ) / A is a nontrivial finite p p p -group. Hence, by Cauchy’s theorem, it contains a subgroup K ′ K' K ′ of order p p p .
Let π : N G ( A ) ⟶ N G ( A ) / A \pi:N_G(A)\longrightarrow N_G(A)/A π : N G ( A ) ⟶ N G ( A ) / A , defined by π ( x ) = x A \pi(x)=xA π ( x ) = x A , be the natural quotient homomorphism. Put K = π − 1 ( K ′ ) K=\pi^{-1}(K') K = π − 1 ( K ′ ) . Since the preimage of a subgroup under a homomorphism is a subgroup, K ≤ N G ( A ) ≤ G K\le N_G(A)\le G K ≤ N G ( A ) ≤ G . Moreover, ker ( π ) = A ≤ K \ker(\pi)=A\le K ker ( π ) = A ≤ K , and the restriction π ∣ K : K ⟶ K ′ \pi|_K:K\longrightarrow K' π ∣ K : K ⟶ K ′ is surjective with kernel A A A . The First Isomorphism Theorem, therefore, gives K / A ≅ K ′ K/A\cong K' K / A ≅ K ′ . Consequently, [ K : A ] = p [K:A]=p [ K : A ] = p and ∣ K ∣ = p e + 1 |K|=p^{e+1} ∣ K ∣ = p e + 1 . This implies that A A A is a maximal subgroup of K K K . Also, A A A is cyclic by construction.
Moreover exp ( K ) ∣ p e \exp(K)\mid p^e exp ( K ) ∣ p e , because K ≤ G K\le G K ≤ G . On the other hand, K K K contains g g g , whose order is p e p^e p e . Hence exp ( K ) = p e \exp(K)=p^e exp ( K ) = p e . So K K K is noncyclic.
We now analyse the possible structure of K K K . If K K K is abelian, we can write its standard decomposition as K ≅ Z p λ 1 × ⋯ × Z p λ r K\cong\mathbb{Z}_{p^{\lambda_1}}\times\cdots\times\mathbb{Z}_{p^{\lambda_r}} K ≅ Z p λ 1 × ⋯ × Z p λ r , λ 1 ≥ ⋯ ≥ λ r ≥ 1 \lambda_1\ge\cdots\ge\lambda_r\ge1 λ 1 ≥ ⋯ ≥ λ r ≥ 1 . By our discussion so far, it is easy to see that λ 1 = e \lambda_1=e λ 1 = e , r = 2 r=2 r = 2 and λ 2 = 1 \lambda_2=1 λ 2 = 1 , so K ≅ Z p e × Z p K\cong\mathbb{Z}_{p^e}\times\mathbb{Z}_p K ≅ Z p e × Z p . If K K K is nonabelian, then K K K is a nonabelian p p p -group with a cyclic maximal subgroup A A A . Since p p p is odd, Suzuki’s classification theorem (mentioned in Lemma 5.8 ) gives K ≅ M ( p e + 1 ) K\cong M(p^{e+1}) K ≅ M ( p e + 1 ) .
We will complete the proof in the following two cases.
Case 1: K K K is abelian, i.e., K ≅ Z p e × Z p K\cong\mathbb{Z}_{p^e}\times\mathbb{Z}_p K ≅ Z p e × Z p . We choose generators a a a and b b b such that K = ⟨ a ⟩ × ⟨ b ⟩ K=\langle a\rangle\times\langle b\rangle K = ⟨ a ⟩ × ⟨ b ⟩ , o ( a ) = p e o(a)=p^e o ( a ) = p e , o ( b ) = p o(b)=p o ( b ) = p . For each i ∈ { 0 , 1 , … , p − 1 } i\in\{0,1,\ldots,p-1\} i ∈ { 0 , 1 , … , p − 1 } , define x i = a b − i x_i=ab^{-i} x i = a b − i . Because a a a and b b b commute and b p = 1 b^p=1 b p = 1 , x i p = a p x_i^p=a^p x i p = a p .
Case 2: K K K is non-abelian, i.e., K ≅ M ( p e + 1 ) K\cong M(p^{e+1}) K ≅ M ( p e + 1 ) . We use the presentation of M ( p n ) M(p^n) M ( p n ) with n = e + 1 n=e+1 n = e + 1 stated in Lemma 5.8 and put q = 1 + p e − 1 q=1+p^{e-1} q = 1 + p e − 1 . Note that here M ( p e + 1 ) ≅ Z p e ⋊ Z p M(p^{e+1})\cong\mathbb{Z}_{p^e}\rtimes\mathbb{Z}_p M ( p e + 1 ) ≅ Z p e ⋊ Z p . Moreover, we choose generators a , b a,b a , b of K K K satisfying the relations a p e = b p = 1 a^{p^e}=b^p=1 a p e = b p = 1 , b − 1 a b = a q b^{-1}ab=a^q b − 1 ab = a q . The last relation yields b − j a b j = a q j b^{-j}ab^j=a^{q^j} b − j a b j = a q j , for j ≥ 0 j\ge0 j ≥ 0 .
For i ∈ { 0 , 1 , … , p − 1 } i\in\{0,1,\ldots,p-1\} i ∈ { 0 , 1 , … , p − 1 } , we again define x i = a b − i x_i=ab^{-i} x i = a b − i . The following results from repeatedly applying the group operation of M ( p e + 1 ) M(p^{e+1}) M ( p e + 1 ) .
x i p = ( a b − i ) p = a ( b − i a b i ) ( b − 2 i a b 2 i ) ⋯ ( b − ( p − 1 ) i a b ( p − 1 ) i ) b − p i = a 1 + ∑ j = 1 p − 1 q j i . \begin{aligned}
x_i^p&=(ab^{-i})^p\\
&=a\left(b^{-i}ab^i\right)\left(b^{-2i}ab^{2i}\right)\cdots\left(b^{-(p-1)i}ab^{(p-1)i}\right)b^{-pi}\\
&=a^{1+\sum_{j=1}^{p-1}q^{ji}}.
\end{aligned} x i p = ( a b − i ) p = a ( b − i a b i ) ( b − 2 i a b 2 i ) ⋯ ( b − ( p − 1 ) i a b ( p − 1 ) i ) b − p i = a 1 + ∑ j = 1 p − 1 q j i .
Since e ≥ 2 e\ge2 e ≥ 2 , q j i ≡ 1 + j i p e − 1 ( m o d p e ) q^{ji}\equiv1+ji p^{e-1}\pmod{p^e} q j i ≡ 1 + j i p e − 1 ( mod p e ) . It follows that
1 + ∑ j = 1 p − 1 q j i ≡ ∑ j = 0 p − 1 ( 1 + j i p e − 1 ) ( m o d p e ) = p + i p e − 1 p ( p − 1 ) 2 = p + i p e p − 1 2 ≡ p ( m o d p e ) . (11) \begin{aligned}
1+\sum_{j=1}^{p-1}q^{ji}
&\equiv\sum_{j=0}^{p-1}(1+ji p^{e-1})\pmod{p^e}\\
&=p+ip^{e-1}\frac{p(p-1)}{2}\\
&=p+ip^{e}\frac{p-1}{2}\\
&\equiv p\pmod{p^e}. \tag*{(11)}
\end{aligned} 1 + j = 1 ∑ p − 1 q j i ≡ j = 0 ∑ p − 1 ( 1 + j i p e − 1 ) ( mod p e ) = p + i p e − 1 2 p ( p − 1 ) = p + i p e 2 p − 1 ≡ p ( mod p e ) . (11)
The last step is valid because p p p is odd, and hence ( p − 1 ) / 2 (p-1)/2 ( p − 1 ) /2 is an integer. Since o ( a ) = p e o(a)=p^e o ( a ) = p e , our calculations so far yield that x i p = a p x_i^p=a^p x i p = a p .
Thus, in both Case 1 and 2, we have obtained x i p = a p x_i^p=a^p x i p = a p (0 ≤ i ≤ p − 1 0\leq i\leq p-1 0 ≤ i ≤ p − 1 ). Let us define U = ⟨ a p ⟩ U=\langle a^p\rangle U = ⟨ a p ⟩ and X i = ⟨ x i ⟩ X_i=\langle x_i\rangle X i = ⟨ x i ⟩ . Since o ( a ) = p e o(a)=p^e o ( a ) = p e , we have ∣ U ∣ = p e − 1 |U|=p^{e-1} ∣ U ∣ = p e − 1 . Also, U = ⟨ x i p ⟩ ≤ ⟨ x i ⟩ = X i U=\langle x_i^p\rangle\leq\langle x_i\rangle=X_i U = ⟨ x i p ⟩ ≤ ⟨ x i ⟩ = X i , for 0 ≤ i ≤ p − 1 0\leq i\leq p-1 0 ≤ i ≤ p − 1 . If o ( x i ) = p t o(x_i)=p^t o ( x i ) = p t , then o ( x i p ) = p t − 1 o(x_i^p)=p^{t-1} o ( x i p ) = p t − 1 ; hence t = e t=e t = e (since x i p x_i^p x i p has order p e − 1 p^{e-1} p e − 1 ). Equivalently, each X i X_i X i is a cyclic subgroup of order p e p^e p e which contains the cyclic subgroup U U U of order p e − 1 p^{e-1} p e − 1 .
It remains to verify that these p p p cyclic subgroups X i X_i X i are distinct.
In the abelian case, it is trivial to see that U U U is central in K K K , i.e., U ≤ Z ( K ) U\leq Z(K) U ≤ Z ( K ) . In the nonabelian case, note that b − 1 a p b = ( b − 1 a b ) p = ( a q ) p = a p ( 1 + p e − 1 ) = a p + p e = a p b^{-1}a^pb=(b^{-1}ab)^p=(a^q)^p=a^{p(1+p^{e-1})}=a^{p+p^e}=a^p b − 1 a p b = ( b − 1 ab ) p = ( a q ) p = a p ( 1 + p e − 1 ) = a p + p e = a p . This implies that the generator a p a^p a p of U U U commutes with both generators a , b a,b a , b of K K K . Hence, U ≤ Z ( K ) U\leq Z(K) U ≤ Z ( K ) in the nonabelian case as well. Thus, the quotient K / U K/U K / U is well-defined and ∣ K / U ∣ = p e + 1 p e − 1 = p 2 |K/U|=\frac{p^{e+1}}{p^{e-1}}=p^2 ∣ K / U ∣ = p e − 1 p e + 1 = p 2 .
The element a U aU a U has order p p p . Also, b ∉ ⟨ a ⟩ b\notin\langle a\rangle b ∈ / ⟨ a ⟩ in both Case 1 and 2, so b U ≠ U bU\neq U b U = U and b U bU b U has order p p p . These two elements a U aU a U and b U bU b U generate K / U K/U K / U , and they commute. This is immediate in the abelian case. In the nonabelian case, b − 1 a b = a 1 + p e − 1 b^{-1}ab=a^{1+p^{e-1}} b − 1 ab = a 1 + p e − 1 and a p e − 1 = ( a p ) p e − 2 ∈ U a^{p^{e-1}}=(a^p)^{p^{e-2}}\in U a p e − 1 = ( a p ) p e − 2 ∈ U . Hence, b − 1 a b U = a 1 + p e − 1 U = a U b^{-1}abU=a^{1+p^{e-1}}U=aU b − 1 ab U = a 1 + p e − 1 U = a U . Thus a U aU a U and b U bU b U commute in K / U K/U K / U . Consequently, K / U K/U K / U is an elementary abelian group of order p 2 p^2 p 2 ; that is, K / U ≅ Z p × Z p K/U\cong\mathbb{Z}_p\times\mathbb{Z}_p K / U ≅ Z p × Z p .
The elementary abelian group K / U ≅ Z p × Z p K/U\cong\mathbb{Z}_p\times\mathbb{Z}_p K / U ≅ Z p × Z p can be viewed as a two-dimensional vector space over F p \mathbb{F}_p F p , with the correspondence ( a U ) r ( b U ) s ⟷ ( r , s ) (aU)^r(bU)^s\longleftrightarrow(r,s) ( a U ) r ( b U ) s ⟷ ( r , s ) , r , s ∈ F p r,s\in\mathbb{F}_p r , s ∈ F p using a U aU a U and b U bU b U as a basis. Note that X i / U = ⟨ x i U ⟩ = ⟨ ( a U ) ( b U ) − i ⟩ = ⟨ ( 1 , − i ) ⟩ X_i/U=\langle x_iU\rangle=\langle(aU)(bU)^{-i}\rangle=\langle(1,-i)\rangle X i / U = ⟨ x i U ⟩ = ⟨( a U ) ( b U ) − i ⟩ = ⟨( 1 , − i )⟩ in the two-dimensional vector space K / U K/U K / U over F p \mathbb{F}_p F p . If X i / U = X j / U X_i/U=X_j/U X i / U = X j / U , then ⟨ ( 1 , − i ) ⟩ = ⟨ ( 1 , − j ) ⟩ \langle(1,-i)\rangle=\langle(1,-j)\rangle ⟨( 1 , − i )⟩ = ⟨( 1 , − j )⟩ and hence ( 1 , − i ) = λ ( 1 , − j ) (1,-i)=\lambda(1,-j) ( 1 , − i ) = λ ( 1 , − j ) for some non-zero scalar λ ∈ F p × \lambda\in\mathbb{F}_p^\times λ ∈ F p × . Comparing the first coordinates gives λ = 1 \lambda=1 λ = 1 , and then i = j i=j i = j in F p \mathbb{F}_p F p . Thus X 0 / U , X 1 / U , … , X p − 1 / U X_0/U,X_1/U,\ldots,X_{p-1}/U X 0 / U , X 1 / U , … , X p − 1 / U are pairwise distinct subspaces. This implies X 0 , X 1 , … , X p − 1 X_0,X_1,\ldots,X_{p-1} X 0 , X 1 , … , X p − 1 are pairwise distinct cyclic subgroups of order p e p^e p e , and all of them contain the subgroup U U U of order p e − 1 p^{e-1} p e − 1 . Since p p p is odd, p ≥ 3 p\geq3 p ≥ 3 and the required conclusion follows.
Literature note. The maximal-order coset calculation in the proof of Theorem 1 of Sambale-Wellmann [37 ] gives an independent route to the same conclusion. The ternary fork formulation above is the specialisation needed here and is proved explicitly to identify the common subgroup U U U .
Now, using the above lemma and Lemma 4.8 , we obtain the boxicity of the power graph of a nilpotent group with odd order or a nilpotent group that has cyclic Sylow 2-subgroups.
Corollary 5.10. Let G G G be a finite nilpotent group. Then the following two hold:
(1) If the Sylow 2-subgroup of G G G is cyclic, then box ( Pow ( G ) ) = box ( Pow ( Z exp ( G ) ) ) + t ( G ) \operatorname{box}(\operatorname{Pow}(G))=\operatorname{box}(\operatorname{Pow}(\mathbb{Z}_{\exp(G)}))+t(G) box ( Pow ( G )) = box ( Pow ( Z e x p ( G ) )) + t ( G ) .
(2) If ∣ G ∣ |G| ∣ G ∣ is odd, then box ( Pow ( G ) ) = box ( Pow ( Z exp ( G ) ) ) + s ( G ) \operatorname{box}(\operatorname{Pow}(G))=\operatorname{box}(\operatorname{Pow}(\mathbb{Z}_{\exp(G)}))+s(G) box ( Pow ( G )) = box ( Pow ( Z e x p ( G ) )) + s ( G ) .
Proof. Recall that Equation (8) gives the following: box ( Pow ( G ) ) = box ( Comp ( ∏ i T i ) ) \operatorname{box}(\operatorname{Pow}(G))=\operatorname{box}(\operatorname{Comp}(\prod_i T_i)) box ( Pow ( G )) = box ( Comp ( ∏ i T i )) , where T i T_i T i denotes the rooted tree poset arising from the Sylow p i p_i p i -subgroup S p i S_{p_i} S p i . In particular, T i T_i T i is a chain exactly when S p i S_{p_i} S p i is cyclic. Assuming exp ( S p i ) = p i e i \exp(S_{p_i})=p_i^{e_i} exp ( S p i ) = p i e i , height of the rooted tree poset T i T_i T i is e i e_i e i . By Lemma 5.9 , every noncyclic Sylow subgroup S p i S_{p_i} S p i of G G G for odd p i p_i p i satisfies h 3 ( S p i ) = e i − 1 h_3(S_{p_i})=e_i-1 h 3 ( S p i ) = e i − 1 . There are t ( G ) t(G) t ( G ) noncyclic odd order Sylow subgroups of G G G . Hence, applying Lemma 4.8 we have the lower bound: box ( Pow ( G ) ) ≥ box ( Pow ( Z exp ( G ) ) ) + t ( G ) \operatorname{box}(\operatorname{Pow}(G))\geq\operatorname{box}(\operatorname{Pow}(\mathbb{Z}_{\exp(G)}))+t(G) box ( Pow ( G )) ≥ box ( Pow ( Z e x p ( G ) )) + t ( G ) .
When the Sylow 2-subgroup is absent or cyclic, the only noncyclic Sylow subgroups are the t ( G ) t(G) t ( G ) odd ones. From the universal upper bound in Lemma 5.6, it follows that the two bounds coincide. Also, when ∣ G ∣ |G| ∣ G ∣ is odd or Sylow 2-subgroup is absent, then t ( G ) = s ( G ) t(G)=s(G) t ( G ) = s ( G ) .
:::
Boxicity Due to Non-cyclic Sylow 2 2 2 -subgroup
Recall that for k ≥ 2 k \ge2 k ≥ 2 , an element u u u of a poset P P P is said to have a k k k -ary fork if u u u has k k k pairwise incomparable strict descendants in P P P . At an odd prime, Lemma 5.9 supplies a ternary fork one level below the exponent. This fails at p = 2 p=2 p = 2 . For example, the cyclic subgroup poset (also a rooted tree poset) of a dihedral 2 2 2 -group has one long rotation chain, while its reflection subgroups branch only from the root. We therefore need to record the depth of branching rather than merely whether the rooted tree poset is a chain.
The next lemma shows that a deep binary fork in the cyclic-subgroup rooted tree poset of a 2 2 2 -group always creates a ternary fork at the same depth or one level lower. This special fact is false for arbitrary rooted tree posets; its proof uses group multiplication.
Lemma 5.11. For every noncyclic finite 2 2 2 -group G G G , h 2 ( G ) ≤ h 3 ( G ) + 1 h_2(G) \le h_3(G) + 1 h 2 ( G ) ≤ h 3 ( G ) + 1 .
Proof. Let d = h 2 ( G ) d=h_2(G) d = h 2 ( G ) .
First, suppose d = 0 d=0 d = 0 . Then every element of G G G lies in a maximal cyclic subgroup. A group cannot be the union of two proper subgroups (see [6 ] for details). Since G G G is noncyclic, it follows that G G G has at least three maximal cyclic subgroups. These are pairwise incomparable, and all contain the trivial subgroup. Hence h 3 ( G ) ≥ 0 h_3(G) \ge0 h 3 ( G ) ≥ 0 , and the lemma follows in this case.
Now suppose d ≥ 1 d \ge1 d ≥ 1 . Choose a cyclic subgroup U = ⟨ u ⟩ U=\langle u\rangle U = ⟨ u ⟩ of order 2 d 2^d 2 d contained in two incomparable cyclic subgroups A A A and B B B . Let X = ⟨ x ⟩ X=\langle x\rangle X = ⟨ x ⟩ and Y = ⟨ y ⟩ Y=\langle y\rangle Y = ⟨ y ⟩ be their respective unique subgroups of order 2 d + 1 2^{d+1} 2 d + 1 . Note that both contain U U U . If X = Y X=Y X = Y , this common subgroup is strictly contained in both A A A and B B B , since A A A and B B B are incomparable. It would therefore support a binary fork at depth d + 1 d+1 d + 1 , contrary to d = h 2 ( G ) d=h_2(G) d = h 2 ( G ) . Thus X ≠ Y X\ne Y X = Y . Since U ≤ X ∩ Y U\le X\cap Y U ≤ X ∩ Y and U U U has index 2 2 2 in X X X , while X X X and Y Y Y have the same order, it follows that X ∩ Y = U X\cap Y=U X ∩ Y = U .
Note that without loss of generality, we can put u = x 2 u=x^2 u = x 2 . Since y 2 = u s y^2=u^s y 2 = u s for some odd integer s s s , replacing y y y by y t y^t y t , where s t ≡ 1 ( m o d 2 d ) st\equiv1\pmod{2^d} s t ≡ 1 ( mod 2 d ) , gives x 2 = y 2 = u x^2=y^2=u x 2 = y 2 = u . The integer t t t is odd, so this replacement preserves ⟨ y ⟩ = Y \langle y\rangle=Y ⟨ y ⟩ = Y . We define the subgroup H = ⟨ x , y ⟩ H=\langle x,y\rangle H = ⟨ x , y ⟩ . Both generators centralize u u u , and therefore U ≤ Z ( H ) U\le Z(H) U ≤ Z ( H ) .
Write X y = y − 1 X y X^y=y^{-1}Xy X y = y − 1 X y . If X y ≠ X X^y\ne X X y = X , then X y X^y X y contains U U U and differs from Y Y Y : equality would imply X = Y y − 1 = Y X=Y^{y^{-1}}=Y X = Y y − 1 = Y . Thus X X X , X y X^y X y , Y Y Y are three distinct cyclic overgroups of U U U of the same order, yielding h 3 ( G ) ≥ d h_3(G)\ge d h 3 ( G ) ≥ d .
Suppose now that X y = X X^y=X X y = X . Then y − 1 x y = x r y^{-1}xy=x^r y − 1 x y = x r for some odd integer r r r , so [ x , y ] = x − 1 y − 1 x y = x r − 1 ∈ ⟨ x 2 ⟩ = U [x,y]=x^{-1}y^{-1}xy=x^{r-1}\in\langle x^2\rangle=U [ x , y ] = x − 1 y − 1 x y = x r − 1 ∈ ⟨ x 2 ⟩ = U . Write [ x , y ] = u k [x,y]=u^k [ x , y ] = u k . Since U ≤ Z ( H ) U\le Z(H) U ≤ Z ( H ) , the commutator is central, and
( x y ) 2 = x 2 y 2 [ x , y ] − 1 = u 2 − k , (xy)^2=x^2y^2[x,y]^{-1}=u^{2-k}, ( x y ) 2 = x 2 y 2 [ x , y ] − 1 = u 2 − k ,
( x y − 1 ) 2 = x 2 y − 2 [ x , y ] = u k . (12) (xy^{-1})^2=x^2y^{-2}[x,y]=u^k. \tag*{(12)} ( x y − 1 ) 2 = x 2 y − 2 [ x , y ] = u k . (12)
Moreover, H / U ≅ C 2 × C 2 H/U\cong C_2\times C_2 H / U ≅ C 2 × C 2 , because it is generated by the distinct nonidentity commuting involutions x U xU xU and y U yU y U .
If k k k is odd, take z = x y − 1 z=xy^{-1} z = x y − 1 . Then ⟨ z 2 ⟩ = U \langle z^2\rangle=U ⟨ z 2 ⟩ = U . If k k k is even, put W = ⟨ u 2 ⟩ W=\langle u^2\rangle W = ⟨ u 2 ⟩ . When d = 1 d=1 d = 1 , take z = x y z=xy z = x y ; equation () gives z 2 = 1 z^2=1 z 2 = 1 , so ⟨ z 2 ⟩ = W \langle z^2\rangle=W ⟨ z 2 ⟩ = W . When d ≥ 2 d\ge2 d ≥ 2 , exactly one of k k k and 2 − k 2-k 2 − k is congruent to 2 ( m o d 4 ) 2\pmod4 2 ( mod 4 ) . Choose the corresponding z ∈ { x y − 1 , x y } z\in\{xy^{-1},xy\} z ∈ { x y − 1 , x y } ; then ( ) gives ⟨ z 2 ⟩ = W \langle z^2\rangle=W ⟨ z 2 ⟩ = W .
Thus, in every case, Z = ⟨ z ⟩ Z=\langle z\rangle Z = ⟨ z ⟩ contains a subgroup W 0 = ⟨ z 2 ⟩ ≤ U W_0=\langle z^2\rangle\le U W 0 = ⟨ z 2 ⟩ ≤ U , depth ( W 0 ) ≥ d − 1 \operatorname{depth}(W_0)\ge d-1 depth ( W 0 ) ≥ d − 1 . Under the quotient map H → H / U H\to H/U H → H / U , the images of X , Y , Z X,Y,Z X , Y , Z are the three distinct subgroups of order 2 2 2 , since z U = x y U zU=xyU z U = x y U . Subgroup inclusion is preserved by homomorphisms, so X , Y , Z X,Y,Z X , Y , Z are pairwise incomparable. They all contain W 0 W_0 W 0 , and hence form a ternary fork at depth at least d − 1 d-1 d − 1 . Therefore, h 3 ( G ) ≥ d − 1 = h 2 ( G ) − 1 h_3(G)\ge d-1=h_2(G)-1 h 3 ( G ) ≥ d − 1 = h 2 ( G ) − 1 .
Remark 5.12. If a node u u u at depth d d d lies below k k k incomparable descendants, then every ancestor of u u u also lies below those same descendants. Consequently, a fork known at depth at least r r r may always be used at any smaller depth by replacing its core with the appropriate ancestor. We will use this when a > m a > m a > m in Lemma 5.15 .
Corollary 5.13. Let q ≥ 1 q \ge1 q ≥ 1 . Then h 3 ( S 2 ) ≤ q − 2 ⟹ h 2 ( S 2 ) ≤ q − 1 h_3(S_2) \le q - 2 \Longrightarrow h_2(S_2) \le q - 1 h 3 ( S 2 ) ≤ q − 2 ⟹ h 2 ( S 2 ) ≤ q − 1 .
Proof. If not, Lemma 5.11 would produce a ternary fork at depth at least d − 1 ≥ q − 1 d - 1 \ge q - 1 d − 1 ≥ q − 1 , contradicting h 3 ( S 2 ) ≤ q − 2 h_3(S_2) \le q - 2 h 3 ( S 2 ) ≤ q − 2 .
Proposition 5.14. Let S 2 S_2 S 2 be a finite 2-group of exponent 2 a 2^a 2 a , let m ≥ 1 m \ge1 m ≥ 1 , and put q = min { a , m } q = \min\{a,m\} q = min { a , m } . If h 3 ( S 2 ) ≤ q − 2 h_3(S_2) \le q - 2 h 3 ( S 2 ) ≤ q − 2 , then
box ( Comp ( C ( S 2 ) × C m ) ) = q . (13) \operatorname{box}(\operatorname{Comp}(\mathcal{C}(S_2) \times C_m)) = q. \tag*{(13)} box ( Comp ( C ( S 2 ) × C m )) = q . (13)
Proof. By Corollary 5.13, the rooted tree poset T 2 = C ( S 2 ) T_2 = \mathcal{C}(S_2) T 2 = C ( S 2 ) satisfies h 3 ( T 2 ) ≤ q − 2 h_3(T_2) \le q - 2 h 3 ( T 2 ) ≤ q − 2 and h 2 ( T 2 ) ≤ q − 1 h_2(T_2) \le q - 1 h 2 ( T 2 ) ≤ q − 1 . By Lemma 4.10, the stated equality follows.
We now prove the even-order classification. Assume first that the odd part of G G G is nontrivial, and write a = e 2 a = e_2 a = e 2 , m = max p o d d e p m = \max_{p\ \mathrm{odd}} e_p m = max p odd e p , q = min { a , m } q = \min\{a,m\} q = min { a , m } , E o d d = ∑ p o d d e p E_{\mathrm{odd}} = \sum_{p\ \mathrm{odd}} e_p E odd = ∑ p odd e p . Let t = ∣ { p o d d : S p is noncyclic } ∣ t = \lvert\{p\ \mathrm{odd} : S_p\ \text{is noncyclic}\}\rvert t = ∣{ p odd : S p is noncyclic }∣ , B = a + E o d d − max { a , m } B = a + E_{\mathrm{odd}} - \max\{a,m\} B = a + E odd − max { a , m } , L = B + t L = B + t L = B + t .
Lemma 5.15. Let G G G be a finite nilpotent group whose Sylow 2-subgroup S 2 S_2 S 2 is noncyclic and whose odd part is nontrivial. With the notation above,
box ( Pow ( G ) ) = { L + 1 , h 3 ( S 2 ) ≥ q − 1 , L , h 3 ( S 2 ) ≤ q − 2. (14) \operatorname{box}(\operatorname{Pow}(G)) =
\begin{cases}
L + 1, & h_3(S_2) \ge q - 1,\\
L, & h_3(S_2) \le q - 2.
\end{cases} \tag*{(14)} box ( Pow ( G )) = { L + 1 , L , h 3 ( S 2 ) ≥ q − 1 , h 3 ( S 2 ) ≤ q − 2. (14) Proof. For each prime p ∣ o ( G ) p \mid o(G) p ∣ o ( G ) , choose an induced subposet P p P_p P p of C ( S p ) \mathcal{C}(S_p) C ( S p ) as follows. For every noncyclic odd Sylow subgroup S p S_p S p , Lemma 5.9 supplies a cyclic subgroup at depth e p − 1 e_p - 1 e p − 1 contained in three incomparable cyclic subgroups at depth e p e_p e p . This induces a broom2 {}^{2} 2 .5 If h 3 ( S 2 ) ≥ q − 1 h_3(S_2) \ge q - 1 h 3 ( S 2 ) ≥ q − 1 , choose, using Remark 5.12, a node U U U at depth q − 1 q - 1 q − 1 with three pairwise incomparable strict descendants. Let P 2 P_2 P 2 be the induced subposet consisting of the root-to-U U U chain and these three descendants; thus P 2 P_2 P 2 is a broom of height q q q . If h 3 ( S 2 ) ≤ q − 2 h_3(S_2) \le q - 2 h 3 ( S 2 ) ≤ q − 2 , let P 2 P_2 P 2 be a root-to-leaf chain of height a a a .
On the other hand, if S p S_p S p is cyclic, let P p P_p P p be its unique chain of height e p e_p e p . The product P 2 × ∏ p o d d P p P_2 \times\prod_{p\ \mathrm{odd}} P_p P 2 × ∏ p odd P p is an induced subposet of C ( G ) \mathcal{C}(G) C ( G ) . Apply Lemma 4.8 with R R R consisting of the t t t noncyclic odd factors, together with the 2-factor when h 3 ( S 2 ) ≥ q − 1 h_3(S_2) \ge q - 1 h 3 ( S 2 ) ≥ q − 1 . Observe the sum of the factor heights minus their maximum. When h 3 ( S 2 ) ≤ q − 2 h_3(S_2) \le q - 2 h 3 ( S 2 ) ≤ q − 2 , it is a + E o d d − max { a , m } = B a + E_{\mathrm{odd}} - \max\{a,m\} = B a + E odd − max { a , m } = B , and when h 3 ( S 2 ) ≥ q − 1 h_3(S_2) \ge q - 1 h 3 ( S 2 ) ≥ q − 1 , it is q + E o d d − max { q , m } = q + E o d d − m = B q + E_{\mathrm{odd}} - \max\{q,m\} = q + E_{\mathrm{odd}} - m = B q + E odd − max { q , m } = q + E odd − m = B since q = min { a , m } q = \min\{a,m\} q = min { a , m } and max { a , m } + min { a , m } = a + m \max\{a,m\} + \min\{a,m\} = a + m max { a , m } + min { a , m } = a + m .
Therefore, we have
box ( Pow ( G ) ) ≥ { B + t = L if h 3 ( S 2 ) ≤ q − 2 , B + t + 1 = L + 1 if h 3 ( S 2 ) ≥ q − 1. (15) \operatorname{box}(\operatorname{Pow}(G)) \ge
\begin{cases}
B + t = L & \text{if } h_3(S_2) \le q - 2,\\
B + t + 1 = L + 1 & \text{if } h_3(S_2) \ge q - 1.
\end{cases} \tag*{(15)} box ( Pow ( G )) ≥ { B + t = L B + t + 1 = L + 1 if h 3 ( S 2 ) ≤ q − 2 , if h 3 ( S 2 ) ≥ q − 1. (15) Since exactly t + 1 t + 1 t + 1 Sylow subgroups are noncyclic, the universal upper bound in Lemma 5.6 gives
box ( Pow ( G ) ) ≤ B + t + 1 = L + 1. (16) \operatorname{box}(\operatorname{Pow}(G)) \le B + t + 1 = L + 1. \tag*{(16)} box ( Pow ( G )) ≤ B + t + 1 = L + 1. (16)
Thus, only the two values L L L and L + 1 L+1 L + 1 are possible.
Let h 3 ( S 2 ) ≤ q − 2 h_3(S_2) \le q-2 h 3 ( S 2 ) ≤ q − 2 . Choose an odd prime p 0 p_0 p 0 with e p 0 = m e_{p_0}=m e p 0 = m . Proposition 5.14 gives
box ( Comp ( C ( S 2 ) × C m ) ) = q . (17) \operatorname{box}(\operatorname{Comp}(\mathcal{C}(S_2)\times C_m))=q. \tag*{(17)} box ( Comp ( C ( S 2 ) × C m )) = q . (17)
Therefore, we have
box ( Pow ( G ) ) = box ( Comp ( C ( S 2 ) × ∏ p o d d C ( S p ) ) ) ≤ box ( Comp ( C ( S 2 ) × ∏ p o d d C e p ) ) + t (Lemma 4.3) ≤ box ( Comp ( C ( S 2 ) × C m ) ) + E o d d − m + t (Lemma 4.2) = q + E o d d − m + t (Equation (14)) = L . \begin{aligned}
\operatorname{box}(\operatorname{Pow}(G))&=\operatorname{box}\left(\operatorname{Comp}\left(\mathcal{C}(S_2)\times\prod_{p\ \mathrm{odd}}\mathcal{C}(S_p)\right)\right)\\
&\le\operatorname{box}\left(\operatorname{Comp}\left(\mathcal{C}(S_2)\times\prod_{p\ \mathrm{odd}}C_{e_p}\right)\right)+t &&\text{(Lemma 4.3)}\\
&\le\operatorname{box}(\operatorname{Comp}(\mathcal{C}(S_2)\times C_m))+E_{\mathrm{odd}}-m+t &&\text{(Lemma 4.2)}\\
&=q+E_{\mathrm{odd}}-m+t &&\text{(Equation (14))}\\
&=L.
\end{aligned} box ( Pow ( G )) = box Comp C ( S 2 ) × p odd ∏ C ( S p ) ≤ box Comp C ( S 2 ) × p odd ∏ C e p + t ≤ box ( Comp ( C ( S 2 ) × C m )) + E odd − m + t = q + E odd − m + t = L . (Lemma 4.3) (Lemma 4.2) (Equation (14))
□
Proof of Theorem 1.5
(i) This follows from Lemma 5.6 and Corollary 5.10.
(ii) This is Lemma 5.15.
(iii) This follows from Lemma 5.2 and Lemma 4.1. Note that a noncyclic p p p -group corresponds to a cyclic subgroup poset, which is non-chain, and hence boxicity is at least 1. □
Declaration of AI use: Our preliminary investigation of the boxicity of power graphs of cyclic groups led us to its complete solution via Lemma A.6, without any use of AI tools. An upper bound for the general nilpotent case was also similarly derived. As a result of playing with small cases, we observed that for odd primes p p p and q q q , the reduced power graph of the group Z p q × Z p q \mathbb{Z}_{pq}\times\mathbb{Z}_{pq} Z pq × Z pq contains an isomorphic copy of the fully subdivided K 3 , 3 K_{3,3} K 3 , 3 as an induced subgraph. It is known that the boxicity of the full subdivision of any non-planar graph is at least 3[25 , 40 ] . This observation led us to believe that there might be an underlying topological obstruction affecting the representability of these graphs, even for more general nilpotent groups. This curiosity led us to look for such an obstruction, for which we used ChatGPT 5.6 Sol. The LLM was able to find exactly the kind of structure that we were looking for. The text has been carefully vetted for mistakes. None of the references is generated by the LLM. We take full responsibility for the contents of this paper.
Alternate proof of lem:boolean
The alternate proof is via the proof of Lemma A.6 . This technique uses the notion of a divisor graph , so we need some additional definitions and facts. We first set the background for that.
Definition A.1. Define g : Z + → Z + ∪ { 0 } g:\mathbb{Z}^{+}\to\mathbb{Z}^{+}\cup\{0\} g : Z + → Z + ∪ { 0 } as g ( x ) : = g(x):= g ( x ) := the number of distinct prime divisors in the prime factorisation of x x x .
Definition A.2. For a positive integer n n n let D ( n ) D(n) D ( n ) be the graph with vertex set equal to the set of all non-trivial proper divisors of n n n , such that two vertices are adjacent in D ( n ) D(n) D ( n ) if one divides the other. D ( n ) D(n) D ( n ) is called the divisor graph of n n n .
Let n n n be a square-free positive integer. Suppose g ( n ) = r g(n)=r g ( n ) = r . It was observed in [15 ] and also in § 4.5 that box ( D ( n ) ) = box ( T C ( H r ) ) \operatorname{box}(D(n))=\operatorname{box}(TC(H_r)) box ( D ( n )) = box ( T C ( H r )) . Therefore, it is enough to compute the exact boxicity of D ( n ) D(n) D ( n ) .
Definition A.3. For a positive integer n n n , define D ( n ) \mathcal{D}(n) D ( n ) to be the collection of all graphs Γ \Gamma Γ such that V ( Γ ) = V ( D ( n ) ) V(\Gamma)=V(D(n)) V ( Γ ) = V ( D ( n )) and E ( D ( n ) ) ⊆ E ( Γ ) E(D(n))\subseteq E(\Gamma) E ( D ( n )) ⊆ E ( Γ ) such that E ( Γ ) E(\Gamma) E ( Γ ) does not contain the edges { x y : x , y ∈ V ( Γ ) and y = n x } \{xy:x,y\in V(\Gamma)\text{ and }y=\frac{n}{x}\} { x y : x , y ∈ V ( Γ ) and y = x n } . Define
D ~ ( r ) : = ⋃ g ( n ) = r n is square free D ( n ) . \widetilde{\mathcal{D}}(r):=\bigcup_{\substack{g(n)=r\\ n\text{ is square free}}}\mathcal{D}(n). D ( r ) := g ( n ) = r n is square free ⋃ D ( n ) .
The following two statements are used in the proof of Lemma A.6.
Observation A.4. Let Γ \Gamma Γ be a graph having V ( Γ ) = { v 1 , v 2 , … , v 6 } V(\Gamma)=\{v_1,v_2,\ldots,v_6\} V ( Γ ) = { v 1 , v 2 , … , v 6 } such that:
v 1 , v 2 , v 3 , v 4 , v 5 , v 6 v_1,v_2,v_3,v_4,v_5,v_6 v 1 , v 2 , v 3 , v 4 , v 5 , v 6 forms a cycle in Γ \Gamma Γ , and
v 1 v 4 , v 2 v 5 , v 3 v 6 ∉ E ( Γ ) v_1v_4,v_2v_5,v_3v_6\notin E(\Gamma) v 1 v 4 , v 2 v 5 , v 3 v 6 ∈ / E ( Γ ) .
Then box ( Γ ) > 1 \operatorname{box}(\Gamma)>1 box ( Γ ) > 1 .
The observation follows by noting that graphs defined as above always contain C 4 C_4 C 4 , C 5 C_5 C 5 , C 6 C_6 C 6 or the Hajós graph as an induced subgraph, all of which are forbidden induced subgraphs for interval graphs. The following more general theorem is by Cozzens and Roberts [23 ] .
Theorem A.5 ([23 ] ). Let Γ \Gamma Γ be a graph and p ≥ 1 p\geq1 p ≥ 1 . Suppose that V ( Γ ) V(\Gamma) V ( Γ ) contains two disjoint sets of vertices S 1 = { a 1 , a 2 , … , a 2 p − 1 } S_1=\{a_1,a_2,\ldots,a_{2p-1}\} S 1 = { a 1 , a 2 , … , a 2 p − 1 } and S 2 = { b 1 , b 2 , … , b 2 p − 1 } S_2=\{b_1,b_2,\ldots,b_{2p-1}\} S 2 = { b 1 , b 2 , … , b 2 p − 1 } , and suppose that the only edges between S 1 S_1 S 1 and S 2 S_2 S 2 in Γ \Gamma Γ are { a i b i : i ∈ [ 2 p − 1 ] } \{a_ib_i:i\in[2p-1]\} { a i b i : i ∈ [ 2 p − 1 ]} . Then box ( Γ ) ≥ p \operatorname{box}(\Gamma)\geq p box ( Γ ) ≥ p .
Lemma A.6. The boxicity of any graph in D ~ ( r ) \widetilde{\mathcal{D}}(r) D ( r ) is at least r − 1 r-1 r − 1 .
Proof. We will proceed by induction on the number of primes. For r ≤ 2 r\leq2 r ≤ 2 , it is obvious. For r = 3 r=3 r = 3 , the statement follows from Observation A.4. So assume r ≥ 4 r\geq4 r ≥ 4 .
Base case: Suppose r = 4 r=4 r = 4 . Suppose n n n is a positive integer and suppose n = p 1 p 2 p 3 p 4 n=p_1p_2p_3p_4 n = p 1 p 2 p 3 p 4 is its prime factorisation. Suppose Γ ∈ D ( n ) \Gamma\in\mathcal{D}(n) Γ ∈ D ( n ) . Let, for the sake of contradiction, box ( Γ ) ≤ 2 \operatorname{box}(\Gamma)\leq2 box ( Γ ) ≤ 2 and I 1 , I 2 I_1,I_2 I 1 , I 2 be an optimal box representation of Γ \Gamma Γ . Take S = { n p 4 , n p 3 , n p 2 , n p 1 , p 4 , p 3 , p 2 , p 1 } S=\{\frac{n}{p_4},\frac{n}{p_3},\frac{n}{p_2},\frac{n}{p_1},p_4,p_3,p_2,p_1\} S = { p 4 n , p 3 n , p 2 n , p 1 n , p 4 , p 3 , p 2 , p 1 } . The graph induced by S S S in Γ \Gamma Γ is the graph as described in Theorem A.5. Therefore, the interval supergraphs I 1 I_1 I 1 and I 2 I_2 I 2 each contain exactly two of the pairs { n p 4 , p 4 } , { n p 3 , p 3 } , { n p 2 , p 2 } , { n p 1 , p 1 } \{\frac{n}{p_4},p_4\},\{\frac{n}{p_3},p_3\},\{\frac{n}{p_2},p_2\},\{\frac{n}{p_1},p_1\} { p 4 n , p 4 } , { p 3 n , p 3 } , { p 2 n , p 2 } , { p 1 n , p 1 } because otherwise, there is a subgraph of the form described in Observation A.4. Suppose without loss of generality, I 1 I_1 I 1 contains { n p 4 , p 4 } , { n p 3 , p 3 } \{\frac{n}{p_4},p_4\},\{\frac{n}{p_3},p_3\} { p 4 n , p 4 } , { p 3 n , p 3 } as non-edges. Then the graph induced by { p 1 p 2 , p 3 p 4 , n p 4 , p 4 , n p 3 , p 3 } \{p_1p_2,p_3p_4,\frac{n}{p_4},p_4,\frac{n}{p_3},p_3\} { p 1 p 2 , p 3 p 4 , p 4 n , p 4 , p 3 n , p 3 } in I 1 I_1 I 1 is the graph of the form described as in Observation A.4 unless there is an edge between p 1 p 2 , p 3 p 4 p_1p_2,p_3p_4 p 1 p 2 , p 3 p 4 . Similarly, in I 2 I_2 I 2 , the graph induced by { p 1 p 2 , p 3 p 4 , n p 2 , n p 1 , p 1 , p 2 } \{p_1p_2,p_3p_4,\frac{n}{p_2},\frac{n}{p_1},p_1,p_2\} { p 1 p 2 , p 3 p 4 , p 2 n , p 1 n , p 1 , p 2 } is the graph of the form described in Observation A.4 unless there is an edge between p 1 p 2 , p 3 p 4 p_1p_2,p_3p_4 p 1 p 2 , p 3 p 4 . But this forces p 1 p 2 , p 3 p 4 p_1p_2,p_3p_4 p 1 p 2 , p 3 p 4 to be an edge in E ( I 1 ) ∩ E ( I 2 ) = E ( Γ ) E(I_1)\cap E(I_2)=E(\Gamma) E ( I 1 ) ∩ E ( I 2 ) = E ( Γ ) . We have a contradiction.
Now suppose the statement is true for D ~ ( r ) \widetilde{\mathcal{D}}(r) D ( r ) for r ≤ l − 1 r\leq l-1 r ≤ l − 1 . We need to show that D ~ ( l ) \widetilde{\mathcal{D}}(l) D ( l ) has boxicity at least l − 1 l-1 l − 1 . Suppose n n n is a positive integer and suppose n = ∏ i ∈ [ l ] p i n=\prod_{i\in[l]}p_i n = ∏ i ∈ [ l ] p i is its prime factorisation. Let Γ ∈ D ( n ) \Gamma\in\mathcal{D}(n) Γ ∈ D ( n ) .
Suppose box ( Γ ) = k \operatorname{box}(\Gamma)=k box ( Γ ) = k and assume that I 1 , I 2 , … , I k I_1,I_2,\ldots,I_k I 1 , I 2 , … , I k is an optimal box representation of Γ \Gamma Γ . For i ∈ [ l ] i\in[l] i ∈ [ l ] , define S i : = { n p i , p i } S_i:=\{\frac{n}{p_i},p_i\} S i := { p i n , p i } and let S = { S 1 , S 2 , … , S l } S=\{S_1,S_2,\ldots,S_l\} S = { S 1 , S 2 , … , S l } . If each I j I_j I j contains at most one S i S_i S i as an independent set, then k ≥ l ≥ l − 1 k\geq l\geq l-1 k ≥ l ≥ l − 1 and we are done. Therefore, assume that there exists j ′ ∈ [ k ] , i 1 , i 2 ∈ [ l ] j'\in[k],i_1,i_2\in[l] j ′ ∈ [ k ] , i 1 , i 2 ∈ [ l ] such that I j ′ I_{j'} I j ′ contains S i 1 S_{i_1} S i 1 and S i 2 S_{i_2} S i 2 as independent sets. Without loss of generality, we can assume that i 1 = 1 , i 2 = 2 i_1=1,i_2=2 i 1 = 1 , i 2 = 2 and j ′ = 1 j'=1 j ′ = 1 . This means that the set { n p 1 p 2 , p 1 p 2 , n p 1 , n p 2 , p 2 , p 1 } \{\frac{n}{p_1p_2},p_1p_2,\frac{n}{p_1},\frac{n}{p_2},p_2,p_1\} { p 1 p 2 n , p 1 p 2 , p 1 n , p 2 n , p 2 , p 1 } induces in I 1 I_1 I 1 the graph described as in Observation A.4 unless there is an edge between n p 1 p 2 \frac{n}{p_1p_2} p 1 p 2 n and p 1 p 2 p_1p_2 p 1 p 2 . By a similar argument, we can conclude that all the edges of the form { x y : y = n p 1 p 2 x and p 1 p 2 divides y } \{xy:y=\frac{n}{p_1p_2x}\text{ and }p_1p_2\text{ divides }y\} { x y : y = p 1 p 2 x n and p 1 p 2 divides y } are present in I 1 I_1 I 1 .
Claim A.7. The graph ⋂ j ∈ [ k ] ∖ { 1 } I j \bigcap_{j\in[k]\setminus\{1\}} I_j ⋂ j ∈ [ k ] ∖ { 1 } I j contains a graph from D ~ ( l − 1 ) \widetilde{D}(l-1) D ( l − 1 ) as an induced subgraph.
Proof of Claim: Let Γ ~ = ⋂ j ∈ [ k ] ∖ { 1 } I j \widetilde{\Gamma}=\bigcap_{j\in[k]\setminus\{1\}} I_j Γ = ⋂ j ∈ [ k ] ∖ { 1 } I j . Define T 1 = { x ∈ V ( Γ ~ ) : p 1 p 2 divides x } T_1=\{x\in V(\widetilde{\Gamma}):p_1p_2\text{ divides }x\} T 1 = { x ∈ V ( Γ ) : p 1 p 2 divides x } and T 2 = { x ∈ V ( Γ ~ ) : neither p 1 nor p 2 divides x } T_2=\{x\in V(\widetilde{\Gamma}):\text{ neither }p_1\text{ nor }p_2\text{ divides }x\} T 2 = { x ∈ V ( Γ ) : neither p 1 nor p 2 divides x } . Fix a prime p 0 p_0 p 0 which is not a divisor of n n n . Define n ′ = p 0 n p 1 p 2 n'=\frac{p_0n}{p_1p_2} n ′ = p 1 p 2 p 0 n . Construct Γ ~ ′ \widetilde{\Gamma}' Γ ′ by removing all vertices in V ( Γ ~ ) ∖ ( T 1 ∪ T 2 ) V(\widetilde{\Gamma})\setminus(T_1\cup T_2) V ( Γ ) ∖ ( T 1 ∪ T 2 ) and relabeling all vertices x ∈ T 1 x\in T_1 x ∈ T 1 as p 0 x p 1 p 2 \frac{p_0x}{p_1p_2} p 1 p 2 p 0 x . We will show that the graph Γ ~ ′ ∈ D ~ ( l − 1 ) \widetilde{\Gamma}'\in\widetilde{D}(l-1) Γ ′ ∈ D ( l − 1 ) . It is clear that V ( Γ ~ ′ ) = V ( D ( n ′ ) ) V(\widetilde{\Gamma}')=V(D(n')) V ( Γ ′ ) = V ( D ( n ′ )) and E ( Γ ~ ′ ) ⊇ E ( D ( n ′ ) ) E(\widetilde{\Gamma}')\supseteq E(D(n')) E ( Γ ′ ) ⊇ E ( D ( n ′ )) . Suppose x , y ∈ V ( Γ ~ ′ ) x,y\in V(\widetilde{\Gamma}') x , y ∈ V ( Γ ′ ) such that y = n ′ x y=\frac{n'}{x} y = x n ′ . By definition, p 0 p_0 p 0 divides exactly one of y y y or x x x . Without loss of generality, assume that p 0 p_0 p 0 divides x x x . Then p 1 p 2 x p 0 ∈ T 1 \frac{p_1p_2x}{p_0}\in T_1 p 0 p 1 p 2 x ∈ T 1 and y ∈ T 2 y\in T_2 y ∈ T 2 . Then p 1 p 2 x p 0 y ∈ E ( I 1 ) \frac{p_1p_2x}{p_0}y\in E(I_1) p 0 p 1 p 2 x y ∈ E ( I 1 ) but p 1 p 2 x p 0 y ∉ E ( Γ ) \frac{p_1p_2x}{p_0}y\notin E(\Gamma) p 0 p 1 p 2 x y ∈ / E ( Γ ) . Therefore, p 1 p 2 x p 0 y ∉ E ( Γ ~ ) \frac{p_1p_2x}{p_0}y\notin E(\widetilde{\Gamma}) p 0 p 1 p 2 x y ∈ / E ( Γ ) and it follows that x y ∉ E ( Γ ~ ′ ) xy\notin E(\widetilde{\Gamma}') x y ∈ / E ( Γ ′ ) . Therefore, Γ ~ ′ ∈ D ( n ′ ) ⊂ D ~ ( l − 1 ) \widetilde{\Gamma}'\in D(n')\subset\widetilde{D}(l-1) Γ ′ ∈ D ( n ′ ) ⊂ D ( l − 1 ) . ■
By the induction hypothesis and by the above claim, k − 1 ≥ l − 2 k-1\ge l-2 k − 1 ≥ l − 2 and we are done. □
Omitted Proof
Proof of Observation 4.4
Proof. First, we label the vertices of D 3 ∗ r D_3^{*r} D 3 ∗ r by ordered pairs ( i , j ) (i,j) ( i , j ) , i ∈ [ r ] i\in[r] i ∈ [ r ] , j ∈ { 1 , 2 , 3 } j\in\{1,2,3\} j ∈ { 1 , 2 , 3 } , where the index i i i represents one of the r r r copies of D 3 D_3 D 3 and j j j represents which vertex to choose from that copy of D 3 = { ∅ , { 1 } , { 2 } , { 3 } } D_3=\{\varnothing,\{1\},\{2\},\{3\}\} D 3 = { ∅ , { 1 } , { 2 } , { 3 }} .
For z = ( z 1 , … , z r ) ∈ S r ∖ { ρ } z=(z_1,\ldots,z_r)\in S^r\setminus\{\rho\} z = ( z 1 , … , z r ) ∈ S r ∖ { ρ } , we define the mapping Φ : S r ∖ { ρ } → P ( D 3 ∗ r ) \Phi:S^r\setminus\{\rho\}\to\mathcal{P}(D_3^{*r}) Φ : S r ∖ { ρ } → P ( D 3 ∗ r ) as follows: Φ ( z ) = { ( i , j ) : z i = a j } \Phi(z)=\{(i,j):z_i=a_j\} Φ ( z ) = {( i , j ) : z i = a j } . Since each coordinate z i z_i z i is either the root or one of the three leaves, Φ ( z ) \Phi(z) Φ ( z ) selects at most one vertex from each copy of D 3 ∗ D_3^* D 3 ∗ . So, Φ ( z ) \Phi(z) Φ ( z ) is a face of D 3 ∗ r D_3^{*r} D 3 ∗ r . Conversely, a non-empty face σ ∈ D 3 ∗ r \sigma\in D_3^{*r} σ ∈ D 3 ∗ r uniquely determines a tuple z z z : use a j a_j a j in coordinate i i i when ( i , j ) ∈ σ (i,j)\in\sigma ( i , j ) ∈ σ , and use ρ \rho ρ when the face makes no choice from the i i i -th copy. Hence Φ \Phi Φ is a bijection.
Furthermore, z ≤ z ′ z\le z' z ≤ z ′ in S r ⟺ Φ ( z ) ⊆ Φ ( z ′ ) S^r\Longleftrightarrow\Phi(z)\subseteq\Phi(z') S r ⟺ Φ ( z ) ⊆ Φ ( z ′ ) . Indeed, z < z ′ z<z' z < z ′ holds exactly when for certain coordinates we have the relations ρ < a 1 \rho<a_1 ρ < a 1 , ρ < a 2 \rho<a_2 ρ < a 2 or ρ < a 3 \rho<a_3 ρ < a 3 and Φ ( z ) ⊊ Φ ( z ′ ) \Phi(z)\subsetneq\Phi(z') Φ ( z ) ⊊ Φ ( z ′ ) occurs exactly when certain factors of D 3 D_3 D 3 in D 3 ∗ r D_3^{*r} D 3 ∗ r do not contribute to Φ ( z ) \Phi(z) Φ ( z ) . These two situations occur one-to-one: ρ \rho ρ appears in a coordinate of z z z if and only if that particular factor of D 3 D_3 D 3 in D 3 ∗ r D_3^{*r} D 3 ∗ r does not contribute to Φ ( z ) \Phi(z) Φ ( z ) . Therefore, Φ \Phi Φ is an order isomorphism. The all-root tuple ρ = ( ρ , … , ρ ) \boldsymbol{\rho}=(\rho,\ldots,\rho) ρ = ( ρ , … , ρ ) in S r S^r S r corresponds to the empty face of D 3 ∗ r D_3^{*r} D 3 ∗ r . Consequently, P ( D 3 ∗ r ) ≅ S r ∖ { ρ } \mathcal{P}(D_3^{*r})\cong S^r\setminus\{\rho\} P ( D 3 ∗ r ) ≅ S r ∖ { ρ } .
It follows that Γ r = Comp ( P ( D 3 ∗ r ) ) \Gamma_r=\operatorname{Comp}(\mathcal{P}(D_3^{*r})) Γ r = Comp ( P ( D 3 ∗ r )) is the subgraph of Comp ( S r ) \operatorname{Comp}(S^r) Comp ( S r ) induced by S r ∖ { ρ } S^r\setminus\{\rho\} S r ∖ { ρ } . □