Characterizing graphs of critical pairs of layered generalized crowns

Abstract

The generalized crown ${\mathbb{S}}_n^k$ is a well-known family of bipartite graphs whose order dimension is given in terms of the parameters $n$ and $k$. In recent work, Garcia and Silva defined the notion of layering generalized crowns, producing multipartite posets called $\ell$-layered generalized crowns, whose order dimension is easily determined using $\ell$, $n$, and $k$. This paper extends the authors’ prior work on characterizing the associated graphs of critical pairs of generalized crowns, by providing a new and concrete description of an infinite family of graphs arising from critical pairs of the $\ell$-layered generalized crowns. Our main result gives a characterization of the adjacency matrices of these graphs. Through their associated posets with computable order dimension, these graphs have a strict upper bound on their chromatic number.

Keywords:

• Order dimension
• Multipartite poset
• Chromatic number

1 Introduction

Part of the rich history of computing the chromatic number of a graph includes a result of Felsner and Trotter who proved a connection between the order dimension of partially ordered sets and the chromatic number for certain associated graphs. In [1], Felsner and Trotter proved that if $\mathbb{P}$ is a poset and ${\mathbf{G}}_{\mathbb{P}}^c$ is the associated graph of critical pairs of $\mathbb{P}$, then $\chi \left({\mathbf{G}}_{\mathbb{P}}^c\right)\le dim\left(\mathbb{P}\right)$, thereby providing an upper bound on the chromatic number of the graphs ${\mathbf{G}}_{\mathbb{P}}^c$. Barrera-Cruz et al. [2] proved that, in the case of a particular family of posets called crowns, the upper bound for the chromatic number of the associated graph is a tight bound. Equality is not known in the layered case, but the order dimension still provides an upper bound on the chromatic number of the associated graph. However, it is important to note that the existence of a strict upper bound on the chromatic number of a graph does not always yield complete information about the structure of the graph. For example, a trivial upper bound for the chromatic number of a graph is given by the number of vertices, yet this fact alone does not characterize the graph.

With the aim of concretely describing the associated graph of critical pairs, in [3], we considered the graphs ${\mathbf{G}}_{\mathbb{P}}^c$, where $\mathbb{P}$ is the generalized crown ${\mathbb{S}}_n^k$. We recall that the generalized crown ${\mathbb{S}}_n^k$, as defined in [4], is a height two poset with maximal elements $b_1,\dots ,b_{n+k}$ and minimal elements $a_1,\dots ,a_{n+k}$. Each $b_i$ is incomparable with $a_i,a_{i+1},\dots ,a_{i+k}$, and comparable over the remaining $n-1$ elements. Fig. 1 shows the Hasse diagram for the generalized crown ${\mathbb{S}}_4^1$. In [3], we provided a complete characterization of the infinite family of graphs ${\mathbf{G}}_{{\mathbb{S}}_n^k}^c$ via their adjacency matrices was provided.

Fig. 1 ${\mathbb{S}}_4^1$.

In this paper, we consider a natural extension of the work developed in [3] by considering the graphs ${\mathbf{G}}_{\mathbb{P}}^c$, where $\mathbb{P}$ is the $\ell$-layered generalized crown ${⋊}_{\ell }{\mathbb{S}}_n^k$. The $\ell$-layered generalized crown was defined by Garcia and Silva in [5] through the development of the operation of layering posets. The layering “…produces a larger poset from two compatible posets by gluing one poset above the other in a well-defined way” [5]. The operation of layering generalized crowns produces a multipartite set, whose order dimension is easily computed. For an illustration of layering of generalized crowns see Fig. 2, which provides the Hasse diagram of the $2$-layered generalized crown ${\mathbb{S}}_4^1$, which we denote by ${⋊}_2{\mathbb{S}}_4^1$.

Fig. 2 ${⋊}_2{\mathbb{S}}_4^1$.

Our main result gives a characterization of the graphs ${\mathbf{G}}_{\mathbb{P}}^c$, where $\mathbb{P}$ is the $\ell$-layered generalized crown ${⋊}_{\ell }{\mathbb{S}}_n^k$, by completely and concretely describing the adjacency matrices of these graphs. Moreover, the computation of the matrices depends only on the values of $n,k$, and $\ell$. In Section 3 we characterize the adjacency matrices of the graphs ${\mathbf{G}}_{{⋊}_{\ell }{\mathbb{S}}_n^k}^c$ in the case where $n\ge k+3$ and $\ell \ge 1$. In Section 4 we consider the case where $3\le n<k+3$ and $\ell \ge 1$. These sections thus provide a complete characterization of the adjacency matrices of the graphs ${\mathbf{G}}_{\mathbb{P}}^c$, where $\mathbb{P}$ is the $\ell$-layered generalized crown ${⋊}_{\ell }{\mathbb{S}}_n^k$, for all possible values of $n,k$ and $\ell$.

2 Background

The definitions in this paper are consistent with those used in [1,5–7].

Definition 1

Let $X$ be a set, called the ground set, and let $P\subset X\times X$ be a partial ordering on $X$ with the following binary relations on $X$:

1.	reflexive: for all $a\in X$ we have $a\le a$;
2.	antisymmetry: if $a\le b$ and $b\le a$, then $a=b$; and
3.	transitivity: if $a\le b$ and $b\le c$, then $a\le c$.

Then the pair $\mathbb{P}=(X,P)$ is a called poset or partially ordered set.

All ground sets $X$ considered in this paper are finite.

Example 1

Let $X$ be a finite set and let the ground set of our poset be the power set $\wp \left(X\right)$. Consider a partial ordering on this set by containment of subsets. Then $\mathbb{P}=(\wp \left(X\right),\subseteq )$ forms a poset.

Notation 1

Let $X$ be a finite ground set and let $a,b\in X$. We write $b\left|\right|a$ to denote that $b$ is incomparable with $a$. We write $b>a$ or $(a,b)$ to denote that $b$ lies over $a$ in the partial ordering.

Our paper focuses on a special family of posets called $\ell$-layered generalized crowns. We thus begin with the definition of a generalized crown, which was originally introduced by Trotter; see [6].

Definition 2

Let $n,k\in \mathbb{N}$ with $n\ge 3$ and $k\ge 0$. Then the generalized crown, denoted ${\mathbb{S}}_n^k$, is a height 2 poset with $min\left({\mathbb{S}}_n^k\right)=\{a_1,\dots ,a_{k+n}\}$ and $max\left({\mathbb{S}}_n^k\right)=\{b_1,\dots ,b_{k+n}\}$, where

