Block circulant graphs and the graphs of critical pairs of crowns

Electronic Journal of Graph Theory and Applications

Rebecca E. Garcia^a, Pamela E. Harris^b, Bethany Kubik^c, Shannon Talbott^d

mth_reg@shsu.edu, peh2@williams.edu, bakubik@d.umn.edu, talbotts@moravian.edu

In this paper, we provide a natural bijection between a special family of block circulant graphs and the graphs of critical pairs of the posets known as generalized crowns. In particular, every graph in this family of block circulant graphs we investigate has a generating block row that follows a symmetric growth pattern of the all ones matrix. The natural bijection provides an upper bound on the chromatic number for this infinite family of graphs.

Keywords: circulant matrix, order dimension, bipartite poset, chromatic number Mathematics Subject Classification: 05C15, 06A06, 06A07

DOI: 10.5614/ejgta.2019.7.2.1

1. Introduction

Computing the chromatic number of circulant graphs, graphs whose adjacency matrices are circulant, is an NP-hard problem, as shown by Codenotti, Gerace, and Vigna [1]. This led to the development of efficient algorithms to compute the chromatic number of circulant graphs which improve current graph coloring algorithms [3]. However, even with this improvement, the chromatic number problem for circulant and block circulant matrices remains an active area of research. Similarly, current algorithms for computing the order dimension of posets in general rely on the computation of the chromatic number of an associated hypergraph, whose computational time

Received: 18 October 2018, Revised: 8 February 2019, Accepted: 30 March 2019.

^&lt;sup>a</sup>Department of Mathematics and Statistics, Sam Houston State University

^&lt;sup>b</sup>Department of Mathematics and Statistics, Williams College

^&lt;sup>c</sup>Department of Mathematics and Statistics, University of Minnesota Duluth

^&lt;sup>d</sup>Mathematics and Computer Science Department, Moravian College

grows exponentially with the poset size [8]. However, for a specific family of height 2 posets known as generalized crowns, there is an explicit formula for the order dimension [6].

In this paper, we provide a natural bijection between the associated graphs of generalized crowns and a particular family of block circulant graphs. The special family of block circulant graphs, whose elements are denoted by \(\mathcal{BC}_s^t\), are parameterized by two positive integer values s and t. These graphs are generated by a block row with a symmetric growth pattern of the all ones matrix. Our main result is as follows:

Theorem 1.1. [Graph Isomorphism] Let \(n \geq 3\) and \(k \geq 0\). If \(\mathbf{G}_n^k\) is the graph of critical pairs of \(\mathbb{S}_n^k\), then \(\mathbf{G}_n^k\) is the graph isomorphic to \(\mathcal{BC}_{n+k}^{k+1}\).

The significance of this work comes from the relation between the chromatic number of the graph \(\mathbf{G}_n^k\) and the order dimension of the crown \(\mathbb{S}_n^k\). Felsner and Trotter showed that for every finite poset \(\mathbb{P}\), \(\dim(\mathbb{P}) \geq \chi(\mathbf{G}_{\mathbb{P}}^c)\) where \(\dim(\mathbb{P})\) denotes the order dimension of the poset \(\mathbb{P}\), \(\mathbf{G}_{\mathbb{P}}^c\) denotes the graph of critical pairs of \(\mathbb{P}\), and \(\chi\) refers to the chromatic number of \(\mathbf{G}_{\mathbb{P}}^c\) [4, Lemma 3.3]. Thus, the chromatic number of these particular block circulant graphs equals the chromatic number of the associated graph of a generalized crown, and so has an upper bound given by the dimension of the poset.

This paper is organized as follows: Section 2 provides the necessary background material on block circulant matrices and poset theory to make our approach precise. In Section 3, we prove the graph isomorphism between \(G_n^k\) and \(\mathcal{BC}_{n+k}^{k+1}\) (see Theorem 1.1). Section 4 concludes with a few open questions and directions for future work.

2. Background

An m-block circulant matrix C is a matrix of dimension \(nm \times nm\) that is generated by the matrices \(C_1, C_2, \ldots, C_n\) of dimension \(m \times m\), where the block rows of C are obtained by cyclically shifting the \(C_i\)'s as follows:

