Introduction
Motivation
The automorphism problem for a graph product asks how its symmetries are determined by the factors. For a direct product of connected bipartite graphs, there are two questions: what is the automorphism group of each connected component, and which components are isomorphic? The first determines the symmetries within components; the second determines which components may be permuted. We answer both questions from prime-factor data for connected twin-free bipartite factors, none isomorphic to K 2 K_2 K 2 . The factorization used here is for the fibre product over K 2 K_2 K 2 .
All graphs considered in this paper are finite and undirected and have no multiple edges. We write Γ 0 \Gamma_0 Γ 0 for the class of graphs in which loops are allowed, otherwise graphs are loopless. Write x ∼ X y x \sim_X y x ∼ X y when x x x and y y y are adjacent in X X X . For a graph X X X , let V ( X ) V(X) V ( X ) , E ( X ) E(X) E ( X ) , and Aut ( X ) \operatorname{Aut}(X) Aut ( X ) denote its vertex set, edge set, and automorphism group, respectively, and let N X ( x ) N_X(x) N X ( x ) denote the neighbourhood of a vertex x x x . A graph is twin-free if distinct vertices have distinct neighbourhoods. We follow the graph terminology of [2 , 11 ] , the group terminology of [13 ] and the categorical terminology of [17 ] .
The direct product [11 ] of two graphs X X X and Y Y Y in Γ 0 \Gamma_0 Γ 0 , denoted by X × Y X \times Y X × Y , has vertex set V ( X ) × V ( Y ) V(X) \times V(Y) V ( X ) × V ( Y ) , where ( x , y ) (x,y) ( x , y ) is adjacent to ( x ′ , y ′ ) (x',y') ( x ′ , y ′ ) if and only if { x , x ′ } ∈ E ( X ) \{x,x'\} \in E(X) { x , x ′ } ∈ E ( X ) and { y , y ′ } ∈ E ( Y ) \{y,y'\} \in E(Y) { y , y ′ } ∈ E ( Y ) . This product is commutative and associative up to the natural coordinate isomorphisms, and its unit is the graph with one vertex and one loop. A nonunit graph is prime if at least one factor is the unit in every factorization as a direct product. Two graphs are coprime if they have no common direct factor of order greater than one. For nonempty graphs X X X and Y Y Y , the coordinatewise action gives a natural embedding
Aut ( X ) × Aut ( Y ) ≤ Aut ( X × Y ) . (1) \operatorname{Aut}(X) \times\operatorname{Aut}(Y) \leq\operatorname{Aut}(X \times Y). \tag*{(1)} Aut ( X ) × Aut ( Y ) ≤ Aut ( X × Y ) . (1)
Determining when equality holds in (1) , and describing the additional automorphisms when the inclusion is strict, are basic problems in the theory of graph products. A complete answer must account for the way automorphisms interact with the factor coordinates.
For connected nonbipartite graphs, prime factorization supplies the relevant coordinates. Such graphs have unique prime factorizations with respect to the direct product in Γ 0 \Gamma_0 Γ 0 [11 , 14 , 18 ] . Under the additional twin-free hypothesis, every isomorphism between products of prime factors is induced by factor isomorphisms and a permutation of the corresponding coordinates [4 , 11 ] . Thus prime factorization determines not only the isomorphism types of the factors but also the coordinate form of isomorphisms between products.
For bipartite factors, two different issues intervene. First, Weichsel’s theorem [29 ] , also stated in [11 Theorem 5.9] , implies that a direct product of r ≥ 1 r \ge1 r ≥ 1 connected bipartite graphs, each with at least one edge, has 2 r − 1 2^{r-1} 2 r − 1 connected components. A description of its full automorphism group therefore requires both the automorphism groups of individual components and a criterion for deciding which components are isomorphic. Second, prime direct product factorizations of connected bipartite graphs need not be unique [11 , 12 ] . Thus the nonbipartite coordinate theory cannot simply be applied to the components of the direct product of bipartite graphs. The component isomorphism question has a precise answer for two factors. Jha, Klavžar and Zmažek [15 ] proved that the two components are isomorphic if one factor admits an automorphism interchanging its bipartition classes, and conjectured the converse. Hammack studied the problem in [8 ] and proved the converse in [9 ] . A separate result of Hammack and Puffenberger [12 ] , extending [10 ] , shows that the unique bipartite prime factor occurring in any prime factorization of a connected bipartite graph is determined up to isomorphism. That theorem concerns a connected direct product with exactly one bipartite prime factor. Here we study the connected components of a product in which every factor is bipartite, and we seek the structure of their isomorphisms as well as their isomorphism types.
Our approach retains an ordering of the two bipartition classes and replaces the direct product by the fibre product over K 2 K_2 K 2 . For connected factors, the fibre product is the component in which the coordinate colours agree. It remains connected and retains the factor coordinates. We encode such ordered bipartite graphs by binary relations on their edge sets, prove that the relevant class of relations is closed under direct factors, and use McKenzie’s refinement theory [18 ] to obtain fibre prime factorizations and coordinate descriptions of specified isomorphisms. The resulting graph-theoretic description keeps track of factorization, bipartition reversals, and permutations of repeated isomorphic factors simultaneously.
The remaining problem is to recover the component isomorphism classes and their automorphism groups from prime-factor data. The wreath-product formula for the automorphism group of a disjoint union is classical. The essential task is to identify its constituent groups and their multiplicities directly from the factors, without treating the components as independent input data. This leads to the following question.
Problem 1.1. How can one describe the automorphism groups of the connected components of direct products of connected bipartite graphs and account for the interaction between bipartition reversals and permutations of repeated isomorphic factors?
Main results
The results proceed in three stages. First, Theorem 1.3 identifies the fibre-prime factors. Next, Theorems 1.4 and 1.5 show how a specified isomorphism acts on their coordinates, including a common colour-reversal sign. Finally, Theorem 1.6 uses these data to determine component isomorphism classes, their automorphism groups, and the automorphism group of the full direct product.
We first introduce the notation needed for the statements. Write F 2 \mathbb{F}_2 F 2 for the field with two elements, 0 t , 1 t ∈ F 2 t \mathbf{0}_t,\mathbf{1}_t \in\mathbb{F}_2^t 0 t , 1 t ∈ F 2 t for the constant vectors, and Q t = F 2 t / ⟨ 1 t ⟩ Q_t = \mathbb{F}_2^t/\langle\mathbf{1}_t\rangle Q t = F 2 t / ⟨ 1 t ⟩ for t ≥ 1 t \ge1 t ≥ 1 . A bar denotes the class of a binary vector in this quotient. Write S t S_t S t for the symmetric group on { 1 , … , t } \{1,\ldots,t\} { 1 , … , t } , with S 0 = 1 S_0 = 1 S 0 = 1 . Maps act on the left and are composed from right to left. We use the same convention for relations: x ( S ∘ R ) z x(S \circ R)z x ( S ∘ R ) z means that x R y xRy x R y and y S z ySz y S z for some y y y . Write Z n = Z / n Z \mathbb{Z}_n = \mathbb{Z}/n\mathbb{Z} Z n = Z / n Z , and denote the path and cycle on n n n vertices by P n P_n P n and C n C_n C n , respectively. For a finite set J J J , write S J S_J S J for its symmetric group. For a group G G G , the notation G ≀ S t = G t ⋊ S t G \wr S_t = G^t \rtimes S_t G ≀ S t = G t ⋊ S t uses the action ( σ ⋅ g ) i = g σ − 1 ( i ) (\sigma\cdot g)_i = g_{\sigma^{-1}(i)} ( σ ⋅ g ) i = g σ − 1 ( i ) ; we set G ≀ S 0 = 1 G \wr S_0 = 1 G ≀ S 0 = 1 . Bold lower-case letters denote tuples, whereas their subscripted entries are individual coordinates.
An ordered bipartite graph is a pair ( B , ϱ B ) (B,\varrho_B) ( B , ϱ B ) , where B B B is a bipartite graph and ϱ B : B → K 2 \varrho_B:B \to K_2 ϱ B : B → K 2 is a surjective graph homomorphism. Equivalently, B B B has a fixed ordered bipartition V ( B ) = B 0 ⊔ B 1 V(B) = B^0 \sqcup B^1 V ( B ) = B 0 ⊔ B 1 , where B i = ϱ B − 1 ( i ) B^i = \varrho_B^{-1}(i) B i = ϱ B − 1 ( i ) for i ∈ { 0 , 1 } i \in\{0,1\} i ∈ { 0 , 1 } . We call ϱ B \varrho_B ϱ B the colour map and write U ( B ) U(B) U ( B ) for the underlying graph of B B B , obtained by forgetting the order of the two classes. A morphism from B B B to C C C is a graph homomorphism f : U ( B ) → U ( C ) f:U(B) \to U(C) f : U ( B ) → U ( C ) satisfying
ϱ C ∘ f = ϱ B . \varrho_C \circ f = \varrho_B. ϱ C ∘ f = ϱ B .
Ordered bipartite graphs and their colour-preserving homomorphisms form a category, denoted by Bip 2 _2 2 . A graph isomorphism f : U ( B ) → U ( C ) f:U(B) \to U(C) f : U ( B ) → U ( C ) is called an ordinary isomorphism . Such an isomorphism need not preserve the colour classes.
Definition 1.2. Let B B B and C C C be ordered bipartite graphs. Their fibre product over K 2 K_2 K 2 , denoted by B ⋆ C B \star C B ⋆ C , is the ordered bipartite graph with vertex set
V ( B ⋆ C ) = { ( b , c ) ∈ V ( B ) × V ( C ) : ϱ B ( b ) = ϱ C ( c ) } V(B \star C) = \{(b,c) \in V(B) \times V(C) : \varrho_B(b) = \varrho_C(c)\} V ( B ⋆ C ) = {( b , c ) ∈ V ( B ) × V ( C ) : ϱ B ( b ) = ϱ C ( c )} and edge set
E ( B ⋆ C ) = { { ( b , c ) , ( b ′ , c ′ ) } : ( b , c ) , ( b ′ , c ′ ) ∈ V ( B ⋆ C ) , { b , b ′ } ∈ E ( B ) , { c , c ′ } ∈ E ( C ) } . E(B \star C) = \{\{(b,c),(b',c')\} : (b,c),(b',c') \in V(B \star C), \{b,b'\} \in E(B), \{c,c'\} \in E(C)\}. E ( B ⋆ C ) = {{( b , c ) , ( b ′ , c ′ )} : ( b , c ) , ( b ′ , c ′ ) ∈ V ( B ⋆ C ) , { b , b ′ } ∈ E ( B ) , { c , c ′ } ∈ E ( C )} . The colour map is ϱ B ⋆ C ( b , c ) = ϱ B ( b ) = ϱ C ( c ) \varrho_{B \star C}(b,c) = \varrho_B(b) = \varrho_C(c) ϱ B ⋆ C ( b , c ) = ϱ B ( b ) = ϱ C ( c ) , so its two ordered colour classes are
( B ⋆ C ) 0 = B 0 × C 0 , ( B ⋆ C ) 1 = B 1 × C 1 . (B \star C)^0 = B^0 \times C^0,\qquad(B \star C)^1 = B^1 \times C^1. ( B ⋆ C ) 0 = B 0 × C 0 , ( B ⋆ C ) 1 = B 1 × C 1 . The graph K 2 K_2 K 2 , equipped with its identity colour map, is the unit of this product. A connected nonunit ordered bipartite graph B B B is called fibre-prime (or, f-prime ) if, in every factorization B ≅ X ⋆ Y B \cong X \star Y B ≅ X ⋆ Y in Bip 2 _2 2 , at least one of X X X and Y Y Y is isomorphic to K 2 K_2 K 2 .
The fibre product is associative and commutative up to the natural coordinate isomorphisms. We write ⋆ i = 1 r B i \mathop{\star}_{i=1}^r B_i ⋆ i = 1 r B i for an iterated fibre product and take the empty product to be K 2 K_2 K 2 . The fibre product has a different unit and notion of primality from the ordinary direct product. The first theorem gives a common refinement of any two fibre product decompositions and, in particular, unique factorization into nonunit f f f -prime factors.
Theorem 1.3. Let B B B be a finite connected twin-free ordered bipartite graph. Let r , s ≥ 0 r,s \ge0 r , s ≥ 0 , with empty fibre products interpreted as K 2 K_2 K 2 , and suppose
B ≅ G 1 ⋆ ⋯ ⋆ G r ≅ H 1 ⋆ ⋯ ⋆ H s B \cong G_1 \star\cdots\star G_r \cong H_1 \star\cdots\star H_s B ≅ G 1 ⋆ ⋯ ⋆ G r ≅ H 1 ⋆ ⋯ ⋆ H s in Bip 2 _2 2 . Then the following statements hold.
(i) There are connected twin-free f f f -prime ordered bipartite graphs B λ B_\lambda B λ and two indexed partitions of a finite set S S S (with empty parts allowed),
S = U 1 ⊔ ⋯ ⊔ U r = V 1 ⊔ ⋯ ⊔ V s S = U_1 \sqcup\cdots\sqcup U_r = V_1 \sqcup\cdots\sqcup V_s S = U 1 ⊔ ⋯ ⊔ U r = V 1 ⊔ ⋯ ⊔ V s such that
B ≅ ⋆ λ ∈ S B λ , G i ≅ ⋆ λ ∈ U i B λ , H j ≅ ⋆ λ ∈ V j B λ . B \cong\mathop{\star}_{\lambda\in S} B_\lambda,\qquad
G_i \cong\mathop{\star}_{\lambda\in U_i} B_\lambda,\qquad
H_j \cong\mathop{\star}_{\lambda\in V_j} B_\lambda. B ≅ ⋆ λ ∈ S B λ , G i ≅ ⋆ λ ∈ U i B λ , H j ≅ ⋆ λ ∈ V j B λ . Thus B B B admits a factorization into f f f -prime factors.
(ii) If G 1 ⋆ ⋯ ⋆ G r G_1 \star\cdots\star G_r G 1 ⋆ ⋯ ⋆ G r and H 1 ⋆ ⋯ ⋆ H s H_1 \star\cdots\star H_s H 1 ⋆ ⋯ ⋆ H s are already factorizations into nonunit f f f -prime factors, then r = s r=s r = s and there is a permutation σ ∈ S r \sigma\in S_r σ ∈ S r such that for each 1 ≤ i ≤ r 1 \le i \le r 1 ≤ i ≤ r , G i ≅ H σ ( i ) G_i \cong H_{\sigma(i)} G i ≅ H σ ( i ) in Bip 2 _2 2 . Consequently, the multiset of nonunit f f f -prime factors of B B B is unique up to isomorphism in Bip 2 _2 2 .
Unique factorization identifies the prime factors up to colour-preserving isomorphism and permutation. Determining automorphism groups requires additional information, namely a coordinate description of each specified isomorphism. The next theorem provides this description, covering cases where isomorphic factors repeat.
Theorem 1.4. Let B = B 1 ⋆ ⋯ ⋆ B r B=B_1\star\cdots\star B_r B = B 1 ⋆ ⋯ ⋆ B r and C = C 1 ⋆ ⋯ ⋆ C s C=C_1\star\cdots\star C_s C = C 1 ⋆ ⋯ ⋆ C s be products of connected twin-free nonunit f f f -prime ordered bipartite graphs, where r , s ≥ 1 r,s\geq1 r , s ≥ 1 . If φ : B → C \varphi:B\to C φ : B → C is an isomorphism in B i p 2 \mathbf{Bip}_2 Bip 2 , then r = s r=s r = s , and there exist a permutation σ ∈ S r \sigma\in S_r σ ∈ S r and isomorphisms φ i : B i → C σ ( i ) \varphi_i:B_i\to C_{\sigma(i)} φ i : B i → C σ ( i ) in B i p 2 \mathbf{Bip}_2 Bip 2 for 1 ≤ i ≤ r 1\leq i\leq r 1 ≤ i ≤ r such that, whenever φ ( b 1 , … , b r ) = ( c 1 , … , c r ) \varphi(b_1,\ldots,b_r)=(c_1,\ldots,c_r) φ ( b 1 , … , b r ) = ( c 1 , … , c r ) , we have
c σ ( i ) = φ i ( b i ) , (2) c_{\sigma(i)}=\varphi_i(b_i), \tag*{(2)} c σ ( i ) = φ i ( b i ) , (2) for every $1\leq i\leq r.
An ordinary isomorphism between connected bipartite graphs either preserves both bipartition classes or interchanges them. For a fibre product, these choices cannot be made independently in different coordinates since all factor maps must have the same colour sign. The next theorem gives this precise compatibility condition. It is the fibre product counterpart of the coordinate description for connected nonbipartite twin-free direct products in [11 Theorem 8.15] .
Theorem 1.5. Let B B B and C C C be connected twin-free ordered bipartite graphs with fixed nonunit f f f -prime decompositions B ≅ B 1 ⋆ ⋯ ⋆ B r B\cong B_1\star\cdots\star B_r B ≅ B 1 ⋆ ⋯ ⋆ B r and C ≅ C 1 ⋆ ⋯ ⋆ C s C\cong C_1\star\cdots\star C_s C ≅ C 1 ⋆ ⋯ ⋆ C s in B i p 2 \mathbf{Bip}_2 Bip 2 , where r , s ≥ 1 r,s\geq1 r , s ≥ 1 . Let φ : U ( B ) ⟶ U ( C ) \varphi:U(B)\longrightarrow U(C) φ : U ( B ) ⟶ U ( C ) be an ordinary graph isomorphism. Then r = s r=s r = s . Moreover, there are a unique global sign δ ∈ F 2 \delta\in\mathbb{F}_2 δ ∈ F 2 , a permutation σ ∈ S r \sigma\in S_r σ ∈ S r , and ordinary isomorphisms φ i : U ( B i ) ⟶ U ( C σ ( i ) ) \varphi_i:U(B_i)\longrightarrow U(C_{\sigma(i)}) φ i : U ( B i ) ⟶ U ( C σ ( i ) ) , for 1 ≤ i ≤ r 1\leq i\leq r 1 ≤ i ≤ r , such that, for each 1 ≤ i ≤ r 1\leq i\leq r 1 ≤ i ≤ r and every x ∈ V ( B i ) x\in V(B_i) x ∈ V ( B i ) ,
ϱ C σ ( i ) ( φ i ( x ) ) = ϱ B i ( x ) + δ . (3) \varrho_{C_{\sigma(i)}}(\varphi_i(x))=\varrho_{B_i}(x)+\delta. \tag*{(3)} ϱ C σ ( i ) ( φ i ( x )) = ϱ B i ( x ) + δ . (3) If φ ( b 1 , … , b r ) = ( c 1 , … , c r ) \varphi(b_1,\ldots,b_r)=(c_1,\ldots,c_r) φ ( b 1 , … , b r ) = ( c 1 , … , c r ) , then for each 1 ≤ i ≤ r 1\leq i\leq r 1 ≤ i ≤ r ,
c σ ( i ) = φ i ( b i ) . (4) c_{\sigma(i)}=\varphi_i(b_i). \tag*{(4)} c σ ( i ) = φ i ( b i ) . (4) Thus all corresponding factor isomorphisms preserve their ordered bipartitions when δ = 0 \delta=0 δ = 0 , and all reverse them when δ = 1 \delta=1 δ = 1 .
We now return to the direct product. Its components correspond to choices of factor colourings, with two choices identified when every colour is reversed. Theorem 1.5 will turn isomorphisms between these components into permutations and isomorphisms of fibre prime factors. We first describe the component labels and the action of factor symmetries on them.
For an ordered bipartite graph B B B , let B o p B^{\mathrm{op}} B op have the same underlying graph with the two colour classes interchanged, and put B ( 0 ) = B B^{(0)}=B B ( 0 ) = B and B ( 1 ) = B o p B^{(1)}=B^{\mathrm{op}} B ( 1 ) = B op . Given connected ordered bipartite graphs B 1 , … , B r B_1,\ldots,B_r B 1 , … , B r and ϵ = ( ϵ 1 , … , ϵ r ) ∈ F 2 r \epsilon=(\epsilon_1,\ldots,\epsilon_r)\in\mathbb{F}_2^r ϵ = ( ϵ 1 , … , ϵ r ) ∈ F 2 r , the fibre product U = B 1 ( ϵ 1 ) ⋆ ⋯ ⋆ B r ( ϵ r ) U=B_1^{(\epsilon_1)}\star\cdots\star B_r^{(\epsilon_r)} U = B 1 ( ϵ 1 ) ⋆ ⋯ ⋆ B r ( ϵ r ) has a colour map given, for x = ( x 1 , … , x r ) ∈ V ( U ) \mathbf{x}=(x_1,\ldots,x_r)\in V(U) x = ( x 1 , … , x r ) ∈ V ( U ) , by
ϱ U ( x ) = ϱ B 1 ( x 1 ) + ϵ 1 = ⋯ = ϱ B r ( x r ) + ϵ r ∈ F 2 . (5) \varrho_U(\mathbf{x})=\varrho_{B_1}(x_1)+\epsilon_1=\cdots=\varrho_{B_r}(x_r)+\epsilon_r\in\mathbb{F}_2. \tag*{(5)} ϱ U ( x ) = ϱ B 1 ( x 1 ) + ϵ 1 = ⋯ = ϱ B r ( x r ) + ϵ r ∈ F 2 . (5)
We call ϱ U ( x ) \varrho_U(\mathbf{x}) ϱ U ( x ) the global colour of x \mathbf{x} x . The two sets U 0 = ϱ U − 1 ( 0 ) U^0=\varrho_U^{-1}(0) U 0 = ϱ U − 1 ( 0 ) and U 1 = ϱ U − 1 ( 1 ) U^1=\varrho_U^{-1}(1) U 1 = ϱ U − 1 ( 1 ) are the global bipartition classes.
Reversing all factor colourings leaves the underlying graph of U U U unchanged and reverses only its global colouring. Thus component labels lie in the quotient Q r Q_r Q r defined above. For ϵ = ( ϵ 1 , … , ϵ r ) ∈ F 2 r \epsilon=(\epsilon_1,\ldots,\epsilon_r)\in\mathbb{F}_2^r ϵ = ( ϵ 1 , … , ϵ r ) ∈ F 2 r , write ϵ ‾ \overline{\epsilon} ϵ for its class in Q r Q_r Q r and define
Ω ϵ ‾ = U ( B 1 ( ϵ 1 ) ⋆ ⋯ ⋆ B r ( ϵ r ) ) , P = U ( B 1 ) × ⋯ × U ( B r ) . \Omega_{\overline{\epsilon}}=U(B_1^{(\epsilon_1)}\star\cdots\star B_r^{(\epsilon_r)}),\qquad P=U(B_1)\times\cdots\times U(B_r). Ω ϵ = U ( B 1 ( ϵ 1 ) ⋆ ⋯ ⋆ B r ( ϵ r ) ) , P = U ( B 1 ) × ⋯ × U ( B r ) .
For x = ( x 1 , x 2 , … , x r ) ∈ V ( P ) \mathbf{x}=(x_1,x_2,\ldots,x_r)\in V(P) x = ( x 1 , x 2 , … , x r ) ∈ V ( P ) , its coordinate colour vector is π ( x ) = ( ϱ B 1 ( x 1 ) , … , ϱ B r ( x r ) ) \boldsymbol{\pi}(\mathbf{x})=(\varrho_{B_1}(x_1),\ldots,\varrho_{B_r}(x_r)) π ( x ) = ( ϱ B 1 ( x 1 ) , … , ϱ B r ( x r )) . Proposition 2.3 shows that x ∈ V ( Ω ϵ ‾ ) \mathbf{x}\in V(\Omega_{\overline{\epsilon}}) x ∈ V ( Ω ϵ ) precisely when π ( x ) = ϵ ‾ \boldsymbol{\pi}(\mathbf{x})=\overline{\epsilon} π ( x ) = ϵ , and that the graphs Ω ϵ ‾ \Omega_{\overline{\epsilon}} Ω ϵ are exactly the 2 r − 1 2^{r-1} 2 r − 1 connected components of P P P .
Choose σ ∈ S r \sigma\in S_r σ ∈ S r and ordinary isomorphisms f i : U ( B i ) → U ( B σ ( i ) ) f_i : \mathrm{U}(B_i) \to\mathrm{U}(B_{\sigma(i)}) f i : U ( B i ) → U ( B σ ( i ) ) for every i i i . With f = ( f 1 , … , f r ) \mathbf{f} = (f_1,\ldots,f_r) f = ( f 1 , … , f r ) , define w σ , f : P → P w_{\sigma,\mathbf{f}} : P \to P w σ , f : P → P by w σ , f ( x ) = y w_{\sigma,\mathbf{f}}(\mathbf{x}) = \mathbf{y} w σ , f ( x ) = y for x = ( x i ) i = 1 r \mathbf{x} = (x_i)_{i=1}^r x = ( x i ) i = 1 r and y = ( y i ) i = 1 r \mathbf{y} = (y_i)_{i=1}^r y = ( y i ) i = 1 r , where, for 1 ≤ i ≤ r 1 \leq i \leq r 1 ≤ i ≤ r ,
y σ ( i ) = f i ( x i ) . y_{\sigma(i)} = f_i(x_i). y σ ( i ) = f i ( x i ) .
Equivalently, [ w σ , f ( x ) ] σ ( i ) = f i ( x i ) [w_{\sigma,\mathbf{f}}(\mathbf{x})]_{\sigma(i)} = f_i(x_i) [ w σ , f ( x ) ] σ ( i ) = f i ( x i ) , where [ z ] j [\mathbf{z}]_j [ z ] j denotes the j j j -th coordinate of a tuple z \mathbf{z} z . Thus f i f_i f i acts on the i i i -th input coordinate, and σ \sigma σ specifies its output position. Each w σ , f w_{\sigma,\mathbf{f}} w σ , f is bijective and preserves adjacency, and its inverse is determined by σ − 1 \sigma^{-1} σ − 1 and the maps f i − 1 f_i^{-1} f i − 1 . These maps form the factor symmetry group W = W ( B 1 , … , B r ) \mathcal{W} = \mathcal{W}(B_1,\ldots,B_r) W = W ( B 1 , … , B r ) . For clarity, the composition rule is w τ , g w σ , f = w τ σ , h w_{\tau,\mathbf{g}}w_{\sigma,\mathbf{f}} = w_{\tau\sigma,\mathbf{h}} w τ , g w σ , f = w τ σ , h , where h i = g σ ( i ) ∘ f i h_i = g_{\sigma(i)} \circ f_i h i = g σ ( i ) ∘ f i . Since each B i B_i B i , 1 ≤ i ≤ r 1 \leq i \leq r 1 ≤ i ≤ r , is connected, each f i f_i f i has a unique sign s i ∈ F 2 s_i \in\mathbb{F}_2 s i ∈ F 2 , determined by the identity
ϱ B σ ( i ) ( f i ( x i ) ) = ϱ B i ( x i ) + s i . \varrho_{B_{\sigma(i)}}(f_i(x_i)) = \varrho_{B_i}(x_i) + s_i. ϱ B σ ( i ) ( f i ( x i )) = ϱ B i ( x i ) + s i .
Here x i x_i x i ranges over V ( B i ) V(B_i) V ( B i ) . Put s = ( s 1 , … , s r ) \mathbf{s} = (s_1,\ldots,s_r) s = ( s 1 , … , s r ) and define σ ∗ v \sigma_*\mathbf{v} σ ∗ v by ( σ ∗ v ) σ ( i ) = v i (\sigma_*\mathbf{v})_{\sigma(i)} = v_i ( σ ∗ v ) σ ( i ) = v i for v ∈ F 2 r \mathbf{v} \in\mathbb{F}_2^r v ∈ F 2 r . The induced action on component indices is
w σ , f ⋅ ϵ ‾ = σ ∗ ( ϵ + s ) ‾ . (6) w_{\sigma,\mathbf{f}} \cdot\overline{\boldsymbol{\epsilon}} = \overline{\sigma_*(\boldsymbol{\epsilon}+\mathbf{s})}. \tag*{(6)} w σ , f ⋅ ϵ = σ ∗ ( ϵ + s ) . (6)
This is well defined since σ ∗ 1 r = 1 r \sigma_*\mathbf{1}_r = \mathbf{1}_r σ ∗ 1 r = 1 r , where 1 r = ( 1 , … , 1 ) \mathbf{1}_r = (1,\ldots,1) 1 r = ( 1 , … , 1 ) . Write Stab W ( ϵ ‾ ) = { w ∈ W : w ⋅ ϵ ‾ = ϵ ‾ } \operatorname{Stab}_{\mathcal{W}}(\overline{\boldsymbol{\epsilon}}) = \{w \in\mathcal{W} : w \cdot\overline{\boldsymbol{\epsilon}} = \overline{\boldsymbol{\epsilon}}\} Stab W ( ϵ ) = { w ∈ W : w ⋅ ϵ = ϵ } for the stabilizer of the indicated quotient class.
The original factors B i B_i B i need not be f f f -prime, so their coordinate symmetries alone need not describe all component isomorphisms. We therefore refine each B i B_i B i into its f f f -prime factors. The original coordinates become blocks of refined coordinates, and the components belonging to the original product are selected by requiring the refined colour labels to be constant within each block.
Let r ≥ 1 r \geq1 r ≥ 1 , and let B 1 , … , B r B_1,\ldots,B_r B 1 , … , B r be connected twin-free nonunit ordered bipartite graphs. By Theorem 1.3 , for each 1 ≤ i ≤ r 1 \leq i \leq r 1 ≤ i ≤ r , fix an isomorphism in Bip 2 \operatorname{Bip}_2 Bip 2
θ i : B i ⟶ ⋆ k ∈ I i C k . (7) \theta_i : B_i \longrightarrow\mathop{\star}_{k \in I_i} C_k. \tag*{(7)} θ i : B i ⟶ ⋆ k ∈ I i C k . (7)
where I 1 , … , I r I_1,\ldots,I_r I 1 , … , I r partition { 1 , … , N } \{1,\ldots,N\} { 1 , … , N } into nonempty sets, and every C k C_k C k is connected, twin-free, nonunit, and f f f -prime. The order of the coordinates within each I i I_i I i is fixed. Write I = ( I 1 , … , I r ) \mathcal{I} = (I_1,\ldots,I_r) I = ( I 1 , … , I r ) , and define
P ~ = ∏ k = 1 N U ( C k ) , W ~ = W ( C 1 , … , C N ) . \widetilde{P} = \prod_{k=1}^{N} \mathrm{U}(C_k), \qquad\widetilde{\mathcal{W}} = \mathcal{W}(C_1,\ldots,C_N). P = k = 1 ∏ N U ( C k ) , W = W ( C 1 , … , C N ) .
We use the same quotient notation Q N Q_N Q N for the refined coordinates. For a vector a = ( a 1 , … , a N ) ∈ F 2 N \mathbf{a} = (a_1,\ldots,a_N) \in\mathbb{F}_2^N a = ( a 1 , … , a N ) ∈ F 2 N , define
Λ a = U ( C 1 ( a 1 ) ⋆ ⋯ ⋆ C N ( a N ) ) . \Lambda_{\mathbf{a}} = \mathrm{U}(C_1^{(a_1)} \star\cdots\star C_N^{(a_N)}). Λ a = U ( C 1 ( a 1 ) ⋆ ⋯ ⋆ C N ( a N ) ) .
Each C k C_k C k is a factor graph, whereas Λ a \Lambda_{\mathbf{a}} Λ a is a connected component of P ~ \widetilde{P} P . An element x = ( x 1 , … , x N ) ∈ V ( Λ a ) \mathbf{x} = (x_1,\ldots,x_N) \in V(\Lambda_{\mathbf{a}}) x = ( x 1 , … , x N ) ∈ V ( Λ a ) is a vertex, with x k ∈ V ( C k ) x_k \in V(C_k) x k ∈ V ( C k ) for each k k k .
Define the repetition map d : F 2 r → F 2 N d : \mathbb{F}_2^r \to\mathbb{F}_2^N d : F 2 r → F 2 N and its induced map d ˉ : Q r → Q N \bar d : Q_r \to Q_N d ˉ : Q r → Q N by
( d ( ϵ ) ) k = ϵ i , d ˉ ( ϵ ˉ ) = d ( ϵ ) ‾ , (d(\boldsymbol{\epsilon}))_k = \epsilon_i, \qquad\bar d(\bar{\boldsymbol{\epsilon}}) = \overline{d(\boldsymbol{\epsilon})}, ( d ( ϵ ) ) k = ϵ i , d ˉ ( ϵ ˉ ) = d ( ϵ ) ,
where ϵ = ( ϵ 1 , … , ϵ r ) ∈ F 2 r \boldsymbol{\epsilon} = (\epsilon_1,\ldots,\epsilon_r) \in\mathbb{F}_2^r ϵ = ( ϵ 1 , … , ϵ r ) ∈ F 2 r and k ∈ I i k \in I_i k ∈ I i . Since d ( 1 r ) = 1 N d(\mathbf{1}_r) = \mathbf{1}_N d ( 1 r ) = 1 N , the map d ˉ \bar d d ˉ is well defined. Write
L I = d ˉ ( Q r ) = { a ∈ Q N : a k = a ℓ whenever k , ℓ ∈ I i for some i } . L_{\mathcal{I}} = \bar d(Q_r) = \{\mathbf{a} \in Q_N : a_k = a_\ell\text{ whenever } k,\ell\in I_i \text{ for some } i\}. L I = d ˉ ( Q r ) = { a ∈ Q N : a k = a ℓ whenever k , ℓ ∈ I i for some i } .
The condition on the right is unchanged when a \mathbf{a} a is replaced by a + 1 N \mathbf{a}+\mathbf{1}_N a + 1 N . For x = ( x 1 , … , x r ) ∈ V ( P ) \mathbf{x} = (x_1,\ldots,x_r) \in V(P) x = ( x 1 , … , x r ) ∈ V ( P ) , write θ i ( x i ) = ( u k ) k ∈ I i \theta_i(x_i) = (u_k)_{k \in I_i} θ i ( x i ) = ( u k ) k ∈ I i for each i i i , and define Θ ( x ) = ( u 1 , … , u N ) ∈ V ( P ~ ) \Theta(\mathbf{x}) = (u_1,\ldots,u_N) \in V(\widetilde{P}) Θ ( x ) = ( u 1 , … , u N ) ∈ V ( P ) . We write Θ ‾ ϵ ˉ \overline{\Theta}_{\bar{\boldsymbol{\epsilon}}} Θ ϵ ˉ for the restriction Θ ∣ V ( Σ ϵ ˉ ) \Theta|_{V(\Sigma_{\bar{\boldsymbol{\epsilon}}})} Θ ∣ V ( Σ ϵ ˉ ) (its image will be identified in Theorem 1.6 (i)).
The group W ~ \widetilde{\mathcal{W}} W acts on Q N Q_N Q N by Eq. (6) , now using the C k C_k C k -coordinates. The subset L T \mathcal{L}_{\mathcal{T}} L T need not be invariant; all orbits below are taken in the ambient label space Q N Q_N Q N . Let O T \mathcal{O}_{\mathcal{T}} O T be the set of its orbits that meet L T \mathcal{L}_{\mathcal{T}} L T . For each O ∈ O T \mathcal{O} \in\mathcal{O}_{\mathcal{T}} O ∈ O T , choose a ‾ O ∈ O ∩ L T \overline{a}_{\mathcal{O}} \in\mathcal{O} \cap\mathcal{L}_{\mathcal{T}} a O ∈ O ∩ L T and let n O = ∣ O ∩ L T ∣ n_{\mathcal{O}} = |\mathcal{O} \cap\mathcal{L}_{\mathcal{T}}| n O = ∣ O ∩ L T ∣ .
Theorem 1.6. Let r ≥ 1 r \ge1 r ≥ 1 , and let B 1 , … , B r B_1,\ldots,B_r B 1 , … , B r be connected twin-free nonunit ordered bipartite graphs. Put
P = U ( B 1 ) × ⋯ × U ( B r ) . P = \mathrm{U}(B_1) \times\cdots\times\mathrm{U}(B_r). P = U ( B 1 ) × ⋯ × U ( B r ) . For each 1 ≤ i ≤ r 1 \le i \le r 1 ≤ i ≤ r , fix an f f f -prime factorization θ i : B i ⟶ ⋆ k ∈ I i C k \theta_i : B_i \longrightarrow\star_{k \in I_i} C_k θ i : B i ⟶ ⋆ k ∈ I i C k in B i p 2 \mathbf{Bip}_2 Bip 2 as in (7) . With the notation introduced above for these fixed factorizations, the following statements hold.
(i) The map Θ \Theta Θ is an isomorphism P ⟶ ⨆ a ‾ ∈ L T Λ a ‾ P \longrightarrow\bigsqcup_{\overline{a} \in\mathcal{L}_{\mathcal{T}}} \Lambda_{\overline{a}} P ⟶ ⨆ a ∈ L T Λ a , and Θ ϵ ‾ : Ω ϵ ‾ ⟶ Λ d ‾ ( ϵ ‾ ) \Theta_{\overline{\epsilon}} : \Omega_{\overline{\epsilon}} \longrightarrow\Lambda_{\overline{d}(\overline{\epsilon})} Θ ϵ : Ω ϵ ⟶ Λ d ( ϵ ) is an isomorphism for every ϵ ‾ ∈ Q r \overline{\epsilon} \in Q_r ϵ ∈ Q r . Moreover, ∣ L T ∣ = 2 r − 1 |\mathcal{L}_{\mathcal{T}}| = 2^{r-1} ∣ L T ∣ = 2 r − 1 .
(ii) For ϵ ‾ , η ‾ ∈ Q r \overline{\epsilon}, \overline{\eta} \in Q_r ϵ , η ∈ Q r , the components Ω ϵ ‾ \Omega_{\overline{\epsilon}} Ω ϵ and Ω η ‾ \Omega_{\overline{\eta}} Ω η are isomorphic if and only if d ‾ ( ϵ ‾ ) \overline{d}(\overline{\epsilon}) d ( ϵ ) and d ‾ ( η ‾ ) \overline{d}(\overline{\eta}) d ( η ) belong to the same W ~ \widetilde{\mathcal{W}} W -orbit in Q N Q_N Q N .
(iii) For every ϵ ‾ ∈ Q r \overline{\epsilon} \in Q_r ϵ ∈ Q r , restriction followed by conjugation by Θ ϵ ‾ \Theta_{\overline{\epsilon}} Θ ϵ defines an isomorphism from Stab W ~ ( d ‾ ( ϵ ‾ ) ) \operatorname{Stab}_{\widetilde{\mathcal{W}}}(\overline{d}(\overline{\epsilon})) Stab W ( d ( ϵ )) to Aut ( Ω ϵ ‾ ) \operatorname{Aut}(\Omega_{\overline{\epsilon}}) Aut ( Ω ϵ ) mapping elements w ∈ Stab W ~ ( d ‾ ( ϵ ‾ ) ) w \in\operatorname{Stab}_{\widetilde{\mathcal{W}}}(\overline{d}(\overline{\epsilon})) w ∈ Stab W ( d ( ϵ )) to Θ ϵ ‾ − 1 ∘ ( w ∣ Λ d ‾ ( ϵ ‾ ) ) ∘ Θ ϵ ‾ \Theta_{\overline{\epsilon}}^{-1} \circ(w|_{\Lambda_{\overline{d}(\overline{\epsilon})}}) \circ\Theta_{\overline{\epsilon}} Θ ϵ − 1 ∘ ( w ∣ Λ d ( ϵ ) ) ∘ Θ ϵ .
(iv) The automorphism group of P P P is given by
Aut ( P ) ≅ ∏ O ∈ O T ( Stab W ~ ( a ‾ O ) ≀ S n O ) . (8) \operatorname{Aut}(P) \cong\prod_{\mathcal{O} \in\mathcal{O}_{\mathcal{T}}} \left(\operatorname{Stab}_{\widetilde{\mathcal{W}}}(\overline{a}_{\mathcal{O}}) \wr S_{n_{\mathcal{O}}}\right). \tag*{(8)} Aut ( P ) ≅ O ∈ O T ∏ ( Stab W ( a O ) ≀ S n O ) . (8) (v) Let T 1 , … , T q T_1,\ldots,T_q T 1 , … , T q represent the distinct isomorphism types of the underlying graphs among the C k C_k C k . For each 1 ≤ λ ≤ q 1 \le\lambda\le q 1 ≤ λ ≤ q , let J λ = { k : U ( C k ) ≅ T λ } J_\lambda= \{k : \mathrm{U}(C_k) \cong T_\lambda\} J λ = { k : U ( C k ) ≅ T λ } and t λ = ∣ J λ ∣ t_\lambda= |J_\lambda| t λ = ∣ J λ ∣ . Then
W ~ ≅ ∏ λ = 1 q ( Aut ( T λ ) ≀ S t λ ) . \widetilde{\mathcal{W}} \cong\prod_{\lambda=1}^{q} \left(\operatorname{Aut}(T_\lambda) \wr S_{t_\lambda}\right). W ≅ λ = 1 ∏ q ( Aut ( T λ ) ≀ S t λ ) .
Theorem 1.6 answers Problem 1.1 for connected twin-free nonunit factors. Parts (ii) and (iii) show that two selected components are isomorphic precisely when their refined labels lie in the same orbit, and the full automorphism group of a selected component is the stabilizer of its label. Part (iv) then assembles the independent component automorphisms and the permutations of isomorphic components. Part (v) expresses the refined factor symmetry group using the automorphism groups and multiplicities of the underlying f f f -prime factors.
Significance and relation to previous work
The essential content of Theorem 1.6 is the determination of component data from the refined factors. The wreath product formula for a disjoint union is standard. Here its constituent groups and multiplicities are obtained as stabilizers and orbit-intersection sizes. The component groups and component isomorphism types are not additional inputs. In particular, specified isomorphisms between components, rather than only the existence of such isomorphisms, must be controlled.
The dependence on classical theory is explicit. McKenzie’s strict refinement theorem [18 ] is the decomposition input. Lemmas 2.7 and 2.8 supply the edge-relation correspondence and its closure under factors. These lemmas transfer specified relation isomorphisms back to graph coordinates. Theorem 1.5 then handles the common colour sign, and the original blocks specify the components selected in Theorem 1.6. The correspondence is used for objects and isomorphisms (no assertion about all noninvertible homomorphisms is needed). This theory concerns fibre products, not uniqueness of ordinary direct prime factorizations of bipartite graphs.
Hammack’s two-factor theorem [9 ] determines when the two components are isomorphic. Our treatment applies to any number of bipartite factors and recovers both the component isomorphism classes and the component automorphism groups via a common action on refined factor labels. The restriction to connected twin-free factors is essential throughout. We describe all component isomorphisms and automorphism groups for arbitrary numbers of factors. Corollary 4.5 makes the description explicit for products of fibre powers of one prime graph. This calculation uses the refinement of the original factors and distinguishes the present setting from the singleton-block specialization.
Following [23 ] , a graph pair ( X , Y ) (X,Y) ( X , Y ) is stable if equality holds in (1) . The canonical double cover is D ( X ) = X × K 2 D(X)=X\times K_2 D ( X ) = X × K 2 , and X X X is stable when ( X , K 2 ) (X,K_2) ( X , K 2 ) is stable. See [5 , 16 , 19 , 20 , 24 , 25 , 30 ] for graph stability and [7 , 22 , 23 , 26 , 27 , 28 ] for graph pairs. Corollary 4.7 computes the mixed-product group when D ( X ) D(X) D ( X ) and the bipartite factor are nonisomorphic fibre-prime graphs. Its stability equivalence is covered by the factor-loopless theorem in Theorem 1.3 of [28 ] . We explain the implication between the hypotheses after the proof. The final generalized Petersen formulas recover Theorem 1.2(iii) of [21 ] and are not new classifications.
Organization of the paper
Section 2 introduces the necessary notation and basic results on ordered bipartite graphs, fibre products, and binary relation structures. In Section 3, we prove Theorems 1.3, 1.4 and 1.5, and derive the component isomorphism criterion in Corollary 3.4. In Section 4, we prove Theorem 1.6 and derive Corollaries 4.2 and 4.3 as special cases. We then compute products of fibre powers in Corollary 4.5, derive the semidirect product formula of Corollary 4.7 and obtain the automorphism group of canonical double covers of bipartite generalized Petersen graphs in Corollary 4.11.
Preliminaries
We introduce notation for ordered bipartite graphs, establish basic properties of their fibre products, and describe their correspondence with binary relation structures.
Ordered bipartite graphs
Recall that B ( ϵ ) B^{(\epsilon)} B ( ϵ ) denotes a recolouring of B B B , whereas B ϵ B^\epsilon B ϵ is one of its vertex classes. In this subsection B B B and C C C are connected ordered bipartite graphs. An isomorphism in B i p 2 \mathrm{Bip}_2 Bip 2 preserves the two ordered classes; an ordinary isomorphism may interchange them. For any ordinary isomorphism f : U ( B ) → U ( C ) f:\mathrm{U}(B)\to\mathrm{U}(C) f : U ( B ) → U ( C ) , the uniqueness of the bipartition up to interchange implies that there is a unique sign χ ( f ) ∈ F 2 \chi(f)\in\mathbb{F}_2 χ ( f ) ∈ F 2 such that, for every vertex x ∈ V ( B ) x\in V(B) x ∈ V ( B ) ,
ϱ C ( f ( x ) ) = ϱ B ( x ) + χ ( f ) . (9) \varrho_C(f(x))=\varrho_B(x)+\chi(f). \tag*{(9)} ϱ C ( f ( x )) = ϱ B ( x ) + χ ( f ) . (9)
The map f f f preserves the two colour classes when χ ( f ) = 0 \chi(f)=0 χ ( f ) = 0 and interchanges them when χ ( f ) = 1 \chi(f)=1 χ ( f ) = 1 .
For a connected ordered bipartite graph B B B , define χ B : Aut ( U ( B ) ) → F 2 \chi_B:\operatorname{Aut}(\mathrm{U}(B))\to\mathbb{F}_2 χ B : Aut ( U ( B )) → F 2 by χ B ( g ) = χ ( g ) \chi_B(g)=\chi(g) χ B ( g ) = χ ( g ) for g ∈ Aut ( U ( B ) ) g\in\operatorname{Aut}(\mathrm{U}(B)) g ∈ Aut ( U ( B )) . Applying Eq. (9) twice, we obtain χ B ( g h ) = χ B ( g ) + χ B ( h ) \chi_B(gh)=\chi_B(g)+\chi_B(h) χ B ( g h ) = χ B ( g ) + χ B ( h ) for g , h ∈ Aut ( U ( B ) ) g,h\in\operatorname{Aut}(\mathrm{U}(B)) g , h ∈ Aut ( U ( B )) . Thus χ B \chi_B χ B is a group homomorphism. Define
Aut + ( B ) = ker χ B = { g ∈ Aut ( U ( B ) ) : g ( B 0 ) = B 0 } , \operatorname{Aut}^{+}(B)=\ker\chi_B=\{g\in\operatorname{Aut}(\mathrm{U}(B)):g(B^0)=B^0\}, Aut + ( B ) = ker χ B = { g ∈ Aut ( U ( B )) : g ( B 0 ) = B 0 } ,
Aut − ( B ) = χ B − 1 ( 1 ) = { g ∈ Aut ( U ( B ) ) : g ( B 0 ) = B 1 } . \operatorname{Aut}^{-}(B)=\chi_B^{-1}(1)=\{g\in\operatorname{Aut}(\mathrm{U}(B)):g(B^0)=B^1\}. Aut − ( B ) = χ B − 1 ( 1 ) = { g ∈ Aut ( U ( B )) : g ( B 0 ) = B 1 } .
The automorphism group of B B B as an object of B i p 2 \mathrm{Bip}_2 Bip 2 is precisely Aut + ( B ) \operatorname{Aut}^{+}(B) Aut + ( B ) . If an automorphism interchanges the two colour classes, then Aut + ( B ) \operatorname{Aut}^{+}(B) Aut + ( B ) has index two in Aut ( U ( B ) ) \operatorname{Aut}(\mathrm{U}(B)) Aut ( U ( B )) , and Aut − ( B ) \operatorname{Aut}^{-}(B) Aut − ( B ) is its nontrivial coset. In all cases, \operatorname{Aut}(\mathrm{U}(B))=\operatorname{Aut}^{+}(B)\mathbin{\mathaccent\cdot\cup}\operatorname{Aut}^{-}(B) . If no automorphism interchanges the colour classes, then Aut − ( B ) = ∅ \operatorname{Aut}^{-}(B)=\varnothing Aut − ( B ) = ∅ .
For connected ordered bipartite graphs B B B and C C C , define the group
G ( B , C ) = { ( g , h ) ∈ Aut ( U ( B ) ) × Aut ( U ( C ) ) : χ B ( g ) = χ C ( h ) } . \mathcal{G}(B,C)=\{(g,h)\in\operatorname{Aut}(\mathrm{U}(B))\times\operatorname{Aut}(\mathrm{U}(C)):\chi_B(g)=\chi_C(h)\}. G ( B , C ) = {( g , h ) ∈ Aut ( U ( B )) × Aut ( U ( C )) : χ B ( g ) = χ C ( h )} .
In other words,
G ( B , C ) = ( Aut + ( B ) × Aut + ( C ) ) ∪ ( Aut − ( B ) × Aut − ( C ) ) , \mathcal{G}(B,C)=\left(\operatorname{Aut}^{+}(B)\times\operatorname{Aut}^{+}(C)\right)\cup\left(\operatorname{Aut}^{-}(B)\times\operatorname{Aut}^{-}(C)\right), G ( B , C ) = ( Aut + ( B ) × Aut + ( C ) ) ∪ ( Aut − ( B ) × Aut − ( C ) ) ,
where the second set is empty if either factor has no automorphism interchanging its two colour classes. Since G ( B , C ) \mathcal{G}(B,C) G ( B , C ) is the kernel of the homomorphism ( g , h ) ↦ χ B ( g ) + χ C ( h ) (g,h) \mapsto\chi_B(g) + \chi_C(h) ( g , h ) ↦ χ B ( g ) + χ C ( h ) from Aut ( U ( B ) ) × Aut ( U ( C ) ) \operatorname{Aut}(U(B)) \times\operatorname{Aut}(U(C)) Aut ( U ( B )) × Aut ( U ( C )) to F 2 \mathbb{F}_2 F 2 , it is a subgroup of Aut ( U ( B ) ) × Aut ( U ( C ) ) \operatorname{Aut}(U(B)) \times\operatorname{Aut}(U(C)) Aut ( U ( B )) × Aut ( U ( C )) .
For the canonical double cover D ( X ) D(X) D ( X ) defined in the introduction, we use the ordered bipartition
D ( X ) 0 = V ( X ) × { 0 } , D ( X ) 1 = V ( X ) × { 1 } , D(X)^0 = V(X) \times\{0\}, \qquad D(X)^1 = V(X) \times\{1\}, D ( X ) 0 = V ( X ) × { 0 } , D ( X ) 1 = V ( X ) × { 1 } ,
and write κ X ( ( x , i ) ) = ( x , 1 − i ) \kappa_X((x,i)) = (x,1-i) κ X (( x , i )) = ( x , 1 − i ) for the covering involution, where ( x , i ) ∈ V ( D ( X ) ) (x,i) \in V(D(X)) ( x , i ) ∈ V ( D ( X )) . Recall that a graph X X X is called stable if Aut ( D ( X ) ) = Aut ( X ) × ⟨ κ X ⟩ \operatorname{Aut}(D(X)) = \operatorname{Aut}(X) \times\langle\kappa_X \rangle Aut ( D ( X )) = Aut ( X ) × ⟨ κ X ⟩ [19 ] .
Lemma 2.1. Let B B B be a connected twin-free ordered bipartite graph. If all vertices in one colour class have degree one, then B ≅ K 2 B \cong K_2 B ≅ K 2 in Bip 2 \operatorname{Bip}_2 Bip 2 . Consequently, if B B B is nonunit, each colour class has at least two vertices and contains a vertex of degree at least two.
Proof. Suppose that every vertex of B 0 B^0 B 0 has degree one. If B 1 B^1 B 1 contained two vertices, a path between them would have an internal vertex in B 0 B^0 B 0 of degree at least two. Thus B 1 B^1 B 1 has one vertex. Since B B B is connected and twin-free B ≅ K 2 B \cong K_2 B ≅ K 2 . The same argument applies with the colours reversed.
If either colour class has only one vertex, then B B B is a star by the connectedness, and moreover, B ≅ K 2 B \cong K_2 B ≅ K 2 since B B B is twin-free. Consequently, a nonunit graph has at least two vertices in each class. Since B B B is connected, each class contains a vertex of degree at least two.
The fibre product over K 2 K_2 K 2
We first establish some basic properties of the fibre product over K 2 K_2 K 2 . Throughout this subsection, we assume that every ordered bipartite graph has two nonempty colour classes and at least one edge.
Let B B B , C C C and D D D be ordered bipartite graphs. The natural maps
( B ⋆ C ) ⋆ D ⟶ B ⋆ ( C ⋆ D ) , ( ( b , c ) , d ) ⟼ ( b , ( c , d ) ) , (B \star C) \star D \longrightarrow B \star(C \star D), \qquad((b,c),d) \longmapsto(b,(c,d)), ( B ⋆ C ) ⋆ D ⟶ B ⋆ ( C ⋆ D ) , (( b , c ) , d ) ⟼ ( b , ( c , d )) ,
and
B ⋆ C ⟶ C ⋆ B , ( b , c ) ⟼ ( c , b ) , B \star C \longrightarrow C \star B, \qquad(b,c) \longmapsto(c,b), B ⋆ C ⟶ C ⋆ B , ( b , c ) ⟼ ( c , b ) ,
are isomorphisms in Bip 2 \operatorname{Bip}_2 Bip 2 , where b ∈ V ( B ) b \in V(B) b ∈ V ( B ) , c ∈ V ( C ) c \in V(C) c ∈ V ( C ) and d ∈ V ( D ) d \in V(D) d ∈ V ( D ) . Hence the fibre product is associative and commutative up to these natural isomorphisms. We write ⋆ i = 1 r B i \mathop{\star}_{i=1}^{r} B_i ⋆ i = 1 r B i . For connected factors, B ⋆ C B \star C B ⋆ C is connected, whereas U ( B ) × U ( C ) U(B) \times U(C) U ( B ) × U ( C ) has two connected components. Thus the fibre product is precisely the component in which the coordinate colours agree. Its unit and its notion of primality differ from those of the direct product.
We now establish the fibre product properties used in the sequel.
Lemma 2.2. Let B B B and C C C be connected ordered bipartite graphs. Then B ⋆ C B \star C B ⋆ C is connected.
Proof. Let ( b , c ) (b,c) ( b , c ) and ( b ′ , c ′ ) (b',c') ( b ′ , c ′ ) be vertices of B ⋆ C B \star C B ⋆ C . Then ϱ B ( b ) = ϱ C ( c ) \varrho_B(b) = \varrho_C(c) ϱ B ( b ) = ϱ C ( c ) and ϱ B ( b ′ ) = ϱ C ( c ′ ) \varrho_B(b') = \varrho_C(c') ϱ B ( b ′ ) = ϱ C ( c ′ ) . Choose a path P : b = b 0 , b 1 , … , b p = b ′ P : b = b_0,b_1,\ldots,b_p = b' P : b = b 0 , b 1 , … , b p = b ′ in B B B and a path Q : c = c 0 , c 1 , … , c q = c ′ Q : c = c_0,c_1,\ldots,c_q = c' Q : c = c 0 , c 1 , … , c q = c ′ in C C C . We have p ≡ ϱ B ( b ′ ) − ϱ B ( b ) ( m o d 2 ) p \equiv\varrho_B(b') - \varrho_B(b) \pmod2 p ≡ ϱ B ( b ′ ) − ϱ B ( b ) ( mod 2 ) and q ≡ ϱ C ( c ′ ) − ϱ C ( c ) ( m o d 2 ) q \equiv\varrho_C(c') - \varrho_C(c) \pmod2 q ≡ ϱ C ( c ′ ) − ϱ C ( c ) ( mod 2 ) , so p ≡ q ( m o d 2 ) p \equiv q \pmod2 p ≡ q ( mod 2 ) . Without loss of generality, assume that p ≤ q p \leq q p ≤ q . Then q − p q-p q − p is even. Since B B B is connected and has an edge, every vertex of B B B has a neighbour. We obtain a walk b = b 0 ′ , b 1 ′ , … , b q ′ = b ′ b = b'_0,b'_1,\ldots,b'_q = b' b = b 0 ′ , b 1 ′ , … , b q ′ = b ′ of length q q q by inserting the walk z , z ′ , z z,z',z z , z ′ , z at a vertex z z z of P P P exactly ( q − p ) / 2 (q-p)/2 ( q − p ) /2 times, where z ′ z' z ′ is a neighbour of z z z . At each step, both coordinates move along an edge, and their colours change simultaneously. Therefore ( b 0 ′ , c 0 ) , ( b 1 ′ , c 1 ) , … , ( b q ′ , c q ) (b'_0,c_0),(b'_1,c_1),\ldots,(b'_q,c_q) ( b 0 ′ , c 0 ) , ( b 1 ′ , c 1 ) , … , ( b q ′ , c q ) is a walk in B ⋆ C B \star C B ⋆ C from ( b , c ) (b,c) ( b , c ) to ( b ′ , c ′ ) (b',c') ( b ′ , c ′ ) . Every walk contains a path with the same endpoints, so B ⋆ C B \star C B ⋆ C is connected.
The next result indexes all connected components of a direct product of bipartite graphs by coordinate colour vectors.
Proposition 2.3. Let B 1 , … , B r B_1,\ldots,B_r B 1 , … , B r be connected ordered bipartite graphs, where r ≥ 2 r \ge2 r ≥ 2 is an integer, and let Q r = F 2 r / ⟨ 1 r ⟩ Q_r = \mathbb{F}_2^r/\langle\mathbf{1}_r\rangle Q r = F 2 r / ⟨ 1 r ⟩ . Let P = U ( B 1 ) × ⋯ × U ( B r ) P = \mathrm{U}(B_1) \times\cdots\times\mathrm{U}(B_r) P = U ( B 1 ) × ⋯ × U ( B r ) . Then the following statements hold.
(i) The graphs Ω ϵ ˉ \Omega_{\bar{\epsilon}} Ω ϵ ˉ , indexed by ϵ ˉ ∈ Q r \bar{\epsilon} \in Q_r ϵ ˉ ∈ Q r , are exactly the connected components of P P P .
(ii) P P P has 2 r − 1 2^{r-1} 2 r − 1 connected components.
(iii) The representatives ϵ \epsilon ϵ and ϵ + 1 r \epsilon+\mathbf{1}_r ϵ + 1 r determine the same underlying component with opposite ordered bipartitions.
Proof. (i). For any vertex x = ( x 1 , … , x r ) \mathbf{x}=(x_1,\ldots,x_r) x = ( x 1 , … , x r ) in V ( P ) V(P) V ( P ) , its coordinate colour vector is π ( x ) = ( ϱ B 1 ( x 1 ) , … , ϱ B r ( x r ) ) ∈ F 2 r \pi(\mathbf{x})=(\varrho_{B_1}(x_1),\ldots,\varrho_{B_r}(x_r))\in\mathbb{F}_2^r π ( x ) = ( ϱ B 1 ( x 1 ) , … , ϱ B r ( x r )) ∈ F 2 r . If x \mathbf{x} x is adjacent to y = ( y 1 , … , y r ) \mathbf{y}=(y_1,\ldots,y_r) y = ( y 1 , … , y r ) in P P P , then x i x_i x i is adjacent to y i y_i y i in B i B_i B i for every 1 ≤ i ≤ r 1\le i\le r 1 ≤ i ≤ r . Since every edge of a bipartite graph joins vertices of opposite colours, we have ϱ B i ( y i ) = ϱ B i ( x i ) + 1 \varrho_{B_i}(y_i)=\varrho_{B_i}(x_i)+1 ϱ B i ( y i ) = ϱ B i ( x i ) + 1 for every 1 ≤ i ≤ r 1\le i\le r 1 ≤ i ≤ r . Thus π ( y ) = π ( x ) + 1 r \pi(\mathbf{y})=\pi(\mathbf{x})+\mathbf{1}_r π ( y ) = π ( x ) + 1 r . The class π ( x ) ‾ ∈ Q r \overline{\pi(\mathbf{x})}\in Q_r π ( x ) ∈ Q r is constant on every edge of P P P and is therefore constant on every connected component of P P P .
Fix ϵ ˉ = ( ϵ 1 , … , ϵ r ) ∈ F 2 r \bar{\epsilon}=(\epsilon_1,\ldots,\epsilon_r)\in\mathbb{F}_2^r ϵ ˉ = ( ϵ 1 , … , ϵ r ) ∈ F 2 r . By the definition of the fibre product, a vertex x = ( x 1 , … , x r ) \mathbf{x}=(x_1,\ldots,x_r) x = ( x 1 , … , x r ) belongs to V ( B 1 ( ϵ 1 ) ⋆ ⋯ ⋆ B r ( ϵ r ) ) V(B_1^{(\epsilon_1)}\star\cdots\star B_r^{(\epsilon_r)}) V ( B 1 ( ϵ 1 ) ⋆ ⋯ ⋆ B r ( ϵ r ) ) if and only if ϱ B i ( x i ) + ϵ i = ϱ B j ( x j ) + ϵ j \varrho_{B_i}(x_i)+\epsilon_i=\varrho_{B_j}(x_j)+\epsilon_j ϱ B i ( x i ) + ϵ i = ϱ B j ( x j ) + ϵ j for every $1\le i,j\le r$. Thus there is a value t ∈ F 2 t\in\mathbb{F}_2 t ∈ F 2 such that ϱ B i ( x i ) = ϵ i + t \varrho_{B_i}(x_i)=\epsilon_i+t ϱ B i ( x i ) = ϵ i + t for every 1 ≤ i ≤ r . B y x r e f ‘ E q . ( 5 ) ‘ , 1\le i\le r. By {xref}`Eq. (5)`, 1 ≤ i ≤ r . B y x r e f ‘ E q . ( 5 ) ‘ , t$ is the global colour of x \mathbf{x} x in the fibre product. Hence π ( x ) = ϵ + t 1 r \pi(\mathbf{x})=\epsilon+t\mathbf{1}_r π ( x ) = ϵ + t 1 r , which is equivalent to π ( x ) ‾ = ϵ ˉ \overline{\pi(\mathbf{x})}=\bar{\epsilon} π ( x ) = ϵ ˉ in Q r Q_r Q r . Therefore, the vertex set of Ω ϵ ˉ \Omega_{\bar{\epsilon}} Ω ϵ ˉ is precisely the set of vertices of P P P whose coordinate colour vectors have class ϵ ˉ \bar{\epsilon} ϵ ˉ .
By Lemma 2.2 , each fibre product B 1 ( ϵ 1 ) ⋆ ⋯ ⋆ B r ( ϵ r ) B_1^{(\epsilon_1)}\star\cdots\star B_r^{(\epsilon_r)} B 1 ( ϵ 1 ) ⋆ ⋯ ⋆ B r ( ϵ r ) is connected. Since no edge joins a vertex in this set to a vertex whose colour vector lies in a different class, Ω ϵ ˉ \Omega_{\bar{\epsilon}} Ω ϵ ˉ is a connected component of P P P .
(ii). Each factor has two nonempty colour classes. Thus every vector in F 2 r \mathbb{F}_2^r F 2 r occurs as a coordinate colour vector and every quotient class indexes a component. As Q r = F 2 r / ⟨ 1 r ⟩ Q_r=\mathbb{F}_2^r/\langle\mathbf{1}_r\rangle Q r = F 2 r / ⟨ 1 r ⟩ has order 2 r − 1 2^{r-1} 2 r − 1 , the number of components is 2 r − 1 2^{r-1} 2 r − 1 .
(iii). The vectors ϵ \epsilon ϵ and ϵ + 1 r \epsilon+\mathbf{1}_r ϵ + 1 r represent the same class in Q r Q_r Q r and therefore specify the same underlying component. Replacing one representative by the other changes the common colour t t t in the preceding display to t + 1 t+1 t + 1 , which interchanges the two global colour classes of that component. □
Lemma 2.4. Let B B B and C C C be connected ordered bipartite graphs. Then B ⋆ C B\star C B ⋆ C is twin-free if and only if both B B B and C C C are twin-free. Moreover, U ( B ) × U ( C ) = U ( B ⋆ C ) ⊔ U ( B ⋆ C o p ) \mathrm{U}(B)\times\mathrm{U}(C)=\mathrm{U}(B\star C)\sqcup\mathrm{U}(B\star C^{\mathrm{op}}) U ( B ) × U ( C ) = U ( B ⋆ C ) ⊔ U ( B ⋆ C op ) .
Proof. By Proposition 2.3 (i), B ⋆ C B\star C B ⋆ C is a connected component of U ( B ) × U ( C ) \mathrm{U}(B)\times\mathrm{U}(C) U ( B ) × U ( C ) . Together with [11 Lemma 2.3] , this shows that B ⋆ C B\star C B ⋆ C is twin-free if and only if both B B B and C C C are twin-free. Moreover, when r = 2 r=2 r = 2 , the two elements of Q 2 Q_2 Q 2 are represented by ( 0 , 0 ) (0,0) ( 0 , 0 ) and ( 0 , 1 ) (0,1) ( 0 , 1 ) . By Proposition 2.3 , we have U ( B ) × U ( C ) = U ( B ⋆ C ) ⊔ U ( B ⋆ C o p ) \mathrm{U}(B)\times\mathrm{U}(C)=\mathrm{U}(B\star C)\sqcup\mathrm{U}(B\star C^{\mathrm{op}}) U ( B ) × U ( C ) = U ( B ⋆ C ) ⊔ U ( B ⋆ C op ) . □
We next give a useful sufficient condition for fibre primality.
Lemma 2.5. Let B B B be a connected twin-free nonunit ordered bipartite graph. Then B B B is f f f -prime if one of the following statements holds:
(i) all vertices of one colour class have the same prime degree;
(ii) U ( B ) \mathrm{U}(B) U ( B ) contains no cycle of length four.
Proof. Suppose that B ≅ X ⋆ Y B\cong X\star Y B ≅ X ⋆ Y in B i p 2 \mathbf{Bip}_2 Bip 2 , where both factors are nonunit. Since both colour classes of each factor are nonempty, the coordinate projections are surjective graph homomorphisms. Hence X X X and Y Y Y are connected. By Lemma 2.4 , since B B B is twin-free, X X X and Y Y Y are twin-free. For a ∈ X i a\in X^i a ∈ X i , c ∈ Y i c\in Y^i c ∈ Y i and i ∈ { 0 , 1 } i\in\{0,1\} i ∈ { 0 , 1 } ,
deg X ⋆ Y ( a , c ) = deg X ( a ) deg Y ( c ) . \deg_{X\star Y}(a,c)=\deg_X(a)\deg_Y(c). deg X ⋆ Y ( a , c ) = deg X ( a ) deg Y ( c ) .
Under (i), interchange the colour labels if necessary so that the common prime degree occurs on B 0 B^{0} B 0 , and denote it by p p p . Fix a 0 ∈ X 0 , c 0 ∈ Y 0 a_{0} \in X^{0}, c_{0} \in Y^{0} a 0 ∈ X 0 , c 0 ∈ Y 0 . Varying a a a in deg X ( a ) deg Y ( c 0 ) = p \deg_{X}(a)\deg_{Y}(c_{0})=p deg X ( a ) deg Y ( c 0 ) = p makes deg X \deg_{X} deg X constant on X 0 X^{0} X 0 . Varying c c c with a 0 a_{0} a 0 fixed makes deg Y \deg_{Y} deg Y constant on Y 0 Y^{0} Y 0 . The two positive constants multiply to the prime p p p , so deg X \deg_{X} deg X is 1 or deg Y \deg_{Y} deg Y is 1. Lemma 2.1 makes that factor K 2 K_{2} K 2 , a contradiction.
Under (ii), Lemma 2.1 supplies a ∈ X 0 a \in X^{0} a ∈ X 0 with distinct neighbours a 1 , a 2 ∈ X 1 a_{1},a_{2} \in X^{1} a 1 , a 2 ∈ X 1 , and c ∈ Y 1 c \in Y^{1} c ∈ Y 1 with distinct neighbours c 1 , c 2 ∈ Y 0 c_{1},c_{2} \in Y^{0} c 1 , c 2 ∈ Y 0 . The four vertices
( a , c 1 ) , ( a 1 , c ) , ( a , c 2 ) , ( a 2 , c ) (a,c_{1}),\ (a_{1},c),\ (a,c_{2}),\ (a_{2},c) ( a , c 1 ) , ( a 1 , c ) , ( a , c 2 ) , ( a 2 , c )
are distinct, and form a four-cycle in X ⋆ Y X \star Y X ⋆ Y , again a contradiction. □
Relation structures on ordered bipartite graphs
We now construct a binary relation structure on the edge set of a connected twin-free ordered bipartite graph. We begin with definitions from the theory of relational structures [3 , 18 ] .
Definition 2.6. [18 ] A relation structure is a pair X = ( X , R ) \mathcal{X}=(X,R) X = ( X , R ) , where X X X is a nonempty set and R ⊆ X × X R \subseteq X \times X R ⊆ X × X is a binary relation. For x ∈ X x \in X x ∈ X , write R [ x ] = { y ∈ X : x R y } R[x]=\{y \in X:xRy\} R [ x ] = { y ∈ X : x R y } and R − 1 [ x ] = { y ∈ X : y R x } R^{-1}[x]=\{y \in X:yRx\} R − 1 [ x ] = { y ∈ X : y R x } . The structure is reflexive if x R x xRx x R x for every x ∈ X x \in X x ∈ X . It is connected if for any two elements x , y ∈ X x,y \in X x , y ∈ X , there are an integer m ≥ 0 m \ge0 m ≥ 0 and elements x = x 0 , x 1 , … , x m = y x=x_{0},x_{1},\ldots,x_{m}=y x = x 0 , x 1 , … , x m = y such that for every 0 ≤ i ≤ m − 1 0 \le i \le m-1 0 ≤ i ≤ m − 1 , either x i R x i + 1 x_{i}Rx_{i+1} x i R x i + 1 or x i R − 1 x i + 1 x_{i}R^{-1}x_{i+1} x i R − 1 x i + 1 .
Define two equivalence relations on X X X by
x ≡ 0 x ′ ⟺ R [ x ] = R [ x ′ ] , x ≡ 1 x ′ ⟺ R − 1 [ x ] = R − 1 [ x ′ ] . (10) x \mathrel{\equiv_{0}} x' \Longleftrightarrow R[x]=R[x'],\qquad x \mathrel{\equiv_{1}} x' \Longleftrightarrow R^{-1}[x]=R^{-1}[x']. \tag*{(10)} x ≡ 0 x ′ ⟺ R [ x ] = R [ x ′ ] , x ≡ 1 x ′ ⟺ R − 1 [ x ] = R − 1 [ x ′ ] . (10)
The relation structure is thin if ( ≡ 0 ∩ ≡ 1 ) = Δ X (\equiv_{0}\cap\equiv_{1})=\Delta_{X} ( ≡ 0 ∩ ≡ 1 ) = Δ X , where Δ X = { ( x , x ) : x ∈ X } \Delta_{X}=\{(x,x):x \in X\} Δ X = {( x , x ) : x ∈ X } is the diagonal relation. We call it rectangular in this paper if
x R y ⟺ there exists z ∈ X such that z ≡ 0 x and z ≡ 1 y . (11) xRy \Longleftrightarrow\text{there exists }z \in X\text{ such that }z\equiv_{0}x\text{ and }z\equiv_{1}y. \tag*{(11)} x R y ⟺ there exists z ∈ X such that z ≡ 0 x and z ≡ 1 y . (11)
For any x ∈ X x \in X x ∈ X , write [ x ] ≡ 0 = { y ∈ X : x ≡ 0 y } [x]_{\equiv_{0}}=\{y \in X:x\equiv_{0}y\} [ x ] ≡ 0 = { y ∈ X : x ≡ 0 y } and [ x ] ≡ 1 = { y ∈ X : x ≡ 1 y } [x]_{\equiv_{1}}=\{y \in X:x\equiv_{1}y\} [ x ] ≡ 1 = { y ∈ X : x ≡ 1 y } for its two equivalence classes. Write X / ≡ 0 = { [ x ] ≡ 0 : x ∈ X } X/\equiv_{0}=\{[x]_{\equiv_{0}}:x \in X\} X / ≡ 0 = {[ x ] ≡ 0 : x ∈ X } and X / ≡ 1 = { [ x ] ≡ 1 : x ∈ X } X/\equiv_{1}=\{[x]_{\equiv_{1}}:x \in X\} X / ≡ 1 = {[ x ] ≡ 1 : x ∈ X } .
For relation structures X = ( X , R ) \mathcal{X}=(X,R) X = ( X , R ) and Y = ( Y , Q ) \mathcal{Y}=(Y,Q) Y = ( Y , Q ) , a relation isomorphism is a bijection f : X → Y f:X \to Y f : X → Y satisfying x R x ′ ⟺ f ( x ) Q f ( x ′ ) xRx' \Longleftrightarrow f(x)Qf(x') x R x ′ ⟺ f ( x ) Q f ( x ′ ) . Their direct product is ( X × Y , R × Q ) (X \times Y,R \times Q) ( X × Y , R × Q ) , where ( x , y ) ( R × Q ) ( x ′ , y ′ ) (x,y)(R \times Q)(x',y') ( x , y ) ( R × Q ) ( x ′ , y ′ ) if and only if x R x ′ xRx' x R x ′ and y Q y ′ yQy' y Q y ′ . When two underlying sets occur in one formula, superscripts R R R , Q Q Q , or R × Q R \times Q R × Q on ≡ i \equiv_{i} ≡ i identify the relation defining the equivalence class. The one-element reflexive relation structure is the unit. A nonunit relation structure is d d d -prime if, in every factorization into two relation structures, at least one factor is isomorphic to the unit. Denote by G \mathcal{G} G the class of all finite connected reflexive thin rectangular relation structures, together with the one-element unit.
Let B B B be a connected twin-free ordered bipartite graph with V ( B ) = B 0 ⊔ B 1 V(B)=B^{0}\sqcup B^{1} V ( B ) = B 0 ⊔ B 1 . We identify an edge with the ordered pair ( a , b ) (a,b) ( a , b ) of its endpoints, where a ∈ B 0 a \in B^{0} a ∈ B 0 and b ∈ B 1 b \in B^{1} b ∈ B 1 . For edges e = ( a , b ) e=(a,b) e = ( a , b ) and f = ( c , d ) f=(c,d) f = ( c , d ) , define
e ρ 0 f ⟺ a = c , e ρ 1 f ⟺ b = d . e\rho_{0}f \Longleftrightarrow a=c,\qquad e\rho_{1}f \Longleftrightarrow b=d. e ρ 0 f ⟺ a = c , e ρ 1 f ⟺ b = d .
Let R B = ρ 0 ∘ ρ 1 R_{B}=\rho_{0}\circ\rho_{1} R B = ρ 0 ∘ ρ 1 and R ( B ) = ( E ( B ) , R B ) \mathcal{R}(B)=(E(B),R_{B}) R ( B ) = ( E ( B ) , R B ) . With the right-to-left convention fixed above, e R B f eR_{B}f e R B f means that there exists an edge g g g of B B B such that e ρ 0 g e\rho_{0}g e ρ 0 g and g ρ 1 f g\rho_{1}f g ρ 1 f . Thus
( a , b ) R B ( c , d ) ⟺ ( a , d ) ∈ E ( B ) . (12) (a,b)R_{B}(c,d)\Longleftrightarrow(a,d)\in E(B). \tag*{(12)} ( a , b ) R B ( c , d ) ⟺ ( a , d ) ∈ E ( B ) . (12)
Conversely, let X = ( X , R ) ∈ G \mathcal{X}=(X,R)\in\mathcal{G} X = ( X , R ) ∈ G . Define an ordered bipartite graph B ( X ) \mathcal{B}(\mathcal{X}) B ( X ) with B ( X ) 0 = ( X / ≡ 0 ) × { 0 } \mathcal{B}(\mathcal{X})^{0}=(X/\equiv_{0})\times\{0\} B ( X ) 0 = ( X / ≡ 0 ) × { 0 } and B ( X ) 1 = ( X / ≡ 1 ) × { 1 } \mathcal{B}(\mathcal{X})^{1}=(X/\equiv_{1})\times\{1\} B ( X ) 1 = ( X / ≡ 1 ) × { 1 } . For every x ∈ X x \in X x ∈ X , include the edge e x = { ( [ x ] ≡ 0 , 0 ) , ( [ x ] ≡ 1 , 1 ) } e_{x}=\{([x]_{\equiv_{0}},0),([x]_{\equiv_{1}},1)\} e x = {([ x ] ≡ 0 , 0 ) , ([ x ] ≡ 1 , 1 )} . If e x = e y e_{x}=e_{y} e x = e y , then x ≡ 0 y x\equiv_{0}y x ≡ 0 y and x ≡ 1 y x\equiv_{1}y x ≡ 1 y . Since X \mathcal{X} X is thin, we obtain x = y x=y x = y . Thus, distinct elements of X X X correspond to distinct edges, so B ( X ) \mathcal{B}(\mathcal{X}) B ( X ) is a simple bipartite graph.
The next lemma shows that the two constructions recover one another and respect the corresponding products.
Lemma 2.7. Let B B B be a connected twin-free ordered bipartite graph, and let X = ( X , R ) , Y = ( Y , Q ) ∈ G \mathcal{X}=(X,R),\mathcal{Y}=(Y,Q)\in\mathcal{G} X = ( X , R ) , Y = ( Y , Q ) ∈ G . Then the following statements hold.
(i) The relation structure R ( B ) = ( E ( B ) , R B ) \mathcal{R}(B)=(E(B),R_B) R ( B ) = ( E ( B ) , R B ) belongs to G \mathcal{G} G , and the two equivalence relations defined in (10) are exactly ρ 0 \rho_0 ρ 0 and ρ 1 \rho_1 ρ 1 .
(ii) The bipartite graph B ( X ) B(\mathcal{X}) B ( X ) is connected and twin-free, and R ( B ( X ) ) ≅ X \mathcal{R}(B(\mathcal{X}))\cong\mathcal{X} R ( B ( X )) ≅ X . Every relation isomorphism X → Y \mathcal{X}\to\mathcal{Y} X → Y induces an isomorphism in B i p 2 \mathbf{Bip}_2 Bip 2 from B ( X ) B(\mathcal{X}) B ( X ) to B ( Y ) B(\mathcal{Y}) B ( Y ) .
(iii) For connected twin-free ordered bipartite graphs B B B and C C C , there is a natural isomorphism R ( B ⋆ C ) ≅ R ( B ) × R ( C ) \mathcal{R}(B\star C)\cong\mathcal{R}(B)\times\mathcal{R}(C) R ( B ⋆ C ) ≅ R ( B ) × R ( C ) . Moreover, B ( X × Y ) ≅ B ( X ) ⋆ B ( Y ) B(\mathcal{X}\times\mathcal{Y})\cong B(\mathcal{X})\star B(\mathcal{Y}) B ( X × Y ) ≅ B ( X ) ⋆ B ( Y ) in B i p 2 \mathbf{Bip}_2 Bip 2 .
(iv) The constructions from B B B to R ( B ) \mathcal{R}(B) R ( B ) and from X \mathcal{X} X to B ( X ) B(\mathcal{X}) B ( X ) are mutually inverse up to natural isomorphism, on objects and isomorphisms, and preserve products.
Proof. (i). We first prove that the two equivalence relations defined in (10) are exactly ρ 0 \rho_0 ρ 0 and ρ 1 \rho_1 ρ 1 . Let e = ( a , b ) ∈ E ( B ) e=(a,b)\in E(B) e = ( a , b ) ∈ E ( B ) . By (12) , an edge f = ( c , d ) f=(c,d) f = ( c , d ) belongs to R B [ e ] R_B[e] R B [ e ] if and only if ( a , d ) (a,d) ( a , d ) is an edge of B B B , or equivalently, d ∈ N B ( a ) d\in N_B(a) d ∈ N B ( a ) . Thus R B [ e ] = { ( c , d ) ∈ E ( B ) : d ∈ N B ( a ) } R_B[e]=\{(c,d)\in E(B):d\in N_B(a)\} R B [ e ] = {( c , d ) ∈ E ( B ) : d ∈ N B ( a )} . If e ρ 0 f e\rho_0f e ρ 0 f , then the two edges have the same endpoint in B 0 B^0 B 0 , so R B [ e ] = R B [ f ] R_B[e]=R_B[f] R B [ e ] = R B [ f ] . Conversely, suppose that e = ( a , b ) e=(a,b) e = ( a , b ) and f = ( a ′ , b ′ ) f=(a',b') f = ( a ′ , b ′ ) satisfy R B [ e ] = R B [ f ] R_B[e]=R_B[f] R B [ e ] = R B [ f ] . By the preceding description of R B [ e ] R_B[e] R B [ e ] and the fact that every vertex lies on an edge, we have N B ( a ) = N B ( a ′ ) N_B(a)=N_B(a') N B ( a ) = N B ( a ′ ) . Since B B B is twin-free, a = a ′ a=a' a = a ′ , and hence e ρ 0 f e\rho_0f e ρ 0 f . Therefore, ≡ 0 \equiv_0 ≡ 0 is exactly ρ 0 \rho_0 ρ 0 . The same argument shows that ≡ 1 \equiv_1 ≡ 1 is exactly ρ 1 \rho_1 ρ 1 .
We next verify that R ( B ) ∈ G \mathcal{R}(B)\in\mathcal{G} R ( B ) ∈ G . If e ρ 0 f e\rho_0f e ρ 0 f and e ρ 1 f e\rho_1f e ρ 1 f , then e e e and f f f have both endpoints in common and therefore e = f e=f e = f . Hence ρ 0 ∩ ρ 1 \rho_0\cap\rho_1 ρ 0 ∩ ρ 1 is the diagonal relation, so R ( B ) \mathcal{R}(B) R ( B ) is thin.
For every edge e = ( a , b ) e=(a,b) e = ( a , b ) of B B B , we have e ρ 0 e e\rho_0e e ρ 0 e and e ρ 1 e e\rho_1e e ρ 1 e , so e R B e eR_Be e R B e . Hence R B R_B R B is reflexive.
If two edges share an endpoint in either B 0 B^0 B 0 or B 1 B^1 B 1 , then they are related by R B R_B R B . Since B B B is connected, any two of its edges can be joined by a sequence of edges in which consecutive edges share an endpoint. Consecutive edges in this sequence are related by R B R_B R B , so R B R_B R B is connected.
To verify rectangularity, let e = ( a , b ) e=(a,b) e = ( a , b ) and f = ( c , d ) f=(c,d) f = ( c , d ) . By (12) , if e R B f eR_Bf e R B f , then g = ( a , d ) g=(a,d) g = ( a , d ) is an edge satisfying g ρ 0 e g\rho_0e g ρ 0 e and g ρ 1 f g\rho_1f g ρ 1 f . Conversely, if an edge h h h satisfies h ρ 0 e h\rho_0e h ρ 0 e and h ρ 1 f h\rho_1f h ρ 1 f , then h = ( a , d ) h=(a,d) h = ( a , d ) and hence e R B f eR_Bf e R B f . Since ρ 0 \rho_0 ρ 0 and ρ 1 \rho_1 ρ 1 are the two equivalence relations from (10) , this is precisely rectangularity. Thus R ( B ) ∈ G \mathcal{R}(B)\in\mathcal{G} R ( B ) ∈ G , which proves part (i).
(ii). We first prove that R ( B ( X ) ) ≅ X \mathcal{R}(B(\mathcal{X}))\cong\mathcal{X} R ( B ( X )) ≅ X . Since X \mathcal{X} X is thin, the construction of B ( X ) B(\mathcal{X}) B ( X ) defines a bijection ι X \iota_{\mathcal{X}} ι X from X X X to E ( B ( X ) ) E(B(\mathcal{X})) E ( B ( X )) with ι X ( x ) = e x \iota_{\mathcal{X}}(x)=e_x ι X ( x ) = e x . In B ( X ) B(\mathcal{X}) B ( X ) , the edges e x e_x e x and e z e_z e z have the same endpoint in ( B ( X ) ) 0 (B(\mathcal{X}))^0 ( B ( X ) ) 0 if and only if z ≡ 0 x z\equiv_0x z ≡ 0 x , and e z e_z e z and e y e_y e y have the same endpoint in ( B ( X ) ) 1 (B(\mathcal{X}))^1 ( B ( X ) ) 1 if and only if z ≡ 1 y z\equiv_1y z ≡ 1 y . Therefore e x R B ( X ) e y e_xR_{B(\mathcal{X})}e_y e x R B ( X ) e y if and only if there is an element z ∈ X z\in X z ∈ X such that z ≡ 0 x z\equiv_0x z ≡ 0 x and z ≡ 1 y z\equiv_1y z ≡ 1 y . By rectangularity, e x R B ( X ) e y e_xR_{B(\mathcal{X})}e_y e x R B ( X ) e y if and only if x R y xRy x R y . Thus ι X \iota_{\mathcal{X}} ι X is a relation isomorphism from X \mathcal{X} X to R ( B ( X ) ) \mathcal{R}(B(\mathcal{X})) R ( B ( X )) .
We now prove that B ( X ) B(\mathcal{X}) B ( X ) is connected. Suppose first that x R y xRy x R y . By (11) , there is an element z ∈ X z\in X z ∈ X such that e x e_x e x and e z e_z e z share their endpoint in B ( X ) 0 B(\mathcal{X})^0 B ( X ) 0 , and e z e_z e z and e y e_y e y share their endpoint in B ( X ) 1 B(\mathcal{X})^1 B ( X ) 1 . Thus e x , e z , e y e_x,e_z,e_y e x , e z , e y , with consecutive repetitions removed, form a walk in the line graph of B ( X ) B(\mathcal{X}) B ( X ) . If y R x yRx y R x , the same argument produces a walk in the reverse direction. Since R R R is connected, any two elements x , y x,y x , y of X X X can be joined by a sequence x = x 0 , x 1 , … , x m = y x=x_0,x_1,\ldots,x_m=y x = x 0 , x 1 , … , x m = y such that, for every 0 ≤ i ≤ m − 1 0\leq i\leq m-1 0 ≤ i ≤ m − 1 , either x i R x i + 1 x_iRx_{i+1} x i R x i + 1 or x i + 1 R x i x_{i+1}Rx_i x i + 1 R x i . Replacing each step by the corresponding edge sequence gives a walk from e x e_x e x to e y e_y e y in the line graph of B ( X ) B(\mathcal{X}) B ( X ) . Hence the line graph of B ( X ) B(\mathcal{X}) B ( X ) is connected. Every vertex of B ( X ) B(\mathcal{X}) B ( X ) lies on an edge by construction, so B ( X ) B(\mathcal{X}) B ( X ) is connected.
We next prove that B ( X ) B(\mathcal{X}) B ( X ) is twin-free. Let ( [ x ] ≡ 0 , 0 ) ([x]_{\equiv_0},0) ([ x ] ≡ 0 , 0 ) be a vertex in ( B ( X ) ) 0 (B(\mathcal{X}))^0 ( B ( X ) ) 0 . By (11) , ( [ y ] ≡ 1 , 1 ) ([y]_{\equiv_1},1) ([ y ] ≡ 1 , 1 ) is adjacent to ( [ x ] ≡ 0 , 0 ) ([x]_{\equiv_0},0) ([ x ] ≡ 0 , 0 ) if and only if there is an element z ∈ X z\in X z ∈ X such that z ≡ 0 x z\equiv_0x z ≡ 0 x and z ≡ 1 y z\equiv_1y z ≡ 1 y , which is equivalent to x R y xRy x R y . The set R [ x ] R[x] R [ x ] is a union of ≡ 1 \equiv_1 ≡ 1 classes by the definition of ≡ 1 \equiv_1 ≡ 1 . Thus N B ( X ) ( ( [ x ] ≡ 0 , 0 ) ) = { ( [ y ] ≡ 1 , 1 ) : y ∈ R [ x ] } N_{B(\mathcal{X})}(([x]_{\equiv_0},0))=\{([y]_{\equiv_1},1):y\in R[x]\} N B ( X ) (([ x ] ≡ 0 , 0 )) = {([ y ] ≡ 1 , 1 ) : y ∈ R [ x ]} . If the neighbourhoods of two vertices in ( B ( X ) ) 0 (B(\mathcal{X}))^0 ( B ( X ) ) 0 are equal, then their ≡ 0 \equiv_0 ≡ 0 classes are equal. Similarly, $N_{B(\mathcal{X})}(([x]_{\equiv_1},1))={([y]_{\equiv_0},0): y ∈ R − 1 [ x ] y \in R^{-1}[x] y ∈ R − 1 [ x ] , and if the neighbourhoods of two vertices in ( B ( X ) ) 1 (B(\mathcal{X}))^{1} ( B ( X ) ) 1 are equal, then their ≡ 1 \equiv_{1} ≡ 1 classes are equal. Vertices in opposite colour classes also have different neighbourhoods, since these neighbourhoods are nonempty subsets of disjoint colour classes. Hence B ( X ) B(\mathcal{X}) B ( X ) is twin-free.
Suppose that f : X → Y f:\mathcal{X}\to\mathcal{Y} f : X → Y is a relation isomorphism. Then x R y xRy x R y if and only if f ( x ) Q f ( y ) f(x)Qf(y) f ( x ) Q f ( y ) . Consequently, for i = 0 , 1 i=0,1 i = 0 , 1 , the elements x , x ′ ∈ X x,x'\in X x , x ′ ∈ X satisfy x ≡ i R x ′ x\equiv^{R}_{i}x' x ≡ i R x ′ in X \mathcal{X} X if and only if f ( x ) , f ( x ′ ) f(x),f(x') f ( x ) , f ( x ′ ) satisfy f ( x ) ≡ i Q f ( x ′ ) f(x)\equiv^{Q}_{i}f(x') f ( x ) ≡ i Q f ( x ′ ) in Y \mathcal{Y} Y . For each i ∈ { 0 , 1 } i\in\{0,1\} i ∈ { 0 , 1 } , define the induced graph map f ^ : B ( X ) → B ( Y ) \widehat{f}:B(\mathcal{X})\to B(\mathcal{Y}) f : B ( X ) → B ( Y ) by
f ^ ( ( [ x ] ≡ i R , i ) ) = ( [ f ( x ) ] ≡ i Q , i ) . \widehat{f}(([x]_{\equiv^{R}_{i}},i))=([f(x)]_{\equiv^{Q}_{i}},i). f (([ x ] ≡ i R , i )) = ([ f ( x ) ] ≡ i Q , i ) .
where the equivalence class on each side is taken in its respective relation structure. This map is well defined and bijective. It maps the edge e x e_x e x to the edge e f ( x ) e_{f(x)} e f ( x ) , and so it is an isomorphism in B i p 2 \mathrm{Bip}_{2} Bip 2 . This completes part (ii).
(iii). An edge of B ⋆ C B\star C B ⋆ C is uniquely specified by a pair of edges, one of B B B and one of C C C , with endpoints paired by colour. Under this edge bijection, equality of a colour-i i i endpoint is exactly coordinatewise equality of colour-i i i endpoints. Moreover, the two witnesses for a composite relation can be chosen independently in the factors. Hence R B ⋆ C R_{B\star C} R B ⋆ C corresponds to R B × R C R_B\times R_C R B × R C , giving
R ( B ⋆ C ) ≅ R ( B ) × R ( C ) . (13) R(B\star C)\cong R(B)\times R(C). \tag*{(13)} R ( B ⋆ C ) ≅ R ( B ) × R ( C ) . (13)
By parts (i)–(ii) and Lemmas 2.2 –2.4 , this also shows that X × Y \mathcal{X}\times\mathcal{Y} X × Y belongs to G \mathcal{G} G .
All row and column neighbourhoods of the reflexive factors are nonempty. Projecting their Cartesian products gives, for i = 0 , 1 i=0,1 i = 0 , 1 ,
( x , y ) ≡ i R × Q ( x ′ , y ′ ) ⟺ x ≡ i R x ′ and y ≡ i Q y ′ . (x,y)\equiv^{R\times Q}_{i}(x',y')\Longleftrightarrow x\equiv^{R}_{i}x'\text{ and }y\equiv^{Q}_{i}y'. ( x , y ) ≡ i R × Q ( x ′ , y ′ ) ⟺ x ≡ i R x ′ and y ≡ i Q y ′ .
The resulting map on vertices is
( [ ( x , y ) ] ≡ i R × Q , i ) ⟼ ( [ x ] ≡ i R , i ) , ( [ y ] ≡ i Q , i ) . ([(x,y)]_{\equiv^{R\times Q}_{i}},i)\longmapsto([x]_{\equiv^{R}_{i}},i),([y]_{\equiv^{Q}_{i}},i). ([( x , y ) ] ≡ i R × Q , i ) ⟼ ([ x ] ≡ i R , i ) , ([ y ] ≡ i Q , i ) .
It is a bijection on each colour class and sends the edge indexed by ( x , y ) (x,y) ( x , y ) to the pair of edges indexed by x x x and y y y . Thus it preserves adjacency in both directions and proves
B ( X × Y ) ≅ B ( X ) ⋆ B ( Y ) . (14) B(\mathcal{X}\times\mathcal{Y})\cong B(\mathcal{X})\star B(\mathcal{Y}). \tag*{(14)} B ( X × Y ) ≅ B ( X ) ⋆ B ( Y ) . (14)
(iv) For a ∈ B 0 a\in B^{0} a ∈ B 0 , choose an edge e e e incident with a a a and define ϑ B ( a ) = ( [ e ] ρ 0 , 0 ) \vartheta_{B}(a)=([e]_{\rho_{0}},0) ϑ B ( a ) = ([ e ] ρ 0 , 0 ) . Since all edges incident with a a a belong to the same ρ 0 \rho_{0} ρ 0 class, this definition is independent of the choice of e e e . Similarly, for b ∈ B 1 b\in B^{1} b ∈ B 1 , choose an incident edge f f f and define ϑ B ( b ) = ( [ f ] ρ 1 , 1 ) \vartheta_{B}(b)=([f]_{\rho_{1}},1) ϑ B ( b ) = ([ f ] ρ 1 , 1 ) . This is likewise well defined. Part (i) shows that every ρ 0 \rho_{0} ρ 0 class consists exactly of the edges incident with one vertex of B 0 B^{0} B 0 , and every ρ 1 \rho_{1} ρ 1 class consists exactly of the edges incident with one vertex of B 1 B^{1} B 1 . Hence ϑ B \vartheta_{B} ϑ B is a bijection that preserves the two colour classes.
If e = ( a , b ) e=(a,b) e = ( a , b ) is an edge of B B B , then the edge of B ( R ( B ) ) B(\mathcal{R}(B)) B ( R ( B )) corresponding to the element e e e is ( ( [ e ] ρ 0 , 0 ) , ( [ e ] ρ 1 , 1 ) ) = ( ϑ B ( a ) , ϑ B ( b ) ) (([e]_{\rho_{0}},0),([e]_{\rho_{1}},1))=(\vartheta_{B}(a),\vartheta_{B}(b)) (([ e ] ρ 0 , 0 ) , ([ e ] ρ 1 , 1 )) = ( ϑ B ( a ) , ϑ B ( b )) . Conversely, every edge of B ( R ( B ) ) B(\mathcal{R}(B)) B ( R ( B )) arises from a unique edge e e e of B B B . Therefore ϑ B \vartheta_{B} ϑ B is an isomorphism from B B B to B ( R ( B ) ) B(\mathcal{R}(B)) B ( R ( B )) in B i p 2 \mathrm{Bip}_{2} Bip 2 . Together with X ≅ R ( B ( X ) ) \mathcal{X}\cong\mathcal{R}(B(\mathcal{X})) X ≅ R ( B ( X )) , Eqs. (13) and (14) , this shows that the two constructions are mutually inverse up to natural isomorphism and preserve products.
Lemma 2.8. Let X \mathcal{X} X and Y \mathcal{Y} Y be nonempty relation structures. If X × Y ∈ G \mathcal{X}\times\mathcal{Y}\in\mathcal{G} X × Y ∈ G , then X , Y ∈ G \mathcal{X},\mathcal{Y}\in\mathcal{G} X , Y ∈ G .
Proof. Write X = ( X , R ) \mathcal{X}=(X,R) X = ( X , R ) and Y = ( Y , Q ) \mathcal{Y}=(Y,Q) Y = ( Y , Q ) , where X , Y X,Y X , Y are nonempty. Since X × Y \mathcal{X}\times\mathcal{Y} X × Y is finite, both X X X and Y Y Y are finite. For x ∈ X x\in X x ∈ X and y ∈ Y y\in Y y ∈ Y , reflexivity of R × Q R\times Q R × Q gives ( x , y ) ( R × Q ) ( x , y ) (x,y)(R\times Q)(x,y) ( x , y ) ( R × Q ) ( x , y ) . Hence x R x xRx x R x and y Q y yQy y Q y , so both factors are reflexive.
To prove connectedness, take x , y ∈ X x,y\in X x , y ∈ X and fix z ∈ Y z\in Y z ∈ Y . Since R × Q R\times Q R × Q is connected, there is a sequence ( x , z ) = ( x 0 , z 0 ) , ( x 1 , z 1 ) , … , ( x m , z m ) = ( y , z ) (x,z)=(x_{0},z_{0}),(x_{1},z_{1}),\ldots,(x_{m},z_{m})=(y,z) ( x , z ) = ( x 0 , z 0 ) , ( x 1 , z 1 ) , … , ( x m , z m ) = ( y , z ) such that, for every 0 ≤ i ≤ m − 1 0\leq i\leq m-1 0 ≤ i ≤ m − 1 , either ( x i , z i ) ( R × Q ) ( x i + 1 , z i + 1 ) (x_{i},z_{i})(R\times Q)(x_{i+1},z_{i+1}) ( x i , z i ) ( R × Q ) ( x i + 1 , z i + 1 ) or ( x i , z i ) ( R × Q ) − 1 ( x i + 1 , z i + 1 ) (x_{i},z_{i})(R\times Q)^{-1}(x_{i+1},z_{i+1}) ( x i , z i ) ( R × Q ) − 1 ( x i + 1 , z i + 1 ) . Projecting onto the first coordinate gives a sequence x = x 0 , x 1 , … , x m = y x=x_{0},x_{1},\ldots,x_{m}=y x = x 0 , x 1 , … , x m = y such that, for every $0\leq i\leq m-1, either x i R x i + 1 x_iRx_{i+1} x i R x i + 1 or x i R − 1 x i + 1 x_iR^{-1}x_{i+1} x i R − 1 x i + 1 . Hence R R R is connected. The same argument shows that Q Q Q is connected.
Suppose that X \mathcal{X} X is not thin. There are distinct x , x ′ ∈ X x,x' \in X x , x ′ ∈ X for which R [ x ] = R [ x ′ ] R[x] = R[x'] R [ x ] = R [ x ′ ] and R − 1 [ x ] = R − 1 [ x ′ ] R^{-1}[x] = R^{-1}[x'] R − 1 [ x ] = R − 1 [ x ′ ] . Fix y ∈ Y y \in Y y ∈ Y . Then
( R × Q ) [ ( x , y ) ] = R [ x ] × Q [ y ] = R [ x ′ ] × Q [ y ] = ( R × Q ) [ ( x ′ , y ) ] , (R \times Q)[(x,y)] = R[x] \times Q[y] = R[x'] \times Q[y] = (R \times Q)[(x',y)], ( R × Q ) [( x , y )] = R [ x ] × Q [ y ] = R [ x ′ ] × Q [ y ] = ( R × Q ) [( x ′ , y )] ,
( R × Q ) − 1 [ ( x , y ) ] = R − 1 [ x ] × Q − 1 [ y ] = R − 1 [ x ′ ] × Q − 1 [ y ] = ( R × Q ) − 1 [ ( x ′ , y ) ] . (R \times Q)^{-1}[(x,y)] = R^{-1}[x] \times Q^{-1}[y] = R^{-1}[x'] \times Q^{-1}[y] = (R \times Q)^{-1}[(x',y)]. ( R × Q ) − 1 [( x , y )] = R − 1 [ x ] × Q − 1 [ y ] = R − 1 [ x ′ ] × Q − 1 [ y ] = ( R × Q ) − 1 [( x ′ , y )] .
This contradicts the fact that X × Y \mathcal{X} \times\mathcal{Y} X × Y is thin. Thus X \mathcal{X} X is thin. A similar argument shows that Y \mathcal{Y} Y is thin.
We prove rectangularity of R R R . Let x , x ′ ∈ X x,x' \in X x , x ′ ∈ X . If x R x ′ xRx' x R x ′ , fix y ∈ Y y \in Y y ∈ Y . Since y Q y yQy y Q y , we have ( x , y ) ( R × Q ) ( x ′ , y ) (x,y)(R \times Q)(x',y) ( x , y ) ( R × Q ) ( x ′ , y ) . Rectangularity of the product gives ( u , v ) ∈ X × Y (u,v) \in X \times Y ( u , v ) ∈ X × Y such that
R [ u ] × Q [ v ] = R [ x ] × Q [ y ] , R[u] \times Q[v] = R[x] \times Q[y], R [ u ] × Q [ v ] = R [ x ] × Q [ y ] ,
R − 1 [ u ] × Q − 1 [ v ] = R − 1 [ x ′ ] × Q − 1 [ y ] . R^{-1}[u] \times Q^{-1}[v] = R^{-1}[x'] \times Q^{-1}[y]. R − 1 [ u ] × Q − 1 [ v ] = R − 1 [ x ′ ] × Q − 1 [ y ] .
All four factor neighbourhoods are nonempty by reflexivity, so projection of these Cartesian products yields R [ u ] = R [ x ] R[u] = R[x] R [ u ] = R [ x ] and R − 1 [ u ] = R − 1 [ x ′ ] R^{-1}[u] = R^{-1}[x'] R − 1 [ u ] = R − 1 [ x ′ ] . Hence u ≡ R 0 x u \mathrel{\overset{R}{\equiv}_{0}} x u ≡ R 0 x and u ≡ R 1 x ′ u \mathrel{\overset{R}{\equiv}_{1}} x' u ≡ R 1 x ′ .
Conversely, suppose u ∈ X u \in X u ∈ X satisfies R [ u ] = R [ x ] R[u] = R[x] R [ u ] = R [ x ] and R − 1 [ u ] = R − 1 [ x ′ ] R^{-1}[u] = R^{-1}[x'] R − 1 [ u ] = R − 1 [ x ′ ] . Fix y ∈ Y y \in Y y ∈ Y . The identities
( R × Q ) [ ( u , y ) ] = ( R × Q ) [ ( x , y ) ] , ( R × Q ) − 1 [ ( u , y ) ] = ( R × Q ) − 1 [ ( x ′ , y ) ] (R \times Q)[(u,y)] = (R \times Q)[(x,y)], \qquad(R \times Q)^{-1}[(u,y)] = (R \times Q)^{-1}[(x',y)] ( R × Q ) [( u , y )] = ( R × Q ) [( x , y )] , ( R × Q ) − 1 [( u , y )] = ( R × Q ) − 1 [( x ′ , y )]
show that ( u , y ) ≡ R × Q 0 ( x , y ) (u,y) \mathrel{\overset{R \times Q}{\equiv}_{0}} (x,y) ( u , y ) ≡ R × Q 0 ( x , y ) and ( u , y ) ≡ R × Q 1 ( x ′ , y ) (u,y) \mathrel{\overset{R \times Q}{\equiv}_{1}} (x',y) ( u , y ) ≡ R × Q 1 ( x ′ , y ) in the product relation. Its rectangularity gives ( x , y ) ( R × Q ) ( x ′ , y ) (x,y)(R \times Q)(x',y) ( x , y ) ( R × Q ) ( x ′ , y ) , hence x R x ′ xRx' x R x ′ . This proves rectangularity of R R R , and the same argument proves rectangularity of Q Q Q . Thus both factors belong to G \mathcal{G} G . □
Corollary 2.9. Let B B B be a connected twin-free ordered bipartite graph. Then B B B is f f f -prime in B i p 2 \mathbf{Bip}_2 Bip 2 if and only if R ( B ) \mathcal{R}(B) R ( B ) is d d d -prime. Moreover, the one-element relation structure corresponds to K 2 K_2 K 2 .
Proof. If B ≅ K 2 B \cong K_2 B ≅ K 2 , then both B B B and R ( B ) \mathcal{R}(B) R ( B ) are units, and neither is prime. We may therefore assume that B B B is nonunit. Suppose first that B B B has a nontrivial factorization B ≅ X ⋆ Y B \cong X \star Y B ≅ X ⋆ Y with neither factor isomorphic to K 2 K_2 K 2 in B i p 2 \mathbf{Bip}_2 Bip 2 .
The surjective coordinate projections show that both factors are connected, and Lemma 2.4 shows that they are twin-free. By Lemma 2.7 (iii), R ( B ) ≅ R ( X ) × R ( Y ) \mathcal{R}(B) \cong\mathcal{R}(X) \times\mathcal{R}(Y) R ( B ) ≅ R ( X ) × R ( Y ) . Since R ( B ) ∈ G \mathcal{R}(B) \in\mathcal{G} R ( B ) ∈ G , Lemma 2.8 implies that R ( X ) , R ( Y ) ∈ G \mathcal{R}(X),\mathcal{R}(Y) \in\mathcal{G} R ( X ) , R ( Y ) ∈ G . The relation structure associated with a connected ordered graph has one element if and only if the graph is K 2 K_2 K 2 . Thus both relation factors are nonunit, and R ( B ) \mathcal{R}(B) R ( B ) is not d d d -prime.
Conversely, suppose that R ( B ) ≅ X × Y \mathcal{R}(B) \cong\mathcal{X} \times\mathcal{Y} R ( B ) ≅ X × Y with both X \mathcal{X} X and Y \mathcal{Y} Y nonunit. By Lemma 2.8 , X , Y ∈ G \mathcal{X},\mathcal{Y} \in\mathcal{G} X , Y ∈ G . Applying Lemma 2.7 , we obtain
B ≅ B ( R ( B ) ) ≅ B ( X × Y ) ≅ B ( X ) ⋆ B ( Y ) . B \cong\mathcal{B}(\mathcal{R}(B)) \cong\mathcal{B}(\mathcal{X} \times\mathcal{Y}) \cong\mathcal{B}(\mathcal{X}) \star\mathcal{B}(\mathcal{Y}). B ≅ B ( R ( B )) ≅ B ( X × Y ) ≅ B ( X ) ⋆ B ( Y ) . Since X \mathcal{X} X and Y \mathcal{Y} Y are nonunit, neither graph factor is K 2 K_2 K 2 . Thus B B B is not f f f -prime. This proves the equivalence. The one-element relation structure corresponds to K 2 K_2 K 2 by construction. □
Unique factorization for the fibre product over K 2 K_2 K 2
We now prove Theorems 1.3 , 1.4 , and 1.5 , beginning with unique factorization for relation structures.
Unique factorization of relation structures
The following result is a formulation of [18 Theorem 4.1] in terms of coordinate isomorphisms. For completeness, we state this formulation and derive it from the cited result.
Lemma 3.1. Let A \mathcal{A} A be a finite connected reflexive thin relation structure. Suppose r , s ≥ 1 r,s \ge1 r , s ≥ 1 and
α : A ⟶ ∏ i = 1 r A i , β : A ⟶ ∏ j = 1 s C j \alpha: \mathcal{A} \longrightarrow\prod_{i=1}^{r} \mathcal{A}_{i}, \qquad\beta: \mathcal{A} \longrightarrow\prod_{j=1}^{s} \mathcal{C}_{j} α : A ⟶ i = 1 ∏ r A i , β : A ⟶ j = 1 ∏ s C j are relation isomorphisms. Then there exist relation structures D i j \mathcal{D}_{ij} D ij (possibly units), relation isomorphisms
λ i : A i ⟶ ∏ j = 1 s D i j , μ j : C j ⟶ ∏ i = 1 r D i j , \lambda_i : \mathcal{A}_i \longrightarrow\prod_{j=1}^{s} \mathcal{D}_{ij}, \qquad\mu_j : \mathcal{C}_j \longrightarrow\prod_{i=1}^{r} \mathcal{D}_{ij}, λ i : A i ⟶ j = 1 ∏ s D ij , μ j : C j ⟶ i = 1 ∏ r D ij , and the canonical transposition of coordinates
τ : ∏ j = 1 s ∏ i = 1 r D i j ⟶ ∏ i = 1 r ∏ j = 1 s D i j \tau: \prod_{j=1}^{s}\prod_{i=1}^{r} \mathcal{D}_{ij} \longrightarrow\prod_{i=1}^{r}\prod_{j=1}^{s} \mathcal{D}_{ij} τ : j = 1 ∏ s i = 1 ∏ r D ij ⟶ i = 1 ∏ r j = 1 ∏ s D ij such that
( ∏ i = 1 r λ i ) ∘ α = τ ∘ ( ∏ j = 1 s μ j ) ∘ β . (15) \left(\prod_{i=1}^{r}\lambda_i\right) \circ\alpha= \tau\circ\left(\prod_{j=1}^{s}\mu_j\right) \circ\beta. \tag*{(15)} ( i = 1 ∏ r λ i ) ∘ α = τ ∘ ( j = 1 ∏ s μ j ) ∘ β . (15)
Proof. Let A = ( A , R ) \mathcal{A}=(A,R) A = ( A , R ) . For 1 ≤ i ≤ r 1\leq i\leq r 1 ≤ i ≤ r and 1 ≤ j ≤ s 1\leq j\leq s 1 ≤ j ≤ s , let p i p_i p i denote the i i i -th projection from ∏ t = 1 r A t \prod_{t=1}^{r} A_t ∏ t = 1 r A t to A i A_i A i , and let q j q_j q j denote the j j j -th projection from ∏ t = 1 s C t \prod_{t=1}^{s} C_t ∏ t = 1 s C t to C j C_j C j . For 1 ≤ i ≤ r 1\leq i\leq r 1 ≤ i ≤ r and 1 ≤ j ≤ s 1\leq j\leq s 1 ≤ j ≤ s , we define equivalence relations E i E_i E i and F j F_j F j on A A A by
a E i b ⟺ p i ( α ( a ) ) = p i ( α ( b ) ) , aE_i b \Longleftrightarrow p_i(\alpha(a))=p_i(\alpha(b)), a E i b ⟺ p i ( α ( a )) = p i ( α ( b )) ,
a F j b ⟺ q j ( β ( a ) ) = q j ( β ( b ) ) . aF_j b \Longleftrightarrow q_j(\beta(a))=q_j(\beta(b)). a F j b ⟺ q j ( β ( a )) = q j ( β ( b )) .
For each 1 ≤ i ≤ r 1\leq i\leq r 1 ≤ i ≤ r , define the quotient structure A / E i \mathcal{A}/E_i A / E i on the set of E i E_i E i classes by
[ a ] E i R i ‾ [ b ] E i ⟺ p i ( α ( a ) ) R i p i ( α ( b ) ) , [a]_{E_i}\,\overline{R_i}\,[b]_{E_i} \Longleftrightarrow p_i(\alpha(a))\,R_i\,p_i(\alpha(b)), [ a ] E i R i [ b ] E i ⟺ p i ( α ( a )) R i p i ( α ( b )) ,
where R i R_i R i is the relation of A i \mathcal{A}_i A i . For every 1 ≤ i ≤ r 1\leq i\leq r 1 ≤ i ≤ r , define a map α i ‾ \overline{\alpha_i} α i from A / E i \mathcal{A}/E_i A / E i to A i \mathcal{A}_i A i by α i ‾ ( [ a ] E i ) = p i ( α ( a ) ) \overline{\alpha_i}([a]_{E_i})=p_i(\alpha(a)) α i ([ a ] E i ) = p i ( α ( a )) for [ a ] E i ∈ A / E i [a]_{E_i}\in\mathcal{A}/E_i [ a ] E i ∈ A / E i . Since α \alpha α and p i p_i p i are surjective, the map α i ‾ \overline{\alpha_i} α i is surjective. For any elements [ a ] E i , [ b ] E i ∈ A / E i [a]_{E_i},[b]_{E_i}\in\mathcal{A}/E_i [ a ] E i , [ b ] E i ∈ A / E i , α i ‾ ( [ a ] E i ) = α i ‾ ( [ b ] E i ) \overline{\alpha_i}([a]_{E_i})=\overline{\alpha_i}([b]_{E_i}) α i ([ a ] E i ) = α i ([ b ] E i ) if and only if p i ( α ( a ) ) = p i ( α ( b ) ) p_i(\alpha(a))=p_i(\alpha(b)) p i ( α ( a )) = p i ( α ( b )) . The latter equality holds if and only if a E i b aE_i b a E i b , equivalently, [ a ] E i = [ b ] E i [a]_{E_i}=[b]_{E_i} [ a ] E i = [ b ] E i . Hence α i ‾ \overline{\alpha_i} α i is injective and therefore bijective. The definition of R i ‾ \overline{R_i} R i shows that α i ‾ \overline{\alpha_i} α i is a relation isomorphism. Similarly, we construct a relation isomorphism β j ‾ \overline{\beta_j} β j from A / F j \mathcal{A}/F_j A / F j to C j \mathcal{C}_j C j such that β j ‾ ( [ a ] F j ) = q j ( β ( a ) ) \overline{\beta_j}([a]_{F_j})=q_j(\beta(a)) β j ([ a ] F j ) = q j ( β ( a )) for 1 ≤ j ≤ s 1\leq j\leq s 1 ≤ j ≤ s .
Since R R R is reflexive, both R ∘ R − 1 R\circ R^{-1} R ∘ R − 1 and R − 1 ∘ R R^{-1}\circ R R − 1 ∘ R contain R ∪ R − 1 R\cup R^{-1} R ∪ R − 1 . Thus both compositions are connected whenever R R R is connected. By Definition 2.6 , A \mathcal{A} A is thin. Therefore McKenzie’s theorem [18 Theorem 4.1] applies and gives the strict refinement property for factor relations.
Applying this property to ( E i ) 1 ≤ i ≤ r (E_i)_{1\leq i\leq r} ( E i ) 1 ≤ i ≤ r and ( F j ) 1 ≤ j ≤ s (F_j)_{1\leq j\leq s} ( F j ) 1 ≤ j ≤ s , we obtain an r × s r\times s r × s array of factor relations E i j E_{ij} E ij with 1 ≤ i ≤ r 1\leq i\leq r 1 ≤ i ≤ r and 1 ≤ j ≤ s 1\leq j\leq s 1 ≤ j ≤ s such that
E i = ⋂ j = 1 s E i j , F j = ⋂ i = 1 r E i j , E_i=\bigcap_{j=1}^{s}E_{ij}, \qquad F_j=\bigcap_{i=1}^{r}E_{ij}, E i = j = 1 ⋂ s E ij , F j = i = 1 ⋂ r E ij ,
and the natural maps
ξ i : A / E i ⟶ ∏ j = 1 s A / E i j , [ a ] E i ⟼ ( [ a ] E i 1 , … , [ a ] E i s ) , \xi_i:\mathcal{A}/E_i\longrightarrow\prod_{j=1}^{s}\mathcal{A}/E_{ij}, \qquad[a]_{E_i}\longmapsto([a]_{E_{i1}},\ldots,[a]_{E_{is}}), ξ i : A / E i ⟶ j = 1 ∏ s A / E ij , [ a ] E i ⟼ ([ a ] E i 1 , … , [ a ] E i s ) ,
ζ j : A / F j ⟶ ∏ i = 1 r A / E i j , [ a ] F j ⟼ ( [ a ] E 1 j , … , [ a ] E r j ) \zeta_j:\mathcal{A}/F_j\longrightarrow\prod_{i=1}^{r}\mathcal{A}/E_{ij}, \qquad[a]_{F_j}\longmapsto([a]_{E_{1j}},\ldots,[a]_{E_{rj}}) ζ j : A / F j ⟶ i = 1 ∏ r A / E ij , [ a ] F j ⟼ ([ a ] E 1 j , … , [ a ] E r j )
are relation isomorphisms for 1 ≤ i ≤ r 1 \le i \le r 1 ≤ i ≤ r and 1 ≤ j ≤ s 1 \le j \le s 1 ≤ j ≤ s . For each pair ( i , j ) (i,j) ( i , j ) , let D i j = A / E i j \mathcal{D}_{ij} = \mathcal{A}/E_{ij} D ij = A / E ij . Define the maps
λ i = ξ i ∘ α ˉ i − 1 : A i ⟶ ∏ j = 1 s D i j \lambda_i = \xi_i \circ\bar{\alpha}_i^{-1} : A_i \longrightarrow\prod_{j=1}^{s} \mathcal{D}_{ij} λ i = ξ i ∘ α ˉ i − 1 : A i ⟶ j = 1 ∏ s D ij
and
μ j = ζ j ∘ β ˉ j − 1 : C j ⟶ ∏ i = 1 r D i j . \mu_j = \zeta_j \circ\bar{\beta}_j^{-1} : C_j \longrightarrow\prod_{i=1}^{r} \mathcal{D}_{ij}. μ j = ζ j ∘ β ˉ j − 1 : C j ⟶ i = 1 ∏ r D ij .
Since ξ i \xi_i ξ i and α ˉ i − 1 \bar{\alpha}_i^{-1} α ˉ i − 1 are relation isomorphisms, λ i \lambda_i λ i is also a relation isomorphism. Similarly, μ j \mu_j μ j is a relation isomorphism. For every a ∈ A a \in A a ∈ A , these maps satisfy
λ i ( p i ( α ( a ) ) ) = ( [ a ] E i 1 , … , [ a ] E i s ) , μ j ( q j ( β ( a ) ) ) = ( [ a ] E 1 j , … , [ a ] E r j ) . \lambda_i\bigl(p_i(\alpha(a))\bigr) = \bigl([a]_{E_{i1}},\ldots,[a]_{E_{is}}\bigr), \qquad\mu_j\bigl(q_j(\beta(a))\bigr) = \bigl([a]_{E_{1j}},\ldots,[a]_{E_{rj}}\bigr). λ i ( p i ( α ( a )) ) = ( [ a ] E i 1 , … , [ a ] E i s ) , μ j ( q j ( β ( a )) ) = ( [ a ] E 1 j , … , [ a ] E r j ) .
The maps λ i \lambda_i λ i and μ j \mu_j μ j are relation isomorphisms as compositions of relation isomorphisms. For every a ∈ A a \in A a ∈ A , the j j j -th coordinate of λ i ( p i ( α ( a ) ) ) \lambda_i(p_i(\alpha(a))) λ i ( p i ( α ( a ))) and the i i i -th coordinate of μ j ( q j ( β ( a ) ) ) \mu_j(q_j(\beta(a))) μ j ( q j ( β ( a ))) are both [ a ] E i j [a]_{E_{ij}} [ a ] E ij . After the transposition τ \tau τ , the two sides of Eq. (15) therefore agree in every coordinate. This proves the asserted compatibility for the given maps α \alpha α and β \beta β . □
Remark 3.2. In Lemma 3.1 , a universal factor equivalence E i j E_{ij} E ij gives the one-element reflexive quotient. Such unit entries can be omitted from the displayed row and column products.
Let A \mathcal{A} A be a finite connected reflexive thin relation structure. For a rectangular array ( D i j ) (\mathcal{D}_{ij}) ( D ij ) obtained in Lemma 3.1 , the family ( D i j ) 1 ≤ j ≤ s (\mathcal{D}_{ij})_{1\le j\le s} ( D ij ) 1 ≤ j ≤ s with i i i fixed is the i i i -th row, and ∏ j = 1 s D i j \prod_{j=1}^{s}\mathcal{D}_{ij} ∏ j = 1 s D ij is its row product . Similarly, the family ( D i j ) 1 ≤ i ≤ r (\mathcal{D}_{ij})_{1\le i\le r} ( D ij ) 1 ≤ i ≤ r with j j j fixed is the j j j -th column , and ∏ i = 1 r D i j \prod_{i=1}^{r}\mathcal{D}_{ij} ∏ i = 1 r D ij is its column product .
Prime factorization of ordered bipartite graphs
We now apply the preceding results to prove Theorem 1.3 .
Proof of Theorem 1.3 . If B ≅ K 2 B \cong K_2 B ≅ K 2 , every displayed factor is connected by surjectivity of its projection. Since the number of edges of a fibre product is the product of the factor edge counts, each displayed factor has one edge and is K 2 K_2 K 2 . For part (i), take S = ∅ S = \varnothing S = ∅ and all indexed parts empty. For part (ii), a decomposition into nonunit factors must be empty, so r = s = 0 r = s = 0 r = s = 0 . We may assume B B B nonunit, which forces r , s ≥ 1 r,s \ge1 r , s ≥ 1 .
(i). Fix the two factorization isomorphisms. For each 1 ≤ i ≤ r 1 \le i \le r 1 ≤ i ≤ r and 1 ≤ j ≤ s 1 \le j \le s 1 ≤ j ≤ s , let p i p_i p i and q j q_j q j be the coordinate projections from B B B to G i G_i G i and H j H_j H j , respectively. Since p i p_i p i and q j q_j q j are surjective, all G i G_i G i and H j H_j H j are connected. Repeated application of Lemma 2.4 shows that every G i G_i G i and H j H_j H j is twin-free. Let A = R ( B ) \mathcal{A} = \mathcal{R}(B) A = R ( B ) . By Lemma 2.7 (iii), R ( B ) ≅ R ( G 1 ) × ⋯ × R ( G r ) ≅ R ( H 1 ) × ⋯ × R ( H s ) \mathcal{R}(B) \cong\mathcal{R}(G_1) \times\cdots\times\mathcal{R}(G_r) \cong\mathcal{R}(H_1) \times\cdots\times\mathcal{R}(H_s) R ( B ) ≅ R ( G 1 ) × ⋯ × R ( G r ) ≅ R ( H 1 ) × ⋯ × R ( H s ) . Choose isomorphisms
α : A ⟶ ∏ i = 1 r R ( G i ) , β : A ⟶ ∏ j = 1 s R ( H j ) . \alpha: \mathcal{A} \longrightarrow\prod_{i=1}^{r}\mathcal{R}(G_i), \qquad\beta: \mathcal{A} \longrightarrow\prod_{j=1}^{s}\mathcal{R}(H_j). α : A ⟶ i = 1 ∏ r R ( G i ) , β : A ⟶ j = 1 ∏ s R ( H j ) .
Applying Lemma 3.1 , we obtain an r × s r \times s r × s array ( D i j ) (\mathcal{D}_{ij}) ( D ij ) such that
R ( G i ) ≅ ∏ j = 1 s D i j , R ( H j ) ≅ ∏ i = 1 r D i j . (16) \mathcal{R}(G_i) \cong\prod_{j=1}^{s}\mathcal{D}_{ij}, \qquad\mathcal{R}(H_j) \cong\prod_{i=1}^{r}\mathcal{D}_{ij}. \tag*{(16)} R ( G i ) ≅ j = 1 ∏ s D ij , R ( H j ) ≅ i = 1 ∏ r D ij . (16)
Moreover, A ≅ ∏ i = 1 r ∏ j = 1 s D i j ≅ ∏ j = 1 s ∏ i = 1 r D i j \mathcal{A} \cong\prod_{i=1}^{r}\prod_{j=1}^{s}\mathcal{D}_{ij} \cong\prod_{j=1}^{s}\prod_{i=1}^{r}\mathcal{D}_{ij} A ≅ ∏ i = 1 r ∏ j = 1 s D ij ≅ ∏ j = 1 s ∏ i = 1 r D ij . Since the i i i -th row product in (16) is isomorphic to R ( G i ) ∈ G \mathcal{R}(G_i) \in\mathcal{G} R ( G i ) ∈ G , repeated application of Lemma 2.8 shows that each entry D i j \mathcal{D}_{ij} D ij belongs to G \mathcal{G} G .
We next factor each nonunit D i j \mathcal{D}_{ij} D ij into d d d -prime factors. In a nontrivial direct product factorization of a finite relation structure, each nonunit factor has strictly fewer elements than the relation structure. Repeated factorization must terminate and yields a factorization of each row product R ( G i ) \mathcal{R}(G_i) R ( G i ) into d d d -prime factors. Repeated application of Lemma 2.8 ensures that every factor belongs to B \mathcal{B} B .
Index the d d d -prime nonunit factors of all D i j \mathcal{D}_{ij} D ij , for $1 \leq i \leq r, 1 \leq j \leq s$, as T λ \mathcal{T}_{\lambda} T λ with λ ∈ S \lambda\in S λ ∈ S . Each indexed occurrence T λ \mathcal{T}_{\lambda} T λ arises from a unique entry D i j \mathcal{D}_{ij} D ij . Let U i U_i U i be the set of indices arising from row i i i , and define V j V_j V j analogously for column j j j . Since every D i j \mathcal{D}_{ij} D ij belongs to one row and one column, the indexed families { U i : 1 ≤ i ≤ r } \{U_i: 1 \leq i \leq r\} { U i : 1 ≤ i ≤ r } and { V j : 1 ≤ j ≤ s } \{V_j: 1 \leq j \leq s\} { V j : 1 ≤ j ≤ s } both partition S S S , with empty parts allowed.
Define B λ = B ( T λ ) B_{\lambda} = \mathrm{B}(\mathcal{T}_{\lambda}) B λ = B ( T λ ) . Lemma 2.7 shows that each B λ B_{\lambda} B λ is connected and twin-free. Corollary 2.9 shows that each is f f f -prime. Applying B \mathrm{B} B to the row products, column products, and the product of all D i j \mathcal{D}_{ij} D ij , and using Lemma 2.7 (iii) and (iv), we obtain
G i ≅ ⋆ λ ∈ U i B λ , H j ≅ ⋆ λ ∈ V j B λ , B ≅ ⋆ λ ∈ S B λ . G_i \cong\mathop{\star}_{\lambda\in U_i} B_{\lambda}, \qquad H_j \cong\mathop{\star}_{\lambda\in V_j} B_{\lambda}, \qquad B \cong\mathop{\star}_{\lambda\in S} B_{\lambda}. G i ≅ ⋆ λ ∈ U i B λ , H j ≅ ⋆ λ ∈ V j B λ , B ≅ ⋆ λ ∈ S B λ .
This proves part (i).
(ii). Assume that all G i G_i G i and H j H_j H j are f f f -prime for 1 ≤ i ≤ r 1 \leq i \leq r 1 ≤ i ≤ r and 1 ≤ j ≤ s 1 \leq j \leq s 1 ≤ j ≤ s . Then every row product R ( G i ) \mathcal{R}(G_i) R ( G i ) in (16) is d d d -prime and nonunit by Corollary 2.9 . Therefore its row contains exactly one nonunit entry (since two nonunit entries would give a nontrivial factorization of the row product). By the same argument, every column contains exactly one nonunit entry.
Consequently, matching each row to the column containing its nonunit entry defines a bijection between the rows and columns. Thus r = s r = s r = s . Let σ ( i ) \sigma(i) σ ( i ) be the unique column containing the nonunit entry in row i i i . By the row and column isomorphisms in (16) , we have
R ( G i ) ≅ D i , σ ( i ) ≅ R ( H σ ( i ) ) . \mathcal{R}(G_i) \cong\mathcal{D}_{i,\sigma(i)} \cong\mathcal{R}(H_{\sigma(i)}). R ( G i ) ≅ D i , σ ( i ) ≅ R ( H σ ( i ) ) .
where D i , σ ( i ) \mathcal{D}_{i,\sigma(i)} D i , σ ( i ) is the unique nonunit entry in row i i i , corresponding to j = σ ( i ) j = \sigma(i) j = σ ( i ) . By Lemma 2.7 , G i ≅ H σ ( i ) G_i \cong H_{\sigma(i)} G i ≅ H σ ( i ) in B i p 2 \mathrm{Bip}_2 Bip 2 . This proves part (ii) and the uniqueness statement. □ \square □
Coordinate isomorphisms and colour signs
We next prove Theorems 1.4 and 1.5 .
Proof of Theorem 1.4 . Since B i B_i B i and C j C_j C j , for 1 ≤ i ≤ r 1 \leq i \leq r 1 ≤ i ≤ r and 1 ≤ j ≤ s 1 \leq j \leq s 1 ≤ j ≤ s , are nonunit factors, both B B B and C C C are nonunit. By Lemma 2.7 (iii), we have the natural isomorphisms
η B : R ( B ) ⟶ ∏ i = 1 r R ( B i ) , η C : R ( C ) ⟶ ∏ j = 1 s R ( C j ) . \eta_B : \mathcal{R}(B) \longrightarrow\prod_{i=1}^{r} \mathcal{R}(B_i), \qquad\eta_C : \mathcal{R}(C) \longrightarrow\prod_{j=1}^{s} \mathcal{R}(C_j). η B : R ( B ) ⟶ i = 1 ∏ r R ( B i ) , η C : R ( C ) ⟶ j = 1 ∏ s R ( C j ) .
The graph isomorphism φ \varphi φ maps an edge e = { x , y } e = \{x,y\} e = { x , y } of B B B to the edge φ ( e ) = { φ ( x ) , φ ( y ) } \varphi(e) = \{\varphi(x),\varphi(y)\} φ ( e ) = { φ ( x ) , φ ( y )} of C C C . Since φ \varphi φ preserves the two colour classes, it maps each endpoint in B 0 B^0 B 0 to an endpoint in C 0 C^0 C 0 and each endpoint in B 1 B^1 B 1 to an endpoint in C 1 C^1 C 1 . Hence it induces a relation isomorphism Φ \Phi Φ from R ( B ) \mathcal{R}(B) R ( B ) to R ( C ) \mathcal{R}(C) R ( C ) .
Applying Lemma 3.1 to the two coordinatizations α = η B \alpha= \eta_B α = η B and β = η C ∘ Φ \beta= \eta_C \circ\Phi β = η C ∘ Φ of R ( B ) \mathcal{R}(B) R ( B ) , we obtain relation structures D i j \mathcal{D}_{ij} D ij satisfying
R ( B i ) ≅ ∏ j = 1 s D i j , R ( C j ) ≅ ∏ i = 1 r D i j . \mathcal{R}(B_i) \cong\prod_{j=1}^{s} \mathcal{D}_{ij}, \qquad\mathcal{R}(C_j) \cong\prod_{i=1}^{r} \mathcal{D}_{ij}. R ( B i ) ≅ j = 1 ∏ s D ij , R ( C j ) ≅ i = 1 ∏ r D ij .
By Corollary 2.9 , every row product ∏ j = 1 s D i j \prod_{j=1}^{s} \mathcal{D}_{ij} ∏ j = 1 s D ij and every column product ∏ i = 1 r D i j \prod_{i=1}^{r} \mathcal{D}_{ij} ∏ i = 1 r D ij is d d d -prime and nonunit. As shown in the proof of Theorem 1.3 , each row and column contains exactly one nonunit entry. It follows that r = s r = s r = s , and there is a permutation σ ∈ S r \sigma\in S_r σ ∈ S r such that the unique nonunit entry in row i i i is D i , σ ( i ) \mathcal{D}_{i,\sigma(i)} D i , σ ( i ) .
After deleting all unit coordinates, the row and column isomorphisms in Lemma 3.1 become
λ i : R ( B i ) ⟶ D i , σ ( i ) , μ σ ( i ) : R ( C σ ( i ) ) ⟶ D i , σ ( i ) . \lambda_i : \mathcal{R}(B_i) \longrightarrow\mathcal{D}_{i,\sigma(i)}, \qquad\mu_{\sigma(i)} : \mathcal{R}(C_{\sigma(i)}) \longrightarrow\mathcal{D}_{i,\sigma(i)}. λ i : R ( B i ) ⟶ D i , σ ( i ) , μ σ ( i ) : R ( C σ ( i ) ) ⟶ D i , σ ( i ) .
Define
Φ i = μ σ ( i ) − 1 ∘ λ i : R ( B i ) ⟶ R ( C σ ( i ) ) . \Phi_i = \mu_{\sigma(i)}^{-1} \circ\lambda_i : \mathcal{R}(B_i) \longrightarrow\mathcal{R}(C_{\sigma(i)}). Φ i = μ σ ( i ) − 1 ∘ λ i : R ( B i ) ⟶ R ( C σ ( i ) ) .
Let p i : ∏ h = 1 r R ( B h ) → R ( B i ) p_i : \prod_{h=1}^{r} \mathcal{R}(B_h) \to\mathcal{R}(B_i) p i : ∏ h = 1 r R ( B h ) → R ( B i ) and q j : ∏ h = 1 r R ( C h ) → R ( C j ) q_j : \prod_{h=1}^{r} \mathcal{R}(C_h) \to\mathcal{R}(C_j) q j : ∏ h = 1 r R ( C h ) → R ( C j ) denote the source and target coordinate projections, respectively. Combining this with Eq. (15) , we have
q σ ( i ) ∘ η C ∘ Φ = Φ i ∘ p i ∘ η B . (17) q_{\sigma(i)} \circ\eta_C \circ\Phi= \Phi_i \circ p_i \circ\eta_B. \tag*{(17)} q σ ( i ) ∘ η C ∘ Φ = Φ i ∘ p i ∘ η B . (17)
Thus the σ ( i ) \sigma(i) σ ( i ) -th edge coordinate of Φ ( e ) \Phi(e) Φ ( e ) is obtained by applying the fixed relation isomorphism Φ i \Phi_i Φ i to the i i i -th edge coordinate of e e e .
By Lemma 2.7 (ii), the relation isomorphism Φ i \Phi_i Φ i induces a unique graph isomorphism φ i \varphi_i φ i from B i B_i B i to C σ ( i ) C_{\sigma(i)} C σ ( i ) , which preserves the ordered bipartition. We now show that these factor maps also determine the vertex coordinates of φ \varphi φ .
Fix a vertex b = ( b 1 , … , b r ) ∈ V ( B ) \mathbf{b} = (b_1, \ldots, b_r) \in V(B) b = ( b 1 , … , b r ) ∈ V ( B ) . Since B B B is connected and has an edge, b \mathbf{b} b has a neighbour. Choose an incident edge e = ( e 1 , … , e r ) \mathbf{e} = (e_1, \ldots, e_r) e = ( e 1 , … , e r ) , where e i e_i e i is an edge of B i B_i B i incident with b i b_i b i . The edge Φ ( e ) \Phi(\mathbf{e}) Φ ( e ) is incident with φ ( b ) \varphi(\mathbf{b}) φ ( b ) . By Eq. (17) , the σ ( i ) \sigma(i) σ ( i ) -th edge coordinate of Φ ( e ) \Phi(\mathbf{e}) Φ ( e ) is Φ i ( e i ) \Phi_i(e_i) Φ i ( e i ) . The graph isomorphism induced by Φ i \Phi_i Φ i sends the endpoint b i b_i b i of e i e_i e i to the endpoint φ i ( b i ) \varphi_i(b_i) φ i ( b i ) of Φ i ( e i ) \Phi_i(e_i) Φ i ( e i ) having the same colour. Since φ \varphi φ preserves the global colour, these endpoints are the coordinates of φ ( b ) \varphi(\mathbf{b}) φ ( b ) . Therefore, if φ ( b ) = ( c 1 , … , c r ) \varphi(\mathbf{b}) = (c_1, \ldots, c_r) φ ( b ) = ( c 1 , … , c r ) , then c σ ( i ) = φ i ( b i ) c_{\sigma(i)} = \varphi_i(b_i) c σ ( i ) = φ i ( b i ) for every i i i , proving Eq. (2) . This completes the proof. □
Proof of Theorem 1.5. Since B B B and C C C are connected bipartite graphs, their bipartitions are unique up to interchange. Thus there is a unique δ ∈ F 2 \delta\in\mathbb{F}_2 δ ∈ F 2 such that for every b ∈ V ( B ) \mathbf{b} \in V(B) b ∈ V ( B )
ϱ C ( φ ( b ) ) = ϱ B ( b ) + δ . (18) \varrho_C(\varphi(\mathbf{b})) = \varrho_B(\mathbf{b}) + \delta. \tag*{(18)} ϱ C ( φ ( b )) = ϱ B ( b ) + δ . (18)
Both B B B and C C C are nonunit by the assumed nonunit factorizations. We use the fixed factorizations to identify their vertices with compatible coordinate tuples. If δ = 0 \delta= 0 δ = 0 , then by Eq. (18) , φ \varphi φ is an isomorphism from B B B to C C C in B i p 2 \mathbf{Bip}_2 Bip 2 . By Theorem 1.4 , r = s r = s r = s and there are a permutation σ \sigma σ and factor isomorphisms that preserve colours and satisfy the coordinate formula. These maps satisfy Eqs. (3) and (4) with δ = 0 \delta= 0 δ = 0 .
Now assume δ = 1 \delta= 1 δ = 1 . Regard φ \varphi φ as a map into C o p C^{\mathrm{op}} C op . Its colour map is ϱ C o p = ϱ C + 1 \varrho_{C^{\mathrm{op}}} = \varrho_C + 1 ϱ C op = ϱ C + 1 , so Eq. (18) becomes ϱ C o p ( φ ( b ) ) = ϱ B ( b ) \varrho_{C^{\mathrm{op}}}(\varphi(\mathbf{b})) = \varrho_B(\mathbf{b}) ϱ C op ( φ ( b )) = ϱ B ( b ) . Thus φ : B → C o p \varphi: B \to C^{\mathrm{op}} φ : B → C op is an isomorphism in B i p 2 \mathbf{Bip}_2 Bip 2 . Since reversing every factor colouring reverses the global colouring, we have the following isomorphism in B i p 2 \mathbf{Bip}_2 Bip 2 ,
C o p ≅ C 1 o p ⋆ ⋯ ⋆ C s o p in B i p 2 . (19) C^{\mathrm{op}} \cong C_1^{\mathrm{op}} \star\cdots\star C_s^{\mathrm{op}} \quad\text{in } \mathbf{Bip}_2. \tag*{(19)} C op ≅ C 1 op ⋆ ⋯ ⋆ C s op in Bip 2 . (19)
Reversing all factor colours in a nontrivial factorization of C o p C^{\mathrm{op}} C op produces a nontrivial factorization of C j C_j C j . Since C j C_j C j is f f f -prime, each C j o p C_j^{\mathrm{op}} C j op is also f f f -prime for 1 ≤ j ≤ s 1 \leq j \leq s 1 ≤ j ≤ s .
By Theorem 1.4 and the decomposition (19) , we obtain r = s r = s r = s , a permutation σ ∈ S r \sigma\in S_r σ ∈ S r , and isomorphisms φ i : B i ⟶ C σ ( i ) o p \varphi_i : B_i \longrightarrow C_{\sigma(i)}^{\mathrm{op}} φ i : B i ⟶ C σ ( i ) op that preserve colours. Viewed as ordinary isomorphisms into C σ ( i ) C_{\sigma(i)} C σ ( i ) , these maps interchange the two colour classes and hence satisfy Eq. (3) with δ = 1 \delta= 1 δ = 1 . The coordinate formula (4) follows from Theorem 1.4 .
The sign δ \delta δ is unique since it is determined by the ordinary isomorphism φ \varphi φ in Eq. (18) . This completes the proof. □
The following example illustrates Theorem 1.5 .
Example 3.3. Let P P P and Q Q Q be nonisomorphic connected twin-free nonunit f f f -prime ordered bipartite graphs. Let B = P ⋆ Q B = P \star Q B = P ⋆ Q and C = Q ⋆ P C = Q \star P C = Q ⋆ P . The coordinate transposition ( p , q ) ↦ ( q , p ) (p,q) \mapsto(q,p) ( p , q ) ↦ ( q , p ) is an isomorphism in B i p 2 \mathbf{Bip}_2 Bip 2 . The permutation in Theorem 1.5 interchanges the two positions (the factor P P P of B B B corresponds to the second factor of C C C , and the factor Q Q Q corresponds to the first).
The identity map on vertices is also an ordinary isomorphism U ( B ) ⟶ U ( B o p ) \mathrm{U}(B) \longrightarrow\mathrm{U}(B^{\mathrm{op}}) U ( B ) ⟶ U ( B op ) with global sign 1 1 1 . Since B o p ≅ P o p ⋆ Q o p B^{\mathrm{op}} \cong P^{\mathrm{op}} \star Q^{\mathrm{op}} B op ≅ P op ⋆ Q op , both factor maps reverse their bipartitions. If one factor map preserves colours and another reverses them, the resulting coordinate map does not preserve the condition that all coordinates have the same colour. This explains why all factor maps must have the same sign in Theorem 1.5 .
We conclude this section with an application of Theorem 1.5 .
Corollary 3.4. Let B 1 , … , B r B_1,\ldots,B_r B 1 , … , B r and C 1 , … , C s C_1,\ldots,C_s C 1 , … , C s be connected twin-free nonunit f f f -prime ordered bipartite graphs, where r , s ≥ 1 r,s\ge1 r , s ≥ 1 . For ϵ ∈ F 2 s \epsilon\in\mathbb{F}_2^s ϵ ∈ F 2 s and η ∈ F 2 s \eta\in\mathbb{F}_2^s η ∈ F 2 s , write Ω ϵ B = ∪ ⋅ ( B 1 ( ϵ 1 ) ⋆ ⋯ ⋆ B r ( ϵ r ) ) \Omega^B_{\epsilon}=\mathop{\mathop{\cup}\limits^{\cdot}}(B_1^{(\epsilon_1)}\star\cdots\star B_r^{(\epsilon_r)}) Ω ϵ B = ∪ ⋅ ( B 1 ( ϵ 1 ) ⋆ ⋯ ⋆ B r ( ϵ r ) ) , and Ω η C = ∪ ⋅ ( C 1 ( η 1 ) ⋆ ⋯ ⋆ C s ( η s ) ) \Omega^C_{\eta}=\mathop{\mathop{\cup}\limits^{\cdot}}(C_1^{(\eta_1)}\star\cdots\star C_s^{(\eta_s)}) Ω η C = ∪ ⋅ ( C 1 ( η 1 ) ⋆ ⋯ ⋆ C s ( η s ) ) . Then Ω ϵ B ≅ Ω η C \Omega^B_{\epsilon}\cong\Omega^C_{\eta} Ω ϵ B ≅ Ω η C if and only if r = s r=s r = s and there are δ ∈ F 2 \delta\in\mathbb{F}_2 δ ∈ F 2 and a permutation σ ∈ S r \sigma\in S_r σ ∈ S r such that, for each 1 ≤ i ≤ r 1\le i\le r 1 ≤ i ≤ r , the following holds in Bip 2 \operatorname{Bip}_2 Bip 2 ,
B i ( ϵ i ) ≅ C σ ( i ) ( η σ ( i ) + δ ) . (20) B_i^{(\epsilon_i)}\cong C_{\sigma(i)}^{(\eta_{\sigma(i)}+\delta)}. \tag*{(20)} B i ( ϵ i ) ≅ C σ ( i ) ( η σ ( i ) + δ ) . (20)
Proof. First suppose that Ω ϵ B \Omega^B_{\epsilon} Ω ϵ B is isomorphic to Ω η C \Omega^C_{\eta} Ω η C . Equip Ω ϵ B \Omega^B_{\epsilon} Ω ϵ B and Ω η C \Omega^C_{\eta} Ω η C with the ordered bipartitions of B 1 ( ϵ 1 ) ⋆ ⋯ ⋆ B r ( ϵ r ) B_1^{(\epsilon_1)}\star\cdots\star B_r^{(\epsilon_r)} B 1 ( ϵ 1 ) ⋆ ⋯ ⋆ B r ( ϵ r ) and C 1 ( η 1 ) ⋆ ⋯ ⋆ C s ( η s ) C_1^{(\eta_1)}\star\cdots\star C_s^{(\eta_s)} C 1 ( η 1 ) ⋆ ⋯ ⋆ C s ( η s ) , respectively. By Theorem 1.5 , r = s r=s r = s , and there are a coordinate permutation σ \sigma σ and a common global sign δ \delta δ . By Eq. (3) , each factor map from B i ( ϵ i ) B_i^{(\epsilon_i)} B i ( ϵ i ) to C σ ( i ) ( η σ ( i ) ) C_{\sigma(i)}^{(\eta_{\sigma(i)})} C σ ( i ) ( η σ ( i ) ) with sign δ \delta δ preserves the ordered bipartition when its codomain is given the colouring of C σ ( i ) ( η σ ( i ) + δ ) C_{\sigma(i)}^{(\eta_{\sigma(i)}+\delta)} C σ ( i ) ( η σ ( i ) + δ ) . Thus B i ( ϵ i ) ≅ C σ ( i ) ( η σ ( i ) + δ ) B_i^{(\epsilon_i)}\cong C_{\sigma(i)}^{(\eta_{\sigma(i)}+\delta)} B i ( ϵ i ) ≅ C σ ( i ) ( η σ ( i ) + δ ) in Bip 2 \operatorname{Bip}_2 Bip 2 , which proves Eq. (20) .
Conversely, take the fibre product of the factor isomorphisms in Eq. (20) and permute the output coordinates by σ \sigma σ . The resulting map is an isomorphism in Bip 2 \operatorname{Bip}_2 Bip 2 from B 1 ( ϵ 1 ) ⋆ ⋯ ⋆ B r ( ϵ r ) B_1^{(\epsilon_1)}\star\cdots\star B_r^{(\epsilon_r)} B 1 ( ϵ 1 ) ⋆ ⋯ ⋆ B r ( ϵ r ) to C 1 ( η 1 + δ ) ⋆ ⋯ ⋆ C r ( η r + δ ) C_1^{(\eta_1+\delta)}\star\cdots\star C_r^{(\eta_r+\delta)} C 1 ( η 1 + δ ) ⋆ ⋯ ⋆ C r ( η r + δ ) . Forgetting the order of the bipartition gives an ordinary isomorphism from Ω ϵ B \Omega^B_{\epsilon} Ω ϵ B to Ω η C \Omega^C_{\eta} Ω η C . This completes the proof.
Automorphism groups of the direct product of bipartite graphs
We first prove the component and group statements in Theorem 1.6 . We then specialize to distinct factors and to fibre powers, making the orbit intersections explicit in the latter case. The final applications are a stability transfer and a recovery of known double cover formulas.
Proof of Theorem 1.6
We prove the component identification, orbit criterion, stabilizer formula, and group decomposition in that order. The distinction between an individual component and a coordinate factor will be used throughout.
Proof of Theorem 1.6. All decompositions θ i \theta_i θ i are fixed as in (7) . We use x , y , z \mathbf{x},\mathbf{y},\mathbf{z} x , y , z for vertices of P P P and u , v , w \mathbf{u},\mathbf{v},\mathbf{w} u , v , w for vertices of P ~ \widetilde{P} P . Binary vectors a , b \mathbf{a},\mathbf{b} a , b and their classes a ‾ \overline{\mathbf{a}} a and b ‾ \overline{\mathbf{b}} b label components, not vertices.
(i). We first prove that Θ \Theta Θ is an isomorphism from P P P to ∪ ⋅ a ‾ ∈ L Λ a ‾ \mathop{\mathop{\cup}\limits^{\cdot}}_{\overline{\mathbf{a}}\in\mathcal{L}}\Lambda_{\overline{\mathbf{a}}} ∪ ⋅ a ∈ L Λ a . Let x = ( x 1 , … , x r ) ∈ V ( P ) \mathbf{x}=(x_1,\ldots,x_r)\in V(P) x = ( x 1 , … , x r ) ∈ V ( P ) , and write Θ ( x ) = u = ( u 1 , … , u N ) \Theta(\mathbf{x})=\mathbf{u}=(u_1,\ldots,u_N) Θ ( x ) = u = ( u 1 , … , u N ) . By the definition of Θ \Theta Θ , for each 1 ≤ i ≤ r 1\le i\le r 1 ≤ i ≤ r , θ i ( x i ) = ( u k ) k ∈ I i \theta_i(x_i)=(u_k)_{k\in I_i} θ i ( x i ) = ( u k ) k ∈ I i . Since each θ i \theta_i θ i is an isomorphism in Bip 2 \operatorname{Bip}_2 Bip 2 , it preserves the ordered colour classes. Consequently, for every i ∈ { 1 , … , r } i\in\{1,\ldots,r\} i ∈ { 1 , … , r } and k ∈ I i k\in I_i k ∈ I i , ϱ C k ( u k ) = ϱ B i ( x i ) \varrho_{C_k}(u_k)=\varrho_{B_i}(x_i) ϱ C k ( u k ) = ϱ B i ( x i ) . Consider the following set of vertices of the refined direct product:
W = { v = ( v 1 , … , v N ) ∈ V ( P ~ ) : ϱ C k ( v k ) = ϱ C ℓ ( v ℓ ) whenever k , ℓ ∈ I i for some i } . W=\{\mathbf{v}=(v_1,\ldots,v_N)\in V(\widetilde{P}):\varrho_{C_k}(v_k)=\varrho_{C_\ell}(v_\ell)\text{ whenever }k,\ell\in I_i\text{ for some }i\}. W = { v = ( v 1 , … , v N ) ∈ V ( P ) : ϱ C k ( v k ) = ϱ C ℓ ( v ℓ ) whenever k , ℓ ∈ I i for some i } .
The colour-preservation identity above shows that Θ ( V ( P ) ) ⊆ W \Theta(V(P))\subseteq W Θ ( V ( P )) ⊆ W . Conversely, take v ∈ W \mathbf{v}\in W v ∈ W . For every i i i , the coordinates ( v k ) k ∈ I i (v_k)_{k\in I_i} ( v k ) k ∈ I i have a common colour and hence form a vertex of ⋆ k ∈ I i C k \star_{k\in I_i}C_k ⋆ k ∈ I i C k . Since θ i \theta_i θ i is bijective, there is a unique y i ∈ V ( B i ) y_i\in V(B_i) y i ∈ V ( B i ) with θ i ( y i ) = ( v k ) k ∈ I i \theta_i(y_i)=(v_k)_{k\in I_i} θ i ( y i ) = ( v k ) k ∈ I i . The resulting tuple y = ( y 1 , … , y r ) \mathbf{y}=(y_1,\ldots,y_r) y = ( y 1 , … , y r ) belongs to V ( P ) V(P) V ( P ) and satisfies Θ ( y ) = v \Theta(\mathbf{y})=\mathbf{v} Θ ( y ) = v . Uniqueness of each y i y_i y i makes this preimage unique. Thus Θ \Theta Θ is a bijection from V ( P ) V(P) V ( P ) onto W W W .
To check adjacency, let z , z ′ ∈ V ( P ) \mathbf{z},\mathbf{z}'\in V(P) z , z ′ ∈ V ( P ) , and put w = Θ ( z ) \mathbf{w}=\Theta(\mathbf{z}) w = Θ ( z ) and w ′ = Θ ( z ′ ) \mathbf{w}'=\Theta(\mathbf{z}') w ′ = Θ ( z ′ ) . Since each θ i \theta_i θ i is a graph isomorphism, we have
z ∼ P z ′ ⟺ z i ∼ U ( B i ) z i ′ for all i \mathbf{z}\sim_P\mathbf{z}'\Longleftrightarrow z_i\sim_{U(B_i)}z_i'\text{ for all }i z ∼ P z ′ ⟺ z i ∼ U ( B i ) z i ′ for all i
⟺ ( w k ) k ∈ I i ∼ ⋆ k ∈ I i C k ( w k ′ ) k ∈ I i for all i \Longleftrightarrow(w_k)_{k\in I_i}\sim_{\star_{k\in I_i}C_k}(w_k')_{k\in I_i}\text{ for all }i ⟺ ( w k ) k ∈ I i ∼ ⋆ k ∈ I i C k ( w k ′ ) k ∈ I i for all i
⟺ w k ∼ U ( C k ) w k ′ for all k \Longleftrightarrow w_k\sim_{U(C_k)}w_k'\text{ for all }k ⟺ w k ∼ U ( C k ) w k ′ for all k
⟺ w ∼ P ~ w ′ . (21) \Longleftrightarrow\mathbf{w}\sim_{\widetilde{P}}\mathbf{w}'. \tag*{(21)} ⟺ w ∼ P w ′ . (21)
Hence Θ \Theta Θ is a graph isomorphism from P P P onto the subgraph of P ~ \widetilde{P} P induced by W W W . We next identify this induced subgraph as a union of whole connected components. For any v = ( v 1 , … , v N ) ∈ V ( P ~ ) \mathbf{v}=(v_1,\ldots,v_N)\in V(\widetilde{P}) v = ( v 1 , … , v N ) ∈ V ( P ) , define its coordinate colour vector by
π ~ ( v ) = ( ϱ C 1 ( v 1 ) , … , ϱ C N ( v N ) ) ∈ F 2 N . \widetilde{\pi}(\mathbf{v})=(\varrho_{C_1}(v_1),\ldots,\varrho_{C_N}(v_N))\in\mathbb{F}_2^N. π ( v ) = ( ϱ C 1 ( v 1 ) , … , ϱ C N ( v N )) ∈ F 2 N .
By Proposition 2.3 , the connected component containing v \mathbf{v} v has label π ~ ( v ) ∈ Q N \widetilde{\pi}(\mathbf{v})\in Q_N π ( v ) ∈ Q N . For N = 1 N=1 N = 1 the same assertion is immediate. By the definition of L I \mathcal{L}_{\mathcal{I}} L I , this label belongs to L I \mathcal{L}_{\mathcal{I}} L I if and only if π ~ ( v ) \widetilde{\pi}(\mathbf{v}) π ( v ) is constant on each block I i I_i I i . Indeed, adding 1 N \mathbf{1}_N 1 N changes every entry by the same amount and therefore does not affect the blockwise equalities. It follows that W = ⨆ a ∈ L I V ( Λ ~ a ) W=\bigsqcup_{\mathbf{a}\in\mathcal{L}_{\mathcal{I}}}V(\widetilde{\Lambda}_{\mathbf{a}}) W = ⨆ a ∈ L I V ( Λ a ) .
Each Λ ~ a \widetilde{\Lambda}_{\mathbf{a}} Λ a is a connected component of P ~ \widetilde{P} P , so there are no edges between different such components. Then we have
Θ : P ⟶ ⨆ a ∈ L I Λ ~ a . \Theta:P\longrightarrow\bigsqcup_{\mathbf{a}\in\mathcal{L}_{\mathcal{I}}}\widetilde{\Lambda}_{\mathbf{a}}. Θ : P ⟶ a ∈ L I ⨆ Λ a .
It remains to identify the restriction to each original component. Recall that the coordinate colour vector of x = ( x 1 , … , x r ) ∈ V ( P ) \mathbf{x}=(x_1,\ldots,x_r)\in V(P) x = ( x 1 , … , x r ) ∈ V ( P ) is π ( x ) = ( ϱ B 1 ( x 1 ) , … , ϱ B r ( x r ) ) \pi(\mathbf{x})=(\varrho_{B_1}(x_1),\ldots,\varrho_{B_r}(x_r)) π ( x ) = ( ϱ B 1 ( x 1 ) , … , ϱ B r ( x r )) . The colour-preservation identity gives π ~ ( Θ ( x ) ) = d ‾ ( π ( x ) ) \widetilde{\pi}(\Theta(\mathbf{x}))=\overline{d}(\pi(\mathbf{x})) π ( Θ ( x )) = d ( π ( x )) . We also verify that the induced repetition map d ‾ : Q r → Q N \overline{d}:Q_r\to Q_N d : Q r → Q N is injective. Suppose d ‾ ( ϵ ) = d ‾ ( η ) \overline{d}(\boldsymbol{\epsilon})=\overline{d}(\boldsymbol{\eta}) d ( ϵ ) = d ( η ) . Then d ‾ ( ϵ + η ) = t 1 N \overline{d}(\boldsymbol{\epsilon}+\boldsymbol{\eta})=t\mathbf{1}_N d ( ϵ + η ) = t 1 N for some t ∈ F 2 t\in\mathbb{F}_2 t ∈ F 2 . Since every block I i I_i I i is nonempty, comparing any coordinate in I i I_i I i gives ϵ i + η i = t \epsilon_i+\eta_i=t ϵ i + η i = t for each i i i . Hence ϵ + η = t 1 r \boldsymbol{\epsilon}+\boldsymbol{\eta}=t\mathbf{1}_r ϵ + η = t 1 r , and ϵ = η \boldsymbol{\epsilon}=\boldsymbol{\eta} ϵ = η , as required.
Fix ϵ ‾ ∈ Q r \overline{\boldsymbol{\epsilon}}\in Q_r ϵ ∈ Q r . Proposition 2.3 (and the evident case r = 1 r=1 r = 1 ) shows that y ∈ V ( Ω ϵ ‾ ) \mathbf{y}\in V(\Omega_{\overline{\boldsymbol{\epsilon}}}) y ∈ V ( Ω ϵ ) precisely when π ‾ ( y ) = ϵ ‾ \overline{\pi}(\mathbf{y})=\overline{\boldsymbol{\epsilon}} π ( y ) = ϵ . Taking quotient classes in this identity, we see that Θ \Theta Θ maps Ω ϵ ‾ \Omega_{\overline{\boldsymbol{\epsilon}}} Ω ϵ into Λ ~ d ‾ ( ϵ ‾ ) \widetilde{\Lambda}_{\overline{d}(\overline{\boldsymbol{\epsilon}})} Λ d ( ϵ ) . Conversely, let v ∈ V ( Λ ~ d ‾ ( ϵ ‾ ) ) \mathbf{v}\in V(\widetilde{\Lambda}_{\overline{d}(\overline{\boldsymbol{\epsilon}})}) v ∈ V ( Λ d ( ϵ ) ) . The vertex v \mathbf{v} v lies in W W W and hence has a unique preimage y ∈ V ( P ) \mathbf{y}\in V(P) y ∈ V ( P ) . Thus d ‾ ( π ‾ ( y ) ) = d ‾ ( ϵ ‾ ) \overline{d}(\overline{\pi}(\mathbf{y}))=\overline{d}(\overline{\boldsymbol{\epsilon}}) d ( π ( y )) = d ( ϵ ) . Since d ‾ \overline{d} d is injective, π ‾ ( y ) = ϵ ‾ \overline{\pi}(\mathbf{y})=\overline{\boldsymbol{\epsilon}} π ( y ) = ϵ , so y ∈ V ( Ω ϵ ‾ ) \mathbf{y}\in V(\Omega_{\overline{\boldsymbol{\epsilon}}}) y ∈ V ( Ω ϵ ) . Thus
Θ ϵ ‾ : Ω ϵ ‾ ⟶ Λ ~ d ‾ ( ϵ ‾ ) \Theta_{\overline{\boldsymbol{\epsilon}}}:\Omega_{\overline{\boldsymbol{\epsilon}}}\longrightarrow\widetilde{\Lambda}_{\overline{d}(\overline{\boldsymbol{\epsilon}})} Θ ϵ : Ω ϵ ⟶ Λ d ( ϵ )
is a graph isomorphism. Finally, since L I = d ‾ ( Q r ) \mathcal{L}_{\mathcal{I}}=\overline{d}(Q_r) L I = d ( Q r ) and d ‾ \overline{d} d is injective,
∣ L I ∣ = ∣ Q r ∣ = 2 r − 1 . |\mathcal{L}_{\mathcal{I}}|=|Q_r|=2^{r-1}. ∣ L I ∣ = ∣ Q r ∣ = 2 r − 1 .
This proves part (i).
(ii). We first identify the action of a factor symmetry on a refined component. Let w = w σ , f ∈ W w=w_{\sigma,f}\in\mathbb{W} w = w σ , f ∈ W , where σ ∈ S N \sigma\in S_N σ ∈ S N and f k : U ( C k ) → U ( C σ ( k ) ) f_k:U(C_k)\to U(C_{\sigma(k)}) f k : U ( C k ) → U ( C σ ( k ) ) is an isomorphism for every 1 ≤ k ≤ N 1\leq k\leq N 1 ≤ k ≤ N . Since the factors are connected and bipartite, each f k f_k f k has a unique colour sign s k ∈ F 2 s_k\in\mathbb{F}_2 s k ∈ F 2 satisfying, for any z ∈ V ( C k ) z\in V(C_k) z ∈ V ( C k ) ,
ϱ C σ ( k ) ( f k ( z ) ) = ϱ C k ( z ) + s k . (22) \varrho_{C_{\sigma(k)}}(f_k(z))=\varrho_{C_k}(z)+s_k. \tag*{(22)} ϱ C σ ( k ) ( f k ( z )) = ϱ C k ( z ) + s k . (22)
Since ϱ C σ ( k ) ( f k ( z ) ) + ϱ C k ( z ) \varrho_{C_{\sigma(k)}}(f_k(z))+\varrho_{C_k}(z) ϱ C σ ( k ) ( f k ( z )) + ϱ C k ( z ) is unchanged across every edge and C k C_k C k is connected, the sign s k s_k s k is independent of z z z . Write s = ( s 1 , … , s N ) ∈ F 2 N \mathbf{s}=(s_1,\ldots,s_N)\in\mathbb{F}_2^N s = ( s 1 , … , s N ) ∈ F 2 N .
Fix a ∈ F 2 N \mathbf{a}\in\mathbb{F}_2^N a ∈ F 2 N and a vertex u = ( u 1 , … , u N ) ∈ V ( Λ ~ a ) \mathbf{u}=(u_1,\ldots,u_N)\in V(\widetilde{\Lambda}_{\mathbf{a}}) u = ( u 1 , … , u N ) ∈ V ( Λ a ) . There is t ∈ F 2 t\in\mathbb{F}_2 t ∈ F 2 such that ϱ C k ( x k ) = a k + t \varrho_{C_k}(x_k)=a_k+t ϱ C k ( x k ) = a k + t for every k k k . Write v = w ( u ) = ( v 1 , … , v N ) \mathbf{v}=w(\mathbf{u})=(v_1,\ldots,v_N) v = w ( u ) = ( v 1 , … , v N ) . Then v σ ( k ) = f k ( x k ) v_{\sigma(k)}=f_k(x_k) v σ ( k ) = f k ( x k ) and Eq. (22) gives
π ~ ( v ) = σ ∗ ( a + s ) + t 1 N . \widetilde{\pi}(\mathbf{v})=\sigma_*(\mathbf{a}+\mathbf{s})+t\mathbf{1}_N. π ( v ) = σ ∗ ( a + s ) + t 1 N .
Applying the same argument to w σ , f − 1 w^{-1}_{\sigma,f} w σ , f − 1 , we have
w σ , f ( Λ ~ a ) = Λ ~ σ ∗ ( a + s ) . (23) w_{\sigma,f}(\widetilde{\Lambda}_{\mathbf{a}})=\widetilde{\Lambda}_{\sigma_*(\mathbf{a}+\mathbf{s})}. \tag*{(23)} w σ , f ( Λ a ) = Λ σ ∗ ( a + s ) . (23)
Let φ : Λ ~ a ⟶ Λ ~ b \varphi:\widetilde{\Lambda}_{\mathbf{a}}\longrightarrow\widetilde{\Lambda}_{\mathbf{b}} φ : Λ a ⟶ Λ b be a graph isomorphism, where a , b ∈ F 2 N \mathbf{a},\mathbf{b}\in\mathbb{F}_2^N a , b ∈ F 2 N . We apply Theorem 1.5 to the ordered fibre products ∗ k = 1 N C k ( a k ) \mathop{\ast}\limits_{k=1}^{N}C_k^{(a_k)} k = 1 ∗ N C k ( a k ) and ∗ k = 1 N C k ( b k ) \mathop{\ast}\limits_{k=1}^{N}C_k^{(b_k)} k = 1 ∗ N C k ( b k ) , respectively. There exist a permutation σ ∈ S N \sigma\in S_N σ ∈ S N , factor isomorphisms f k : U ( C k ) → U ( C σ ( k ) ) f_k:U(C_k)\to U(C_{\sigma(k)}) f k : U ( C k ) → U ( C σ ( k ) ) , and a common sign δ ∈ F 2 \delta\in\mathbb{F}_2 δ ∈ F 2 such that for any z ∈ V ( C k ) z\in V(C_k) z ∈ V ( C k ) and 1 ≤ k ≤ N 1\leq k\leq N 1 ≤ k ≤ N ,
ϱ C σ ( k ) ( f k ( z ) ) + b σ ( k ) = ϱ C k ( z ) + a k + δ , (24) \varrho_{C_{\sigma(k)}}(f_k(z))+b_{\sigma(k)}=\varrho_{C_k}(z)+a_k+\delta, \tag*{(24)} ϱ C σ ( k ) ( f k ( z )) + b σ ( k ) = ϱ C k ( z ) + a k + δ , (24)
and, for any u ∈ V ( Λ ‾ a ‾ ) \mathbf{u} \in V(\overline{\Lambda}_{\overline{a}}) u ∈ V ( Λ a ) and 1 ≤ k ≤ N 1 \le k \le N 1 ≤ k ≤ N , we have
[ φ ( u ) ] σ ( k ) = f k ( u k ) . (25) [\varphi(\mathbf{u})]_{\sigma(k)} = f_k(u_k). \tag*{(25)} [ φ ( u ) ] σ ( k ) = f k ( u k ) . (25)
Define w ∈ W ~ w \in\widetilde{\mathcal{W}} w ∈ W on the entire refined direct product by the same σ \sigma σ and f k f_k f k . By Eq. (25) , w ( u ) w(\mathbf{u}) w ( u ) and φ ( u ) \varphi(\mathbf{u}) φ ( u ) have the same coordinate in each output position σ ( k ) \sigma(k) σ ( k ) . Since σ \sigma σ permutes all coordinate positions, we have w ∣ Λ ‾ a ‾ = φ w|_{\overline{\Lambda}_{\overline{a}}} = \varphi w ∣ Λ a = φ . Let s k s_k s k denote the sign of f k f_k f k as in Eq. (22) . By Eqs. (22) and (24) , cancellation of ϱ C k ( z ) \varrho_{C_k}(z) ϱ C k ( z ) in F 2 \mathbb{F}_2 F 2 yields b σ ( k ) = a k + s k + δ b_{\sigma(k)} = a_k + s_k + \delta b σ ( k ) = a k + s k + δ for 1 ≤ k ≤ N 1 \le k \le N 1 ≤ k ≤ N . Thus b = σ ∗ ( a + s ) + δ 1 N \mathbf{b} = \sigma_*(\mathbf{a}+\mathbf{s})+\delta\mathbf{1}_N b = σ ∗ ( a + s ) + δ 1 N . Passing to the quotient, we obtain
b ‾ = σ ∗ ( a + s ) ‾ = w ⋅ a ‾ . \overline{\mathbf{b}}=\overline{\sigma_*(\mathbf{a}+\mathbf{s})}=w\cdot\overline{\mathbf{a}}. b = σ ∗ ( a + s ) = w ⋅ a .
This proves that isomorphic components have indices in the same orbit. Conversely, if b ‾ = w ⋅ a ‾ \overline{\mathbf{b}}=w\cdot\overline{\mathbf{a}} b = w ⋅ a for some w ∈ W ~ w\in\widetilde{\mathcal{W}} w ∈ W , then by Eq. (23) , we have w ( Λ ‾ a ‾ ) = Λ ‾ b ‾ w(\overline{\Lambda}_{\overline{a}})=\overline{\Lambda}_{\overline{b}} w ( Λ a ) = Λ b . Since w w w is a graph automorphism, its restriction is an isomorphism between those components.
Finally, by part (i), the maps Θ ϵ ‾ \Theta_{\overline{\epsilon}} Θ ϵ and Θ η ‾ \Theta_{\overline{\eta}} Θ η are isomorphisms onto Λ d ( ϵ ‾ ) ‾ \Lambda_{\overline{d(\overline{\epsilon})}} Λ d ( ϵ ) and Λ d ( η ‾ ) ‾ \Lambda_{\overline{d(\overline{\eta})}} Λ d ( η ) , respectively. If ψ : Ω ϵ ‾ → Ω η ‾ \psi:\Omega_{\overline{\epsilon}}\to\Omega_{\overline{\eta}} ψ : Ω ϵ → Ω η is an isomorphism, then
Θ η ‾ ∘ ψ ∘ Θ ϵ ‾ − 1 : Λ d ( ϵ ‾ ) ‾ ⟶ Λ d ( η ‾ ) ‾ \Theta_{\overline{\eta}}\circ\psi\circ\Theta_{\overline{\epsilon}}^{-1}:\Lambda_{\overline{d(\overline{\epsilon})}}\longrightarrow\Lambda_{\overline{d(\overline{\eta})}} Θ η ∘ ψ ∘ Θ ϵ − 1 : Λ d ( ϵ ) ⟶ Λ d ( η )
is an isomorphism, so d ( ϵ ‾ ) ‾ \overline{d(\overline{\epsilon})} d ( ϵ ) and d ( η ‾ ) ‾ \overline{d(\overline{\eta})} d ( η ) lie in the same orbit. Conversely, if d ( ϵ ‾ ) ‾ \overline{d(\overline{\epsilon})} d ( ϵ ) and d ( η ‾ ) ‾ \overline{d(\overline{\eta})} d ( η ) lie in the same orbit, choose w w w with w ⋅ d ( ϵ ‾ ) ‾ = d ( η ‾ ) ‾ w\cdot\overline{d(\overline{\epsilon})}=\overline{d(\overline{\eta})} w ⋅ d ( ϵ ) = d ( η ) . Then Θ η ‾ − 1 ∘ ( w ∣ Λ d ( ϵ ‾ ) ‾ ) ∘ Θ ϵ ‾ \Theta_{\overline{\eta}}^{-1}\circ(w|_{\Lambda_{\overline{d(\overline{\epsilon})}}})\circ\Theta_{\overline{\epsilon}} Θ η − 1 ∘ ( w ∣ Λ d ( ϵ ) ) ∘ Θ ϵ is an isomorphism from Ω ϵ ‾ \Omega_{\overline{\epsilon}} Ω ϵ to Ω η ‾ \Omega_{\overline{\eta}} Ω η . This proves part (ii).
(iii). Fix a ‾ = d ( ϵ ‾ ) ‾ \overline{a}=\overline{d(\overline{\epsilon})} a = d ( ϵ ) . By Eq. (23) , restriction defines a homomorphism
Res a ‾ : Stab W ~ ( a ‾ ) ⟶ Aut ( Λ a ‾ ) , \operatorname{Res}_{\overline{a}}:\operatorname{Stab}_{\widetilde{\mathcal{W}}}(\overline{a})\longrightarrow\operatorname{Aut}(\Lambda_{\overline{a}}), Res a : Stab W ( a ) ⟶ Aut ( Λ a ) ,
given by Res a ‾ ( w ) = w ∣ V ( Λ a ‾ ) \operatorname{Res}_{\overline{a}}(w)=w|_{V(\Lambda_{\overline{a}})} Res a ( w ) = w ∣ V ( Λ a ) . To prove surjectivity, take any h ∈ Aut ( Λ a ‾ ) h\in\operatorname{Aut}(\Lambda_{\overline{a}}) h ∈ Aut ( Λ a ) . Apply the isomorphism construction in part (ii) with both source and target label equal to a ‾ \overline{a} a and with φ = h \varphi=h φ = h . It produces w ∈ W ~ w\in\widetilde{\mathcal{W}} w ∈ W whose restriction is exactly h h h , and whose label action satisfies w ⋅ a ‾ = a ‾ w\cdot\overline{a}=\overline{a} w ⋅ a = a . Thus w w w lies in the stated stabilizer and Res a ‾ ( w ) = h \operatorname{Res}_{\overline{a}}(w)=h Res a ( w ) = h .
To prove injectivity, suppose w = w σ , f w=w_{\sigma,f} w = w σ , f fixes every vertex of this component. Each class of each C k C_k C k has at least two vertices, by Lemma Lemma 2.1. Fix a global colour t t t . The vertices with that colour are the unrestricted Cartesian tuples ∏ j C j a j + t \prod_j C_j^{a_j+t} ∏ j C j a j + t . If σ ( k ) ≠ k \sigma(k)\ne k σ ( k ) = k , choose two such tuples u , u ′ \mathbf{u},\mathbf{u}' u , u ′ differing only in position σ ( k ) \sigma(k) σ ( k ) . They have u k = u k ′ u_k=u'_k u k = u k ′ but u σ ( k ) ≠ u σ ( k ) ′ u_{\sigma(k)}\ne u'_{\sigma(k)} u σ ( k ) = u σ ( k ) ′ . Since both are fixed,
u σ ( k ) = [ w ( u ) ] σ ( k ) = f k ( u k ) = f k ( u k ′ ) = [ w ( u ′ ) ] σ ( k ) = u σ ( k ) ′ , u_{\sigma(k)}=[w(\mathbf{u})]_{\sigma(k)}=f_k(u_k)=f_k(u'_k)=[w(\mathbf{u}')]_{\sigma(k)}=u'_{\sigma(k)}, u σ ( k ) = [ w ( u ) ] σ ( k ) = f k ( u k ) = f k ( u k ′ ) = [ w ( u ′ ) ] σ ( k ) = u σ ( k ) ′ ,
a contradiction. We conclude that σ ( k ) = k \sigma(k)=k σ ( k ) = k for every k k k , so σ \sigma σ is the identity. If N = 1 N=1 N = 1 , this conclusion is automatic, and the rest of the argument remains valid.
Now fix a position k k k and a vertex z ∈ V ( C k ) z\in V(C_k) z ∈ V ( C k ) . Set t = ϱ C k ( z ) + a k t=\varrho_{C_k}(z)+a_k t = ϱ C k ( z ) + a k . For each j ≠ k j\ne k j = k , since both colour classes of C j C_j C j are nonempty, we can choose a vertex u j u_j u j of colour a j + t a_j+t a j + t in C j C_j C j . Set u k = z u_k=z u k = z . Then u = ( u 1 , … , u N ) ∈ V ( Λ a ‾ ) \mathbf{u}=(u_1,\ldots,u_N)\in V(\Lambda_{\overline{a}}) u = ( u 1 , … , u N ) ∈ V ( Λ a ) . By w ( u ) = u w(\mathbf{u})=\mathbf{u} w ( u ) = u and the identity σ = 1 \sigma=1 σ = 1 , we have f k ( z ) = [ w ( u ) ] k = u k = z f_k(z)=[w(\mathbf{u})]_k=u_k=z f k ( z ) = [ w ( u ) ] k = u k = z . Since z z z is arbitrary, f k f_k f k is the identity on all of V ( C k ) V(C_k) V ( C k ) . This holds for every k k k , so every coordinate map is the identity. Consequently w w w is the identity on all of V ( P ~ ) V(\widetilde{P}) V ( P ) . Thus ker Res a ‾ = 1 \ker\operatorname{Res}_{\overline{a}}=1 ker Res a = 1 , and Res a ‾ \operatorname{Res}_{\overline{a}} Res a is injective. Combining this with surjectivity, we have Stab W ~ ( a ‾ ) ≅ Aut ( Λ a ‾ ) \operatorname{Stab}_{\widetilde{\mathcal{W}}}(\overline{a})\cong\operatorname{Aut}(\Lambda_{\overline{a}}) Stab W ( a ) ≅ Aut ( Λ a ) .
Finally, Θ ϵ ‾ \Theta_{\overline{\epsilon}} Θ ϵ is an isomorphism by part (i), so conjugation g ↦ Θ ϵ ‾ − 1 g ∘ Θ ϵ ‾ g\mapsto\Theta_{\overline{\epsilon}}^{-1}g\circ\Theta_{\overline{\epsilon}} g ↦ Θ ϵ − 1 g ∘ Θ ϵ is an isomorphism from Aut ( Λ a ‾ ) \operatorname{Aut}(\Lambda_{\overline{a}}) Aut ( Λ a ) to Aut ( Ω ϵ ‾ ) \operatorname{Aut}(\Omega_{\overline{\epsilon}}) Aut ( Ω ϵ ) for g ∈ Aut ( Λ a ‾ ) g\in\operatorname{Aut}(\Lambda_{\overline{a}}) g ∈ Aut ( Λ a ) . Composing this isomorphism with Res a ‾ \operatorname{Res}_{\overline{a}} Res a gives the isomorphism asserted in part (iii). This proves part (iii).
(iv). By part (i), we may identify P P P with the disjoint union of component graphs P : = ∐ a ‾ ∈ L T Λ a ‾ \mathcal{P}:=\coprod_{\overline{a}\in\mathcal{L}_{\mathcal{T}}}\Lambda_{\overline{a}} P := ∐ a ∈ L T Λ a , where L T ⊆ Q N \mathcal{L}_{\mathcal{T}}\subseteq Q_N L T ⊆ Q N is a set of labels, and every Λ a ‾ \Lambda_{\overline{a}} Λ a is an entire connected component. For O ∈ O T \mathcal{O}\in\mathcal{O}_{\mathcal{T}} O ∈ O T , define the subgraph P O : = ∐ a ‾ ∈ O ∩ L T Λ a ‾ \mathcal{P}_{\mathcal{O}}:=\coprod_{\overline{a}\in\mathcal{O}\cap\mathcal{L}_{\mathcal{T}}}\Lambda_{\overline{a}} P O := ∐ a ∈ O ∩ L T Λ a . The nonempty intersections O ∩ L T \mathcal{O}\cap\mathcal{L}_{\mathcal{T}} O ∩ L T partition L T \mathcal{L}_{\mathcal{T}} L T since distinct orbits in Q N Q_N Q N are disjoint. Therefore P = ∐ O ∈ O T P O \mathcal{P}=\coprod_{\mathcal{O}\in\mathcal{O}_{\mathcal{T}}}\mathcal{P}_{\mathcal{O}} P = ∐ O ∈ O T P O . By part (ii), two selected connected components are isomorphic if and only if their labels lie in the same W ~ \widetilde{\mathcal{W}} W -orbit on Q N Q_N Q N . Consequently the graphs P O \mathcal{P}_{\mathcal{O}} P O consist of exactly n O = ∣ O ∩ L I ∣ n_{\mathcal{O}}=|\mathcal{O}\cap\mathcal{L}_I| n O = ∣ O ∩ L I ∣ mutually isomorphic connected components, and graphs from distinct O \mathcal{O} O contain no isomorphic components. Every automorphism of P \mathcal{P} P must preserve each P O \mathcal{P}_{\mathcal{O}} P O setwise. Conversely, automorphisms of these disjoint subgraphs may be chosen independently, yielding
Aut ( P ) ≅ ∏ O ∈ O I Aut ( P O ) . (26) \operatorname{Aut}(\mathcal{P})\cong\prod_{\mathcal{O}\in\mathcal{O}_I}\operatorname{Aut}(\mathcal{P}_{\mathcal{O}}). \tag*{(26)} Aut ( P ) ≅ O ∈ O I ∏ Aut ( P O ) . (26)
Fix O ∈ O I \mathcal{O}\in\mathcal{O}_I O ∈ O I and abbreviate n = n O n=n_{\mathcal{O}} n = n O and Λ ′ = Λ a ‾ O \Lambda'=\Lambda_{\overline{a}_{\mathcal{O}}} Λ ′ = Λ a O . Write G = Aut ( Λ ′ ) G=\operatorname{Aut}(\Lambda') G = Aut ( Λ ′ ) . Enumerate the connected components of P O \mathcal{P}_{\mathcal{O}} P O as Λ 1 , … , Λ n \Lambda_1,\ldots,\Lambda_n Λ 1 , … , Λ n . By part (ii), each Λ j \Lambda_j Λ j is isomorphic to Λ ′ \Lambda' Λ ′ . Fix an isomorphism ι j : Λ ′ → Λ j \iota_j:\Lambda'\to\Lambda_j ι j : Λ ′ → Λ j for every j j j . For g = ( g 1 , … , g n ) ∈ G n \mathbf{g}=(g_1,\ldots,g_n)\in G^n g = ( g 1 , … , g n ) ∈ G n , τ ∈ S n \tau\in S_n τ ∈ S n and u ∈ V ( Λ j ) \mathbf{u}\in V(\Lambda_j) u ∈ V ( Λ j ) , define
Ψ g , τ ( u ) = ι τ ( j ) ∘ g τ ( j ) ∘ ι j − 1 ( u ) . (27) \Psi_{\mathbf{g},\tau}(\mathbf{u})=\iota_{\tau(j)}\circ g_{\tau(j)}\circ\iota_j^{-1}(\mathbf{u}). \tag*{(27)} Ψ g , τ ( u ) = ι τ ( j ) ∘ g τ ( j ) ∘ ι j − 1 ( u ) . (27)
This map is an automorphism that sends Λ j \Lambda_j Λ j to Λ τ ( j ) \Lambda_{\tau(j)} Λ τ ( j ) . Conversely, every automorphism Ψ \Psi Ψ of P O \mathcal{P}_{\mathcal{O}} P O permutes its connected components by a unique τ ∈ S n \tau\in S_n τ ∈ S n , and the restrictions determine uniquely g τ ( j ) = ι τ ( j ) − 1 ∘ ( Ψ ∣ Λ j ) ∘ ι j g_{\tau(j)}=\iota_{\tau(j)}^{-1}\circ(\Psi|_{\Lambda_j})\circ\iota_j g τ ( j ) = ι τ ( j ) − 1 ∘ ( Ψ ∣ Λ j ) ∘ ι j . Thus ( g , τ ) ↦ Ψ g , τ (\mathbf{g},\tau)\mapsto\Psi_{\mathbf{g},\tau} ( g , τ ) ↦ Ψ g , τ is bijective.
For u ∈ V ( Λ j ) \mathbf{u}\in V(\Lambda_j) u ∈ V ( Λ j ) , applying Ψ h , ω \Psi_{\mathbf{h},\omega} Ψ h , ω and then Ψ g , τ \Psi_{\mathbf{g},\tau} Ψ g , τ yields
( Ψ g , τ ∘ Ψ h , ω ) ( u ) = ι τ ω ( j ) ∘ g τ ω ( j ) ∘ ι ω ( j ) − 1 ∘ ι ω ( j ) ∘ h ω ( j ) ∘ ι j − 1 ( u ) = ι τ ω ( j ) ∘ ( g τ ω ( j ) ∘ h ω ( j ) ) ∘ ι j − 1 ( u ) . (\Psi_{\mathbf{g},\tau}\circ\Psi_{\mathbf{h},\omega})(\mathbf{u})=\iota_{\tau\omega(j)}\circ g_{\tau\omega(j)}\circ\iota_{\omega(j)}^{-1}\circ\iota_{\omega(j)}\circ h_{\omega(j)}\circ\iota_j^{-1}(\mathbf{u})
=\iota_{\tau\omega(j)}\circ(g_{\tau\omega(j)}\circ h_{\omega(j)})\circ\iota_j^{-1}(\mathbf{u}). ( Ψ g , τ ∘ Ψ h , ω ) ( u ) = ι τ ω ( j ) ∘ g τ ω ( j ) ∘ ι ω ( j ) − 1 ∘ ι ω ( j ) ∘ h ω ( j ) ∘ ι j − 1 ( u ) = ι τ ω ( j ) ∘ ( g τ ω ( j ) ∘ h ω ( j ) ) ∘ ι j − 1 ( u ) .
Writing ℓ = τ ω ( j ) \ell=\tau\omega(j) ℓ = τ ω ( j ) , we have ω ( j ) = τ − 1 ( ℓ ) \omega(j)=\tau^{-1}(\ell) ω ( j ) = τ − 1 ( ℓ ) . Thus Ψ g , τ ∘ Ψ h , ω = Ψ g ( τ ⋅ h ) , τ ω \Psi_{\mathbf{g},\tau}\circ\Psi_{\mathbf{h},\omega}=\Psi_{\mathbf{g}(\tau\cdot\mathbf{h}),\tau\omega} Ψ g , τ ∘ Ψ h , ω = Ψ g ( τ ⋅ h ) , τ ω , where ( τ ⋅ h ) ℓ = h τ − 1 ( ℓ ) (\tau\cdot\mathbf{h})_\ell=h_{\tau^{-1}(\ell)} ( τ ⋅ h ) ℓ = h τ − 1 ( ℓ ) . This is the multiplication in the semidirect product G n ⋊ S n G^n\rtimes S_n G n ⋊ S n when S n S_n S n acts on G n G^n G n by ( τ ⋅ h ) ℓ = h τ − 1 ( ℓ ) (\tau\cdot\mathbf{h})_\ell=h_{\tau^{-1}(\ell)} ( τ ⋅ h ) ℓ = h τ − 1 ( ℓ ) . Consequently Aut ( P O ) ≅ G n ⋊ S n = G ≀ S n \operatorname{Aut}(\mathcal{P}_{\mathcal{O}})\cong G^n\rtimes S_n=G\wr S_n Aut ( P O ) ≅ G n ⋊ S n = G ≀ S n . The argument also applies when n = 1 n=1 n = 1 since S 1 S_1 S 1 is trivial. Together with part (ii), this identifies the factor in (8) corresponding to this isomorphism class of components.
Part (iii) further identifies G ≅ Stab W ~ ( a ‾ O ) . S u b s t i t u t i n g t h i s i n t o E q . ( 25 ) a n d t r a n s p o r t i n g t h e r e s u l t i n g i s o m o r p h i s m t h r o u g h G\cong\operatorname{Stab}_{\widetilde{\mathcal{W}}}(\overline{a}_{\mathcal{O}}). Substituting this into Eq. (25) and transporting the resulting isomorphism through G ≅ Stab W ( a O ) . S u b s t i t u t in g t hi s in t o E q . ( 25 ) an d t r an s p or t in g t h er es u l t in g i so m or p hi s m t h r o ug h \Theta$ gives Eq. (8), proving part (iv).
(v). Use the type classes J λ J_\lambda J λ and their sizes t λ t_\lambda t λ from the statement. Fix an isomorphism ι k : U ( C k ) → T λ ( k ) \iota_k:U(C_k)\to T_{\lambda(k)} ι k : U ( C k ) → T λ ( k ) , where k ∈ J λ ( k ) k\in J_{\lambda(k)} k ∈ J λ ( k ) . A factor symmetry has a unique coordinate permutation. Otherwise, suppose two representations used different input positions for one output position. Varying just one of those inputs would change that output in one representation but not the other. Each factor has at least two vertices, and its coordinate maps are injective, so this is impossible. With the permutation fixed, varying each input determines its map uniquely. Consequently the map sending w σ , f w_{\sigma,\mathbf{f}} w σ , f to σ \sigma σ is a homomorphism onto Π = ∏ λ = 1 q S J λ \Pi=\prod_{\lambda=1}^{q}S_{J_\lambda} Π = ∏ λ = 1 q S J λ . Its kernel K K K is the coordinatewise group, which the maps ι k \iota_k ι k identify with ∏ λ = 1 q Aut ( T λ ) J λ \prod_{\lambda=1}^{q}\operatorname{Aut}(T_\lambda)^{J_\lambda} ∏ λ = 1 q Aut ( T λ ) J λ . For σ ∈ Π \sigma\in\Pi σ ∈ Π , define a lift ℓ σ \ell_\sigma ℓ σ by the factor maps ι σ ( k ) − 1 ι k \iota_{\sigma(k)}^{-1}\iota_k ι σ ( k ) − 1 ι k . Their composites satisfy
( ι τ σ ( k ) − 1 ι σ ( k ) ) ( ι σ ( k ) − 1 ι k ) = ι τ σ ( k ) − 1 ι k , (\iota_{\tau\sigma(k)}^{-1}\iota_{\sigma(k)})(\iota_{\sigma(k)}^{-1}\iota_k)=\iota_{\tau\sigma(k)}^{-1}\iota_k, ( ι τ σ ( k ) − 1 ι σ ( k ) ) ( ι σ ( k ) − 1 ι k ) = ι τ σ ( k ) − 1 ι k ,
so ℓ τ ℓ σ = ℓ τ σ \ell_\tau\ell_\sigma=\ell_{\tau\sigma} ℓ τ ℓ σ = ℓ τ σ . They give a homomorphic section of the permutation map. In the transported coordinates, conjugation by ℓ σ \ell_\sigma ℓ σ sends a tuple h \mathbf{h} h in the kernel to the tuple with j j j -th entry h σ − 1 ( j ) h_{\sigma^{-1}(j)} h σ − 1 ( j ) . This is well defined since σ \sigma σ preserves all J λ J_\lambda J λ . The semidirect product is therefore
W ~ ≅ ∏ λ = 1 q ( Aut ( T λ ) J λ ⋊ S J λ ) ≅ ∏ λ = 1 q ( Aut ( T λ ) ≀ S t λ ) . \widetilde{\mathcal{W}}\cong\prod_{\lambda=1}^{q}\left(\operatorname{Aut}(T_\lambda)^{J_\lambda}\rtimes S_{J_\lambda}\right)\cong\prod_{\lambda=1}^{q}\left(\operatorname{Aut}(T_\lambda)\wr S_{t_\lambda}\right). W ≅ λ = 1 ∏ q ( Aut ( T λ ) J λ ⋊ S J λ ) ≅ λ = 1 ∏ q ( Aut ( T λ ) ≀ S t λ ) .
This proves part (v).
Remark 4.1. The following observations clarify the choices in Theorem 1.6. (1) The description is independent, up to the indicated isomorphisms, of the chosen maps θ i \theta_i θ i . To see this, let θ i ′ : B i → ⋆ ℓ ∈ I i ′ C ℓ ′ \theta'_i:B_i\to\mathop{\star}_{\ell\in I'_i}C'_\ell θ i ′ : B i → ⋆ ℓ ∈ I i ′ C ℓ ′ be another family of fibre-prime decompositions. Theorem 1.4 , applied to θ i ′ θ i − 1 \theta'_i{\theta_i}^{-1} θ i ′ θ i − 1 , gives a bijection σ i : I i → I i ′ \sigma_i:I_i\to I'_i σ i : I i → I i ′ and colour-preserving factor isomorphisms f k : C k → C σ i ( k ) ′ f_k:C_k\to C'_{\sigma_i(k)} f k : C k → C σ i ( k ) ′ . In particular the two refinements have the same total number N N N of factors. Their union is a bijection σ \sigma σ of the two refined index sets and defines a coordinate isomorphism F : P ~ → P ~ ′ F:\widetilde{P}\to\widetilde{P}' F : P → P ′ satisfying F ∘ Θ = Θ ′ F\circ\Theta=\Theta' F ∘ Θ = Θ ′ . Since every f k f_k f k preserves colour, the induced bijection on labels is a ˉ ↦ σ ∗ a ˉ \bar{a}\mapsto\sigma_*\bar{a} a ˉ ↦ σ ∗ a ˉ . It maps L I \mathcal{L}_{\mathcal{I}} L I onto L I ′ \mathcal{L}_{\mathcal{I}'} L I ′ , because σ ( I i ) = I i ′ \sigma(I_i)=I'_i σ ( I i ) = I i ′ for each original factor. Conjugation by F F F sends the refined factor-symmetry group onto the other refined factor-symmetry group: a coordinate permutation and its factor maps are carried to the corresponding conjugate coordinate data, and the inverse conjugation has the same property. The two label actions are therefore equivalent. Corresponding stabilizers are conjugate and the corresponding orbit intersections have equal sizes. Hence changing factorization coordinates does not change the group or multiplicity data in Theorem 1.6 .
(2) The label set L I \mathcal{L}_{\mathcal{I}} L I need not be preserved by W \mathbb{W} W . For example, take B 1 = C 6 ⋆ C 6 B_1=C_6\star C_6 B 1 = C 6 ⋆ C 6 and B 2 = C 6 B_2=C_6 B 2 = C 6 . Each C 6 C_6 C 6 is twin-free and fibre-prime by Lemma 2.5 (i). With I 1 = { 1 , 2 } I_1=\{1,2\} I 1 = { 1 , 2 } and I 2 = { 3 } I_2=\{3\} I 2 = { 3 } , the label ( 0 , 0 , 0 ) (0,0,0) ( 0 , 0 , 0 ) is admissible. A colour-reversing automorphism in the first refined coordinate sends it to ( 1 , 0 , 0 ) (1,0,0) ( 1 , 0 , 0 ) , which is not admissible. Thus the multiplicities in Theorem 1.6 are intersections of ambient orbits with L I \mathcal{L}_{\mathcal{I}} L I ; they are not orbits of an action on L I \mathcal{L}_{\mathcal{I}} L I .
We next derive consequences of Theorem 1.6 .
Corollary 4.2. Let r ≥ 1 r\geq1 r ≥ 1 , and let B 1 , … , B r B_1,\ldots,B_r B 1 , … , B r be connected twin-free nonunit f f f -prime ordered bipartite graphs. Put P = ∏ i = 1 r U ( B i ) P=\prod_{i=1}^{r}U(B_i) P = ∏ i = 1 r U ( B i ) and W = W ( B 1 , … , B r ) \mathbb{W}=\mathbb{W}(B_1,\ldots,B_r) W = W ( B 1 , … , B r ) . For ϵ ˉ ∈ Q r \bar{\epsilon}\in Q_r ϵ ˉ ∈ Q r , put Ω ϵ ˉ = U ( B 1 ( ϵ 1 ) ⋆ ⋯ ⋆ B r ( ϵ r ) ) \Omega_{\bar{\epsilon}}=U(B_1^{(\epsilon_1)}\star\cdots\star B_r^{(\epsilon_r)}) Ω ϵ ˉ = U ( B 1 ( ϵ 1 ) ⋆ ⋯ ⋆ B r ( ϵ r ) ) . Then the following statements hold.
(i) Two components Ω ϵ ˉ \Omega_{\bar{\epsilon}} Ω ϵ ˉ and Ω η ˉ \Omega_{\bar{\eta}} Ω η ˉ are isomorphic if and only if ϵ ˉ \bar{\epsilon} ϵ ˉ and η ˉ \bar{\eta} η ˉ lie in the same orbit of W \mathbb{W} W on Q r Q_r Q r .
(ii) For each ϵ ˉ ∈ Q r \bar{\epsilon}\in Q_r ϵ ˉ ∈ Q r , Aut ( Ω ϵ ˉ ) ≅ Stab W ( ϵ ˉ ) \operatorname{Aut}(\Omega_{\bar{\epsilon}})\cong\operatorname{Stab}_{\mathbb{W}}(\bar{\epsilon}) Aut ( Ω ϵ ˉ ) ≅ Stab W ( ϵ ˉ ) .
(iii) Write Q r / W Q_r/\mathbb{W} Q r / W for the set of orbits of W \mathbb{W} W on Q r Q_r Q r . If O O O runs through these orbits and one representative ϵ ˉ O ∈ O \bar{\epsilon}_O\in O ϵ ˉ O ∈ O is chosen for each orbit, then
Aut ( P ) ≅ ∏ O ∈ Q r / W ( Stab W ( ϵ ˉ O ) ≀ S ∣ O ∣ ) . \operatorname{Aut}(P)\cong\prod_{O\in Q_r/\mathbb{W}}\left(\operatorname{Stab}_{\mathbb{W}}(\bar{\epsilon}_O)\wr S_{\lvert O\rvert}\right). Aut ( P ) ≅ O ∈ Q r / W ∏ ( Stab W ( ϵ ˉ O ) ≀ S ∣ O ∣ ) . (iv) Let F 1 , … , F q F_1,\ldots,F_q F 1 , … , F q be representatives of the pairwise nonisomorphic underlying graphs occurring among U ( B 1 ) , … , U ( B r ) U(B_1),\ldots,U(B_r) U ( B 1 ) , … , U ( B r ) . Let J λ = { i : U ( B i ) ≅ F λ } J_\lambda=\{i:U(B_i)\cong F_\lambda\} J λ = { i : U ( B i ) ≅ F λ } and t λ = ∣ J λ ∣ t_\lambda=\lvert J_\lambda\rvert t λ = ∣ J λ ∣ . Then
W ≅ ∏ λ = 1 q ( Aut ( F λ ) ≀ S t λ ) . (28) \mathbb{W}\cong\prod_{\lambda=1}^{q}\left(\operatorname{Aut}(F_\lambda)\wr S_{t_\lambda}\right). \tag*{(28)} W ≅ λ = 1 ∏ q ( Aut ( F λ ) ≀ S t λ ) . (28)
Proof. Since each B i B_i B i is connected, twin-free, nonunit, and f f f -prime, choose the factorization consisting only of B i B_i B i , with θ i = id B i \theta_i=\operatorname{id}_{B_i} θ i = id B i in (7) . Then N = r N=r N = r , I i = { i } I_i=\{i\} I i = { i } and C i = B i C_i=B_i C i = B i . For ϵ ∈ F 2 r \epsilon\in\mathbb{F}_2^r ϵ ∈ F 2 r , the i i i -th coordinate of d ( ϵ ) d(\epsilon) d ( ϵ ) is then ϵ i \epsilon_i ϵ i , so both d d d and d ˉ \bar{d} d ˉ are identity maps. Every vector is constant on each singleton block. Hence L I = Q r \mathcal{L}_{\mathcal{I}}=Q_r L I = Q r . Since each θ i \theta_i θ i is the identity and each block contains one coordinate, the map Θ \Theta Θ is also the identity. Thus, Λ ϵ ˉ = Ω ϵ ˉ \Lambda_{\bar{\epsilon}}=\Omega_{\bar{\epsilon}} Λ ϵ ˉ = Ω ϵ ˉ and Θ ϵ ˉ = id Ω ϵ ˉ \Theta_{\bar{\epsilon}}=\operatorname{id}_{\Omega_{\bar{\epsilon}}} Θ ϵ ˉ = id Ω ϵ ˉ . Moreover, W ~ = W \widetilde{\mathbb{W}}=\mathbb{W} W = W and their actions on Q r Q_r Q r agree. Theorem 1.6 therefore applies. Parts (ii), (iii), (iv) and (v) of Theorem 1.6 establish parts (i), (ii), (iii) and (iv), respectively. □ \square □
The next corollary treats pairwise nonisomorphic factors and permits one unit factor. Its notation is local to the corollary and the following remark.
Corollary 4.3. Let r ≥ 1 r \ge1 r ≥ 1 , and let B 1 , … , B r B_1,\ldots,B_r B 1 , … , B r be connected twin-free ordered bipartite graphs with pairwise nonisomorphic underlying graphs. Assume each B i B_i B i is either K 2 K_2 K 2 or a nonunit f f f -prime graph. Put B = ( B 1 , … , B r ) \mathbf{B}=(B_1,\ldots,B_r) B = ( B 1 , … , B r ) and P = ∏ i U ( B i ) \mathbf{P}=\prod_i \mathrm{U}(B_i) P = ∏ i U ( B i ) , and define
G B = { ( g i ) i : g i ∈ Aut ( U ( B i ) ) , χ B 1 ( g 1 ) = ⋯ = χ B r ( g r ) } , \mathcal{G}_{\mathbf{B}}=\{(g_i)_i:g_i\in\operatorname{Aut}(\mathrm{U}(B_i)),\ \chi_{B_1}(g_1)=\cdots=\chi_{B_r}(g_r)\}, G B = {( g i ) i : g i ∈ Aut ( U ( B i )) , χ B 1 ( g 1 ) = ⋯ = χ B r ( g r )} , L B = ⟨ e ˉ i : Aut − ( B i ) ≠ ∅ ⟩ ≤ Q r , L_{\mathbf{B}}=\langle\bar{e}_i:\operatorname{Aut}^{-}(B_i)\ne\varnothing\rangle\le Q_r, L B = ⟨ e ˉ i : Aut − ( B i ) = ∅ ⟩ ≤ Q r , where e ˉ i \bar{e}_i e ˉ i is the i i i -th standard basis vector and an empty set of generators gives L B = 0 L_{\mathbf{B}}=0 L B = 0 . Then the following hold.
(i) For every ϵ ˉ ∈ Q r \bar{\epsilon}\in Q_r ϵ ˉ ∈ Q r , Aut ( Ω ϵ ˉ ) ≅ G B \operatorname{Aut}(\Omega_{\bar{\epsilon}})\cong\mathcal{G}_{\mathbf{B}} Aut ( Ω ϵ ˉ ) ≅ G B .
(ii) Two components Ω ϵ ˉ \Omega_{\bar{\epsilon}} Ω ϵ ˉ and Ω η ˉ \Omega_{\bar{\eta}} Ω η ˉ are isomorphic if and only if η ˉ − ϵ ˉ ∈ L B \bar{\eta}-\bar{\epsilon}\in L_{\mathbf{B}} η ˉ − ϵ ˉ ∈ L B .
(iii) Each coset of L B L_{\mathbf{B}} L B indexes one isomorphism class of ∣ L B ∣ |L_{\mathbf{B}}| ∣ L B ∣ components, and
Aut ( P ) ≅ ∏ O ∈ Q r / L B ( G B ≀ S ∣ L B ∣ ) . (29) \operatorname{Aut}(P)\cong\prod_{\mathcal{O}\in Q_r/L_{\mathbf{B}}}\left(\mathcal{G}_{\mathbf{B}}\wr S_{|L_{\mathbf{B}}|}\right). \tag*{(29)} Aut ( P ) ≅ O ∈ Q r / L B ∏ ( G B ≀ S ∣ L B ∣ ) . (29)
Proof. We first assume that no factor is K 2 K_2 K 2 . Since every factor is connected, twin-free, nonunit, and f f f -prime, Corollary 4.2 applies. If w σ , f ∈ W w_{\sigma,f}\in\mathcal{W} w σ , f ∈ W , then U ( B i ) ≅ U ( B σ ( i ) ) \mathrm{U}(B_i)\cong\mathrm{U}(B_{\sigma(i)}) U ( B i ) ≅ U ( B σ ( i ) ) for every i i i . By pairwise nonisomorphism, σ ( i ) = i \sigma(i)=i σ ( i ) = i . Conversely, arbitrary automorphisms of the individual factors act coordinatewise. Thus, as a group of permutations of V ( P ) V(P) V ( P ) ,
W = ∏ i = 1 r Aut ( U ( B i ) ) . \mathcal{W}=\prod_{i=1}^{r}\operatorname{Aut}(\mathrm{U}(B_i)). W = i = 1 ∏ r Aut ( U ( B i )) .
For g = ( g 1 , … , g r ) \mathbf{g}=(g_1,\ldots,g_r) g = ( g 1 , … , g r ) , define its colour sign vector by s ( g ) = ( χ B i ( g i ) ) i = 1 r ∈ F 2 r \mathbf{s}(\mathbf{g})=(\chi_{B_i}(g_i))_{i=1}^{r}\in\mathbb{F}_2^r s ( g ) = ( χ B i ( g i ) ) i = 1 r ∈ F 2 r . This map is a homomorphism into the additive group F 2 r \mathbb{F}_2^r F 2 r . By Eq. (6) , g ⋅ ϵ ˉ = ϵ ˉ + s ( g ) \mathbf{g}\cdot\bar{\epsilon}=\bar{\epsilon}+\mathbf{s}(\mathbf{g}) g ⋅ ϵ ˉ = ϵ ˉ + s ( g ) .
(i). A tuple g \mathbf{g} g fixes ϵ ˉ \bar{\epsilon} ϵ ˉ if and only if s ( g ) = 0 \mathbf{s}(\mathbf{g})=0 s ( g ) = 0 . Since the kernel of F 2 r → Q r \mathbb{F}_2^r\to Q_r F 2 r → Q r is ⟨ 1 r ⟩ \langle\mathbf{1}_r\rangle ⟨ 1 r ⟩ , s ( g ) = 0 \mathbf{s}(\mathbf{g})=0 s ( g ) = 0 means s ( g ) = 0 \mathbf{s}(\mathbf{g})=0 s ( g ) = 0 or s ( g ) = 1 r \mathbf{s}(\mathbf{g})=\mathbf{1}_r s ( g ) = 1 r . These alternatives are equivalent to g i ∈ Aut + ( B i ) g_i\in\operatorname{Aut}^{+}(B_i) g i ∈ Aut + ( B i ) for every i i i , or g i ∈ Aut − ( B i ) g_i\in\operatorname{Aut}^{-}(B_i) g i ∈ Aut − ( B i ) for every i i i , respectively. Thus Stab W ( ϵ ˉ ) = ( ∏ i Aut + ( B i ) ) ∪ ( ∏ i Aut − ( B i ) ) = G B \operatorname{Stab}_{\mathcal{W}}(\bar{\epsilon})=\left(\prod_i\operatorname{Aut}^{+}(B_i)\right)\cup\left(\prod_i\operatorname{Aut}^{-}(B_i)\right)=\mathcal{G}_{\mathbf{B}} Stab W ( ϵ ˉ ) = ( ∏ i Aut + ( B i ) ) ∪ ( ∏ i Aut − ( B i ) ) = G B . Since Stab W ( ϵ ˉ ) \operatorname{Stab}_{\mathcal{W}}(\bar{\epsilon}) Stab W ( ϵ ˉ ) is the kernel of g ↦ s ( g ) \mathbf{g}\mapsto\mathbf{s}(\mathbf{g}) g ↦ s ( g ) , the indicated union is a subgroup. If some Aut − ( B i ) \operatorname{Aut}^{-}(B_i) Aut − ( B i ) is empty, the second alternative is impossible. By Corollary 4.2(ii), restriction induces the asserted isomorphism.
If one factor, say B r B_r B r , is K 2 K_2 K 2 and r ≥ 2 r\ge2 r ≥ 2 , deleting its coordinate identifies each component with the corresponding fibre product of the remaining factors. The preceding argument determines its automorphism group. Each such automorphism has a common coordinate sign and extends uniquely to the omitted coordinate by the automorphism of K 2 K_2 K 2 with that sign. This again identifies the component automorphism group with G B \mathcal{G}_{\mathbf{B}} G B . If r = 1 r=1 r = 1 and B 1 = K 2 B_1=K_2 B 1 = K 2 , the assertion follows from G B = Aut ( K 2 ) \mathcal{G}_{\mathbf{B}}=\operatorname{Aut}(K_2) G B = Aut ( K 2 ) .
(ii). Suppose first that
φ : Ω ϵ ˉ ⟶ Ω η ˉ \varphi:\Omega_{\bar{\epsilon}}\longrightarrow\Omega_{\bar{\eta}} φ : Ω ϵ ˉ ⟶ Ω η ˉ
is an ordinary isomorphism.
If no factor is K 2 K_2 K 2 , then Corollary 3.4 and the pairwise nonisomorphism of the underlying factors imply that there are graph automorphisms g i ∈ Aut ( U ( B i ) ) g_i\in\operatorname{Aut}(\mathrm{U}(B_i)) g i ∈ Aut ( U ( B i )) and one sign δ ∈ F 2 \delta\in\mathbb{F}_2 δ ∈ F 2 such that for every 1 ≤ i ≤ r 1\le i\le r 1 ≤ i ≤ r
η i = ϵ i + χ B i ( g i ) + δ . (30) \eta_i=\epsilon_i+\chi_{B_i}(g_i)+\delta. \tag*{(30)} η i = ϵ i + χ B i ( g i ) + δ . (30)
If one factor, say B r B_r B r , is K 2 K_2 K 2 , first omit it from both fibre products and apply Corollary 3.4 to the remaining nonunit factors. By pairwise nonisomorphism, the factor permutation must be the identity. Thus, when r ≥ 2 r\ge2 r ≥ 2 , there are automorphisms g i ∈ Aut ( U ( B i ) ) g_i\in\operatorname{Aut}(\mathrm{U}(B_i)) g i ∈ Aut ( U ( B i )) for 1 ≤ i ≤ r − 1 1\le i\le r-1 1 ≤ i ≤ r − 1 and a sign δ ∈ F 2 \delta\in\mathbb{F}_2 δ ∈ F 2 such that η i = ϵ i + χ B i ( g i ) + δ \eta_i=\epsilon_i+\chi_{B_i}(g_i)+\delta η i = ϵ i + χ B i ( g i ) + δ . In the unit case r = 1 r=1 r = 1 , choose δ = 0 \delta=0 δ = 0 . No nonunit coordinates occur in this case. Define s r = η r + ϵ r + δ ∈ F 2 s_r=\eta_r+\epsilon_r+\delta\in\mathbb{F}_2 s r = η r + ϵ r + δ ∈ F 2 . Since K 2 K_2 K 2 has a unique automorphism of each sign, choose g r ∈ Aut ( K 2 ) g_r\in\operatorname{Aut}(K_2) g r ∈ Aut ( K 2 ) with χ K 2 ( g r ) = s r \chi_{K_2}(g_r)=s_r χ K 2 ( g r ) = s r . Then Eq. (30) also holds for i = r i=r i = r . Let s = ( χ B 1 ( g 1 ) , … , χ B r ( g r ) ) \mathbf{s}=(\chi_{B_1}(g_1),\ldots,\chi_{B_r}(g_r)) s = ( χ B 1 ( g 1 ) , … , χ B r ( g r )) . By Eq. (30) , η ˉ − ϵ ˉ = s + δ 1 r \bar{\boldsymbol{\eta}}-\bar{\boldsymbol{\epsilon}}=\mathbf{s}+\delta\mathbf{1}_r η ˉ − ϵ ˉ = s + δ 1 r . Passing to the quotient by ⟨ 1 r ⟩ \langle\mathbf{1}_r\rangle ⟨ 1 r ⟩ , we obtain η ˉ − ϵ ˉ = s ˉ \bar{\boldsymbol{\eta}}-\bar{\boldsymbol{\epsilon}}=\bar{\mathbf{s}} η ˉ − ϵ ˉ = s ˉ . The coordinate s i s_i s i is 1 only if Aut − ( B i ) ≠ ∅ \operatorname{Aut}^{-}(B_i)\ne\varnothing Aut − ( B i ) = ∅ , so s ˉ ∈ L B \bar{\mathbf{s}}\in L_B s ˉ ∈ L B . This proves the necessity.
Conversely, assume η ˉ − ϵ ˉ ∈ L B \bar{\boldsymbol{\eta}}-\bar{\boldsymbol{\epsilon}}\in L_B η ˉ − ϵ ˉ ∈ L B . By the definition of L B L_B L B , choose a vector s = ( s 1 , … , s r ) ∈ F 2 r \mathbf{s}=(s_1,\ldots,s_r)\in\mathbb{F}_2^r s = ( s 1 , … , s r ) ∈ F 2 r representing this difference such that s i = 1 s_i=1 s i = 1 only for indices i i i with Aut − ( B i ) ≠ ∅ \operatorname{Aut}^{-}(B_i)\ne\varnothing Aut − ( B i ) = ∅ . For each i i i , choose g i ∈ Aut + ( B i ) g_i\in\operatorname{Aut}^{+}(B_i) g i ∈ Aut + ( B i ) if s i = 0 s_i=0 s i = 0 and g i ∈ Aut − ( B i ) g_i\in\operatorname{Aut}^{-}(B_i) g i ∈ Aut − ( B i ) otherwise. The coordinatewise map g = ( g 1 , … , g r ) \mathbf{g}=(g_1,\ldots,g_r) g = ( g 1 , … , g r ) is an automorphism of P P P . A vertex x = ( x 1 , … , x r ) \mathbf{x}=(x_1,\ldots,x_r) x = ( x 1 , … , x r ) of Ω ϵ \Omega_{\boldsymbol{\epsilon}} Ω ϵ has coordinate colour vector ϵ + t 1 r \boldsymbol{\epsilon}+t\mathbf{1}_r ϵ + t 1 r for some t ∈ F 2 t\in\mathbb{F}_2 t ∈ F 2 . The vertex g ( x ) \mathbf{g}(\mathbf{x}) g ( x ) has coordinate colour vector ϵ + s + t 1 r \boldsymbol{\epsilon}+\mathbf{s}+t\mathbf{1}_r ϵ + s + t 1 r , whose class in Q r Q_r Q r is η ˉ \bar{\boldsymbol{\eta}} η ˉ . Hence the restriction of g \mathbf{g} g is an ordinary isomorphism from Ω ϵ \Omega_{\boldsymbol{\epsilon}} Ω ϵ onto Ω η \Omega_{\boldsymbol{\eta}} Ω η . This proves part (ii).
(iii). By part (ii), the isomorphism class containing Ω ϵ \Omega_{\boldsymbol{\epsilon}} Ω ϵ is indexed by the coset ϵ ˉ + L B \bar{\boldsymbol{\epsilon}}+L_B ϵ ˉ + L B . Since every coset has ∣ L B ∣ |L_B| ∣ L B ∣ elements, this isomorphism class consists of ∣ L B ∣ |L_B| ∣ L B ∣ connected components. By part (i), the automorphism group of each of these components is G B \mathcal{G}_B G B . For a graph consisting of m m m disjoint copies of a connected graph Σ \Sigma Σ , fix an isomorphism from each copy to Σ \Sigma Σ . An automorphism may then act independently by an element of Aut ( Σ ) \operatorname{Aut}(\Sigma) Aut ( Σ ) on every copy and may also permute the m m m copies. The chosen isomorphisms realize these permutations as automorphisms, and conjugation permutes the m m m coordinate groups. Hence its automorphism group is
Aut ( Σ ) m ⋊ S m = Aut ( Σ ) ≀ S m . \operatorname{Aut}(\Sigma)^m\rtimes S_m=\operatorname{Aut}(\Sigma)\wr S_m. Aut ( Σ ) m ⋊ S m = Aut ( Σ ) ≀ S m .
Automorphisms cannot interchange nonisomorphic connected components. The full automorphism group is therefore the direct product of the groups associated with the different component isomorphism classes. Substituting Σ = Ω ϵ \Sigma=\Omega_{\boldsymbol{\epsilon}} Σ = Ω ϵ and m = ∣ L B ∣ m=|L_B| m = ∣ L B ∣ , we obtain Eq. (29) . This proves part (iii) and completes the proof. □
Remark 4.4. Under the hypotheses of Corollary 4.3, if every factor has a colour-reversing automorphism, then L B = Q r L_B=Q_r L B = Q r . All 2 r − 1 2^{r-1} 2 r − 1 components are isomorphic and Aut ( P ) ≅ G B ≀ S 2 r − 1 \operatorname{Aut}(P)\cong\mathcal{G}_B\wr S_{2^{r-1}} Aut ( P ) ≅ G B ≀ S 2 r − 1 . In general Aut − ( B i ) \operatorname{Aut}^{-}(B_i) Aut − ( B i ) is a coset, not a subgroup. Neither this formula nor the definition of G B \mathcal{G}_B G B assumes a colour-reversing involution or a splitting of the individual sign homomorphisms.
Perducts of fibre powers.
We now apply Theorem 1.6 to products of fibre powers of a single f f f -prime graph. The answer depends on whether this graph admits a colour-reversing automorphism. For an ordered bipartite graph B B B and an integer t ≥ 1 t\ge1 t ≥ 1 , write B ⋆ t = ⋆ k = 1 t B B^{\star t}=\star_{k=1}^{t}B B ⋆ t = ⋆ k = 1 t B . Given positive integers m 1 , … , m r m_1,\ldots,m_r m 1 , … , m r , with r ≥ 1 r\ge1 r ≥ 1 , put
m = ( m 1 , … , m r ) , N = ∑ i = 1 r m i , P m = ∏ i = 1 r U ( B ⋆ m i ) . \mathbf{m}=(m_1,\ldots,m_r),\qquad N=\sum_{i=1}^{r}m_i,\qquad P_{\mathbf{m}}=\prod_{i=1}^{r}\mathop{\mathrm{U}}(B^{\star m_i}). m = ( m 1 , … , m r ) , N = i = 1 ∑ r m i , P m = i = 1 ∏ r U ( B ⋆ m i ) .
For each 1 ≤ j ≤ ⌊ N / 2 ⌋ 1\le j\le\lfloor N/2\rfloor 1 ≤ j ≤ ⌊ N /2 ⌋ , define
ν j = { [ z j ] ∏ i = 1 r ( 1 + z m i ) , 2 j < N , 1 2 [ z j ] ∏ i = 1 r ( 1 + z m i ) , 2 j = N . (31) \nu_j=
\begin{cases}
[z^j]\prod_{i=1}^{r}(1+z^{m_i}), & 2j<N,\\[6pt]
\frac{1}{2}[z^j]\prod_{i=1}^{r}(1+z^{m_i}), & 2j=N.
\end{cases} \tag*{(31)} ν j = ⎩ ⎨ ⎧ [ z j ] ∏ i = 1 r ( 1 + z m i ) , 2 1 [ z j ] ∏ i = 1 r ( 1 + z m i ) , 2 j < N , 2 j = N . (31)
where [ z j ] [z^j] [ z j ] denotes the coefficient of z j z^j z j . In particular, ν 0 = 1 \nu_0=1 ν 0 = 1 since every m i m_i m i is positive.
Corollary 4.5. Let B B B be a connected twin-free nonunit f f f -prime ordered bipartite graph, and set A B = Aut ( U ( B ) ) A_B=\operatorname{Aut}(\mathrm{U}(B)) A B = Aut ( U ( B )) . For r ≥ 1 r\ge1 r ≥ 1 and positive m 1 , … , m r m_1,\ldots,m_r m 1 , … , m r , use the notation above.
(i) If Aut − ( B ) ≠ ∅ \operatorname{Aut}^{-}(B)\ne\varnothing Aut − ( B ) = ∅ , the 2 r − 1 2^{r-1} 2 r − 1 connected components of P m P_{\mathbf{m}} P m are all isomorphic to U ( B ⋆ N ) \mathrm{U}(B^{\star N}) U ( B ⋆ N ) , and
Aut ( P m ) ≅ [ ( Aut + ( B ) N ∪ Aut − ( B ) N ) ⋊ S N ] ≀ S 2 r − 1 . (32) \operatorname{Aut}(P_{\mathbf{m}})\cong\left[\left(\operatorname{Aut}^{+}(B)^N\cup\operatorname{Aut}^{-}(B)^N\right)\rtimes S_N\right]\wr S_{2^{r-1}}. \tag*{(32)} Aut ( P m ) ≅ [ ( Aut + ( B ) N ∪ Aut − ( B ) N ) ⋊ S N ] ≀ S 2 r − 1 . (32) Here the union consists of tuples whose coordinate maps have a common colour sign, and S N S_N S N acts by permuting the coordinates.
(ii) If Aut − ( B ) = ∅ \operatorname{Aut}^{-}(B)=\varnothing Aut − ( B ) = ∅ , the indices j j j with ν j > 0 \nu_j>0 ν j > 0 parametrize all component isomorphism classes. Class j j j has ν j \nu_j ν j components, each with automorphism group
H j = { ( A B ≀ S j ) × ( A B ≀ S N − j ) , 2 j < N , ( A B ≀ S j ) ≀ S 2 , 2 j = N . (33) \mathcal{H}_j=
\begin{cases}
(A_B\wr S_j)\times(A_B\wr S_{N-j}), & 2j<N,\\
(A_B\wr S_j)\wr S_2, & 2j=N.
\end{cases} \tag*{(33)} H j = { ( A B ≀ S j ) × ( A B ≀ S N − j ) , ( A B ≀ S j ) ≀ S 2 , 2 j < N , 2 j = N . (33)
Consequently,
Aut ( P m ) ≅ ∏ 0 ≤ j ≤ ⌊ N / 2 ⌋ ν j > 0 ( H j ≀ S ν j ) . (34) \operatorname{Aut}(P_m)\cong\prod_{\substack{0\leq j\leq\lfloor N/2\rfloor\\ \nu_j>0}}(\mathcal{H}_j\wr S_{\nu_j}). \tag*{(34)} Aut ( P m ) ≅ 0 ≤ j ≤ ⌊ N /2 ⌋ ν j > 0 ∏ ( H j ≀ S ν j ) . (34)
Proof. Each B ⋆ m i B^{\star m_i} B ⋆ m i is connected and twin-free by Lemmas 2.2 and 2.4 . Its two colour classes have sizes ∣ B 0 ∣ m i |B^0|^{m_i} ∣ B 0 ∣ m i and ∣ B 1 ∣ m i |B^1|^{m_i} ∣ B 1 ∣ m i , both at least two by Lemma 2.1 , so it is nonunit. Refine the i i i -th original factor into m i m_i m i copies of B B B on a block I i I_i I i . Theorem 1.6 applies, with W ~ ≅ A B N ⋊ S N \widetilde{W}\cong A_B^N\rtimes S_N W ≅ A B N ⋊ S N . The selected components correspond to the 2 r − 1 2^{r-1} 2 r − 1 labels in L I \mathcal{L}_I L I , represented by vectors constant on each block.
First consider a single fibre power. A factor symmetry fixes the zero label in Q t Q_t Q t exactly when its sign vector is 0 t \mathbf{0}_t 0 t or 1 t \mathbf{1}_t 1 t . Its coordinate maps therefore lie in Aut + ( B ) t ∪ Aut − ( B ) t \operatorname{Aut}^{+}(B)^t\cup\operatorname{Aut}^{-}(B)^t Aut + ( B ) t ∪ Aut − ( B ) t . This is a subgroup, being the inverse image of ⟨ 1 t ⟩ \langle\mathbf{1}_t\rangle ⟨ 1 t ⟩ under the coordinate sign homomorphism. Coordinate permutations normalize it and give a complement in the stabilizer. Theorem 1.6 (iii) gives
Aut ( U ( B ⋆ t ) ) ≅ ( Aut + ( B ) t ∪ Aut − ( B ) t ) ⋊ S t . (35) \operatorname{Aut}(U(B^{\star t}))\cong\left(\operatorname{Aut}^{+}(B)^t\cup\operatorname{Aut}^{-}(B)^t\right)\rtimes S_t. \tag*{(35)} Aut ( U ( B ⋆ t )) ≅ ( Aut + ( B ) t ∪ Aut − ( B ) t ) ⋊ S t . (35)
This includes t = 1 t=1 t = 1 ; the second set is empty if Aut − ( B ) = ∅ \operatorname{Aut}^{-}(B)=\varnothing Aut − ( B ) = ∅ .
(i). Choose γ ∈ Aut − ( B ) \gamma\in\operatorname{Aut}^{-}(B) γ ∈ Aut − ( B ) . For any a ∈ F 2 N \mathbf{a}\in\mathbb{F}_2^N a ∈ F 2 N , apply γ \gamma γ where a k = 1 a_k=1 a k = 1 and the identity elsewhere. Equation (6) sends the zero label to a ‾ \overline{\mathbf{a}} a , so the ambient action on Q N Q_N Q N is transitive. All selected components are therefore isomorphic to the zero component U ( B ⋆ N ) U(B^{\star N}) U ( B ⋆ N ) . Its group is given by Eq. (35) ; Theorem 1.6 (iv) assembles the 2 r − 1 2^{r-1} 2 r − 1 copies and proves Eq. (32) .
(ii). Every factor automorphism now preserves colours, so A B N A_B^N A B N fixes all labels and the action is induced by S N S_N S N . For a binary vector a \mathbf{a} a , let ∣ a ∣ |\mathbf{a}| ∣ a ∣ be its Hamming weight. The value j = min { ∣ a ∣ , N − ∣ a ∣ } j=\min\{|\mathbf{a}|,N-|\mathbf{a}|\} j = min { ∣ a ∣ , N − ∣ a ∣ } is unchanged by coordinate permutations and by replacing a representative with its complement. Conversely, labels with the same value have representatives of weight j j j , and a bijection of their supports extends to a coordinate permutation. Thus this value classifies the ambient orbits. For an original component with label ϵ \boldsymbol{\epsilon} ϵ , its value is
j = min { ∑ i = 1 r m i ϵ i , N − ∑ i = 1 r m i ϵ i } . j=\min\left\{\sum_{i=1}^{r}m_i\epsilon_i,N-\sum_{i=1}^{r}m_i\epsilon_i\right\}. j = min { i = 1 ∑ r m i ϵ i , N − i = 1 ∑ r m i ϵ i } .
To count the selected labels in an orbit, choose the blocks on which an admissible representative equals one. Its weight is the sum of their sizes, so [ z j ] ∏ i ( 1 + z m i ) [z^j]\prod_i(1+z^{m_i}) [ z j ] ∏ i ( 1 + z m i ) counts those representatives. Distinct subsets of blocks count separately even when some sizes agree. A quotient label has two complementary representatives. If 2 j < N 2j<N 2 j < N , exactly one has weight j j j ; if 2 j = N 2j=N 2 j = N , both have that weight. Complementation has no fixed binary vector, so the middle coefficient is even. Thus the orbit intersection has size ν j \nu_j ν j , and these intersections partition the selected labels. In particular ∑ j ν j = 2 r − 1 \sum_j\nu_j=2^{r-1} ∑ j ν j = 2 r − 1 , including the zero-labelled type.
For the stabilizer, choose a representative of weight j j j with support T ⊆ { 1 , … , N } T\subseteq\{1,\ldots,N\} T ⊆ { 1 , … , N } . A coordinate permutation fixes its quotient label exactly when it maps T T T to T T T or to T c T^c T c . If 2 j < N 2j<N 2 j < N , the unequal sizes exclude interchange. Independent coordinate maps and permutations on the two sets give ( A B ≀ S j ) × ( A B ≀ S N − j ) (A_B\wr S_j)\times(A_B\wr S_{N-j}) ( A B ≀ S j ) × ( A B ≀ S N − j ) . If 2 j = N 2j=N 2 j = N , a fixed bijection T → T c T\to T^c T → T c , extended by its inverse, gives a coordinate involution. The subgroup preserving both sets is ( A B ≀ S j ) 2 (A_B\wr S_j)^2 ( A B ≀ S j ) 2 , and conjugation by this involution exchanges its two factors. Every set-interchanging symmetry is the involution times a set-preserving symmetry. Hence the stabilizer is ( A B ≀ S j ) ≀ S 2 (A_B\wr S_j)\wr S_2 ( A B ≀ S j ) ≀ S 2 . This interchange concerns coordinate positions, not a colour reversal of the individual factor B B B .
Theorem 1.6(iii)–(iv) now gives the groups in Eq. (33) and the product in Eq. (34) . The calculation uses ambient orbits intersected with L I \mathcal{L}_{\mathcal{I}} L I . When r = 1 r=1 r = 1 , only the type j = 0 j=0 j = 0 is selected, so the formula also agrees with Eq. (35) for a single fibre power. □ \square □
The direct product power U ( B ) × r \mathrm{U}(B)^{\times r} U ( B ) × r is obtained by taking m 1 = ⋯ = m r = 1 m_1=\cdots=m_r=1 m 1 = ⋯ = m r = 1 . Then N = r N=r N = r and ν j = ( r j ) \nu_j=\binom{r}{j} ν j = ( j r ) for 2 j < r 2j<r 2 j < r , while ν r / 2 = 1 2 ( r r / 2 ) \nu_{r/2}=\frac{1}{2}\binom{r}{r/2} ν r /2 = 2 1 ( r /2 r ) when r r r is even. In the no-reversal case all these multiplicities are positive, so there are exactly ⌊ r / 2 ⌋ + 1 \lfloor r/2\rfloor+1 ⌊ r /2 ⌋ + 1 component types.
The next example illustrates how unequal block sizes affect the multiplicities.
Example 4.6. Take B = P 5 B=P_5 B = P 5 , with ordered colour classes of sizes 3 and 2. It is connected, twin-free, and four-cycle-free, so Lemma 2.5 makes it f f f -prime. The unequal class sizes exclude colour reversal. Its only automorphisms are the identity and path reflection, giving Aut ( U ( B ) ) ≅ Z 2 \operatorname{Aut}(\mathrm{U}(B))\cong\mathbb{Z}_2 Aut ( U ( B )) ≅ Z 2 . For m = ( 1 , 1 , 2 ) \mathbf{m}=(1,1,2) m = ( 1 , 1 , 2 ) , we have
( 1 + z ) 2 ( 1 + z 2 ) = 1 + 2 z + 2 z 2 + 2 z 3 + z 4 . (1+z)^2(1+z^2)=1+2z+2z^2+2z^3+z^4. ( 1 + z ) 2 ( 1 + z 2 ) = 1 + 2 z + 2 z 2 + 2 z 3 + z 4 .
Thus ν 0 = 1 \nu_0=1 ν 0 = 1 , ν 1 = 2 \nu_1=2 ν 1 = 2 , and ν 2 = 1 \nu_2=1 ν 2 = 1 . The corresponding groups are H 0 = Aut ( U ( B ) ) ≀ S 4 \mathcal{H}_0=\operatorname{Aut}(\mathrm{U}(B))\wr S_4 H 0 = Aut ( U ( B )) ≀ S 4 , H 1 = Aut ( U ( B ) ) × ( Aut ( U ( B ) ) ≀ S 3 ) \mathcal{H}_1=\operatorname{Aut}(\mathrm{U}(B))\times(\operatorname{Aut}(\mathrm{U}(B))\wr S_3) H 1 = Aut ( U ( B )) × ( Aut ( U ( B )) ≀ S 3 ) , and H 2 = ( Aut ( U ( B ) ) ≀ S 2 ) ≀ S 2 \mathcal{H}_2=(\operatorname{Aut}(\mathrm{U}(B))\wr S_2)\wr S_2 H 2 = ( Aut ( U ( B )) ≀ S 2 ) ≀ S 2 . Consequently,
Aut ( P ( 1 , 1 , 2 ) ) ≅ H 0 × ( H 1 ≀ S 2 ) × H 2 . \operatorname{Aut}(P_{(1,1,2)})\cong\mathcal{H}_0\times(\mathcal{H}_1\wr S_2)\times\mathcal{H}_2. Aut ( P ( 1 , 1 , 2 ) ) ≅ H 0 × ( H 1 ≀ S 2 ) × H 2 .
Stability of graph pairs
The next result determines the full group behind the stability equivalence. The equivalence is also a consequence of the factor-loopless theorem of Wang and Gao [28 ] ; the relation between the hypotheses is explained below.
Corollary 4.7. Let X X X be a finite connected nonbipartite twin-free graph such that D ( X ) D(X) D ( X ) is f f f -prime with its natural ordered bipartition. Let B B B be a connected twin-free nonunit f f f -prime ordered bipartite graph, and suppose U ( B ) ≇ D ( X ) \mathrm{U}(B)\not\cong D(X) U ( B ) ≅ D ( X ) . Let χ B \chi_B χ B be the colour-sign homomorphism. Then
Aut ( X × U ( B ) ) ≅ Aut + ( D ( X ) ) ⋊ ε B Aut ( U ( B ) ) , (36) \operatorname{Aut}(X\times\mathrm{U}(B))\cong\operatorname{Aut}^{+}(D(X))\rtimes_{\varepsilon_B}\operatorname{Aut}(\mathrm{U}(B)), \tag*{(36)} Aut ( X × U ( B )) ≅ Aut + ( D ( X )) ⋊ ε B Aut ( U ( B )) , (36)
where
ε B ( g ) ( h ) = κ X χ B ( g ) h κ X − χ B ( g ) \varepsilon_B(g)(h)=\kappa_X^{\chi_B(g)}h\kappa_X^{-\chi_B(g)} ε B ( g ) ( h ) = κ X χ B ( g ) h κ X − χ B ( g )
for g ∈ Aut ( U ( B ) ) g\in\operatorname{Aut}(\mathrm{U}(B)) g ∈ Aut ( U ( B )) and h ∈ Aut + ( D ( X ) ) h\in\operatorname{Aut}^{+}(D(X)) h ∈ Aut + ( D ( X )) . Moreover, ( X , U ( B ) ) (X,\mathrm{U}(B)) ( X , U ( B )) is stable if and only if X X X is stable.
Proof. Fix the ordered bipartition V ( B ) = B 0 ⊔ B 1 V(B)=B^0\sqcup B^1 V ( B ) = B 0 ⊔ B 1 . Recall that D ( X ) = X × K 2 D(X)=X\times K_2 D ( X ) = X × K 2 is the canonical double cover of X X X , with ordered bipartition D ( X ) 0 = V ( X ) × { 0 } D(X)^0=V(X)\times\{0\} D ( X ) 0 = V ( X ) × { 0 } and D ( X ) 1 = V ( X ) × { 1 } D(X)^1=V(X)\times\{1\} D ( X ) 1 = V ( X ) × { 1 } . Define
Φ : U ( D ( X ) ⋆ B ) ⟶ X × U ( B ) \Phi:\mathrm{U}(D(X)\star B)\longrightarrow X\times\mathrm{U}(B) Φ : U ( D ( X ) ⋆ B ) ⟶ X × U ( B )
by Φ ( ( x , i ) , b ) = ( x , b ) \Phi((x,i),b)=(x,b) Φ (( x , i ) , b ) = ( x , b ) , for b ∈ B i b\in B^i b ∈ B i and ( x , i ) ∈ V ( D ( X ) ) (x,i)\in V(D(X)) ( x , i ) ∈ V ( D ( X )) . We first verify that Φ \Phi Φ is a graph isomorphism. For each ( x , b ) ∈ V ( X ) × V ( B ) (x,b)\in V(X)\times V(B) ( x , b ) ∈ V ( X ) × V ( B ) , the value i = ϱ B ( b ) i=\varrho_B(b) i = ϱ B ( b ) is uniquely determined. Thus ( ( x , i ) , b ) ((x,i),b) (( x , i ) , b ) is the unique vertex of D ( X ) ⋆ B D(X)\star B D ( X ) ⋆ B mapped to ( x , b ) (x,b) ( x , b ) , so Φ \Phi Φ is bijective.
Moreover, ( ( x , i ) , b ) ((x,i),b) (( x , i ) , b ) is adjacent to ( ( x ′ , 1 − i ) , b ′ ) ((x',1-i),b') (( x ′ , 1 − i ) , b ′ ) in the fibre product if and only if { x , x ′ } ∈ E ( X ) \{x,x'\}\in E(X) { x , x ′ } ∈ E ( X ) and { b , b ′ } ∈ E ( B ) \{b,b'\}\in E(B) { b , b ′ } ∈ E ( B ) . These are precisely the conditions for ( x , b ) (x,b) ( x , b ) and ( x ′ , b ′ ) (x',b') ( x ′ , b ′ ) to be adjacent in the ordinary direct product X × U ( B ) X\times\mathrm{U}(B) X × U ( B ) . Thus Φ \Phi Φ is a graph isomorphism.
Since X X X is connected, twin-free, nonbipartite, D ( X ) = X × K 2 D(X)=X\times K_2 D ( X ) = X × K 2 is connected, bipartite and twin-free. Thus both D ( X ) D(X) D ( X ) and B B B are connected, twin-free, ordered bipartite graphs. By hypothesis, both D ( X ) D(X) D ( X ) and B B B are f f f -prime and D ( X ) ≇ B D(X)\not\cong B D ( X ) ≅ B as underlying graphs. By Corollary 4.3 and the isomorphism Φ \Phi Φ , we have
Aut ( X × U ( B ) ) ≅ G ( D ( X ) , B ) . \operatorname{Aut}(X\times\mathrm{U}(B))\cong\mathcal{G}(D(X),B). Aut ( X × U ( B )) ≅ G ( D ( X ) , B ) .
Recall that G ( D ( X ) , B ) = { ( a , g ) ∈ Aut ( D ( X ) ) × Aut ( U ( B ) ) : χ D ( X ) ( a ) = χ B ( g ) } \mathcal{G}(D(X),B)=\{(a,g)\in\operatorname{Aut}(D(X))\times\operatorname{Aut}(\mathrm{U}(B)):\chi_{D(X)}(a)=\chi_B(g)\} G ( D ( X ) , B ) = {( a , g ) ∈ Aut ( D ( X )) × Aut ( U ( B )) : χ D ( X ) ( a ) = χ B ( g )} . Consider the map ϕ : G ( D ( X ) , B ) ⟶ Aut ( U ( B ) ) \phi:\mathcal{G}(D(X),B)\longrightarrow\operatorname{Aut}(\mathrm{U}(B)) ϕ : G ( D ( X ) , B ) ⟶ Aut ( U ( B )) defined by ϕ ( a , g ) = g \phi(a,g)=g ϕ ( a , g ) = g for ( a , g ) ∈ G ( D ( X ) , B ) (a,g)\in\mathcal{G}(D(X),B) ( a , g ) ∈ G ( D ( X ) , B ) . This is a surjective group homomorphism. Indeed, for every g ∈ Aut ( U ( B ) ) g \in\operatorname{Aut}(\mathrm{U}(B)) g ∈ Aut ( U ( B )) , the covering involution
κ X : ( x , i ) ↦ ( x , 1 − i ) \kappa_X:(x,i)\mapsto(x,1-i) κ X : ( x , i ) ↦ ( x , 1 − i )
has colour sign 1 1 1 , so κ X χ B ( g ) \kappa_X^{\chi_B(g)} κ X χ B ( g ) has the same colour sign as g g g . Hence ( κ X χ B ( g ) , g ) ∈ G ( D ( X ) , B ) (\kappa_X^{\chi_B(g)},g)\in\mathcal{G}(\mathrm{D}(X),B) ( κ X χ B ( g ) , g ) ∈ G ( D ( X ) , B ) , and ϕ ( κ X χ B ( g ) , g ) = g \phi(\kappa_X^{\chi_B(g)},g)=g ϕ ( κ X χ B ( g ) , g ) = g . The kernel of ϕ \phi ϕ consists precisely of the pairs ( h , 1 ) (h,1) ( h , 1 ) for which χ D ( X ) ( h ) = 0 \chi_{\mathrm{D}(X)}(h)=0 χ D ( X ) ( h ) = 0 . Thus ker ( ϕ ) = { ( h , 1 ) : h ∈ Aut + ( D ( X ) ) } \ker(\phi)=\{(h,1):h\in\operatorname{Aut}^{+}(\mathrm{D}(X))\} ker ( ϕ ) = {( h , 1 ) : h ∈ Aut + ( D ( X ))} , and hence ker ( ϕ ) ≅ Aut + ( D ( X ) ) \ker(\phi)\cong\operatorname{Aut}^{+}(\mathrm{D}(X)) ker ( ϕ ) ≅ Aut + ( D ( X )) . We therefore have an exact sequence
1 ⟶ Aut + ( D ( X ) ) ⟶ G ( D ( X ) , B ) → ϕ Aut ( U ( B ) ) ⟶ 1. 1\longrightarrow\operatorname{Aut}^{+}(\mathrm{D}(X))\longrightarrow\mathcal{G}(\mathrm{D}(X),B)\xrightarrow{\phi}\operatorname{Aut}(\mathrm{U}(B))\longrightarrow1. 1 ⟶ Aut + ( D ( X )) ⟶ G ( D ( X ) , B ) ϕ Aut ( U ( B )) ⟶ 1.
To show this exact sequence splits, define
ς : Aut ( U ( B ) ) ⟶ G ( D ( X ) , B ) \varsigma:\operatorname{Aut}(\mathrm{U}(B))\longrightarrow\mathcal{G}(\mathrm{D}(X),B) ς : Aut ( U ( B )) ⟶ G ( D ( X ) , B )
by ς ( g ) = ( κ X χ B ( g ) , g ) \varsigma(g)=(\kappa_X^{\chi_B(g)},g) ς ( g ) = ( κ X χ B ( g ) , g ) . Since χ B \chi_B χ B is a homomorphism and κ X 2 = 1 \kappa_X^2=1 κ X 2 = 1 , we have ς ( g h ) = ς ( g ) ς ( h ) \varsigma(gh)=\varsigma(g)\varsigma(h) ς ( g h ) = ς ( g ) ς ( h ) for all g , h ∈ Aut ( U ( B ) ) g,h\in\operatorname{Aut}(\mathrm{U}(B)) g , h ∈ Aut ( U ( B )) . Moreover, ϕ ( ς ( g ) ) = g \phi(\varsigma(g))=g ϕ ( ς ( g )) = g . Thus ς \varsigma ς is a section of ϕ \phi ϕ . The complement acts on Aut + ( D ( X ) ) \operatorname{Aut}^{+}(\mathrm{D}(X)) Aut + ( D ( X )) by conjugation. For h ∈ Aut + ( D ( X ) ) h\in\operatorname{Aut}^{+}(\mathrm{D}(X)) h ∈ Aut + ( D ( X )) and g ∈ Aut ( U ( B ) ) g\in\operatorname{Aut}(\mathrm{U}(B)) g ∈ Aut ( U ( B )) , we have
ς ( g ) ( h , 1 ) ς ( g ) − 1 = ( κ X χ B ( g ) , g ) ( h , 1 ) ( κ X − χ B ( g ) , g − 1 ) = ( κ X χ B ( g ) h κ X − χ B ( g ) , 1 ) . \varsigma(g)(h,1)\varsigma(g)^{-1}=(\kappa_X^{\chi_B(g)},g)(h,1)(\kappa_X^{-\chi_B(g)},g^{-1})
=(\kappa_X^{\chi_B(g)}h\kappa_X^{-\chi_B(g)},1). ς ( g ) ( h , 1 ) ς ( g ) − 1 = ( κ X χ B ( g ) , g ) ( h , 1 ) ( κ X − χ B ( g ) , g − 1 ) = ( κ X χ B ( g ) h κ X − χ B ( g ) , 1 ) .
Thus the induced action
ε B ( g ) ( h ) = κ X χ B ( g ) h κ X − χ B ( g ) . \varepsilon_B(g)(h)=\kappa_X^{\chi_B(g)}h\kappa_X^{-\chi_B(g)}. ε B ( g ) ( h ) = κ X χ B ( g ) h κ X − χ B ( g ) .
Consequently, Aut ( X × U ( B ) ) ≅ Aut + ( D ( X ) ) ⋊ ε B Aut ( U ( B ) ) \operatorname{Aut}(X\times\mathrm{U}(B))\cong\operatorname{Aut}^{+}(\mathrm{D}(X))\rtimes_{\varepsilon_B}\operatorname{Aut}(\mathrm{U}(B)) Aut ( X × U ( B )) ≅ Aut + ( D ( X )) ⋊ ε B Aut ( U ( B )) .
Now suppose that X X X is stable. Then Aut ( D ( X ) ) = Aut ( X ) × ⟨ κ X ⟩ \operatorname{Aut}(\mathrm{D}(X))=\operatorname{Aut}(X)\times\langle\kappa_X\rangle Aut ( D ( X )) = Aut ( X ) × ⟨ κ X ⟩ , where Aut ( X ) \operatorname{Aut}(X) Aut ( X ) is identified with its natural lift to D ( X ) \mathrm{D}(X) D ( X ) . These lifted automorphisms preserve the two bipartition classes of D ( X ) \mathrm{D}(X) D ( X ) , whereas κ X \kappa_X κ X interchanges them. Therefore Aut + ( D ( X ) ) = Aut ( X ) \operatorname{Aut}^{+}(\mathrm{D}(X))=\operatorname{Aut}(X) Aut + ( D ( X )) = Aut ( X ) .
Every lifted automorphism α \alpha α satisfies κ X α = α κ X \kappa_X\alpha=\alpha\kappa_X κ X α = α κ X , so κ X \kappa_X κ X centralizes Aut + ( D ( X ) ) \operatorname{Aut}^{+}(\mathrm{D}(X)) Aut + ( D ( X )) . Consequently ε B ( g ) ( h ) = h \varepsilon_B(g)(h)=h ε B ( g ) ( h ) = h for every g ∈ Aut ( U ( B ) ) g\in\operatorname{Aut}(\mathrm{U}(B)) g ∈ Aut ( U ( B )) and h ∈ Aut + ( D ( X ) ) h\in\operatorname{Aut}^{+}(\mathrm{D}(X)) h ∈ Aut + ( D ( X )) . Thus the semidirect product in Eq. (36) is a direct product, and Aut ( X × U ( B ) ) ≅ Aut ( X ) × Aut ( U ( B ) ) \operatorname{Aut}(X\times\mathrm{U}(B))\cong\operatorname{Aut}(X)\times\operatorname{Aut}(\mathrm{U}(B)) Aut ( X × U ( B )) ≅ Aut ( X ) × Aut ( U ( B )) .
It remains to identify this isomorphism with the natural coordinatewise action. Under Φ \Phi Φ , an element α ∈ Aut ( X ) \alpha\in\operatorname{Aut}(X) α ∈ Aut ( X ) acts by
( ( x , i ) , b ) ⟼ ( ( α ( x ) , i ) , b ) , ((x,i),b)\longmapsto((\alpha(x),i),b), (( x , i ) , b ) ⟼ (( α ( x ) , i ) , b ) ,
which corresponds to ( x , b ) ⟼ ( α ( x ) , b ) (x,b)\longmapsto(\alpha(x),b) ( x , b ) ⟼ ( α ( x ) , b ) . The element ς ( g ) = ( κ X χ B ( g ) , g ) \varsigma(g)=(\kappa_X^{\chi_B(g)},g) ς ( g ) = ( κ X χ B ( g ) , g ) acts by ( ( x , i ) , b ) ⟼ ( ( x , i + χ B ( g ) ) , g ( b ) ) ((x,i),b)\longmapsto((x,i+\chi_B(g)),g(b)) (( x , i ) , b ) ⟼ (( x , i + χ B ( g )) , g ( b )) . Since ϱ B ( g ( b ) ) = ϱ B ( b ) + χ B ( g ) \varrho_B(g(b))=\varrho_B(b)+\chi_B(g) ϱ B ( g ( b )) = ϱ B ( b ) + χ B ( g ) , the image lies in the fibre product, and Φ \Phi Φ identifies this action with ( x , b ) ⟼ ( x , g ( b ) ) (x,b)\longmapsto(x,g(b)) ( x , b ) ⟼ ( x , g ( b )) . Thus each factor acts naturally on its corresponding coordinate. Therefore, as permutation groups on V ( X ) × V ( B ) V(X)\times V(B) V ( X ) × V ( B ) , Aut ( X × U ( B ) ) = Aut ( X ) × Aut ( U ( B ) ) \operatorname{Aut}(X\times\mathrm{U}(B))=\operatorname{Aut}(X)\times\operatorname{Aut}(\mathrm{U}(B)) Aut ( X × U ( B )) = Aut ( X ) × Aut ( U ( B )) . Hence the graph pair ( X , U ( B ) ) (X,\mathrm{U}(B)) ( X , U ( B )) is stable if X X X is stable. Conversely, if ( X , U ( B ) ) (X,\mathrm{U}(B)) ( X , U ( B )) is stable, by [26 Theorem 1.3(a)] we can obtain that X X X is stable. □
Remark 4.8. The stability equivalence in Corollary 4.7 is covered by [28 Theorem 1.3] . Here is the implication between the hypotheses. If X ≅ A × C X\cong A\times C X ≅ A × C with both factors nonunit, Since C C C is connected and nonbipartite, both A A A and C C C are connected and nonbipartite. The map
( ( a , i ) , ( c , i ) ) ⟼ ( ( a , c ) , i ) ((a,i),(c,i))\longmapsto((a,c),i) (( a , i ) , ( c , i )) ⟼ (( a , c ) , i )
is a colour-preserving isomorphism from D ( A ) ∗ D ( C ) \mathrm{D}(A)*\mathrm{D}(C) D ( A ) ∗ D ( C ) to D ( A × C ) \mathrm{D}(A\times C) D ( A × C ) . It preserves the two edge conditions even when A A A or C C C has loops, and both double covers are nonunit. This contradicts the fact that D \mathrm{D} D is f f f -prime.
Also X X X and U ( B ) \mathrm{U}(B) U ( B ) are directly coprime. Otherwise, Since X X X is prime, U ( B ) ≅ X × Y \mathrm{U}(B)\cong X\times Y U ( B ) ≅ X × Y for a connected bipartite graph Y Y Y . Order the classes of Y Y Y so that this isomorphism preserves the classes of B B B . Deleting the K 2 K_2 K 2 -coordinate gives an isomorphism D ( X ) ∗ Y ≅ B \mathrm{D}(X)*Y\cong B D ( X ) ∗ Y ≅ B . The f f f -primality of B B B forces Y ≅ K 2 Y \cong K_2 Y ≅ K 2 , contrary to U ( B ) ≇ D ( X ) \mathrm{U}(B) \not\cong\mathrm{D}(X) U ( B ) ≅ D ( X ) . The pair is thus nontrivial and X X X is factor-loopless in the terminology of [28 ] . The preceding proof records a direct group calculation in this setting, not an independent new stability theorem.
Automorphism groups of the canonical double covers of bipartite generalized Petersen graphs
We now apply the preceding automorphism formulas to canonical double covers of bipartite generalized Petersen graphs, recovering the bipartite cases of [21 Theorem 1.2(iii)] . Let κ \kappa κ denote the unique nonidentity automorphism of K 2 K_2 K 2 . We begin with the following lemma.
Lemma 4.9. Let B B B be a connected twin-free nonunit fibre prime ordered bipartite graph. Then
Aut ( U ( B ) × K 2 ) ≅ Aut ( U ( B ) ) ≀ S 2 . \operatorname{Aut}(\mathrm{U}(B) \times K_2) \cong\operatorname{Aut}(\mathrm{U}(B)) \wr S_2. Aut ( U ( B ) × K 2 ) ≅ Aut ( U ( B )) ≀ S 2 .
Proof. Equip K 2 K_2 K 2 with the ordered bipartition K 2 0 = { 0 } K_2^0 = \{0\} K 2 0 = { 0 } and K 2 1 = { 1 } K_2^1 = \{1\} K 2 1 = { 1 } , and let κ \kappa κ denote its unique nonidentity automorphism. The projection onto the first coordinate identifies U ( B ⋆ K 2 ) \mathrm{U}(B \star K_2) U ( B ⋆ K 2 ) with U ( B ) \mathrm{U}(B) U ( B ) . The ordinary direct product U ( B ) × K 2 \mathrm{U}(B) \times K_2 U ( B ) × K 2 is the disjoint union of this component and U ( B ⋆ K 2 o p ) \mathrm{U}(B \star K_2^{\mathrm{op}}) U ( B ⋆ K 2 op ) , which is also isomorphic to U ( B ) \mathrm{U}(B) U ( B ) . We apply Corollary 4.3 to the two ordered bipartite factors B 1 = B B_1 = B B 1 = B and B 2 = K 2 B_2 = K_2 B 2 = K 2 . Since B B B is nonunit, B ≇ K 2 B \not\cong K_2 B ≅ K 2 , so the two factors are nonisomorphic. Their sign sets are A 1 0 = Aut + ( B ) A_1^0 = \operatorname{Aut}^{+}(B) A 1 0 = Aut + ( B ) , A 1 1 = Aut − ( B ) A_1^1 = \operatorname{Aut}^{-}(B) A 1 1 = Aut − ( B ) and A 2 0 = { 1 } A_2^0 = \{1\} A 2 0 = { 1 } , A 2 1 = { κ } A_2^1 = \{\kappa\} A 2 1 = { κ } .
The component index group in Corollary 4.3 is Q 2 = F 2 2 / ⟨ ( 1 , 1 ) ⟩ Q_2 = \mathbb{F}_2^2/\langle(1,1)\rangle Q 2 = F 2 2 / ⟨( 1 , 1 )⟩ , which has order 2 2 2 . Since K 2 K_2 K 2 admits the colour interchanging automorphism κ \kappa κ , the second coordinate contributes the generator e ˉ 2 \bar e_2 e ˉ 2 to the subgroup H H H . As e ˉ 2 \bar e_2 e ˉ 2 is the unique nonzero element of Q 2 Q_2 Q 2 , we obtain H = Q 2 H = Q_2 H = Q 2 . Consequently, the two connected components of U ( B ) × K 2 \mathrm{U}(B) \times K_2 U ( B ) × K 2 belong to the same H H H -orbit and hence are isomorphic. It remains to determine the automorphism group of one component. The same sign condition in Corollary 4.3 gives G = ( Aut + ( B ) × { 1 } ) ∪ ( Aut − ( B ) × { κ } ) \mathcal{G} = (\operatorname{Aut}^{+}(B) \times\{1\}) \cup(\operatorname{Aut}^{-}(B) \times\{\kappa\}) G = ( Aut + ( B ) × { 1 }) ∪ ( Aut − ( B ) × { κ }) .
Define ψ : Aut ( U ( B ) ) ⟶ G \psi\colon\operatorname{Aut}(\mathrm{U}(B)) \longrightarrow\mathcal{G} ψ : Aut ( U ( B )) ⟶ G by ψ ( g ) = ( g , κ χ B ( g ) ) \psi(g) = (g,\kappa^{\chi_B(g)}) ψ ( g ) = ( g , κ χ B ( g ) ) , where χ B ( g ) ∈ F 2 \chi_B(g) \in\mathbb{F}_2 χ B ( g ) ∈ F 2 denotes the sign of g g g . We show that ψ \psi ψ is a group isomorphism. Since χ B \chi_B χ B is a homomorphism, χ B ( g h ) = χ B ( g ) + χ B ( h ) \chi_B(gh) = \chi_B(g) + \chi_B(h) χ B ( g h ) = χ B ( g ) + χ B ( h ) , and therefore
ψ ( g h ) = ( g h , κ χ B ( g h ) ) = ( g h , κ χ B ( g ) + χ B ( h ) ) = ( g , κ χ B ( g ) ) ( h , κ χ B ( h ) ) = ψ ( g ) ψ ( h ) . \begin{aligned}
\psi(gh) &= (gh,\kappa^{\chi_B(gh)}) \\
&= (gh,\kappa^{\chi_B(g)+\chi_B(h)}) \\
&= (g,\kappa^{\chi_B(g)})(h,\kappa^{\chi_B(h)}) \\
&= \psi(g)\psi(h).
\end{aligned} ψ ( g h ) = ( g h , κ χ B ( g h ) ) = ( g h , κ χ B ( g ) + χ B ( h ) ) = ( g , κ χ B ( g ) ) ( h , κ χ B ( h ) ) = ψ ( g ) ψ ( h ) .
Thus ψ \psi ψ is a homomorphism. It is injective since its first coordinate is g g g . It is surjective because every element of G \mathcal{G} G has one of the two forms ( g , 1 ) (g,1) ( g , 1 ) , g ∈ Aut + ( B ) g \in\operatorname{Aut}^{+}(B) g ∈ Aut + ( B ) , or ( g , κ ) (g,\kappa) ( g , κ ) , g ∈ Aut − ( B ) g \in\operatorname{Aut}^{-}(B) g ∈ Aut − ( B ) . Hence G ≅ Aut ( U ( B ) ) \mathcal{G} \cong\operatorname{Aut}(\mathrm{U}(B)) G ≅ Aut ( U ( B )) .
Since H = Q 2 H = Q_2 H = Q 2 and ∣ Q 2 ∣ = 2 |Q_2| = 2 ∣ Q 2 ∣ = 2 , there is a single isomorphism class of connected components, consisting of the two components of U ( B ) × K 2 \mathrm{U}(B) \times K_2 U ( B ) × K 2 . The nontrivial element of S 2 S_2 S 2 interchanges these two components. Therefore, by Eq. (29) , Aut ( U ( B ) × K 2 ) ≅ G ≀ S 2 = ( G × G ) ⋊ S 2 \operatorname{Aut}(\mathrm{U}(B) \times K_2) \cong\mathcal{G} \wr S_2 = (\mathcal{G} \times\mathcal{G}) \rtimes S_2 Aut ( U ( B ) × K 2 ) ≅ G ≀ S 2 = ( G × G ) ⋊ S 2 . Using G ≅ Aut ( U ( B ) ) \mathcal{G} \cong\operatorname{Aut}(\mathrm{U}(B)) G ≅ Aut ( U ( B )) , we obtain Aut ( U ( B ) × K 2 ) ≅ Aut ( U ( B ) ) ≀ S 2 \operatorname{Aut}(\mathrm{U}(B) \times K_2) \cong\operatorname{Aut}(\mathrm{U}(B)) \wr S_2 Aut ( U ( B ) × K 2 ) ≅ Aut ( U ( B )) ≀ S 2 . □ \square □
Let n n n and k k k be integers with n ≥ 3 n \ge3 n ≥ 3 and 1 ≤ k < n / 2 1 \le k < n/2 1 ≤ k < n /2 . The generalized Petersen graph GP ( n , k ) \operatorname{GP}(n,k) GP ( n , k ) has vertex set { u i , v i : i ∈ Z n } \{u_i,v_i : i \in\mathbb{Z}_n\} { u i , v i : i ∈ Z n } and edge set
{ { u i , u i + 1 } , { u i , v i } , { v i , v i + k } : i ∈ Z n } . \bigl\{\{u_i,u_{i+1}\},\{u_i,v_i\},\{v_i,v_{i+k}\}:i\in\mathbb{Z}_n\bigr\}. { { u i , u i + 1 } , { u i , v i } , { v i , v i + k } : i ∈ Z n } .
where all subscripts are taken modulo n n n .
Lemma 4.9 now gives a formula for the automorphism group of the double cover of a bipartite generalized Petersen graph.
Lemma 4.10. Let n n n be even and k k k odd, where 1 ≤ k < n / 2 1 \le k < n/2 1 ≤ k < n /2 . Then
Aut ( GP ( n , k ) × K 2 ) ≅ Aut ( GP ( n , k ) ) ≀ S 2 . (37) \operatorname{Aut}(\operatorname{GP}(n,k) \times K_2) \cong\operatorname{Aut}(\operatorname{GP}(n,k)) \wr S_2. \tag*{(37)} Aut ( GP ( n , k ) × K 2 ) ≅ Aut ( GP ( n , k )) ≀ S 2 . (37) Proof. Set B = GP ( n , k ) B = \operatorname{GP}(n,k) B = GP ( n , k ) . By [1 Proposition 4.3] , B B B is bipartite. Equip B B B with either of its two ordered bipartitions. The graph B B B is also connected, twin-free, and cubic. By Lemma 2.5 , B B B is a nonunit f f f -prime object. Lemma 4.9 applies and gives Eq. (37) . □
Combining Lemma 4.10 with the classification of automorphism groups by Frucht, Graver and Watkins [6 ] gives the following corollary, which recovers the bipartite cases of [21 Theorem 1.2(iii)] . We use the following notation.
F ( n ) = ⟨ ρ , δ ∣ ρ n = δ 2 = 1 , δ ρ δ = ρ − 1 ⟩ , F(n) = \langle\rho,\delta\mid\rho^n = \delta^2 = 1,\ \delta\rho\delta= \rho^{-1} \rangle, F ( n ) = ⟨ ρ , δ ∣ ρ n = δ 2 = 1 , δ ρ δ = ρ − 1 ⟩ ,
H ( n , k ) = ⟨ ρ , α ∣ ρ n = α 4 = 1 , α ρ α − 1 = ρ k ⟩ , H(n,k) = \langle\rho,\alpha\mid\rho^n = \alpha^4 = 1,\ \alpha\rho\alpha^{-1} = \rho^k \rangle, H ( n , k ) = ⟨ ρ , α ∣ ρ n = α 4 = 1 , α ρ α − 1 = ρ k ⟩ ,
J ( n , k ) = ⟨ ρ , δ , α ∣ ρ n = δ 2 = α 2 = 1 , δ ρ δ = ρ − 1 , α ρ α = ρ k , α δ α = δ ⟩ . J(n,k) = \langle\rho,\delta,\alpha\mid\rho^n = \delta^2 = \alpha^2 = 1,\ \delta\rho\delta= \rho^{-1},\ \alpha\rho\alpha= \rho^k,\ \alpha\delta\alpha= \delta\rangle. J ( n , k ) = ⟨ ρ , δ , α ∣ ρ n = δ 2 = α 2 = 1 , δ ρ δ = ρ − 1 , α ρ α = ρ k , α δ α = δ ⟩ .
Here these group names are local to the generalized Petersen application. In particular F ( n ) F(n) F ( n ) is the dihedral group of order 2 n 2n 2 n . The exceptional groups are specified by the presentations in [21 Lemma 2.1] :
E 8 = ⟨ a , b , c ∣ a 8 = b 2 = c 3 = 1 , b a b = a − 1 , b c b = c − 1 , c a c = a − 1 , c a 4 = a 4 c ⟩ , E_8 = \langle a,b,c \mid a^8 = b^2 = c^3 = 1,\quad bab = a^{-1},\quad bcb = c^{-1},\quad cac = a^{-1},\quad ca^4 = a^4c \rangle, E 8 = ⟨ a , b , c ∣ a 8 = b 2 = c 3 = 1 , bab = a − 1 , b c b = c − 1 , c a c = a − 1 , c a 4 = a 4 c ⟩ ,
E 24 = ⟨ a , b , c ∣ ( c a ) 2 = b 2 = c 3 = 1 , b a b = a − 1 , b c b = c − 1 , c a 4 = a 4 c ⟩ . E_{24} = \langle a,b,c \mid(ca)^2 = b^2 = c^3 = 1,\quad bab = a^{-1},\quad bcb = c^{-1},\quad ca^4 = a^4c \rangle. E 24 = ⟨ a , b , c ∣ ( c a ) 2 = b 2 = c 3 = 1 , bab = a − 1 , b c b = c − 1 , c a 4 = a 4 c ⟩ .
These presentations remove any choice of an unstated semidirect-product action. The presentation of H ( n , k ) H(n,k) H ( n , k ) uses our right-to-left map convention: when k 2 ≡ − 1 ( m o d n ) k^2 \equiv-1 \pmod n k 2 ≡ − 1 ( mod n ) , it is realized by the shift ρ ( u i ) = u i + 1 \rho(u_i) = u_{i+1} ρ ( u i ) = u i + 1 , ρ ( v i ) = v i + 1 \rho(v_i) = v_{i+1} ρ ( v i ) = v i + 1 and the automorphism α ( u i ) = v k i \alpha(u_i) = v_{ki} α ( u i ) = v k i , α ( v i ) = u k i \alpha(v_i) = u_{ki} α ( v i ) = u k i . All three edge types are preserved; α 2 \alpha^2 α 2 negates subscripts and α ρ α − 1 = ρ k \alpha\rho\alpha^{-1} = \rho^k α ρ α − 1 = ρ k . The 4 n 4n 4 n maps ρ a α b \rho^a\alpha^b ρ a α b (0 ≤ a < n 0 \le a < n 0 ≤ a < n , 0 ≤ b < 4 0 \le b < 4 0 ≤ b < 4 ) are distinct, as their layer actions, subscript slopes, and then translations distinguish them. The relations reduce every word to this form. Identification with the full group in the generic case is the cited classification.
Corollary 4.11. Let n n n be even and k k k odd, where 1 ≤ k < n / 2 1 \le k < n/2 1 ≤ k < n /2 , and write A ( n , k ) = Aut ( D ( GP ( n , k ) ) ) = Aut ( GP ( n , k ) × K 2 ) A(n,k) = \operatorname{Aut}(\operatorname{D}(\operatorname{GP}(n,k))) = \operatorname{Aut}(\operatorname{GP}(n,k) \times K_2) A ( n , k ) = Aut ( D ( GP ( n , k ))) = Aut ( GP ( n , k ) × K 2 ) . If
( n , k ) ∉ { ( 4 , 1 ) , ( 8 , 3 ) , ( 10 , 3 ) , ( 12 , 5 ) , ( 24 , 5 ) } , (n,k) \notin\{(4,1),(8,3),(10,3),(12,5),(24,5)\}, ( n , k ) ∈ / {( 4 , 1 ) , ( 8 , 3 ) , ( 10 , 3 ) , ( 12 , 5 ) , ( 24 , 5 )} , then
A ( n , k ) ≅ { F ( n ) ≀ S 2 , k 2 ≢ ± 1 ( m o d n ) , J ( n , k ) ≀ S 2 , k 2 ≡ 1 ( m o d n ) , H ( n , k ) ≀ S 2 , k 2 ≡ − 1 ( m o d n ) . A(n,k) \cong
\begin{cases}
F(n) \wr S_2, & k^2 \not\equiv\pm1 \pmod n,\\
J(n,k) \wr S_2, & k^2 \equiv1 \pmod n,\\
H(n,k) \wr S_2, & k^2 \equiv-1 \pmod n.
\end{cases} A ( n , k ) ≅ ⎩ ⎨ ⎧ F ( n ) ≀ S 2 , J ( n , k ) ≀ S 2 , H ( n , k ) ≀ S 2 , k 2 ≡ ± 1 ( mod n ) , k 2 ≡ 1 ( mod n ) , k 2 ≡ − 1 ( mod n ) . Moreover,
A ( 4 , 1 ) ≅ ( S 4 × Z 2 ) ≀ S 2 , A(4,1) \cong(S_4 \times Z_2) \wr S_2, A ( 4 , 1 ) ≅ ( S 4 × Z 2 ) ≀ S 2 , A ( 8 , 3 ) ≅ E 8 ≀ S 2 , A(8,3) \cong E_8 \wr S_2, A ( 8 , 3 ) ≅ E 8 ≀ S 2 , A ( 10 , 3 ) ≅ ( S 5 × Z 2 ) ≀ S 2 , A(10,3) \cong(S_5 \times Z_2) \wr S_2, A ( 10 , 3 ) ≅ ( S 5 × Z 2 ) ≀ S 2 , A ( 12 , 5 ) ≅ ( S 4 × S 3 ) ≀ S 2 , A(12,5) \cong(S_4 \times S_3) \wr S_2, A ( 12 , 5 ) ≅ ( S 4 × S 3 ) ≀ S 2 , A ( 24 , 5 ) ≅ ( E 24 ⋊ Z 2 ) ≀ S 2 . A(24,5) \cong(E_{24} \rtimes Z_2) \wr S_2. A ( 24 , 5 ) ≅ ( E 24 ⋊ Z 2 ) ≀ S 2 . Proof. Lemma 4.10 gives A ( n , k ) ≅ Aut ( GP ( n , k ) ) ≀ S 2 A(n,k) \cong\operatorname{Aut}(\operatorname{GP}(n,k)) \wr S_2 A ( n , k ) ≅ Aut ( GP ( n , k )) ≀ S 2 . The classification in [6 ] , with the exceptional presentations recorded in [21 Lemma 2.1] , identifies the factor group as F ( n ) F(n) F ( n ) , J ( n , k ) J(n,k) J ( n , k ) , H ( n , k ) H(n,k) H ( n , k ) , or the listed exceptional group in precisely the stated cases. Substitution
proves each formula. The classification of these factor groups is an external input; the double-cover step is the preceding lemma.
Acknowledgements The author is supported by the National Natural Science Foundation of China (12401453). The author is grateful to Binzhou Xia for his feedback on the first draft of the paper.
Declaration on the use of AI ChatGPT was used for grammar checking, language polishing, and improving the clarity of the exposition.
Data Availability Statement No data sets were generated or analyzed in this study.
Conflict of Interest The author declares no conflicts of interest.
References
School of Mathematics and Statistics, Lanzhou University, Lanzhou, Gansu 730000, P. R. China
Email address: wangxiaomeng@lzu.edu.cn