1.	$b_i\left|\right|a_i,a_{i+1},\dots ,a_{i+k}$, corresponding to $k+1$ “misses”,
2.	$b_i>a_{i+k+1},a_{i+k+2},\dots ,a_{i-1}$, corresponding to $n-1$ “hits”.

Definition 3

Elements in the top row of the crown are called maximal elements and the set of all such elements is denoted by $B=max\left({\mathbb{S}}_n^k\right)$. Elements in the bottom row of the crown are called minimal elements and the set of minimal elements is denoted by $A=min\left({\mathbb{S}}_n^k\right)$. Thus we have $X=A\cup B$ for the ground set of the crown ${\mathbb{S}}_n^k$.

We identify $a_i$ with $a_{i-(n+k)}$ and $b_i$ with $b_{i-(n+k)}$ whenever $i>n+k$. This indexing scheme is called cyclic indexing.

We recall the definition of layering of posets introduced in [5] by Garcia and Silva.

Definition 4

Let ${\mathbb{P}}_1=(X_1,P_1)$ and ${\mathbb{P}}_2=(X_2,P_2)$ be two posets, such that there exists a bijection $\beta :max\left({\mathbb{P}}_1\right)\to min\left({\mathbb{P}}_2\right)$. The $\beta$-layering of ${\mathbb{P}}_2$ over${\mathbb{P}}_1$ is a poset $${\mathbb{P}}_1{⋊}_{\beta }{\mathbb{P}}_2=(X_1\cup X_2,Q)$$where $Q$ is the transitive closure of $$P_1\cup P_2\cup {\{(x,\beta \left(x\right)),(\beta \left(x\right),x)\}}_{x\in max\left(\mathbb{P}\right).}$$

In this process $x$ is literally glued with $\beta \left(x\right)$. Since $\beta$ is a bijection, there are no issues in doing so. In fact, this process can be repeated a finite number of times to obtain as many layers as desired.

Definition 5

The $\ell$-layered generalized crown of ${\mathbb{S}}_n^k$ is denoted by $${⋊}_{\ell }{\mathbb{S}}_n^k≔\underset{\ell \text{times}}{\underbrace{{\mathbb{S}}_n^k⋊\cdots ⋊{\mathbb{S}}_n^k}}.$$

Notation 2

Elements in a layered generalized crown are denoted$x_j^i$, where the subscript of each element denotes its location within a row and the superscript denotes its row. When considering${⋊}_{\ell }{\mathbb{S}}_n^k$ where$\ell \ge 2$, we let$X^i$ denote the set of elements in the $i\text{th}$ row (counting from bottom to top) of ${⋊}_{\ell }{\mathbb{S}}_n^k$, namely $X^i=\{x_1^i,x_2^i,\dots ,x_{n+k}^i\}$. Note that in this case $X={\cup }_{i=1}^{\ell +1}{X}^i$.

Example 2

Fig. 1 gives the Hasse diagram of the generalized crown ${\mathbb{S}}_4^1$ and Fig. 2 gives the Hasse diagram of the $2$-layered generalized crown ${⋊}_2{\mathbb{S}}_4^1$.

Definition 6

Let $\mathbb{P}=(X,P)$ be a poset and let $x\in X$. We say the strict downset of $x$ is the set $$D_{\mathbb{P}}\left(x\right)=\{y\in X:y{<}_{P}x\}$$and the strict upset of $x$ is the set $$U_{\mathbb{P}}\left(x\right)=\{y\in X:x{<}_{P}y\}.$$

Definition 7

Let $\mathbb{P}=(X,P)$ be a poset and let $x\in X$. We say that $x$ is minimal if there does not exist $y\in X$ such that $y{<}_{P}x$. We say that $x$ is maximal if there does not exist $y\in X$ such that $x{<}_{P}y$.

When the poset $\mathbb{P}$ is understood we drop the subscript notation.

Definition 8

For a maximal element $b\in \mathbb{P}$, the set of all minimal elements of $\mathbb{P}$ that are incomparable with $b$ is denoted by $$\mathrm{Inc}\left(b\right)=\{a\in A:b|\left|a\right\}.$$For a minimal element $a\in \mathbb{P}$, the set of all maximal elements of $\mathbb{P}$ that are incomparable to $a$ is denoted by $$\mathrm{Inc}\left(a\right)=\{b\in B:b|\left|a\right\}.$$

The set of all incomparable pairs of $\mathbb{P}$ is denoted by $$\mathrm{Inc}\left(\mathbb{P}\right)=\{(x,y)\in \mathbb{P}\times \mathbb{P}:x|\left|y\right\}.$$

Definition 9

Let $\mathbb{P}=(X,P)$ be a poset and let $x,y\in X$. We call $(x,y)$ a critical pair if the following conditions hold:

1.	$x\left|\right|y$;
2.	$D\left(x\right)\subset D\left(y\right)$; and
3.	$U\left(y\right)\subset U\left(x\right)$.

We let $\mathrm{Crit}\left(\mathbb{P}\right)$ denote the set of all critical pairs of $\mathbb{P}$. If $(x,y)\in \mathrm{Crit}\left(\mathbb{P}\right)$, then we say $(y,x)$ is dual to $(x,y)$.

The next few definitions set the ground work for obtaining results concerning hypergraphs and graphs of $\ell$-layered generalized crowns.

Definition 10

An alternating cycle in a poset $\mathbb{P}$ is a sequence $\{(x_i,y_i):1\le i\le k\}$ of ordered pairs from $\mathrm{Inc}\left(\mathbb{P}\right)$, where $y_i\le x_{i+1}$ in $\mathbb{P}$ (cyclically) for $i=1,2,\dots ,k$.

We say an alternating cycle is strict when $y_i\le x_j$ in $\mathbb{P}$ if and only if $j=i+1$ (cyclically) for $i,j=1,2,\dots ,k$.

Definition 11

A hypergraph $H=(V,E)$ is a set $V$ of vertices along with a set $E$ of edges which are subsets of $V$ with size $\ge 2$. If an edge has size 2, it is called a graph edge. If an edge has size $\ge 3$, it is called a hyperedge. If a graph has only graph edges, then it is simply called a graph.

Definition 12

Given a hypergraph $H=(V,E_H)$, we define the graph of $H$, to be $(V,E_G)$, where $E_G=\{e\in E_H:\left|e\right|=2\}$.

Definition 13