\[C = \operatorname{circ}(C_1, C_2, \dots, C_n) = \begin{bmatrix} C_1 & C_2 & C_3 & \cdots & C_{n-1} & C_n \\ C_n & C_1 & C_2 & \cdots & C_{n-2} & C_{n-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ C_3 & C_4 & C_5 & \cdots & C_1 & C_2 \\ C_2 & C_3 & C_4 & \cdots & C_n & C_1 \end{bmatrix}.\]

The matrix C has block size m and a generating block row consisting of the matrices \(C_1, C_2, \ldots, C_n\). If the matrices \(C_1, C_2, \ldots, C_n\) are circulant, then C is said to be an m-block circulant matrix with circulant blocks. We note that a circulant matrix is a 1-block circulant matrix. Whenever m is understood, we refer to an m-block circulant matrix as a block circulant matrix.

Let \(\mathcal{BC}\) denote the family of block circulant matrices with non-negative integer entries. Abusing notation, let \(\mathcal{BC}\) also denote the family of graphs whose adjacency matrices are block circulant. Our object of study is an infinite subfamily of graphs in \(\mathcal{BC}\), whose elements are the graphs denoted by \(\mathcal{BC}_s^t\) having a t-block circulant adjacency matrix and generating block row \(B_1, B_2, \ldots, B_s\), where \(t \geq 1\) and \(s \geq t + 2\). To define \(B_1, B_2, \ldots, B_s\), set the following notation:

Notation 2.1. Let \(1 \le i \le t\). The \(t \times t\) block \(\mathbb{1}^i\) has an \(i \times i\) block of ones in the upper right corner, with the remaining entries of the \(t \times t\) block being zero. Similarly, the \(t \times t\) block i has an \(i \times i\) block of ones in the lower left corner, with the remaining entries of the \(t \times t\) block being zero. For example, a \(6 \times 6\) block 1 and a \(6 \times 6\) block 2 are shown below:

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

The \(t \times t\) block \(\mathbb{1}_{t \times t}\) is the all ones \(t \times t\) matrix. Similarly, the \(t \times t\) block \(\mathbb{0}_{t \times t}\) is the zero \(t \times t\) matrix.

Define the generating block row of \(\mathcal{BC}_s^t\) as follows:

Case 1. If \(s \geq 2t\), then set

\[B_{i} = \begin{cases} 0_{t \times t}, & \text{if } i = 1; \\ 1^{i-1}, & \text{if } 2 \leq i \leq t; \\ 1_{t \times t}, & \text{if } t + 1 \leq i \leq s - t + 1; \\ s + 1 - i \mathbb{1}, & \text{if } s - t + 2 \leq i \leq s. \end{cases}\]

As an example, the generating block row of \(\mathcal{BC}_7^3\) is

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

Case 2. If s < 2t - 1, then set

\[B_i = \begin{cases} \mathbb{O}_{t \times t}, & \text{if } i = 1; \\ \mathbb{1}^{i-1}, & \text{if } 2 \leq i \leq s - t + 1; \\ \begin{bmatrix} 0 & 0 & \mathbb{O}_{(t-s-1+i) \times (t-s-1+i)} \\ 0 & \mathbb{1}_{(s-t) \times (s-t)} & 0 \\ \mathbb{O}_{(t-i+1) \times (t-i+1)} & 0 & 0 \\ \end{bmatrix}, & \text{if } s - t + 2 \leq i \leq t; \\ s - t + 1, & \text{if } t + 1 \leq i \leq s. \end{cases}\]

As an example, the generating block row of \(\mathcal{BC}_6^4\) is

\[\left[ B_1 \middle| B_2 \middle| B_3 \middle| B_4 \middle| B_5 \middle| B_6 \right] = \begin{bmatrix} 0\,0\,0\,0 & 0\,0\,0\,1 & 0\,0\,1\,1 & 0\,0\,0\,0 & 0\,0\,0\,0 & 0\,0\,0 \\ 0\,0\,0\,0 & 0\,0\,0\,0 & 0\,0\,1\,1 & 0\,1\,1\,0 & 0\,0\,0\,0 & 0\,0\,0\,0 \\ 0\,0\,0\,0 & 0\,0\,0\,0 & 0\,0\,0\,0 & 0\,1\,1\,0 & 1\,1\,0\,0 & 0\,0\,0\,0 \\ 0\,0\,0\,0 & 0\,0\,0\,0 & 0\,0\,0\,0 & 0\,0\,0\,0 & 1\,1\,0\,0 & 1\,1\,0\,0 & 1\,0\,0\,0 \end{bmatrix}.\]

To provide the connection to the graph of critical pairs of generalized crowns, we now focus our attention on the necessary background in poset theory. We assume some familiarity with posets, order dimension, and chromatic number and refer the interested reader to [2, 5, 6, 7] for further background.

Throughout this paper, let \(n, k \in \mathbb{N}\) with \(n \geq 3\) and \(k \geq 0\). The generalized crown, denoted \(\mathbb{S}_n^k\), is a height 2 poset with \(\min(\mathbb{S}_n^k) = \{a_1, \ldots, a_{n+k}\}\) and \(\max(\mathbb{S}_n^k) = \{b_1, \ldots, b_{n+k}\}\), where

• (1) \(b_i||a_i, a_{i+1}, \dots, a_{i+k},\)and
• (2) \(b_i > a_{i+k+1}, a_{i+k+2}, \dots, a_{i-1}\).

Figure 1. The crown \(\mathbb{S}_4^3\)

Figure 1 provides the diagram for the generalized crown \(\mathbb{S}_4^3\). Identifying \(a_i\) with \(a_{i-(n+k)}\) and \(b_i\) with \(b_{i-(n+k)}\) for i>n+k is called cyclic indexing. The set of all incomparable pairs of \(\mathbb{S}_n^k\) is denoted by \(\operatorname{Inc}(\mathbb{S}_n^k) = \{(x,y) \in \mathbb{S}_n^k \times \mathbb{S}_n^k : x||y\}\). The pair \((x,y) \in \mathbb{S}_n^k \times \mathbb{S}_n^k\) is critical if the following conditions hold:(i) x||y; (ii) \(D(x) \subset D(y)\); and (iii) \(U(y) \subset U(x)\), where \(D(u) = \{z \in \mathbb{S}_n^k : z < u\}\) and \(U(w) = \{z \in \mathbb{S}_n^k : w < z\}\) for any \(u, w \in \mathbb{S}_n^k\). Let \(\operatorname{Crit}(\mathbb{S}_n^k)\) denote the set of all critical pairs of \(\mathbb{S}_n^k\). An alternating cycle is a sequence \(\{(x_i, y_i) : 1 \le i \le k\}\) of ordered pairs from \(\operatorname{Inc}(\mathbb{S}_n^k)\), where \(y_i \le x_{i+1}\) in \(\mathbb{S}_n^k\) (cyclically) for \(i = 1, 2, \ldots, k\). An alternating cycle is said to be strict if \(y_i < x_i\) in \(\mathbb{S}_n^k\) if and only if j = i+1 (cyclically) for \(i, j = 1, 2, \ldots, k\).

strict if \(y_i \leq x_j\) in \(\mathbb{S}_n^k\) if and only if j = i+1 (cyclically) for \(i, j = 1, 2, \ldots, k\). The strict hypergraph of critical pairs of \(\mathbb{S}_n^k\), denoted \(\mathbf{H}_n^k\), is the hypergraph with vertices \(\mathrm{Crit}(\mathbb{S}_n^k)\) and edges consisting of subsets of \(\mathrm{Crit}(\mathbb{S}_n^k)\) whose duals form strict alternating cycles. If (x,y) is a critical pair, then (y,x) is its dual. Let \(\mathbf{G}_n^k\) denote the graph of \(\mathbf{H}_n^k\). That is, \(\mathbf{G}_n^k\) is a graph with vertices \(\mathrm{Crit}(\mathbb{S}_n^k)\) and edges consisting of size 2 subsets of \(\mathrm{Crit}(\mathbb{S}_n^k)\) whose duals form strict alternating cycles.

In general, computation of the order dimension of a poset is an NP-hard problem, as stated in [8]. However, for this particular family of posets, Trotter obtains an explicit formula for the dimension of the crown \(\mathbb{S}_n^k\).

Theorem 2.2 ([5]). For each \(n \geq 3\) and \(k \geq 0\), the dimension of the crown \(\mathbb{S}_n^k\) is given by:

\[\dim(\mathbb{S}_n^k) = \left\lceil \frac{2(n+k)}{k+2} \right\rceil.\]

With these definitions at hand, we now formulate the set bijection between the families of graphs \(\{G_n^k\}_{n\geq 3, k\geq 0}\) and \(\{\mathcal{BC}_s^t\}_{t\geq 1, s\geq t+2}\).

3. The graph isomorphism of \(G_n^k\) and \(\mathcal{BC}_s^t\)

In this section, we prove: Propositions 3.1 and 3.2, which make clear that every \(\mathbf{G}_n^k\) belongs to the family \(\{\mathcal{BC}_s^t\}\), and Theorem 3.4, which demonstrates that every graph \(\mathcal{BC}_s^t\) arises as the graph \(\mathbf{G}_{t-1}^{s-t+1}\), where \(t \geq 1\) and \(s \geq t+2\). Together these results establish Theorem 1.1.

Let \(\mathcal{A}_n^k\) denote the adjacency matrix of \(\mathbf{G}_n^k\). To give the entries of the matrix \(\mathcal{A}_n^k\), first note that \(\mathbb{S}_n^k\) has (n+k)(k+1) critical pairs, which we list in lexicographical order on their dual and use this labeling on the rows (and by symmetry columns) of the matrix \(\mathcal{A}_n^k\). Our notation is as follows:

Notation 3.1. Fix \(1 \le i, j \le n+k\) and let \(A_{i,j}\) denote the \((k+1) \times (k+1)\) submatrix whose rows are labeled by the k+1 critical pairs: \((a_i,b_i), (a_{i+1},b_i), \ldots, (a_{i+k-1},b_i), (a_{i+k},b_i)\), and whose columns are labeled by the k+1 critical pairs: \((a_j,b_j), (a_{j+1},b_j), \ldots, (a_{j+k-1},b_j), (a_{j+k},b_j)\), where all the subscripts of the first component are taken cyclically modulo n+k. Then \(\mathcal{A}_n^k = [A_{i,j}]_{1 \le i,j \le n+k}\). For fixed \(1 \le i,j \le n+k\), let \(m_{u,v}\) denote the (u,v)-entry of the submatrix \(A_{i,j}\). Notice that u ranges from i to k+i, where the order is fixed and all terms are taken modulo n+k. Similarly, v ranges from j to j+k, where the order is fixed and the terms are taken modulo n+k. Denote these ranges by writing \(u \in [i, i+1, \ldots, i+k]_{mod(n+k)}\) and \(v \in [j, j+1, \ldots, j+k]_{mod(n+k)}\).

Example 3.2. The matrix \(\mathcal{A}_4^3\) is determined by which duals of critical pairs of \(\mathbb{S}_4^3\) form strict alternating cycles of size 2; see Table 1. A computation shows that \(\mathbf{G}_4^3\) is 3-colorable; see Figure 2.

Table 1. Adjacency matrix \(A_4^3\)

Figure 2. Graph \(\mathbf{G}_4^3 \cong \mathcal{BC}_7^4\)

Theorem 3.3. Let \(\mathcal{A}_n^k = [A_{i,j}]_{1 \leq i,j \leq n+k}\), where \(n \geq 3\) and \(k \geq 0\). Then the \((k+1) \times (k+1)\) submatrices \(A_{i,j}\) are as follows:

1. If \[i = j\], then \(A_{i,j} = \mathbb{O}_{(k+1)\times(k+1)}\).

2. If \(i \neq j\), then \(A_{i,j} = [m_{u,v}]\), where

\[m_{u,v} = \begin{cases} 1, & \text{for } u \in \{i, i+1, \dots, i+k\} \cap \{j+k+1, j+k+2, \dots, j-1\} \\ & \text{and } v \in \{j, j+1, \dots, j+k\} \cap \{i+k+1, i+k+2, \dots, i-1\}; \\ 0, & \text{otherwise.} \end{cases}\]

Proof. Recall that \(m_{u,v}=1\) if \((b_i,a_u)\) and \((b_j,a_v)\) form a strict alternating cycle, otherwise \(m_{u,v}=0\). By definition, the critical pairs (a,b) and (a',b') form a strict alternating cycle if and only if (1) b||a; (2) a < b'; (3) b'||a'; and (4) a' < b. By the definition of \(\mathbb{S}^k_n\), condition (1) implies \(u \in \{i,i+1,\ldots,i+k\}\); condition (2) implies \(u \in \{j+k+1,j+k+2,\ldots,j-1\}\); condition (3) implies \(v \in \{j,j+1,\ldots,j+k\}\); and condition (4) implies \(v \in \{i+k+1,i+k+2,\ldots,i-1\}\). Thus \(m_{u,v}=1\) whenever the preceding statements hold simultaneously and otherwise \(m_{u,v}=0\).

Case 1. Assume that i=j. We claim that \(A_{i,i}=\mathbb{O}_{(k+1)\times(k+1)}\). Suppose to the contrary that there exists \(u\in[i,i+1,\ldots,k+i]\) \(_{\mathrm{mod}\;(n+k)}\) and \(v\in[j,j+1,\ldots,k+j]\) \(_{\mathrm{mod}\;(n+k)}\) such that \(m_{u,v}=1\). Then \(\{(b_i,a_u),(b_i,a_v)\}\) forms a strict alternating cycle. Condition (2) implies that \(a_u< b_i\). This contradicts condition (1). Therefore \(A_{i,i}=\mathbb{O}_{(k+1)\times(k+1)}\).

Case 2. If \(i \neq j\), then the preceding implications yield the desired result.

We now state our first result in connection with block circulant matrices.

Theorem 3.4. If \(n \geq 3\) and \(k \geq 0\), then \(A_n^k\) is a (k+1)-block circulant matrix.

Proof. We show that \(A_{i,j} = A_{i+1,j+1}\) for all \(1 \le i, j < n+k\). Since \(\mathcal{A}_n^k\) is symmetric, we restrict our attention to the case where \(i \le j\). We proceed by showing that the entries of \(A_{i,j}\) are pointwise identical to the entries of \(A_{i+1,j+1}\).

Theorem 3.3 states that the nonzero entries of \(A_{i,j}\) occur when

\[u \in \{i, i+1, i+2, \dots, i+k\} \cap \{j+k+1, j+k+2, \dots, j-1\}\] and \(v \in \{j, j+1, j+2, \dots, j+k\} \cap \{i+k+1, i+k+2, \dots, i-1\},\)

while the nonzero entries of \(A_{i+1,j+1}\) occur when

\[u' \in \{i+1, i+2, i+3, \dots, i+1+k\} \cap \{j+k+2, j+k+3, \dots, j\}\] and \(v' \in \{j+1, j+2, j+3, \dots, j+1+k\} \cap \{i+k+2, i+k+3, \dots, i\}.\)

Fix \(i \le u \le i + k\) and \(j \le v \le j + k\). Then the \(m_{u,v}\) entry in \(A_{i,j}\) corresponds to the \(m_{u+1,v+1}\) entry in \(A_{i+1,j+1}\). Suppose that \(m_{u,v} = 1\) in \(A_{i,j}\). Then \(u \in \{i, i+1, i+2, \ldots, i+k\} \cap \{j+k+1, j+k+2, \ldots, j-1\}\) and \(v \in \{j, j+1, j+2, \ldots, j+k\} \cap \{i+k+1, i+k+2, \ldots, i-1\}\). Hence

\[u+1 \in \{i+1,i+2,i+3,\ldots,i+1+k\} \cap \{j+k+2,j+k+3,\ldots,j\} \text{ and } v+1 \in \{j+1,j+2,j+3,\ldots,j+1+k\} \cap \{i+k+2,i+k+3,\ldots,i\}.\]

This implies that \(m_{u+1,v+1} = 1\) in \(A_{i+1,j+1}\).

To complete the proof, note that if \(m_{u,v} = 0\) in \(A_{i,j}\) then

\[u \notin \{i, i+1, i+2, \dots, i+k\} \cap \{j+k+1, j+k+2, \dots, j-1\}\] and \(v \notin \{j, j+1, j+2, \dots, j+k\} \cap \{i+k+1, i+k+2, \dots, i-1\}.\)

Hence

\[u+1 \notin \{i+1, i+2, i+3, \dots, i+1+k\} \cap \{j+k+2, j+k+3, \dots, j\}\] and \(v+1 \notin \{j+1, j+2, j+3, \dots, j+1+k\} \cap \{i+k+2, i+k+3, \dots, i\}.\)

This implies that \(m_{u+1,v+1}=0\) in \(A_{i+1,j+1}\). Therefore \(A_{i,j}=A_{i+1,j+1}\) for any \(1\leq i,j\leq n+k\). \(\square\)

Having shown that the matrices \(\mathcal{A}_n^k\) are (k+1)-block circulant, when describing \(\mathcal{A}_n^k\) we specify the generating block row consisting of the \((k+1)\times(k+1)\) submatrices \(A_{1,1},A_{1,2},\ldots,A_{1,n+k}\). That is, rather than build the matrix \(\mathcal{A}_n^k\) element by element as is done in Theorem 3.3, we build each \((k+1)\times(k+1)\) submatrix \(A_{1,j}\) in the first block row in Propositions 3.1 and 3.2. This generating block row is used to obtain the remaining block rows and allows us to obtain \(\mathcal{A}_n^k\) in entirety.

We determine the value of the matrix element \(m_{u,v}\) by using the definition of a strict alternating cycle. We describe \(m_{u,v}\) by considering when u,v, respectively are in the required intersection of the two index sets with consecutive, increasing elements. Throughout the proofs of Propositions 3.1 and 3.2, the following fact about the intersection of two indexing sets with consecutive, increasing elements is used in order to fully describe the elements \(m_{u,v}\).

Fact 3.5. Let X, Y, and Z be ordered sets of integers (indices) written in increasing order (cyclically). If \(Z \subseteq X\) and \(Z \subseteq Y\), where \(\alpha \ge \max(Z) + 1\) implies \(\alpha \notin X \cap Y\) and \(\beta \le \min(Z) - 1\) implies \(\beta \notin X \cap Y\), then \(Z = X \cap Y\).

Proposition 3.1. Assume n-1 > k+1 and let 1 < j < n+k. Then

\[A_{1,j} = \begin{cases} \mathbb{O}_{(k+1)\times(k+1)}, & \text{if } j = 1; \\ \mathbb{1}^{j-1}, & \text{if } 2 \leq j \leq k+1; \\ \mathbb{1}_{(k+1)\times(k+1)}, & \text{if } k+2 \leq j \leq n; \\ n+k+1-j\mathbb{1}, & \text{if } n+1 \leq j \leq n+k. \end{cases}\]

Proof. Theorem 3.3 states that \(A_{1,1} = \mathbb{O}_{(k+1)\times(k+1)}\). Next assume that \(2 \le j \le k+1\). We show that \(A_{1,j} = \mathbb{1}^{j-1}\). Note that \(m_{u,v} = 1\) in \(A_{1,j}\) if and only if \(u \in \{1, 2, \dots, k+1\} \cap \{j+k+1, j+k+2, \dots, j-1\}\) and \(v \in \{j, j+1, \dots, j+k\} \cap \{k+2, k+3, \dots, n+k\}\), where each set contains k+1 elements listed (cyclically) in increasing order.

Assume next that \(2 \le j \le k+1\). Then the containments \(\{1,2,\ldots,j-1\} \subseteq \{1,2,\ldots,k+1\}\) and \(\{1,2,\ldots,j-1\} \subseteq \{j+k+1,j+k+2,\ldots,j-1\}\) hold. The latter containment is due to the fact that \(\{1,2,\ldots,j-1\}\) is a set with \(j-1 \le k+1\) elements. By applying Fact 3.5, this yields \(\{1,2,\ldots,k+1\} \cap \{j+k+1,j+k+2,\ldots,j-1\} = \{1,2,\ldots,j-1\}\). Similarly, \(\{k+2,\ldots,j+k\} \subseteq \{1,2,\ldots,j-1\}\).

{j, . . . , j + k}and {k + 2, . . . , j + k} ⊆ {k + 2, . . . , n + k} since j ≤ k + 1 ≤ n − 1, and so j + k < n + k. Hence by Fact 3.5 we have {j, j + 1, . . . , j + k} ∩ {k + 2, k + 3, . . . , n + k} = {k + 2, . . . , j + k}. Thus, mu,v = 1 only when u ∈ {1, 2, . . . , j − 1} and v ∈ {k + 2, . . . , j + k}. Therefore A1,j = 1 j−1 .

If k + 2 ≤ j ≤ n, then we show A1,j = 1(k+1)×(k+1) by proving that mu,v = 1 for all possible values of u and v. This follows from Fact 3.5 and the containments

\[{j, j+1, j+2, \dots, j+k} \subseteq {k+2, k+3, \dots, n+k}\] and (1)

\[\{1, 2, 3, \dots, k+1\} \subseteq \{j+k+1, j+k+2, \dots, j+n+k-1\}. \tag{2}\]

Containment (1) follows from k + 2 ≤ j and j + k ≤ n + k. Containment (2) follows from j ≤ n, which gives j + k + 1 ≤ n + k + 1 ≡ 1 mod (n + k), and k + 2 ≤ j, which gives k + 1 ≤ j − 1 ≡ j + n + k − 1 mod (n + k).

If n + 1 ≤ j ≤ n + k, we claim A1,j = ⁿ+k+1−j1. It suffices to show that mu,v = 1 whenever u ∈ {j −n+ 1, j −n, . . . , k + 1} and v ∈ {j, j + 1, . . . , n+k}, and mu,v = 0 otherwise. Theorem 3.3 states

\[u \in \{1, 2, \dots, k+1\} \cap \{j+k+1, j+k+2, \dots, j-1\}\]
\[v \in \{j, j+1, \dots, j+k\} \cap \{k+2, k+3, \dots, n+k\}.\]

Hence it suffices to show that

\[\{j-n+1, j-n, \dots, k+1\} = \{1, 2, \dots, k+1\} \cap \{j+k+1, j+k+2, \dots, j-1\}\] \[\{j, j+1, \dots, n+k\} = \{j, j+1, \dots, j+k\} \cap \{k+2, k+3, \dots, n+k\}.\] (4)

Equation (3) follows from Fact 3.5 and the inequalities: n + 1 ≤ j, which gives 1 < j − n + 1, and both k + 1 ≤ n − 1 and n + 1 ≤ j, which gives k + 1 < n ≤ j − 1. Equation (4) follows from Fact 3.5 and the inequalities: n + 1 ≤ j, which gives n + k < j + k, and from both k + 1 ≤ n − 1 and n + 1 ≤ j, which gives k + 2 ≤ n < j.

Proposition 3.2. Assume n − 1 < k + 1 and let 1 ≤ j ≤ n + k. Then

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

Proof. The equality A1,¹ = 0(k+1)×(k+1) follows from Theorem 3.3. If 2 ≤ j ≤ n, then mu,v = 1 in A1,j when u ∈ {1, 2, . . . , k + 1} ∩ {j + k + 1, j + k + 2, . . . , j − 1} and v ∈ {j, j + 1, . . . , j + k} ∩ {k + 2, k + 3, . . . , n + k}. Using the inequalities n − 1 < k + 1 and 2 ≤ j ≤ n, we show that

\[\{1, 2, \dots, j-1\} = \{1, 2, \dots, k+1\} \cap \{j+k+1, j+k+2, \dots, j-1\}\] (5)

\[\{k+2, k+3, \dots, j+k\} = \{j, j+1, \dots, j+k\} \cap \{k+2, k+3, \dots, n+k\}.\] (6)

Equation (5) follows from Fact 3.5 and the observation that 2 ≤ j ≤ n and n − 1 < k + 1 imply j − 1 < k + 1. Equation (6) follows from Fact 3.5 and the observation that 2 ≤ j ≤ n and n − 1 < k + 1 imply j ≤ k + 2.

Next assume n + 1 ≤ j ≤ k + 1. Using the inequalities n − 1 < k + 1 and n + 1 ≤ j ≤ k + 1, we show

\[\{j-n+1, j-n+2\dots, j-1\} = \{1, 2, \dots, k+1\} \cap \{j+k+1, j+k+2, \dots, j-1\}\] (7) \[\{k+2, k+3, \dots, n+k\} = \{j, j+1, \dots, j+k\} \cap \{k+2, k+3, \dots, n+k\}.\] (8)

Note that j − n + 1 ≡ j + k + 1 mod (n + k). Since j ≤ k + 1 it follows that j − 1 < k + 1. It is clear that 1 < j + k + 1. Therefore {j + k + 1, j + k + 2, . . . , j − 1} ⊆ {1, 2, . . . , k + 1}. By containment and the fact that these sets have the same cardinality, they are equal. Since n + 1 ≤ j, then n + k < j + k. By assumption, j < k + 2, therefore {k + 2, . . . , n + k} ⊆ {j, . . . , j + k}. By containment and the fact that these sets have the same cardinality, they are equal. Thus mu,v = 1 if and only if u ∈ {j − n + 1, . . . , j − 1} and v ∈ {k + 2, . . . , n + k}.

Lastly assume k + 2 ≤ j ≤ n+k. Using the inequalities n−1 < k + 1 and k + 2 ≤ j ≤ n+k, we show

\[\{j-n+1, j-n, \dots, k+1\} = \{1, 2, \dots, k+1\} \cap \{j+k+1, j+k+2, \dots, j-1\}\] \[\{j, j+1, \dots, n+k\} = \{j, j+1, \dots, j+k\} \cap \{k+2, k+3, \dots, n+k\}.\] (10)

Equation (9) follows from Fact 3.5 and the inequalities: j − n + 1 ≡ j + k + 1 mod (n + k) > 1, and k + 2 ≤ j, the latter implying k + 1 ≤ j − 1. Equation (10) follows from Fact 3.5 and the inequalities k + 2 ≤ j and n − 1 < k + 1, which imply n + k ≤ j + k.

Theorem 3.6. Let t ≥ 1 and s ≥ t + 2. Then any t-block circulant matrix BC^{t s} with generating block row as described in Section 2 is A t−1 ^s−t+1.

The proof of Theorem 3.6 follows from the definition of the generating block row of BC^t s and from Theorems 3.4, Proposition 3.1 and Proposition 3.2.

4. Closing remarks

In this paper, we demonstrated a canonical association between a family of m-block circulant graphs and the associated graphs of the classical family of posets known as generalized crowns. It is well-known that the chromatic number of the incomparability graphs is bounded above by the dimension of their associated posets, and so this association also provides an upper bound on the chromatic number of the m-block circulant graphs. We conjecture that this bound is tight based on computational evidence using Mathematica. Naturally, it is of interest to find more families of posets with this property, and if they exist, determine what other attributes their graphs possess. Conversely, the richness in theory and applications surrounding circulant graphs beg their generalization to m-block circulant graphs and, specifically, to further investigate the graphs BC^t s , which are the objects of this study.

Acknowledgement

The authors thank Joseph Pedersen for his work on the Mathematica code that provided much insight. The authors acknowledge Charity Bankhead for her initial computational contributions to this project, and thank William T. Trotter for many helpful and enlightening conversations during the completion of this manuscript. As this project began during the 2013 SACNAS National Conference, the authors thank the society for providing an enriching environment that encouraged this scientific collaboration. The authors extend their gratitude to the Center for Leadership and Diversity in STEM at the United States Military Academy, the National Science Foundation Division of Mathematical Sciences (DMS-1045082), and the AMS-Simons Travel Grant for travel support.

References

• [1] B. Codenotti, I. Gerace and S. Vigna, Hardness results and spectral techniques for combinatorial problems on circulant graphs, Linear Algebra Appl. 285 (1-3) (1998), 123–142.
• [2] R. Diestel, Graph theory, Fourth edition, Graduate Texts in Mathematics, 173, Springer, Heidelberg, (2010), ISBN: 978-3-642-14278-9.
• [3] M. Discepoli, I. Gerace, R. Mariani and A. Remigi, A spectral technique to solve the chromatic number problem in circulant graphs, Computational science and its applications– ICCSA 2004 Part III, Lecture Notes in Comput. Sci. 3045, Springer, Berlin, (2004), 745–754.
• [4] S. Felsner and W.T. Trotter, Dimension, graph and hypergraph coloring, Order 17 (2) (2000), 167–177.
• [5] W.T. Trotter, Combinatorics and partially ordered sets, Johns Hopkins Series in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, (1992), Dimension theory.
• [6] W.T. Trotter, Dimension of the crown S k n , Discrete Math. 8 (1974), 85–103.
• [7] W.T. Trotter, Partially ordered sets, Handbook of combinatorics, Vol. 1, 2, Elsevier Sci. B. V., Amsterdam, (1995), 433–480.
• [8] J. Ya´nez and J. Montero, A Poset Dimension Algorithm, ˜ Journal of Algorithms 30 (1) (1999), 185–208.
• [9] J.W.T. Youngs, The Heawood map coloring conjecture, Graph Theory and Theoretical Physics, Academic Press, London, (1967), 313–354.