Given a poset $\mathbb{P}$, the strict hypergraph of critical pairs of $\mathbb{P}$ , denoted ${\mathbf{H}}_{\mathbb{P}}^c$, is the hypergraph $(\mathrm{Crit}\left(\mathbb{P}\right),F)$, where $F$ consists of subsets of $\mathrm{Crit}\left(\mathbb{P}\right)$ whose duals form strict alternating cycles. We let ${\mathbf{G}}_{\mathbb{P}}^c$ denote the graph of ${\mathbf{H}}_{\mathbb{P}}^c$.

Definition 14

Given a graph $G=(V,E)$ with $V=\{1,2,\dots ,n\}$, the adjacency matrix of $G$, denoted $M\left(G\right)={\left[m_{i,j}\right]}_{1\le i,j\le n}$, is defined by $$m_{i,j}=\left\{\begin{array}{cc}1\hfill & \text{if}\{i,j\}\in E\hfill \\ 0\hfill & \text{otherwise.}\hfill \end{array}\right.$$

As this paper concerns the characterization of the graphs ${\mathbf{G}}_{{⋊}_{\ell }{\mathbb{S}}_n^k}^c$ via their adjacency matrix we introduce the following:

Definition 15

Let $n\ge 3$, $k\ge 0$ and $\ell \ge 1$. Then we let ${\mathcal{A}}_n^k\left(\ell \right)=M\left({\mathbf{G}}_{{⋊}_{\ell }{\mathbb{S}}_n^k}^c\right)$, denote the adjacency matrix of the graph ${\mathbf{G}}_{{⋊}_{\ell }{\mathbb{S}}_n^k}^c$.

Example 3

Fig. 3 depicts two layers of ${\mathbb{S}}_3^2$, that is ${⋊}_2{\mathbb{S}}_3^2$.

The critical pairs of ${⋊}_2{\mathbb{S}}_3^2$ are: $$(x_1^1,x_1^3),(x_5^1,x_1^3),(x_1^1,x_2^3),(x_2^1,x_2^3),(x_2^1,x_3^3),(x_3^1,x_3^3),(x_3^1,x_4^3),(x_4^1,x_4^3),(x_4^1,x_5^3),(x_5^1,x_5^3).$$ Using these critical pairs and the definition of a strict alternating cycle (of length two) we can compute the adjacency matrix, Table 1, and graph of ${\mathbf{G}}_{{⋊}_2{\mathbb{S}}_3^2}^c$, Fig. 4.

In [5, Theorem 4.3], Garcia and Silva proved that if $3\le n<k+3$ and for $\ell \in \mathbb{N}$ with $1\le \ell \le ⌈\frac{k+1}{n-2}⌉$, then $dim\left({⋊}_{\ell }{\mathbb{S}}_n^k\right)=⌈\frac{2(n+k)}{k+n-\ell (n-2)}⌉$. Applying this theorem we note that $dim\left({⋊}_2{\mathbb{S}}_3^2\right)=⌈\frac{10}{3}⌉=4$. By applying the result of Felsner and Trotter, we know that $\chi \left({\mathbf{G}}_{{⋊}_2{\mathbb{S}}_3^2}^c\right)\le 4$. Moreover, we recall a theorem in graph theory, which states that the chromatic number of a graph on $n$ vertices satisfies $\chi \ge \frac{n}{\alpha }$, where $\alpha$ is the cardinality of the maximal set of vertices that does not include adjacent vertices. In this case $\alpha =3$ and so $\chi \ge \frac{10}{3}$. Thus $\chi \left({\mathbf{G}}_{{⋊}_2{\mathbb{S}}_3^2}^c\right)=4$, as denoted in Fig. 4.

Table 1 Adjacency matrix ${\mathcal{A}}_3^2\left(2\right)$.

Fig. 3 ${⋊}_2{\mathbb{S}}_3^2$.

Fig. 4 Graph of critical pairs of ${⋊}_2{\mathbb{S}}_3^2$.

3 Characterizing ${\mathcal{A}}_n^k\left(\ell \right)$ when $n\ge k+3$

In this section we assume $n\ge k+3$ and $\ell \ge 1$. In these layered crowns, critical pairs can only be produced from elements in adjacent rows; see [5, Lemma 4.1]. To make this precise it will be important to distinguish between the layers of the poset ${⋊}_{\ell }{\mathbb{S}}_n^k$. To do so we introduce the following:

Notation 3

For each $1\le r\le \ell$, let ${\mathbb{P}}_r={\mathbb{S}}_n^k$ and for $1\le j\le n+k$, we let $x_j^r\in min\left({\mathbb{P}}_r\right)=X^r$ and$x_j^{r+1}\in min\left({\mathbb{P}}_{r+1}\right)=max\left({\mathbb{P}}_r\right)=X^{r+1}$. When$r=\ell +1$, we let$x_j^r\in max\left({\mathbb{P}}_{\ell }\right)=X^{\ell +1}$.

In the case where $n\ge k+3$ and $\ell \ge 1$, the critical pairs of ${⋊}_{\ell }{\mathbb{S}}_n^k$ arise only through adjacent rows $X^i$ and $X^{i+1}$, where$1\le i\le \ell +1$. This occurs because$n$ is large enough to compel an element of $X^i$ to hit every element in $X^{i-2}$. To be precise, this means that for any $\ell \ge 2$ and $3\le i\le \ell +1$:

•	If $x_s^i\in X^i$ and $x_t^{i-2}\in X^{i-2}$, then $x_s^i\ge x_t^{i-2}$ for all $1\le s,t\le n+k$.

Moreover, for any $\ell \ge 2$ and $3\le i\le \ell +1$:

•	If $1\le s\le n+k$ and $x_s^i\in X^i$, then $x_s^i\ge x_t^j$ for all $\le j\le i-2$ and $1\le t\le n+k$.

By definition of ${\mathbb{S}}_n^k$, each adjacent set of rows (there are $\ell$ such pairs) contributes $(k+1)(n+k)$ critical pairs to ${⋊}_{\ell }{\mathbb{S}}_n^k$. This is given by each of the $k+1$ misses from each of the $n+k$ nodes in a given pair of adjacent rows. Considering all of the adjacent pairs of rows yield the$(n+k)(k+1)\ell$ critical pairs of${⋊}_{\ell }{\mathbb{S}}_n^k$. We order these critical pairs using lexicographical order on their dual. This process yields a labeling for all of the rows/columns of the matrix ${\mathcal{A}}_n^k\left(\ell \right)$, which has dimensions $\left[(n+k)(k+1)\ell \right]\times \left[(n+k)(k+1)\ell \right]$.

To simplify the computation of matrix ${\mathcal{A}}_n^k\left(\ell \right)$, we decompose ${\mathcal{A}}_n^k\left(\ell \right)$ into${\ell }^2$ submatrices each of size $(k+1)(n+k)\times (k+1)(n+k)$ as described below. First, for integers $r,i$, with $1\le r\le \ell$ and $1\le i\le n+k$, we let $$L_i^r=[(x_i^r,x_i^{r+1}),(x_{i+1}^r,x_i^{r+1}),\dots ,(x_{i+k}^r,x_i^{r+1})],$$where the subscripts in the listing are taken cyclically modulo$n+k$. Then we let $$L_r=[L_1^r,L_2^r,\dots ,L_{n+k-1}^r,L_{n+k}^r].$$Notice that for any $1\le i\le n+k$,$L_i^r$ is an ordered listing of $(k+1)$ critical pairs and hence $L_r$ is an ordered listing of $(k+1)(n+k)$ critical pairs of ${⋊}_{\ell }{\mathbb{S}}_n^k$. Since $r$ ranges between $1$ and$\ell$, we know that$L_1,L_2,\dots ,L_{\ell }$ account for all $(k+1)(n+k)\ell$ critical pairs of ${⋊}_{\ell }{\mathbb{S}}_n^k$.

Now for any two integers $1\le i,j\le \ell$, we let $A_{i,j}$ be the submatrix of ${\mathcal{A}}_n^k\left(\ell \right)$ whose rows are labeled by $L_i$ and whose columns are labeled by $L_j$. Therefore we write $${\mathcal{A}}_n^k\left(\ell \right)={\left[A_{i,j}\right]}_{1\le i,j\le \ell }=\left[\begin{array}{ccccc}\hfill A_{1,1}\hfill & \hfill \cdots \hfill & \hfill A_{1,j}\hfill & \hfill \cdots \hfill & \hfill A_{1,\ell }\hfill \\ \hfill A_{2,1}\hfill & \hfill \cdots \hfill & \hfill A_{2,j}\hfill & \hfill \cdots \hfill & \hfill A_{2,\ell }\hfill \\ \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill \\ \hfill A_{i,1}\hfill & \hfill \cdots \hfill & \hfill A_{i,j}\hfill & \hfill \cdots \hfill & \hfill A_{i,\ell }\hfill \\ \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill \\ \hfill A_{\ell ,1}\hfill & \hfill \cdots \hfill & \hfill A_{\ell ,j}\hfill & \hfill \cdots \hfill & \hfill A_{\ell ,\ell }\hfill \end{array}\right].$$

Next we describe the submatrices $A_{i,j}$ of ${\mathcal{A}}_n^k\left(\ell \right)$, when $n\ge k+3$ and $\ell \ge 1$.

Lemma 1

Let $n\ge k+3$,$\ell \ge 1$ and$1\le i,j\le \ell$. If$A_{i,j}$ is a submatrix of ${\mathcal{A}}_n^k\left(\ell \right)$ where $|i-j|>1$, then $A_{i,j}=\left[0\right]$.

Proof

Suppose there exists a nonzero entry in $A_{i,j}$ where $|i-j|>1$. This implies there exists a strict alternating cycle of the form $$\{(x^{i+1},x^i),(x^{j+1},x^j)\},$$where $(x^i,x^{i+1})$ and $(x^j,x^{j+1})$ are critical pairs in ${\mathbb{P}}_i$ and ${\mathbb{P}}_j$, respectively. We note that since we are dealing with a general critical pair of the specified posets, for sake of simplicity, we omit the subscripts on these critical pairs. By definition of a strict alternating cycle, the following four conditions must hold:

1.	$x^i\left|\right|x^{i+1}$
2.	$x^i\le x^{j+1}$
3.	$x^j\left|\right|x^{j+1}$
4.	$x^j\le x^{i+1}$.

Since $|i-j|>1$, without loss of generality we can assume that $i<j$. Observe that Condition 4. gives a contradiction since $x^j\in min\left({\mathbb{P}}_j\right)$ and $x^{i+1}\in max\left({\mathbb{P}}_i\right)$ but the elements of $min\left({\mathbb{P}}_j\right)$ are above those of $max\left({\mathbb{P}}_i\right)$. Note that if the opposite inequality $(j<i)$ is considered, then Condition 2. yields a contradiction. □

Lemma 2

Let $n\ge k+3$ and $\ell \ge 1$. If$1\le i\le \ell -1$ and$A_{i,i+1}$ is a submatrix of ${\mathcal{A}}_n^k\left(\ell \right)$, then $${\left[A_{i,i+1}\right]}_{(x^i,x_r^{i+1}),(x_s^{i+1},x^{i+2})}=\left\{\begin{array}{cc}1\hfill & \text{if}r=s\hfill \\ 0\hfill & \text{otherwise,}\hfill \end{array}\right.$$where $(x^i,x_r^{i+1})$ and$(x_s^{i+1},x^{i+2})$ are critical pairs of ${\mathbb{P}}_i$ and ${\mathbb{P}}_{i+1}$, respectively.

Proof

Observe that $\{(x^{i+1},x^i),(x^{i+2},x^{i+1})\}$ is a strict alternating cycle provided that the following conditions are satisfied:

1.	$x^{i+1}\left|\right|x^i$
2.	$x^i\le x^{i+2}$
3.	$x^{i+2}\left|\right|x^{i+1}$
4.	$x^{i+1}\le x^{i+1}$ .

Observe that Conditions 1. and 3. hold by definition of critical pairs. Condition 2. holds since $n\ge k+3$. Now notice that the only comparable elements in $min\left({\mathbb{P}}_{i+1}\right)=max\left({\mathbb{P}}_i\right)$ are $x_r^{i+1}=x_s^{i+1}$ provided $r=s$. Namely if two elements in the same row are comparable, then they must be the same element. □

Lemma 3

Let $n\ge k+3$ and $\ell \ge 1$. If$1\le i\le \ell$ and$A_{i,i}$ is a submatrix of ${\mathcal{A}}_n^k\left(\ell \right)$, then $A_{i,i}={\mathcal{A}}_n^k$, where${\mathcal{A}}_n^k$ is the adjacency matrix of the graph ${\mathbf{G}}_{{\mathbb{S}}_n^k}^c$ as described in [3, Theorem 20].

Proof

By definition $A_{i,i}$ is the submatrix of ${\mathcal{A}}_n^k\left(\ell \right)$ whose rows and columns are labeled by the critical pairs $$L_i=[L_1^i,L_2^i,\dots ,L_{n+k-1}^i,L_{n+k}^i],$$where $$L_m^i=[(x_m^i,x_m^{i+1}),(x_{m+1}^i,x_m^{i+1}),\dots ,(x_{m+k}^i,x_m^{i+1})].$$These are exactly the critical pairs of the crown ${\mathbb{S}}_n^k$ at the $i\text{th}$ layer ordered by lexicographical order on their dual. These critical pairs and their ordering are identical (up to a shift in subscripts) to the critical pairs and ordering used in [3, Theorem 20] to describe the adjacency matrix of the graph ${\mathbf{G}}_{{\mathbb{S}}_n^k}^c$, which is denoted ${\mathcal{A}}_n^k$. Therefore the submatrix $A_{i,i}={\mathcal{A}}_n^k$ for all $1\le i\le \ell$. □

Theorem 1

If $n\ge k+3$ and$\ell \ge 1$, then${\mathcal{A}}_n^k\left(\ell \right)={\left[A_{i,j}\right]}_{1\le i,j\le \ell }$ where the submatrices $A_{i,j}$ are described as follows:

•	$A_{i,j}=\left[0\right]$ when $|i-j|>1$;
•	$A_{i,j}$ is as described in Lemma 2 when $|i-j|=1$; and
•	$A_{i,i}$ is as described in Lemma 3.

The proof follows directly from Lemmas 1–3.

Example 4

The smallest example we can consider, which is an actual layered generalized crown, is ${⋊}_2{\mathbb{S}}_4^1$, Fig. 2. We know that ${\mathcal{A}}_4^1\left(2\right)$ is a 20 × 20 matrix and the submatrices $A_{i,j}$, where $1\le i,j\le 2$, have dimension 10 × 10. So to compute ${\mathcal{A}}_4^1\left(2\right)$ it suffices to compute $A_{1,1}$ and $A_{1,2}$, as $A_{2,2}=A_{1,1}$ and $A_{2,1}=A_{1,2}^T$.

First we recall that $$L_1=[\underset{L_1^1}{\underbrace{(x_1^1,x_1^2),(x_2^1,x_1^2)}},\underset{L_2^1}{\underbrace{(x_2^1,x_2^2),(x_3^1,x_2^2)}},\underset{L_3^1}{\underbrace{(x_3^1,x_3^2),(x_4^1,x_3^2)}},\underset{L_4^1}{\underbrace{(x_4^1,x_4^2),(x_5^1,x_4^2)}},\underset{L_5^1}{\underbrace{(x_5^1,x_5^2),(x_1^1,x_5^2)}}],$$and $$L_2=[\underset{L_1^2}{\underbrace{(x_1^2,x_1^3),(x_2^2,x_1^3)}},\underset{L_2^2}{\underbrace{(x_2^2,x_2^3),(x_3^2,x_2^3)}},\underset{L_3^2}{\underbrace{(x_3^2,x_3^3),(x_4^2,x_3^3)}},\underset{L_4^2}{\underbrace{(x_4^2,x_4^3),(x_5^2,x_4^3)}},\underset{L_5^2}{\underbrace{(x_5^2,x_5^3),(x_1^2,x_5^3)}}].$$Then we know that the submatrix $A_{1,1}$ has rows and columns labeled by $L_1$, so using Lemma 3 and [3, Theorem 20], we can compute that $A_{1,1}$ is given by Table 2. Now by Lemma 2 we know that $A_{1,2}$ has nonzero entries of $1$ only at rows whose second entry in its label equals the first entry in the label of the column. Using this and the labeling given by $L_1$ for rows and $L_2$ by columns, we know that the submatrix $A_{1,2}$ is given by Table 3. Therefore the adjacency matrix

Using the information from this adjacency matrix Fig. 5 gives the graph ${\mathbf{G}}_{{⋊}_2{\mathbb{S}}_4^1}^c$.

Notice that by [5, Theorem], $dim\left({⋊}_2{\mathbb{S}}_4^1\right)=4$, and hence $\chi \left({\mathbf{G}}_{{⋊}_2{\mathbb{S}}_4^1}^c\right)\le 4$. Now notice that the graph ${\mathbf{G}}_{{⋊}_2{\mathbb{S}}_4^1}^c$ contains a few triangles between its vertices, for example between the vertices $(x_3^2,x_3^3)$, $(x_5^2,x_5^3)$, and $(x_2^2,x_1^3)$, hence $\chi \left({\mathbf{G}}_{{⋊}_2{\mathbb{S}}_4^1}^c\right)\ge 3$.

In fact ${\mathbf{G}}_{{⋊}_2{\mathbb{S}}_4^1}^c$ is $4$-colorable as seen in Fig. 5.

Table 2 Submatrix $A_{1,1}$ of ${\mathcal{A}}_4^1\left(2\right)$.

Table 3 Submatrix $A_{1,2}$ of ${\mathcal{A}}_4^1\left(2\right)$.

Fig. 5 Graph of critical pairs ${\mathbf{G}}_{{⋊}_2{\mathbb{S}}_4^1}^c$.

4 Characterizing ${\mathcal{A}}_n^k\left(\ell \right)$ when $3\le n<k+3$

We break Section 4 into two subsections based upon the value of $\ell$.

4.1 A small number of layers

In this section we consider the case where $1\le \ell \le ⌈\frac{k+1}{n-2}⌉$. In this setting, all critical pairs of ${⋊}_{\ell }{\mathbb{S}}_n^k$ come from the extreme subposet $\mathcal{E}\left({⋊}_{\ell }{\mathbb{S}}_n^k\right)$, as was shown in the proof of [5, Theorem 4.3]. The extreme subposet $\mathcal{E}\left({⋊}_{\ell }{\mathbb{S}}_n^k\right)$ is the subposet of ${⋊}_{\ell }{\mathbb{S}}_n^k$ generated by the set of minimal elements and maximal elements in ${⋊}_{\ell }{\mathbb{S}}_n^k$. The extreme subposet plays an important role in finding the critical pairs of ${⋊}_{\ell }{\mathbb{S}}_n^k$ and consequently in characterizing the matrices ${\mathcal{A}}_n^k\left(\ell \right)$.

Theorem 2

Let $3\le n<k+3$ and$1\le \ell \le ⌈\frac{k+1}{n-2}⌉$. Then${\mathcal{A}}_n^k\left(\ell \right)={\mathcal{A}}_{n+(\ell -1)(n-2)}^{k-(\ell -1)(n-2)}$, where${\mathcal{A}}_{n+(\ell -1)(n-2)}^{k-(\ell -1)(n-2)}$ is the adjacency matrix of the graph ${\mathbf{G}}_{{\mathbb{S}}_{n+(\ell -1)(n-2)}^{k-(\ell -1)(n-2)}}^c$ as described in [3, Theorem 20].

Proof

By [5, Theorem 4.3] the critical pairs of ${⋊}_{\ell }{\mathbb{S}}_n^k$ are exactly the critical pairs of the extreme subposet $\mathcal{E}\left({⋊}_{\ell }{\mathbb{S}}_n^k\right)$. Moreover $\mathcal{E}\left({⋊}_{\ell }{\mathbb{S}}_n^k\right)\cong {\mathbb{S}}_{n+(\ell -1)(n-2)}^{k-(\ell -1)(n-2)}$, whenever $3\le n<k+3$ and $1\le \ell \le ⌈\frac{k+1}{n-2}⌉$. Thus the adjacency matrix ${\mathcal{A}}_n^k\left(\ell \right)={\mathcal{A}}_{n+(\ell -1)(n-2)}^{k-(\ell -1)(n-2)}$ as claimed. □

Observe that Example 3 satisfies all of the conditions of Theorem 2.

4.2 A large number of layers

Now we consider $\ell >⌈\frac{k+1}{n-2}⌉$. In this case the critical pairs of ${⋊}_{\ell }{\mathbb{S}}_n^k$ arise from various extreme subposets, as shown in the proof of [5, Theorem 4.4]. We begin by setting some notation.

Notation 4

We adopt the notation used in the proof of [5, Theorem 4.3]. Let $$\mathbb{P}={\mathbb{P}}_1⋊{\mathbb{P}}_2⋊\cdots ⋊{\mathbb{P}}_{\ell },$$where ${\mathbb{P}}_1={\mathbb{P}}_2=\cdots ={\mathbb{P}}_{\ell }={\mathbb{S}}_n^k$. Setting $w=⌈\frac{k+1}{n-2}⌉$, we let ${\mathcal{E}}_{j,j+w}=\mathbb{P}(X^j\cup X^{j+w})$, where $j=1,\dots ,\ell -w+1$. From the proof of [5, Theorem 4.3] we know that the critical pairs of$\mathbb{P}$ come from the incomparable elements in the subposets ${\mathcal{E}}_{j,j+w}$. Hence $$\mathrm{Crit}\left(\mathbb{P}\right)=\underset{j=1}{\overset{\ell -w+1}{⨆}}\mathrm{Crit}\left({\mathcal{E}}_{j,j+w}\right).$$

For $j=1,\dots ,\ell -w+1$, let${\mathcal{C}}_j$ denote the elements of $\mathrm{Crit}\left({\mathcal{E}}_{j,j+w}\right)$ ordered using lexicographical order on the dual of the critical pairs of${\mathcal{E}}_{j,j+w}$. For a fixed $j=1,\dots ,\ell -w+1$, suppose $x_p^j\in X^j$ and $x_q^{j+w}\in X^{j+w}$ such that $x_p^j\left|\right|x_q^{j+w}$ in$\mathbb{P}$. Then the index $q$ must be a value in the set of cyclic indexing values: $$q\in \{p+w(n-1)+1,p+w(n-1)+2,\dots ,p+w-1\}.$$

Therefore, for $j=1,\dots ,\ell -w+1$, $$\mathrm{Crit}\left({\mathcal{E}}_{j,j+w}\right)=\underset{p=1}{\overset{n+k}{⨆}}\left\{(x_p^j,x_s^{j+w}):s\in \{p+w(n-1)+1,p+w(n-1)+2,\dots ,p+w-1\}\right\}.$$

Let $A_{i,j}$ denote the submatrix of ${\mathcal{A}}_n^k\left(\ell \right)$ whose rows are labeled by ${\mathcal{C}}_i$ and whose columns are labeled by ${\mathcal{C}}_j$. Then we write $${\mathcal{A}}_n^k\left(\ell \right)={\left[A_{i,j}\right]}_{1\le i,j\le \ell -w+1}=\left[\begin{array}{ccccc}\hfill A_{1,1}\hfill & \hfill \cdots \hfill & \hfill A_{1,j}\hfill & \hfill \cdots \hfill & \hfill A_{1,\ell -w+1}\hfill \\ \hfill A_{2,1}\hfill & \hfill \cdots \hfill & \hfill A_{2,j}\hfill & \hfill \cdots \hfill & \hfill A_{2,\ell -w+1}\hfill \\ \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill \\ \hfill A_{i,1}\hfill & \hfill \cdots \hfill & \hfill A_{i,j}\hfill & \hfill \cdots \hfill & \hfill A_{i,\ell -w+1}\hfill \\ \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill \\ \hfill A_{\ell -w+1,1}\hfill & \hfill \cdots \hfill & \hfill A_{\ell -w+1,j}\hfill & \hfill \cdots \hfill & \hfill A_{\ell -w+1,\ell -w+1}\hfill \end{array}\right].$$

Lemma 4

Let $3\le n<k+3$,$w=⌈\frac{k+1}{n-2}⌉$, and$\ell >w$. If$1\le i\le \ell -w+1$ and$A_{i,i}$ is a submatrix of ${\mathcal{A}}_n^k\left(\ell \right)$, then $A_{i,i}={\mathcal{A}}_{n+(w-1)(n-2)}^{k-(w-1)(n-2)}$.

Proof

By definition $A_{i,i}$ is the submatrix of ${\mathcal{A}}_n^k\left(\ell \right)$ whose rows and columns are labeled by the elements of ${\mathcal{C}}_i=\mathrm{Crit}\left({\mathcal{E}}_{i,i+w}\right)$, which are ordered using lexicographical order on their dual. These critical pairs are only arising from the extreme subposet of ${⋊}_w{\mathbb{S}}_n^k$, denoted ${\mathcal{E}}_{i,i+w}=(X^i\cup X^{i+w})$. By [5, Theorem 4.3] we know that the extreme subposet ${\mathcal{E}}_{i,i+w}\cong {\mathbb{S}}_{n+(w-1)(n-2)}^{k-(w-1)(n-2)}$. Therefore the submatrix $A_{i,i}={\mathcal{A}}_{n+(w-1)(n-2)}^{k-(w-1)(n-2)}$, where ${\mathcal{A}}_{n+(w-1)(n-2)}^{k-(w-1)(n-2)}$ is the adjacency matrix of the graph ${\mathbf{G}}_{{\mathbb{S}}_{n+(w-1)(n-2)}^{k-(w-1)(n-2)}}^c$. □

Lemma 5

Let $3\le n<k+3$,$w=⌈\frac{k+1}{n-2}⌉$, and$\ell >w$. If$1\le i,j\le \ell -w+1$ and$A_{i,j}$ is a submatrix of ${\mathcal{A}}_n^k\left(\ell \right)$ such that $0<|i-j|=d<w$, then $${\left[A_{i,j}\right]}_{(x^i,x_r^{i+w}),(x_s^j,x^{j+w})}=\left\{\begin{array}{cc}1\hfill & \text{if}s\in [r-w+d,r-w+d-1,\dots ,r-(w-d)(n-1)]\hfill \\ 0\hfill & \text{otherwise},\hfill \end{array}\right.$$where the integers $r-w+d,r-w+d-1,\dots ,r-(w-d)(n-1)$ are taken modulo $(n+k)$.

Proof

Without loss of generality assume that $j>i$. Let $j=i+d$, where $d<w$. Assume $(x^i,x_r^{i+w})\in \mathrm{Crit}\left({\mathcal{E}}_{i,i+w}\right)$ and $(x_s^j,x^{j+w})\in \mathrm{Crit}\left({\mathcal{E}}_{j,j+w}\right)$. Then $$\{(x_r^{i+w},x^i),(x^{j+w},x_s^j)\},$$forms a strict alternating cycle if and only if the following two conditions are satisfied: (1) $$x^i\le x^{j+w},$$$$x_s^j\le x_r^{i+w}.$$(1) Using the fact that $j=i+d$, where $d<w$, Conditions (1) and (2) are (respectively) equivalent to: (3) $$x^i\le x^{i+d+w},$$$$x_s^{i+d}\le x_r^{i+w}.$$(3) Then Condition (3) holds since every element of $X^i$ is comparable to every element of $X^{i+d+w}$. However, Condition (4) holds only when $x_s^{i+d}\in D\left(x_r^{i+w}\right)$. For $x_r^{i+w}\in X^{i+w}$ we compute the following information.

In fact $$D\left(x_r^{i+w}\right)\cap X^{i+d}=\{x_{r+d-w}^{i+w},x_{r+d-w-1}^{i+w},x_{r+d-w-2}^{i+w},\dots ,x_{r-(w-d)(n-1)}^{i+w}\},$$where the subscripts are taken modulo $(n+k)$. Therefore, $x_s^{i+d}\in D\left(x_r^{i+w}\right)$ if and only if $$s\in [r-w+d,r-w+d-1,\dots ,r-(w-d)(n-1)].\square$$

Lemma 6

Let $3\le n<k+3$,$w=⌈\frac{k+1}{n-2}⌉$, and$\ell >w$. If$1\le i,j\le \ell -w+1$ and$A_{i,j}$ is a submatrix of ${\mathcal{A}}_n^k\left(\ell \right)$ such that $|i-j|=w$, then $${\left[A_{i,j}\right]}_{(x^i,x_r^{i+w}),(x_s^j,x^{j+w})}=\left\{\begin{array}{cc}1\hfill & \text{if}r=s\hfill \\ 0\hfill & \text{otherwise.}\hfill \end{array}\right.$$

Proof

Without loss of generality assume that $j=i+w$. Assume $(x^i,x_r^{i+w})\in \mathrm{Crit}\left({\mathcal{E}}_{i,i+w}\right)$ and $(x_s^j,x^{j+w})\in \mathrm{Crit}\left({\mathcal{E}}_{j,j+w}\right)$. Then $$\{(x_r^{i+w},x^i),(x^{j+w},x_s^j)\},$$forms a strict alternating cycle if and only if the following two conditions are satisfied: (5) $$x^i\le x^{j+w},$$$$x_s^j\le x_r^{i+w}.$$(5) Using the fact that $j=i+w$, Conditions (5) and (6) are (respectively) equivalent to: (7) $$x^i\le x^{i+2w},$$$$x_s^j\le x_r^j.$$(7) Then Condition (7) holds since every element of $X^i$ is hit by (or is less than or equal) every element of $X^{i+2w}$. However Condition (8) only holds when $r=s$, as expected. □

Lemma 7

Let $3\le n<k+3$,$w=⌈\frac{k+1}{n-2}⌉$, and$\ell >w$. If$A_{i,j}$ is a submatrix of ${\mathcal{A}}_n^k\left(\ell \right)$ such that $|i-j|>w$, then $A_{i,j}=\left[0\right]$.

Proof

Without loss of generality we assume that $j-i>w$ and let $(x^i,x^{i+w})\in \mathrm{Crit}\left({\mathcal{E}}_{i,i+w}\right)$ and $(x^j,x^{j+w})\in \mathrm{Crit}\left({\mathcal{E}}_{j,j+w}\right)$. Note that $$\{(x^{i+w},x^i),(x^{j+w},x^j)\}$$will never form a strict alternating cycle since $x^j\in X^j$ and $x^{i+w}\in X^{i+w}$, where $j>i+w$ therefore $x^j\nleqq x^{i+w}$. This implies that no strict alternating cycles exist, and thus $A_{i,j}=\left[0\right]$, whenever $|j-i|>w$. □

We now give the main result in this section.

Theorem 3

If $3\le n<k+3$,$w=⌈\frac{k+1}{n-2}⌉$, and$\ell >w$, then${\mathcal{A}}_n^k\left(\ell \right)={\left[A_{i,j}\right]}_{1\le i,j\le \ell }$ where the submatrices $A_{i,j}$ are described as follows:

•	$A_{i,i}$ is as described in Lemma 4,
•	$A_{i,j}$ is as described in Lemma 5 when $0<|i-j|<w$,
•	$A_{i,j}$ is as described in Lemma 6 when $|i-j|=w$,
•	$A_{i,j}=\left[0\right]$ when $|i-j|>w$.

The proof follows directly from Lemmas 4–7.

We demonstrate with an example how the matrix ${\mathcal{A}}_n^k\left(\ell \right)$ changes as more layers are added to a generalized crown.

Example 5

In this example we begin with a detailed computation of ${\mathcal{A}}_3^1\left(3\right)$ and its associated graph ${\mathbf{G}}_{{⋊}_3{\mathbb{S}}_3^1}^c$. We will then provide the matrices ${\mathcal{A}}_3^1\left(4\right)$ and ${\mathcal{A}}_3^1\left(5\right)$ and their associated graphs ${\mathbf{G}}_{{⋊}_4{\mathbb{S}}_3^1}^c$ and ${\mathbf{G}}_{{⋊}_5{\mathbb{S}}_3^1}^c$, respectively.

In this case the critical pairs arise from the extreme subposets ${\mathcal{E}}_{1,3}=\mathbb{P}(X^1\cup X^3)$ and ${\mathcal{E}}_{2,4}=\mathbb{P}(X^2\cup X^4)$, as depicted in Fig. 6. These critical pairs are as follows: $$\text{Critical pairs from}{\mathcal{E}}_{1,3}\text{:}(x_1^1,x_2^3),(x_2^1,x_3^3),(x_3^1,x_4^3),(x_4^1,x_1^3),$$$$\text{Critical pairs from}{\mathcal{E}}_{2,4}\text{:}(x_1^2,x_2^4),(x_2^2,x_3^4),(x_3^2,x_4^4),(x_4^2,x_1^4).$$ The eight critical pairs imply that ${\mathcal{A}}_3^1\left(3\right)$ has dimension 8 × 8. As before, we label the rows/columns by using lexicographical ordering on the dual of the critical pairs. That is, the rows and columns will be labeled as follows: $$(x_4^1,x_1^3),(x_1^1,x_2^3),(x_2^1,x_3^3),(x_3^1,x_4^3),(x_4^2,x_1^4),(x_1^2,x_2^4),(x_2^2,x_3^4),(x_3^2,x_4^4).$$To determine the non-zero entries of ${\mathcal{A}}_3^1\left(3\right)$ we determine that from the above critical pairs the following sets form strict alternating cycles: $$\{(x_1^3,x_4^1),(x_2^3,x_1^1)\},\{(x_1^3,x_4^1),(x_3^3,x_2^1)\},\{(x_1^3,x_4^1),(x_4^3,x_3^1)\},\{(x_1^3,x_4^1),(x_1^4,x_4^2)\},$$ $$\{(x_1^3,x_4^1),(x_4^4,x_3^2)\},\{(x_2^3,x_1^1),(x_3^3,x_2^1)\},\{(x_2^3,x_1^1),(x_4^3,x_3^1)\},\{(x_2^3,x_1^1),(x_1^4,x_4^2)\},$$ $$\{(x_2^3,x_1^1),(x_2^4,x_1^2)\},\{(x_3^3,x_2^1),(x_4^3,x_3^1)\},\{(x_3^3,x_2^1),(x_2^4,x_1^2)\},\{(x_3^3,x_2^1),(x_3^4,x_2^2)\},$$ $$\{(x_4^3,x_3^1),(x_3^4,x_2^2)\},\{(x_4^3,x_3^1),(x_4^4,x_3^2)\},\{(x_1^4,x_4^2),(x_2^4,x_1^2)\},\{(x_1^4,x_4^2),(x_3^4,x_2^2)\},$$ $$\{(x_1^4,x_4^2),(x_4^4,x_3^2)\},\{(x_2^4,x_1^2),(x_3^4,x_2^2)\},\{(x_2^4,x_1^2),(x_4^4,x_3^2)\},\{(x_3^4,x_2^2),(x_4^4,x_3^2)\}.$$The above information is enough to give the graph ${\mathbf{G}}_{{⋊}_3{\mathbb{S}}_3^1}^c$, depicted in Fig. 7, and its adjacency matrix ${\mathcal{A}}_3^1\left(3\right)$, as seen in Table 4. When we consider the $4$-layered crown ${⋊}_4{\mathbb{S}}_3^1$, we obtain ${\mathcal{A}}_3^1\left(4\right)$, as shown in Table 5 and the graph ${\mathbf{G}}_{{⋊}_4{\mathbb{S}}_3^1}^c$ is given in Fig. 8. From the $5$-layered crown ${⋊}_5{\mathbb{S}}_3^1$, we obtain ${\mathcal{A}}_3^1\left(5\right)$, as shown in Table 6 and the graph ${\mathbf{G}}_{{⋊}_5{\mathbb{S}}_3^1}^c$, which is given in Fig. 9.

Table 4 ${\mathcal{A}}_3^1\left(3\right)$.

Table 5 ${\mathcal{A}}_3^1\left(4\right)$.

Table 6 ${\mathcal{A}}_3^1\left(5\right)$.

We recall that Garcia and Silva proved [5, Theorem 4.4]: For $3\le n<k+3$ and for $\ell \in \mathbb{N}$ with $\ell \ge ⌈\frac{k+1}{n-2}⌉$, then $dim\left({⋊}_{\ell }{\mathbb{S}}_n^k\right)=⌈\frac{2(n+k)}{k+n-⌈\frac{k+1}{n-2}⌉(n-2)}⌉$. Using this result and the fact that in our examples $\ell \ge ⌈\frac{1+1}{3-2}⌉=2$, we note that $dim\left({⋊}_3{\mathbb{S}}_3^1\right)=dim\left({⋊}_4{\mathbb{S}}_3^1\right)=dim\left({⋊}_5{\mathbb{S}}_3^1\right)=4$. Then by the result of Trotter and Felsner, [1], the chromatic number of the graphs ${\mathbf{G}}_{{⋊}_3{\mathbb{S}}_3^1}^c$, ${\mathbf{G}}_{{⋊}_4{\mathbb{S}}_3^1}^c$, and ${\mathbf{G}}_{{⋊}_5{\mathbb{S}}_3^1}^c$ is less than or equal to $4$. In fact, all of these graphs contain $K_4$, the complete graph on four vertices, as a subgraph, hence they are in fact $4$-colorable and this is depicted in the respective graphs in Figs. 7–9.

Fig. 6 ${⋊}_3{\mathbb{S}}_3^2$.

Fig. 7 Graph of critical pairs ${\mathbf{G}}_{{⋊}_3{\mathbb{S}}_3^1}^c$.

Fig. 8 Graph of critical pairs ${\mathbf{G}}_{{⋊}_4{\mathbb{S}}_3^1}^c$.

Fig. 9 Graph of critical pairs ${\mathbf{G}}_{{⋊}_5{\mathbb{S}}_3^1}^c$.

Given the results in [2], we conjecture that the chromatic number is equal to the order dimension computed in [5] for layered generalized crowns.

Conjecture 1

Let $\mathbb{P}$ be the$\ell$-layered generalized crown ${⋊}_{\ell }{\mathbb{S}}_n^k$. Then, $\chi \left({\mathbf{G}}_{\mathbb{P}}^c\right)=dim\left(\mathbb{P}\right)$, where $dim\left(\mathbb{P}\right)$ is as given in [5].

Acknowledgment

The authors extend their gratitude to the National Science Foundation Division of Mathematical Sciences (DMS-1045082) for travel support.