betaFeedback

WorksMathematics

Asymptotical results on the automorphism groups of canonical double cover of graphs

Abstract

The canonical double cover BXBX of a graph XX is the direct product X×K2X\times K_2. A graph XX is stable if every automorphism of BXBX is induced by automorphisms of XX and K2K_2, and unstable otherwise. We prove several asymptotic results on stable and unstable graphs. In particular, we show that the automorphism group of the canonical double cover of almost every graph has order 22, and consequently that almost all graphs are stable. We also prove that the dominant sources of instability are having twins and being disconnected, in that order, and that graphs arising from a known construction are the next step in this hierarchy.

Keywords: canonical double cover, unstable graph, automorphism group

AMS Subject Classification (2020): 05C25, 05C76

Introduction

All graphs in this paper are finite and simple. Given a graph XX, its automorphism group is denoted by Aut⁡(X)\operatorname{Aut}(X). The canonical bipartite double cover (also called the bipartite double cover or the Kronecker cover) of XX, denoted by BXBX, is the direct product X×K2X \times K_2 (where K2K_2 denotes the complete graph on two vertices). In other words, we have that

V(BX)=V(X)×{0,1}V(BX) = V(X) \times\{0,1\}

and

E(BX)={{(x,0),(y,1)}:{x,y}∈E(X)}.E(BX) = \{\{(x,0),(y,1)\} : \{x,y\} \in E(X)\}.

We denote by τ\tau the canonical involution on V(BX)V(BX) interchanging (x,0)(x,0) and (x,1)(x,1) for all x∈V(X)x \in V(X). We observe that τ∈Aut⁡(BX)\tau\in\operatorname{Aut}(BX) and that Aut⁡(X)×⟨τ⟩≅Aut⁡(X)×S2\operatorname{Aut}(X) \times\langle\tau\rangle\cong\operatorname{Aut}(X) \times S_2 canonically embeds into Aut⁡(BX)\operatorname{Aut}(BX). The graph XX is stable if BXBX has no additional automorphism, that is, if

Aut⁡(BX)=Aut⁡(X)×⟨τ⟩.\operatorname{Aut}(BX) = \operatorname{Aut}(X) \times\langle\tau\rangle.

Otherwise, XX is called unstable.

Canonical double covers have proven to play an important role in algebraic graph theory and have been studied from a variety of perspectives. For example, their connections with symmetric {0,1}\{0,1\}-matrices were studied by Marušić, Scapellato and Salvi [11], their regular embeddings by Nedela and Škoviera [12], their isomorphisms by Pacco and Scapellato [13] and their symmetry properties in the context of 2-fold covers by Feng, Kutnar, Malnič and Marušič [2].

Wilson gave several sufficient conditions for a graph to be unstable, which he then used to formulate conjectures characterising instability in four families of graphs: circulants, Rose Window graphs, toroidal graphs and generalized Petersen graphs [16]. Wilson’s conjectures were proven for generalized Petersen graphs by Qin, Xia, and Zhou [15], for toroidal graphs by Witte Morris [18], and for Rose Window graphs by Ahanjideh, Kovács, and Kutnar [1].

A lot of work has been done on the stability of circulant graphs. Wilson’s conjecture was shown to be false by Qin, Xia and Zhou, who also proved that there are no nontrivially unstable arc-transitive circulants [14]. It was proven by Fernandez and the second author that there are no nontrivially unstable circulants of odd order [3]. Morris extended this result by proving that there are no nontrivially unstable Cayley graphs on abelian groups of odd order [17]. In [9], several constructions of unstable circulants were presented, and unstable circulants of order twice a prime were classified, whereas in [10] unstable circulants with valency at most 7 were classified. The connection between stability of Cayley graphs and properties of Schur rings was studied in [7]. Nevertheless, the full classification of unstable circulants remains an open problem. In [19], Xia, Zhang and Zheng proved that almost all Cayley graphs on abelian groups are stable.

In this paper, we study the asymptotic behavior of the proportion of various properties related to stability of general graphs. Throughout the paper all asymptotic statements concern labeled graphs; in particular, when we say that almost all graphs in a family have a given property, we mean that the proportion of graphs with that property among all graphs in the family with vertex-set [n]:={1,…,n}[n] := \{1,\ldots,n\} tends to 1 as n→∞n \to\infty. For a precise definition, see Definition 3.1.

We first show that instability is asymptotically rare. In fact, we prove the following stronger statement.

Theorem 1.1. Almost all graphs XX satisfy Aut⁡(BX)=⟨τ⟩\operatorname{Aut}(BX) = \langle\tau\rangle.

As a direct consequence, we have the following:

Corollary 1.2. Almost all graphs are stable.

It is not hard to see that graphs with twins (nonadjacent distinct vertices with the same neighbourhoods) and disconnected graphs are unstable. We will prove that these are the dominant sources of instability, in that order.

Theorem 1.3. Almost all unstable graphs have twins.

Theorem 1.4. Almost all unstable twin-free graphs are disconnected.

Moving further down the asymptotic hierarchy, we consider twin-free connected unstable graphs and show that they almost all arise from the following simple construction, which was first defined in [8].

Construction 1.5. Let XX be a graph and let AA and BB be subsets of V(X)V(X). Let X(A,B)X(A,B) be the graph obtained from XX by adding four new vertices a1,a2,b1,b2a_1,a_2,b_1,b_2 and two new edges {a1,b1},{a2,b2}\{a_1,b_1\},\{a_2,b_2\} to XX, and then joining a1a_1 and a2a_2 with every vertex in AA and b1b_1 and b2b_2 with every vertex in BB.

Theorem 1.6. Almost all unstable twin-free connected graphs arise via Construction 1.5.

Finally, we determine the typical automorphism group of the canonical double cover of the graphs in Theorem 1.6. Let D4D_4 denote the dihedral group of order 8.

Theorem 1.7. Almost all unstable twin-free connected graphs YY that arise via Construction 1.5 satisfy

Aut⁡(BY)=⟨((a1,0),(a2,0))((b1,1),(b2,1)),τ⟩≅D4\operatorname{Aut}(BY)=\langle((a_1,0),(a_2,0))((b_1,1),(b_2,1)),\tau\rangle\cong D_4

for some distinct vertices a1,a2,b1,b2a_1,a_2,b_1,b_2 of YY.

Some authors (for example Wilson in [16]) define a graph to be nontrivially unstable if it is unstable but twin-free, connected and nonbipartite. Note that nonbipartite is slightly different from the other two conditions in this definition: graphs with twins and disconnected graphs are necessarily unstable, whereas a bipartite graph may still be stable. Moreover, we have already noted that, asymptotically speaking, graphs with twins and disconnected graphs are the dominant sources of instability. Being bipartite is much further down the list, see for example Lemma 3.2. It is also lower than graphs arising from Construction 1.5. For this reason, Theorem 1.6 and Theorem 1.7 immediately hold with “unstable twin-free connected” replaced by “nontrivially unstable”.

We first prove some important preliminary results in Section 2 and then the main theorems in Section 3.

Preliminaries

Let XX be a graph with vertex-set VV. For v∈Vv \in V, the neighbourhood NX(v)N_X(v) of vv in XX is the set of vertices of XX adjacent with vv. Note that

NBX(v,0)=NX(v)×{1}andNBX(v,1)=NX(v)×{0}.N_{BX}(v,0) = N_X(v) \times\{1\} \quad\text{and}\quad N_{BX}(v,1) = N_X(v) \times\{0\}.

Let g1,g2∈Sym⁡(V)g_1,g_2 \in\operatorname{Sym}(V). We denote by (g1,g2)(g_1,g_2) the permutation of V(BX)=V×{0,1}V(BX) = V \times\{0,1\} defined by

(v,0)(g1,g2)=(vg1,0)and(v,1)(g1,g2)=(vg2,1).(v,0)^{(g_1,g_2)} = (v^{g_1},0) \quad\text{and}\quad(v,1)^{(g_1,g_2)} = (v^{g_2},1).

Given a group G≤Sym⁡(V)G \leq\operatorname{Sym}(V), the support of GG, denoted supp⁡(G)\operatorname{supp}(G), is the set of elements of VV not fixed by GG.

Lemma 2.1. Let XX be a graph with vertex-set VV, let v∈Vv \in V and let g1,g2∈Sym⁡(V)g_1,g_2 \in\operatorname{Sym}(V) such that (g1,g2)∈Aut⁡(BX)(g_1,g_2) \in\operatorname{Aut}(BX). Let G:=⟨g1,g2⟩G := \langle g_1,g_2\rangle, W:=V∖supp⁡(G)W := V \setminus\operatorname{supp}(G) and g∈Gg \in G. Then

(1) NX(vg1)=(NX(v))g2N_X(v^{g_1}) = (N_X(v))^{g_2} and NX(vg2)=(NX(v))g1N_X(v^{g_2}) = (N_X(v))^{g_1}.

(2) NX(vg)∩W=NX(v)∩WN_X(v^g) \cap W = N_X(v) \cap W.

(3) vv and vg2−1g1v^{g_2^{-1}g_1} are nonadjacent in XX.

If moreover XX is twin-free, then

(4) If one of g1g_1 or g2g_2 is the identity, they both are.

(5) g1g_1 and g2g_2 have the same order.

(6) If g1≠g2g_1 \ne g_2, then ∣supp⁡(G)∣≥4|\operatorname{supp}(G)| \geq4.

Proof. (1) We have

NX(vg1)×{1}=NBX(vg1,0)=NBX((v,0)(g1,g2))=(NBX(v,0))(g1,g2)=(NX(v)×{1})(g1,g2)=NX(v)g2×{1}.\begin{aligned} N_X(v^{g_1}) \times\{1\} = N_{BX}(v^{g_1},0) = N_{BX}((v,0)^{(g_1,g_2)}) \\ &= (N_{BX}(v,0))^{(g_1,g_2)} = (N_X(v) \times\{1\})^{(g_1,g_2)} \\ &= N_X(v)^{g_2} \times\{1\}. \end{aligned}

It follows that NX(vg1)=NX(v)g2N_X(v^{g_1}) = N_X(v)^{g_2}, and an analogous argument yields NX(vg2)=NX(v)g1N_X(v^{g_2}) = N_X(v)^{g_1}.

(2) From (1), we get

NX(vg1)∩W=NX(v)g2∩W=(NX(v)∩W)g2=NX(v)∩W.N_X(v^{g_1}) \cap W = N_X(v)^{g_2} \cap W = (N_X(v) \cap W)^{g_2} = N_X(v) \cap W.

A symmetrical argument yields that NX(vg2)∩W=NX(v)∩WN_X(v^{g_2}) \cap W = N_X(v) \cap W and thus $N_X(v^g) \cap W = N_X(v) \cap W.

Equation not extracted

(3) Note that (vg2−1,0)(v^{g_2^{-1}},0) and (vg2−1,1)(v^{g_2^{-1}},1) are nonadjacent in BXBX. Consequently, since (g1,g2)∈Aut⁡(BX)(g_1,g_2) \in\operatorname{Aut}(BX), we have that

(vg2−1,0)(g1,g2)=(vg2−1g1,0)(v^{g_2^{-1}},0)^{(g_1,g_2)}=(v^{g_2^{-1}g_1},0)

and

(vg2−1,1)(g1,g2)=(v,1)(v^{g_2^{-1}},1)^{(g_1,g_2)}=(v,1)

are also nonadjacent in BXBX. It follows that vg2−1g1v^{g_2^{-1}g_1} and vv are nonadjacent in XX, as desired.

(4) Without loss of generality, suppose that g2=id⁡g_2=\operatorname{id}. Applying (1), we get NX(v)=NX(vg1)N_X(v)=N_X(v^{g_1}). Since XX is twin-free, we have that v=vg1v=v^{g_1} and, since vv is arbitrary, we have g1=id⁡g_1=\operatorname{id}, as required.

(5) Assume for contradiction that ord⁡(g1)≠ord⁡(g2)\operatorname{ord}(g_1)\ne\operatorname{ord}(g_2). Without loss of generality, we may assume that ord⁡(g1)\operatorname{ord}(g_1) does not divide ord⁡(g2)\operatorname{ord}(g_2) and thus g1ord⁡(g2)≠id⁡g_1^{\operatorname{ord}(g_2)}\ne\operatorname{id}, and

(g1ord⁡(g2),id⁡)=(g1,g2)ord⁡(g2)∈Aut⁡(BX),(g_1^{\operatorname{ord}(g_2)},\operatorname{id})=(g_1,g_2)^{\operatorname{ord}(g_2)}\in\operatorname{Aut}(BX),

contradicting (4).

(6) Suppose for a contradiction that ∣supp⁡(G)∣≤3|\operatorname{supp}(G)|\le3. By (5), g1g_1 and g2g_2 have the same order. Since g1≠g2g_1\ne g_2, either g1g_1 and g2g_2 are distinct transpositions or g1g_1 is a 3-cycle and g2=g1−1g_2=g_1^{-1}. In both cases, g2−1g1g_2^{-1}g_1 is a cycle of length 3 on supp⁡(G)\operatorname{supp}(G). By (3), it follows that the three vertices contained in supp⁡(G)\operatorname{supp}(G) are nonadjacent in XX. Let vv such that v≠vg1v\ne v^{g_1}, in particular, v∈supp⁡(G)v\in\operatorname{supp}(G). By (2), we have NX(vg1)∩W=NX(v)∩WN_X(v^{g_1})\cap W=N_X(v)\cap W and thus vv and vg1v^{g_1} are twins in XX, contradicting the assumption that XX is twin-free.

Lemma 2.2. A connected nonbipartite graph XX with vertex-set VV is unstable if and only if there exist g1,g2∈Sym⁡(V)g_1,g_2\in\operatorname{Sym}(V), with g1≠g2g_1\ne g_2, such that (g1,g2)∈Aut⁡(BX)(g_1,g_2)\in\operatorname{Aut}(BX).

Proof. Since XX is connected and nonbipartite, it follows by Weichsel’s Theorem (see [6 Theorem 5.9]) that BXBX is connected hence {V×{0},V×{1}}\{V\times\{0\},V\times\{1\}\} is the unique bipartition of BXBX and thus every automorphism of BXBX preserves it.

Suppose that XX is unstable. Then Aut⁡(X)×⟨τ⟩<Aut⁡(BX)\operatorname{Aut}(X)\times\langle\tau\rangle<\operatorname{Aut}(BX). By the previous paragraph, there exist g1,g2∈Sym⁡(V)g_1,g_2\in\operatorname{Sym}(V) with (g1,g2)∈Aut⁡(BX)(g_1,g_2)\in\operatorname{Aut}(BX) and (g1,g2)(g_1,g_2) not of the form (g,g)(g,g) with g∈Aut⁡(X)g\in\operatorname{Aut}(X). If g1=g2g_1=g_2, then Lemma 2.1(1) implies that g1∈Aut⁡(X)g_1\in\operatorname{Aut}(X), a contradiction, so we have g1≠g2g_1\ne g_2, as required. The converse is obvious. □

Lemma 2.3. Let g1,g2∈Sym⁡(V)g_1,g_2\in\operatorname{Sym}(V), let G:=⟨g1,g2⟩G:=\langle g_1,g_2\rangle and let G∗:=⟨(g1,g2),τ⟩≤Sym⁡(V×{0,1})G^*:=\langle(g_1,g_2),\tau\rangle\le\operatorname{Sym}(V\times\{0,1\}). Then the orbits of G∗G^* are exactly the sets of the form O×{0,1}O\times\{0,1\} with OO an orbit of GG.

Proof. Since τ∈G∗\tau\in G^{*}, an orbit of G∗G^{*} contains (x,0)(x,0) if and only if it contains (x,1)(x,1). Using this and the fact that τ(g1,g2)τ=(g2,g1)∈G∗\tau(g_{1},g_{2})\tau=(g_{2},g_{1})\in G^{*}, the conclusion easily follows.

Corollary 2.4. Let YY be a twin-free graph with vertex-set VV and let g1,g2∈Sym⁡(V)g_{1},g_{2}\in\operatorname{Sym}(V) such that g1≠g2g_{1}\ne g_{2} and (g1,g2)∈Aut⁡(BY)(g_{1},g_{2})\in\operatorname{Aut}(BY). Let G:=⟨g1,g2⟩G:=\langle g_{1},g_{2}\rangle and let XX be the subgraph of YY induced on V∖supp⁡(G)V\setminus\operatorname{supp}(G). If ∣supp⁡(G)∣=4|\operatorname{supp}(G)|=4, then there exist subsets A,B⊆V(X)A,B\subseteq V(X) such that Y=X(A,B)Y=X(A,B).

Proof. Since ∣supp⁡(G)∣=4|\operatorname{supp}(G)|=4, either GG has two orbits of size 22 or one orbit of size 44.

Case 1. GG has an orbit of size 44.

Let OO be this orbit, so W:=V∖O=V∖supp⁡(G)W:=V\setminus O=V\setminus\operatorname{supp}(G). Let ZZ be the subgraph of YY induced on OO. Then BZBZ is a subgraph of BYBY and, by Lemma 2.3, ⟨(g1,g2),τ⟩≤Aut⁡(BY)\langle(g_{1},g_{2}),\tau\rangle\leq\operatorname{Aut}(BY) acts transitively on O×{0,1}=V(BZ)O\times\{0,1\}=V(BZ). In particular, both BZBZ and ZZ are regular graphs.

Let a∈Oa\in O and let A:=NY(a)∩WA:=N_{Y}(a)\cap W. By Lemma 2.1(2), AA does not depend on the choice of aa. In particular, since YY is twin-free, so is ZZ. Since g1≠g2g_{1}\ne g_{2}, supp⁡(g1,g2)⊆O×{0,1}=V(BZ)\operatorname{supp}(g_{1},g_{2})\subseteq O\times\{0,1\}=V(BZ) and (g1,g2)∈Aut⁡(BY)(g_{1},g_{2})\in\operatorname{Aut}(BY), it follows that ZZ is unstable. The only regular twin-free graphs on four vertices are 2K22K_{2} and K4K_{4}, but K4K_{4} is stable hence Z≅2K2Z\cong2K_{2}. Hence Y=X(A,A)Y=X(A,A), as required.

Case 2. GG has two orbits of size 22.

Let {a1,a2}\{a_{1},a_{2}\} and {b1,b2}\{b_{1},b_{2}\} be distinct orbits of size 22 of GG, so W=V∖{a1,a2,b1,b2}W=V\setminus\{a_{1},a_{2},b_{1},b_{2}\}. By Lemma 2.1(5), g1g_{1} and g2g_{2} have the same order. Since g1≠g2g_{1}\ne g_{2}, up to relabeling, we have that either

g1=(a1,a2)(b1,b2) and g2=(a1,a2)g_{1}=(a_{1},a_{2})(b_{1},b_{2})\text{ and }g_{2}=(a_{1},a_{2})

or

g1=(a1,a2) and g2=(b1,b2).g_{1}=(a_{1},a_{2})\text{ and }g_{2}=(b_{1},b_{2}).

Subcase 2.1. g1=(a1,a2)g_{1}=(a_{1},a_{2}) and g2=(b1,b2)g_{2}=(b_{1},b_{2}).

Let W:=V∖supp⁡(G)=V∖{a1,a2,b1,b2}W:=V\setminus\operatorname{supp}(G)=V\setminus\{a_{1},a_{2},b_{1},b_{2}\}. Since g2−1g1=(a1,a2)(b1,b2)g_{2}^{-1}g_{1}=(a_{1},a_{2})(b_{1},b_{2}), Lemma 2.1(3) implies that a1a_{1} is nonadjacent to a2a_{2} in YY and b1b_{1} is nonadjacent to b2b_{2} in YY. By Lemma 2.1(2), we have

A:=NY(a1)∩W=NY(a1g1)∩W=NY(a2)∩WA:=N_{Y}(a_{1})\cap W=N_{Y}(a_{1}^{g_{1}})\cap W=N_{Y}(a_{2})\cap W

and

B:=NY(b1)∩W=NY(b2g2)∩W=NY(b2)∩W.B:=N_{Y}(b_{1})\cap W=N_{Y}(b_{2}^{g_{2}})\cap W=N_{Y}(b_{2})\cap W.

Since YY is twin-free, a1a_{1} and a2a_{2} are not twins, so they are each adjacent to exactly one of b1b_{1} or b1b_{1}, and vice versa. Without loss of generality, let a1a_{1} be adjacent to b1b_{1} and nonadjacent to b2b_{2} and a2a_{2} be adjacent to b2b_{2} and nonadjacent to b1b_{1}. It now follows that Y=X(A,B)Y=X(A,B), as required.

Subcase 2.2. g1=(a1,a2)(b1,b2)g_{1}=(a_{1},a_{2})(b_{1},b_{2}) and g2=(a1,a2)g_{2}=(a_{1},a_{2}). Let g:=(b1,b2)g := (b_1,b_2) and note that (g,g)=(g1g2,g2g1)=(g1,g2)(g1,g2)τ∈Aut⁡(BY)(g,g) = (g_1g_2,g_2g_1) = (g_1,g_2)(g_1,g_2)^\tau\in\operatorname{Aut}(BY). By Lemma 2.1(1) applied with v=b1v=b_1, we have

NY(b2)=NY(b1g1)=NY(b1)g2N_Y(b_2) = N_Y(b_1^{g_1}) = N_Y(b_1)^{g_2}

and

NY(b2)=NY(b1g)=NY(b1)g.N_Y(b_2) = N_Y(b_1^g) = N_Y(b_1)^g.

Let Va:=V∖{a1,a2}V_a := V \setminus\{a_1,a_2\} and Vb:=V∖{b1,b2}V_b := V \setminus\{b_1,b_2\}. We now have

NY(b2)∩Va=NY(b1)g2∩Va=NY(b1)∩VaN_Y(b_2) \cap V_a = N_Y(b_1)^{g_2} \cap V_a = N_Y(b_1) \cap V_a

and

NY(b2)∩Vb=NY(b1)g∩Vb=NY(b1)∩Vb.N_Y(b_2) \cap V_b = N_Y(b_1)^g \cap V_b = N_Y(b_1) \cap V_b.

Since Va∪Vb=VV_a \cup V_b = V, it follows that NY(b2)=NY(b1)N_Y(b_2) = N_Y(b_1), contradicting the fact that YY is twin-free. □

Finally, we recall some basic properties of Construction 1.5.

Proposition 2.5 ([8 Proposition 5.2]). Let XX be a graph with vertex-set VV and let A,B⊆VA, B \subseteq V. Then

  1. (a1,a2)(b1,b2)∈Aut⁡(X(A,B))(a_1,a_2)(b_1,b_2) \in\operatorname{Aut}(X(A,B)),

  2. γ:=((a1,0),(a2,0))((b1,1),(b2,1))\gamma:= ((a_1,0),(a_2,0))((b_1,1),(b_2,1)) is an automorphism of the double cover of X(A,B)X(A,B),

  3. we have ⟨γ,τ⟩≅D4\langle\gamma,\tau\rangle\cong D_4.

In particular, X(A,B)X(A,B) is unstable. Moreover, if XX is connected and twin-free, and at least one of AA and BB is nonempty, then X(A,B)X(A,B) is also connected and twin-free.

Proof. The fact that (a1,a2)(b1,b2)∈Aut⁡(X(A,B))(a_1,a_2)(b_1,b_2) \in\operatorname{Aut}(X(A,B)) follows immediately from Construction 1.5 (and, in particular, Figure 1). By [8 Proposition 5.2], γ\gamma is an automorphism of the double cover of X(A,B)X(A,B). Both γ\gamma and τ\tau are involutions, while their product has order 4, hence, ⟨γ,τ⟩≅D4\langle\gamma,\tau\rangle\cong D_4, as required. The last part is immediate. □

Figure 1. X(A,B)X(A,B).

For fixed g1,g2∈Sym⁡(V)g_1,g_2 \in\operatorname{Sym}(V), we give upper bounds on the number of graphs XX with vertex-set VV such that (g1,g2)∈Aut⁡(BX)(g_1,g_2) \in\operatorname{Aut}(BX).

Lemma 2.6. Let nn be a positive integer, let VV be a set of order nn, let g1,g2∈Sym⁡(V)g_1,g_2 \in\operatorname{Sym}(V) and let G:=⟨g1,g2⟩G := \langle g_1,g_2\rangle. Let X\mathcal{X} be the set of graphs XX with vertex-set VV such that (g1,g2)∈Aut⁡(BX)(g_1,g_2) \in\operatorname{Aut}(BX). Let ss be the size of the support of GG and let the nontrivial orbits of GG have sizes a1≥a2≥⋯≥ak≥2a_1 \ge a_2 \ge\cdots\ge a_k \ge2. Then

  1. ∣X∣≤2(n−1)+(n−1−a1)+(n−1−a1−a2)+⋯+(n−1−a1−⋯−ak−1)+(n−s2)|\mathcal{X}| \le2^{(n-1)+(n-1-a_1)+(n-1-a_1-a_2)+\cdots+(n-1-a_1-\cdots-a_{k-1})+\binom{n-s}{2}}.

  2. If m≥0m \ge0 is an even integer with m≤sm \le s, then

∣X∣≤2(n2)−m2(n−m2−1).|\mathcal{X}| \le2^{\binom{n}{2}-\frac{m}{2}\left(n-\frac{m}{2}-1\right)}.

Proof. Let O1,…,OkO_1,\ldots,O_k be the nontrivial orbits of GG, with ∣Oi∣=ai≥2\lvert O_i\rvert=a_i\ge2 for all i∈{1,…,k}i\in\{1,\ldots,k\}. Then

s=∑i=1kai.s=\sum_{i=1}^{k}a_i.

Let X∈XX\in\mathcal{X} and let vi∈Oiv_i\in O_i. By Lemma 2.3, Oi×{0,1}O_i\times\{0,1\} is an orbit of ⟨(g1,g2),τ⟩\langle(g_1,g_2),\tau\rangle. It follows that NX(vi)N_X(v_i) uniquely determines NBX(w)N_{B_X}(w) for every w∈Oi×{0,1}w\in O_i\times\{0,1\}, which in turn uniquely determines NX(u)N_X(u) for every u∈Oiu\in O_i.

There are at most 2n−12^{n-1} possibilities for the set NX(v1)N_X(v_1). By the previous paragraph, this choice then determines NX(u1)N_X(u_1) for every u1∈O1u_1\in O_1. It follows that NX(v2)∩O1N_X(v_2)\cap O_1 is also determined, which leaves at most 2n−a1−12^{n-a_1-1} possibilities for NX(v2)N_X(v_2), which in turn determines NX(u2)N_X(u_2) for every u2∈O2u_2\in O_2. We repeat this procedure for all i∈{1,…,k}i\in\{1,\ldots,k\} obtaining that there are at most 2n−a1−⋯−ak−1−12^{n-a_1-\cdots-a_{k-1}-1} possibilities for NX(vk)N_X(v_k), hence determining NX(uk)N_X(u_k) for every uk∈Oku_k\in O_k. It remains to determine the adjacencies amongst the vertices of XX fixed by GG, that is, those not contained in O1∪⋯∪OkO_1\cup\cdots\cup O_k. There are n−sn-s such vertices, so at most 2(n−s2)2^{\binom{n-s}{2}} possibilities, which concludes the proof of (1).

We now prove (2). Write m=2tm=2t. We call the vertices of OiO_i other than viv_i non-representative. We order the vertices in the following way: first v1v_1, then non-representative vertices in O1O_1, then v2v_2, then non-representative vertices in O2O_2, etc., with fixed vertices at the end. We choose the neighbourhood of the vertices in order. In the usual count of the total number of labeled graphs

2(n2)=2n−1⋅2n−2⋯20,2^{\binom{n}{2}}=2^{n-1}\cdot2^{n-2}\cdots2^0,

the vertex in the ii-th position contributes 2n−i2^{n-i}. In this case, the adjacency of a non-representative vertex is already determined, as in the proof of (1). Therefore, if the vertex in the ii-th position is non-representative, then we lose a factor of 2n−i2^{n-i} compared to the usual count.

Since ai≥2a_i\ge2, the jj-th non-representative vertex has position at most 2j2j. Therefore, the factor lost because of the jj-th non-representative vertex is at least

2n−2j.2^{n-2j}.

There are s−ks-k non-representative vertices. Since ai≥2a_i\ge2, we have k≤s/2k\le s/2 and therefore

s−k≥s/2≥m/2=t.s-k\ge s/2\ge m/2=t.

Hence there are at least tt non-representative vertices. Consequently, the total loss compared from 2(n2)2^{\binom{n}{2}} is at least

2n−2⋅2n−4⋯2n−2t=2t(n−t−1),2^{n-2}\cdot2^{n-4}\cdots2^{n-2t}=2^{t(n-t-1)},

as required. □

Lemma 2.7. Let nn be a positive integer and let VV be a set of order nn. The number of graphs XX with vertex-set VV for which there exist g1,g2∈Sym⁡(V)g_1,g_2 \in\operatorname{Sym}(V) such that ∣supp⁡(⟨g1,g2⟩)∣≥5\lvert\operatorname{supp}(\langle g_1,g_2\rangle)\rvert\ge5 and (g1,g2)∈Aut⁡(BX)(g_1,g_2) \in\operatorname{Aut}(BX) is o(2n2−5n+42)o\left(2^{\frac{n^2-5n+4}{2}}\right).

Proof. Let g1g_1 and g2g_2 be as in the statement, and let G=⟨g1,g2⟩G=\langle g_1,g_2\rangle. We consider two cases.

Case 1. ∣supp⁡(G)∣=5\lvert\operatorname{supp}(G)\rvert=5. The number of pairs (g1,g2)(g_1,g_2) in this case is at most

(n5)(5!)2\binom{n}{5}(5!)^2

The support of GG is either a single orbit of size 5, or a union of two orbits of sizes 3 and 2. For each fixed pair (g1,g2)(g_1,g_2), Lemma 2.6(1) gives at most

2n−122(n−52)=2n2−9n+2822^{n-12}2^{\binom{n-5}{2}}=2^{\frac{n^2-9n+28}{2}}

graphs XX when GG has an orbit of size 5, and at most

2n−122n−42(n−52)=2n2−7n+2022^{n-12}2^{n-4}2^{\binom{n-5}{2}}=2^{\frac{n^2-7n+20}{2}}

when GG has an orbit of size 3 and one of size 2. The total contribution of this case is thus at most

(n5)(5!)2(2n2−9n+282+2n2−7n+202)=o(2n2−5n+42).\binom{n}{5}(5!)^2\left(2^{\frac{n^2-9n+28}{2}}+2^{\frac{n^2-7n+20}{2}}\right)=o\left(2^{\frac{n^2-5n+4}{2}}\right).

Case 2. ∣supp⁡(G)∣≥6\lvert\operatorname{supp}(G)\rvert\ge6. Let x:=2⌈4log⁡2n⌉x:=2\lceil4\log_2 n\rceil. Note that xx is a positive even integer.

Subcase 2.1. x≥∣supp⁡(G)∣≥6x\ge\lvert\operatorname{supp}(G)\rvert\ge6. The number of pairs (g1,g2)(g_1,g_2) in this case is at most

(nx)(x!)2≤n2x.\binom{n}{x}(x!)^2\le n^{2x}.

For each fixed pair (g1,g2)(g_1,g_2), Lemma 2.6(2) applied with m=6m=6 gives at most

2(n2)−3(n−4)=2n2−7n+2422^{\binom{n}{2}-3(n-4)}=2^{\frac{n^2-7n+24}{2}}

graphs XX satisfying (g1,g2)∈Aut⁡(BX)(g_1,g_2)\in\operatorname{Aut}(BX). The total contribution of this case is thus at most

n2x2n2−7n+242=2n2−7n+242+2xlog⁡2n=o(2n2−5n+42).n^{2x}2^{\frac{n^2-7n+24}{2}}=2^{\frac{n^2-7n+24}{2}+2x\log_2 n}=o\left(2^{\frac{n^2-5n+4}{2}}\right).

Subcase 2.2. ∣supp⁡(G)∣>x\lvert\operatorname{supp}(G)\rvert>x. The number of pairs (g1,g2)(g_1,g_2) in this case is at most

(n!)2≤n2n.(n!)^2\le n^{2n}.

For each fixed pair (g1,g2)(g_1,g_2), Lemma 2.6(2) applied with m=xm=x gives at most

2(n2)−x2(n−x2−1).2^{\binom{n}{2}-\frac{x}{2}\left(n-\frac{x}{2}-1\right)}.

graphs XX satisfying (g1,g2)∈Aut⁡(BX)(g_1,g_2) \in\operatorname{Aut}(B_X). The total contribution of this case is thus at most

n2n2(n2)−x2(n−x2−1)=2(n2)−x2(n−x2−1)+2nlog⁡2n.n^{2n}2^{\binom{n}{2}-\frac{x}{2}\left(n-\frac{x}{2}-1\right)} =2^{\binom{n}{2}-\frac{x}{2}\left(n-\frac{x}{2}-1\right)+2n\log_2 n}.

Dividing by 2n2−5n+422^{\frac{n^2-5n+4}{2}} gives

22n−2−x2(n−x2−1)+2nlog⁡2n.2^{2n-2-\frac{x}{2}\left(n-\frac{x}{2}-1\right)+2n\log_2 n}.

Since x=2⌈4log⁡2n⌉x=2\lceil4\log_2 n\rceil, the above exponent tends to −∞-\infty when n→∞n\to\infty. Therefore this ratio is

22n−2−x2(n−x2−1)+2nlog⁡2n=o(1),2^{2n-2-\frac{x}{2}\left(n-\frac{x}{2}-1\right)+2n\log_2 n}=o(1),

which completes the proof. □

Lemma 2.8. The number of graphs with vertex-set [n][n] admitting two distinct double transpositions as automorphisms is at most

n82n2−7n+482.n^8 2^{\frac{n^2-7n+48}{2}}.

Proof. Note that Sym⁡(n)\operatorname{Sym}(n) contains 3(n4)3\binom{n}{4} double transpositions, so there are at most n8n^8 choices for a pair α,β∈Sym⁡(n)\alpha,\beta\in\operatorname{Sym}(n) of distinct double transpositions. We estimate the number of graphs with vertex-set [n][n] having α\alpha and β\beta as automorphisms. Let G:=⟨α,β⟩G:=\langle\alpha,\beta\rangle, U:=supp⁡(G)U:=\operatorname{supp}(G) and r:=∣U∣r:=|U|. Clearly, 4≤r≤84\le r\le8.

Each of α\alpha and β\beta is a product of two disjoint transpositions. Since α\alpha and β\beta are distinct, these gives us at least 3 distinct transpositions and it follows that GG has at most r−3r-3 orbits on UU.

There are 2(n−r2)2^{\binom{n-r}{2}} choices for the edges within [n]∖U[n]\setminus U, and at most 2(r2)2^{\binom{r}{2}} choices for the edges within UU. Finally, if v∈[n]∖Uv\in[n]\setminus U and u∈Uu\in U, then vv is adjacent to uu if and only if it is adjacent to every element of the GG-orbit of uu. It follows that there are at most 2r−32^{r-3} choices for the edges between vv and UU, and thus 2(r−3)(n−r)2^{(r-3)(n-r)} choices for edges between [n]∖U[n]\setminus U and UU. This gives us an upper bound of

2(n−r2)+(r−3)(n−r)+(r2)=2n2−7n+6r2≤2n2−7n+482.2^{\binom{n-r}{2}+(r-3)(n-r)+\binom{r}{2}} =2^{\frac{n^2-7n+6r}{2}} \le2^{\frac{n^2-7n+48}{2}}.

possible graphs. □

Main results

Definition 3.1. Let F\mathcal{F} and H\mathcal{H} be families of graphs and let Gn\mathcal{G}_n be the family of all graphs with vertex-set [n][n]. We say that “almost all graphs in F\mathcal{F} are in H\mathcal{H}” if

lim⁡n→∞∣F∩Gn∩H∣∣F∩Gn∣=1.\lim_{n\to\infty}\frac{|\mathcal{F}\cap\mathcal{G}_n\cap\mathcal{H}|}{|\mathcal{F}\cap\mathcal{G}_n|}=1.

If the above holds with F=⋃n∈NGn\mathcal{F}=\bigcup_{n\in\mathbb{N}}\mathcal{G}_n, then we say that “almost all graphs are in H\mathcal{H}”.

Recall that f(n)=o(g(n))f(n)=o(g(n)) if

lim⁡n→∞f(n)g(n)=0.\lim_{n\to\infty}\frac{f(n)}{g(n)}=0.

Lemma 3.2. Let nn be a positive integer. Then

  1. The number of disconnected graphs with vertex-set [n][n] is (1−o(1))n2(n−12)(1-o(1))n2^{\binom{n-1}{2}}. In particular, almost all graphs are connected.

  1. The number of bipartite graphs with vertex-set [n][n] is at most 2n24+n2^{\frac{n^2}{4}+n}. In particular, almost all graphs are nonbipartite.

  1. The number of graphs with vertex-set [n][n] with twins is (1−o(1))(n2)2(n−12)(1-o(1))\binom{n}{2}2^{\binom{n-1}{2}}. In particular, almost all graphs are twin-free.

Proof.

(1): See for example [4 Example II.15, p.138].

(2): To count the bipartite graphs with vertex-set [n][n], we consider all possible bipartitions of [n][n] and then all possible edge sets for each of those bipartitions. Let AA and BB form a partition of [n][n] with 0<∣A∣≤∣B∣<n0<|A|\leq|B|<n. Writing k:=∣A∣k:=|A|, there are (nk)\binom{n}{k} choices for AA and k(n−k)k(n-k) possible edges between AA and BB. Hence the following is an upper bound on the number of bipartite graphs with vertex-set [n][n]:

∑k=1⌊n2⌋(nk)2k(n−k)≤2n24∑k=1⌊n2⌋(nk)≤2n24∑k=0n(nk)≤2n24+n.\sum_{k=1}^{\left\lfloor\frac{n}{2}\right\rfloor}\binom{n}{k}2^{k(n-k)} \leq2^{\frac{n^2}{4}}\sum_{k=1}^{\left\lfloor\frac{n}{2}\right\rfloor}\binom{n}{k} \leq2^{\frac{n^2}{4}}\sum_{k=0}^{n}\binom{n}{k} \leq2^{\frac{n^2}{4}+n}.

(3): Let Tn\mathcal{T}_n denote the set of graphs with vertex-set [n][n] having twin vertices, and, for distinct i,j∈[n]i,j\in[n], let Tn(i,j)\mathcal{T}_n(i,j) denote the set of graphs with vertex-set [n][n] in which ii and jj are twins. Clearly,

Tn=⋃{i,j}∈([n]2)Tn(i,j).\mathcal{T}_n=\bigcup_{\{i,j\}\in\binom{[n]}{2}}\mathcal{T}_n(i,j).

By the first two Bonferroni inequalities (that is, the first two truncations of the inclusion–exclusion formula), we obtain

∑{i,j}∈([n]2)∣Tn(i,j)∣−∑{{i,j},{k,ℓ}}⊆([n]2){i,j}≠{k,ℓ}∣Tn(i,j)∩Tn(k,ℓ)∣≤∣Tn∣≤∑{i,j}∈([n]2)∣Tn(i,j)∣.(1)\sum_{\{i,j\}\in\binom{[n]}{2}}|\mathcal{T}_n(i,j)| -\sum_{\substack{\{\{i,j\},\{k,\ell\}\}\subseteq\binom{[n]}{2}\\\{i,j\}\ne\{k,\ell\}}} |\mathcal{T}_n(i,j)\cap\mathcal{T}_n(k,\ell)| \leq|\mathcal{T}_n| \leq\sum_{\{i,j\}\in\binom{[n]}{2}}|\mathcal{T}_n(i,j)|. \tag*{(1)}

Let i,j∈[n]i,j\in[n] be distinct. A graph with vertex-set [n][n] in which ii and jj are twins is uniquely determined by its subgraph induced on [n]∖{j}[n]\setminus\{j\}. Hence,

∣Tn(i,j)∣=2(n−12).|\mathcal{T}_n(i,j)|=2^{\binom{n-1}{2}}.

and

∑{i,j}∈([n]2)∣Tn(i,j)∣=(n2)2(n−12).(2)\sum_{\{i,j\}\in\binom{[n]}{2}}|\mathcal{T}_n(i,j)| =\binom{n}{2}2^{\binom{n-1}{2}}. \tag*{(2)}

There are at most n4n^4 choices for (i,j,k,ℓ)(i,j,k,\ell) and, depending on whether {i,j}∩{k,ℓ}=∅\{i,j\} \cap\{k,\ell\} = \varnothing or not, we either get a set of three distinct twins, or two disjoint sets of disjoint twins. Either way, we get exactly two “redundant” vertices, that is vertices whose neighbourhood is determined by their twins. It follows that, for fixed (i,j,k,ℓ)(i,j,k,\ell), we have

∣Tn(i,j)∩Tn(k,ℓ)∣=2(n−22).|\mathcal{T}_n(i,j) \cap\mathcal{T}_n(k,\ell)| = 2^{\binom{n-2}{2}}.

This implies that

∑{{i,j},{k,ℓ}}⊆([n]2){i,j}≠{k,ℓ}∣Tn(i,j)∩Tn(k,ℓ)∣≤n42(n−22).\sum_{\substack{\{\{i,j\},\{k,\ell\}\}\subseteq\binom{[n]}{2}\\ \{i,j\}\ne\{k,\ell\}}} |\mathcal{T}_n(i,j) \cap\mathcal{T}_n(k,\ell)| \le n^4 2^{\binom{n-2}{2}}.

but

lim⁡n→∞n42(n−22)(n2)2(n−12)=lim⁡n→∞n4(n2)2−(n−2)=0.\lim_{n\to\infty}\frac{n^4 2^{\binom{n-2}{2}}}{\binom{n}{2}2^{\binom{n-1}{2}}} = \lim_{n\to\infty}\frac{n^4}{\binom{n}{2}}2^{-(n-2)}=0.

Together with (1) and (2), this yields

∣Tn∣=(1−o(1))(n2)2(n−12),|\mathcal{T}_n|=(1-o(1))\binom{n}{2}2^{\binom{n-1}{2}},

as desired.

Theorem 1.1. Almost all graphs XX satisfy Aut⁡(BX)=⟨τ⟩\operatorname{Aut}(BX)=\langle\tau\rangle.

Proof. Combining Lemma 3.2(1) and Lemma 3.2(2), we conclude that almost all graphs are connected and nonbipartite. Hence, without loss of generality, we may assume that XX is connected and nonbipartite. As noted earlier, this implies that BXBX is connected and thus {V(X)×{0},V(X)×{1}}\{V(X)\times\{0\}, V(X)\times\{1\}\} is the unique bipartition of BXBX. It follows that, if Aut⁡(BX)>⟨τ⟩\operatorname{Aut}(BX)>\langle\tau\rangle, then there exist g1,g2∈Sym⁡(V)g_1,g_2\in\operatorname{Sym}(V) such that (id⁡,id⁡)≠(g1,g2)∈Aut⁡(BX)(\operatorname{id},\operatorname{id})\ne(g_1,g_2)\in\operatorname{Aut}(BX). Let G:=⟨g1,g2⟩G:=\langle g_1,g_2\rangle. Note that ∣supp⁡(G)∣≥2|\operatorname{supp}(G)|\ge2.

We will give an upper bound on the number of graphs XX with vertex-set [n][n] such that (g1,g2)∈Aut⁡(BX)(g_1,g_2)\in\operatorname{Aut}(BX). We closely follow the ideas of the proof of [5 Lemma 2.3.2]. Let x:=4⌈(log⁡2n)2⌉x:=4\lceil(\log_2 n)^2\rceil. Note that xx is a positive even integer.

Case 1. ∣supp⁡(G)∣≤x|\operatorname{supp}(G)|\le x. The number of pairs (g1,g2)(g_1,g_2) in this case is at most

(nx)(x!)2≤n2x.\binom{n}{x}(x!)^2\le n^{2x}.

For each fixed pair (g1,g2)(g_1,g_2), Lemma 2.6(2) applied with m=2m=2 gives at most

2(n2)−n+22^{\binom{n}{2}-n+2}

graphs XX satisfying (g1,g2)∈Aut⁡(BX)(g_1,g_2)\in\operatorname{Aut}(BX). The total contribution of this case is thus at most

n2x2(n2)−n+2=2(n2)−n+2+2xlog⁡2n=o(2(n2)).n^{2x}2^{\binom{n}{2}-n+2}=2^{\binom{n}{2}-n+2+2x\log_2 n}=o\left(2^{\binom{n}{2}}\right).

Case 2. ∣supp⁡(G)∣>x|\operatorname{supp}(G)| > x. The number of pairs (g1,g2)(g_1,g_2) in this case is at most

(n!)2≤n2n.(n!)^2 \le n^{2n}.

For each fixed pair (g1,g2)(g_1,g_2), Lemma 2.6(2) applied with m=xm=x gives at most

2(n2)−x2(n−x2−1)2^{\binom{n}{2}-\frac{x}{2}(n-\frac{x}{2}-1)}

graphs XX satisfying (g1,g2)∈Aut⁡(BX)(g_1,g_2) \in\operatorname{Aut}(BX). The total contribution of this case is thus again at most

n2n2(n2)−x2(n−x2−1)=2(n2)−x2(n−x2−1)+2nlog⁡2(n)=o(2(n2)),n^{2n}2^{\binom{n}{2}-\frac{x}{2}(n-\frac{x}{2}-1)} =2^{\binom{n}{2}-\frac{x}{2}(n-\frac{x}{2}-1)+2n\log_2(n)} =o\left(2^{\binom{n}{2}}\right),

which concludes the proof. □

We now give an upper bound on the number of unstable twin-free connected graphs which will be used in the proofs of Theorems 1.3 and 1.4.

Lemma 3.3. The number of unstable twin-free connected graphs with vertex-set [n][n] is o(2(n−12))o\left(2^{\binom{n-1}{2}}\right).

Proof. Using Lemma 3.2(2) it is not difficult to see that the number of bipartite graphs is o(2(n−12))o\left(2^{\binom{n-1}{2}}\right). It therefore suffices to count unstable twin-free connected nonbipartite graphs. For each such graph XX, by Lemma 2.2 there exist g1,g2∈Sym⁡(n)g_1,g_2 \in\operatorname{Sym}(n) with g1≠g2g_1 \ne g_2 and (g1,g2)∈Aut⁡(BX)(g_1,g_2) \in\operatorname{Aut}(BX). Let G=⟨g1,g2⟩G=\langle g_1,g_2\rangle. By Lemma 2.1(6), we have ∣supp⁡(G)∣≥4|\operatorname{supp}(G)| \ge4. There are at most (n4)(4!)2\binom{n}{4}(4!)^2 pairs (g1,g2)(g_1,g_2) with ∣supp⁡(G)∣=4|\operatorname{supp}(G)|=4. For each fixed pair, Lemma 2.6(2), applied with m=4m=4, gives at most 2(n2)−2n+62^{\binom{n}{2}-2n+6} graphs. Thus their total number is at most

(n4)(4!)22(n2)−2n+6=o(2(n−12)).\binom{n}{4}(4!)^2 2^{\binom{n}{2}-2n+6} =o\left(2^{\binom{n-1}{2}}\right).

By Lemma 2.7, the number of graphs admitting such a pair with ∣supp⁡(G)∣≥5|\operatorname{supp}(G)| \ge5 is

o(2n2−5n+42)=o(2(n−12)).o\left(2^{\frac{n^2-5n+4}{2}}\right) =o\left(2^{\binom{n-1}{2}}\right).

The result follows. □

:::

Theorem 1.3. Almost all unstable graphs have twins.

Proof. Let UnU_n denote the set of unstable graphs with vertex-set [n][n], and let TnT_n denote the set of graphs on [n][n] containing a pair of twins. Note that Tn⊆UnT_n \subseteq U_n. By Lemma 3.2(3), we have that

∣Tn∣=(1−o(1))(n2)2(n−12).(3)|T_n|=(1-o(1))\binom{n}{2}2^{\binom{n-1}{2}}. \tag*{(3)}

We now estimate ∣Un∖Tn∣|U_n\setminus T_n|, that is the number of unstable twin-free graphs. First, by Lemma 3.2(1), the number of disconnected graphs on [n][n] is

(1−o(1))n2(n−12).(1-o(1))n2^{\binom{n-1}{2}}.

Comparing to (3), we see this is o(∣Tn∣)o(|\mathcal{T}_n|). It remains to count unstable twin-free connected graphs. By Lemma 3.3, their number is

o(2(n−12))=o(∣Tn∣).o\left(2^{\binom{n-1}{2}}\right)=o(|\mathcal{T}_n|).

Combining the estimates, we obtain

∣Un∖Tn∣=o(∣Tn∣),|\mathcal{U}_n\setminus\mathcal{T}_n|=o(|\mathcal{T}_n|),

and the result follows. □

Corollary 3.4. The number of unstable graphs with vertex set [n][n] is (1−o(1))(n2)2(n−12)(1-o(1))\binom{n}{2}2^{\binom{n-1}{2}}.

Proof. This follows directly from Theorem 1.3, Lemma 3.2[3] and the fact that every graph admitting twins is unstable. □

Theorem 1.4. Almost all unstable twin-free graphs are disconnected.

Proof. Let UTFn\mathcal{U}\mathcal{T}\mathcal{F}_n denote the set of unstable twin-free graphs with vertex-set [n][n] and let UTFDn\mathcal{U}\mathcal{T}\mathcal{F}\mathcal{D}_n denote the set of (unstable) twin-free disconnected graphs with vertex-set [n][n]. Clearly, UTFDn⊆UTFn\mathcal{U}\mathcal{T}\mathcal{F}\mathcal{D}_n\subseteq\mathcal{U}\mathcal{T}\mathcal{F}_n. Observe that starting with a twin-free connected graph with vertex-set [n−1][n-1] and adding an isolated vertex labelled nn, we obtain a graph belonging to UTFDn\mathcal{U}\mathcal{T}\mathcal{F}\mathcal{D}_n. By Lemma 3.2, it follows that ∣UTFDn∣≥(1−o(1))2(n−12)|\mathcal{U}\mathcal{T}\mathcal{F}\mathcal{D}_n|\geq(1-o(1))2^{\binom{n-1}{2}}. On the other hand, observe that UTFn∖UTFDn\mathcal{U}\mathcal{T}\mathcal{F}_n\setminus\mathcal{U}\mathcal{T}\mathcal{F}\mathcal{D}_n consists of unstable twin-free connected graphs. By Lemma 3.3 it follows that ∣UTFn∖UTFDn∣=o(2(n−12))=o(∣UTFDn∣)|\mathcal{U}\mathcal{T}\mathcal{F}_n\setminus\mathcal{U}\mathcal{T}\mathcal{F}\mathcal{D}_n|=o\left(2^{\binom{n-1}{2}}\right)=o(|\mathcal{U}\mathcal{T}\mathcal{F}\mathcal{D}_n|), concluding the proof. □

Definition 3.5. We say that a graph YY arises via Construction 1.5 if there exist distinct a1,a2,b1,b2∈V(Y)a_1,a_2,b_1,b_2\in V(Y) and A,B⊆V(Y)∖{a1,a2,b1,b2}A,B\subseteq V(Y)\setminus\{a_1,a_2,b_1,b_2\} such that Y=X(A,B)Y=X(A,B), where XX is the subgraph of YY induced on V(Y)∖{a1,a2,b1,b2}V(Y)\setminus\{a_1,a_2,b_1,b_2\}.

In the context of Definition 3.5, we will allow the vertices a1,a2,b1,b2a_1,a_2,b_1,b_2 of YY to have other labels, such as elements of [n][n].

Let CXn\mathcal{C}X_n be the set of graphs with vertex-set [n][n] that arise via Construction 1.5. Let UTFCn\mathcal{U}\mathcal{T}\mathcal{F}\mathcal{C}_n denote the set of unstable twin-free connected graphs with vertex-set [n][n].

Proposition 3.6. We have ∣CXn∩UTFCn∣≥(1−o(1))2n2−5n+42|\mathcal{C}X_n\cap\mathcal{U}\mathcal{T}\mathcal{F}\mathcal{C}_n|\geq(1-o(1))2^{\frac{n^2-5n+4}{2}}.

Proof. Choose XX a connected twin-free graph with vertex-set [n−4][n-4]. By Lemma 3.2, there are

(1−o(1))2(n−42)(1-o(1))2^{\binom{n-4}{2}}

choices for XX. Now, choose A,B⊆[n−4]A,B\subseteq[n-4], not both empty. There are

22(n−4)−12^{2(n-4)}-1

choices for AA and BB. By Proposition 2.5, X(A,B)X(A,B) is an unstable twin-free connected graph. Let YY be the graph obtained from X(A,B)X(A,B) by relabelling a1,a2,b1,b2a_1,a_2,b_1,b_2 with n−3,n−2,n−1,nn-3,n-2,n-1,n, respectively. Clearly, Y∈Xn∩UTFCnY\in\mathcal{X}_n\cap\mathcal{UTFC}_n. Moreover, (X,A,B)(X,A,B) can be recovered from YY in the following way: XX is the subgraph of YY induced by [n−4][n-4], A=N(a1)∩[n−4]A=N(a_1)\cap[n-4] and B=N(b1)∩[n−4]B=N(b_1)\cap[n-4]. It follows that distinct (X,A,B)(X,A,B) yield distinct YYs and, in particular,

∣Xn∩UTFCn∣≥(1−o(1))2(n−42)+2n−8=(1−o(1))2n2−5n+42,|\mathcal{X}_n\cap\mathcal{UTFC}_n|\ge(1-o(1))2^{\binom{n-4}{2}+2n-8}=(1-o(1))2^{\frac{n^2-5n+4}{2}},

as required.

Theorem 1.6. Almost all unstable twin-free connected graphs arise via Construction 1.5.

Proof. We need to show

∣UTFCn∖Xn∣=o(∣Xn∩UTFCn∣).|\mathcal{UTFC}_n\setminus\mathcal{X}_n|=o(|\mathcal{X}_n\cap\mathcal{UTFC}_n|).

By Proposition 3.6, it suffices to show that

∣UTFCn∖Xn∣=o(2n2−5n+42).|\mathcal{UTFC}_n\setminus\mathcal{X}_n|=o\left(2^{\frac{n^2-5n+4}{2}}\right).

Let Y∈UTFCn∖XnY\in\mathcal{UTFC}_n\setminus\mathcal{X}_n. By Lemma 3.2(2), the number of bipartite graphs is negligible, so we can assume that YY is nonbipartite. By Lemma 2.2, there exist g1,g2∈Sym⁡(n)g_1,g_2\in\operatorname{Sym}(n) such that g1≠g2g_1\ne g_2 and (g1,g2)∈Aut⁡(BY)(g_1,g_2)\in\operatorname{Aut}(BY). Let G=⟨g1,g2⟩G=\langle g_1,g_2\rangle. By Lemma 2.1(6), it follows that ∣supp⁡(G)∣≥4|\operatorname{supp}(G)|\ge4. If ∣supp⁡(G)∣=4|\operatorname{supp}(G)|=4, then by Corollary 2.4 we have Y∈XnY\in\mathcal{X}_n, which is a contradiction. Hence, ∣supp⁡(G)∣≥5|\operatorname{supp}(G)|\ge5 and the result follows from Lemma 2.7. □

Theorem 1.7. Almost all unstable twin-free connected graphs YY that arise via Construction 1.5 satisfy

Aut⁡(BY)=⟨((a1,0),(a2,0))((b1,1),(b2,1)),τ⟩≅D4\operatorname{Aut}(BY)=\langle((a_1,0),(a_2,0))((b_1,1),(b_2,1)),\tau\rangle\cong D_4

for some distinct vertices a1,a2,b1,b2a_1,a_2,b_1,b_2 of YY.

Proof. Let Y∈Xn∩UTFCnY\in\mathcal{X}_n\cap\mathcal{UTFC}_n and let V:=V(Y)V:=V(Y). By definition, there exist distinct a1,a2,b1,b2∈Va_1,a_2,b_1,b_2\in V and A,B⊆V∖{a1,a2,b1,b2}A,B\subseteq V\setminus\{a_1,a_2,b_1,b_2\} such that Y=X(A,B)Y=X(A,B), where XX is the subgraph of YY induced on V∖{a1,a2,b1,b2}V\setminus\{a_1,a_2,b_1,b_2\}. Let

p:=(a1,a2)∈Sym⁡(V)andq:=(b1,b2)∈Sym⁡(V)p:=(a_1,a_2)\in\operatorname{Sym}(V)\qquad\text{and}\qquad q:=(b_1,b_2)\in\operatorname{Sym}(V)

Note that pp and qq have disjoint support and hence commute. It is clear that

pq=(a1,a2)(b1,b2)∈Aut⁡(Y).pq=(a_1,a_2)(b_1,b_2)\in\operatorname{Aut}(Y).

By Proposition 2.5, we have that

(p,q)=((a1,0),(a2,0))((b1,1),(b2,1))∈Aut⁡(BY),(p,q)=((a_1,0),(a_2,0))((b_1,1),(b_2,1))\in\operatorname{Aut}(BY),

and that

H:=⟨(p,q),τ⟩≅D4.H:=\langle(p,q),\tau\rangle\cong D_4.

Note that the kernel of the action of HH on the canonical bipartition of BYBY is

K:={(id,id),(p,q),(q,p),(pq,pq)}.K := \{(\mathrm{id},\mathrm{id}), (p,q), (q,p), (pq,pq)\}.

Recall that, from Proposition 3.6, we have that

∣CXn∩UTFCn∣≥(1−o(1))(2n2−5n+42).|\mathcal{C}X_n \cap\mathcal{U}\mathcal{T}\mathcal{F}C_n| \ge(1-o(1))\left(2^{\frac{n^2-5n+4}{2}}\right).

In order to establish the claim, it suffices to show that the subset CAn\mathcal{C}A_n, consisting of graphs Y∈CXn∩UTFCnY \in\mathcal{C}X_n \cap\mathcal{U}\mathcal{T}\mathcal{F}C_n for which Aut⁡(BY)>H\operatorname{Aut}(BY)>H, is a negligible subset of CXn\mathcal{C}X_n. In particular, we prove that

∣CAn∣=o(2n2−5n+42).|\mathcal{C}A_n| = o\left(2^{\frac{n^2-5n+4}{2}}\right).

Fix Y∈CAnY \in\mathcal{C}A_n. By Lemma 3.2(2), the number of bipartite graphs is negligible, so we can assume that YY is nonbipartite. Since YY is connected and nonbipartite, the assumption Aut⁡(BY)>H\operatorname{Aut}(BY)>H implies that there exist g1,g2∈Sym⁡(V)g_1,g_2 \in\operatorname{Sym}(V) with g1≠g2g_1 \ne g_2 such that

(g1,g2)∈Aut⁡(BY)∖K.(g_1,g_2) \in\operatorname{Aut}(BY)\setminus K.

Let G:=⟨g1,g2⟩G := \langle g_1,g_2\rangle. By Lemma 2.1(6), we have that ∣supp⁡(G)∣≥4|\operatorname{supp}(G)| \ge4. If ∣supp⁡(G)∣≥5|\operatorname{supp}(G)| \ge5, then by Lemma 2.7, the number of possibilities for YY is at most

o(2n2−5n+42).o\left(2^{\frac{n^2-5n+4}{2}}\right).

We may thus assume that ∣supp⁡(G)∣=4|\operatorname{supp}(G)|=4. We now consider the cases which occur in the proof of Corollary 2.4. In Case 1, there exists AA such that Y=X(A,A)Y=X(A,A) and it follows that Aut⁡(Y)\operatorname{Aut}(Y) admits three distinct double transpositions (with support V∖V(X)V\setminus V(X)). In Subcase 2.1, Aut⁡(Y)\operatorname{Aut}(Y) contains the double transposition g1g2g_1g_2 and if g1g2=pqg_1g_2=pq, then (g1,g2)∈K(g_1,g_2)\in K, contrary to the choice of (g1,g2)(g_1,g_2). Finally, Subcase 2.2 does not occur. Thus, in both cases that do occur, Aut⁡(Y)\operatorname{Aut}(Y) admits two distinct double transpositions. By Lemma 2.8, the number of such YY is at most

o(2n2−5n+42).o\left(2^{\frac{n^2-5n+4}{2}}\right).

Hence, we obtain that

∣CAn∣=o(2n2−5n+42),|\mathcal{C}A_n| = o\left(2^{\frac{n^2-5n+4}{2}}\right),

as desired. □\square

Acknowledment

The authors would like to thank to Rajko Nenadov for several helpful discussions regarding this problem. Ademir Hujdurović gratefully acknowledges the hospitality of the University of Auckland and the award of a Kalman Visiting Scholarship in 2024, during which the research leading to this paper was initiated, as well as financial support from the Slovenian Research and Innovation Agency through research program P1-0404 and research projects N1-0481, N1-0428, N1-0459, J1-70035, J1-70046, J1-70047, and J1-60012.

Declaration of AI use

AI was only used for minor polishing of the text.

References

Faculty of Mathematics and Computer Science, Jagiellonian University, Krakow, Poland and Faculty of Mathematics, University of Cambridge, UK Email address: [email protected]

University of Primorska, Faculty of Mathematics, Natural Sciences and Information Technologies, Glagoljaška 8, 6000 Koper, Slovenia Email address: [email protected]

Department of Mathematics, University of Auckland, Private Bag 92019, Auckland 1142, New Zealand Email address: [email protected]

Department of Mathematics, University of Auckland, Private Bag 92019, Auckland 1142, New Zealand Email address: [email protected]

References

  1. [1]Milad Ahanjideh, István Kovács, and Klavdija Kutnar. Stability of Rose Window graphs. J. Graph Theory, 107(4):810–832, 2024.arxiv.org/abs/2306.01619
  2. [2]Yan-Quan Feng, Klavdija Kutnar, Aleksander Malnič, and Dragan Marušič. On 2-fold covers of graphs. Journal of Combinatorial Theory, Series B, 98(2):324–341, 2008.arxiv.org/abs/math/0701722
  3. [3]Blas Fernandez and Ademir Hujdurović. Canonical double covers of circulants. Journal of Combinatorial Theory, Series B, 154:49–59, 2022.DOI
  4. [4]Philippe Flajolet and Robert Sedgewick. Analytic combinatorics. cambridge University press, 2009.
  5. [5]Chris Godsil and Gordon Royle. Algebraic Graph Theory, volume 207 of Graduate Texts in Mathematics. Springer-Verlag, New York, 2001.DOI
  6. [6]Richard H Hammack, Wilfried Imrich, and Sandi Klavžar. Handbook of product graphs, volume 2. CRC press Boca Raton, 2011.DOI
  7. [7]Ademir Hujdurović and István Kovács. Stability of Cayley graphs and Schur rings. Electron. J. Combin., 32(2):Paper No. 2.49, 23, 2025.DOI
  8. [8]Ademir Hujdurović and Đorđe Mitrović. Some conditions implying stability of graphs. Journal of Graph Theory, 105(1):98–109, 2024.arxiv.org/abs/2210.15249
  9. [9]Ademir Hujdurović, Djordje Mitrović, and Dave Witte Morris. On automorphisms of the double cover of a circulant graph. The Electronic Journal of Combinatorics, 28(4)(P4.43), 2021.
  10. [10]Ademir Hujdurović, Djordje Mitrović, and Dave Witte Morris. Automorphisms of the double cover of a circulant graph of valency at most 7. Algebr. Comb., 6(5):1235–1271, 2023.
  11. [11]Dragan Marušič, Raffaele Scapellato, and N Zagaglia Salvi. A characterization of particular symmetric (0, 1) matrices. Linear Algebra and its Applications, 119:153–162, 1989.
  12. [12]Roman Nedela and Martin Škoviera. Regular embeddings of canonical double coverings of graphs. Journal of Combinatorial Theory, Series B, 67(2):249–277, 1996.
  13. [13]Walter Pacco and Raffaele Scapellato. Digraphs having the same canonical double covering. Discrete Math., 173(1-3):291–296, 1997.
  14. [14]Yan-Li Qin, Binzhou Xia, and Sanming Zhou. Stability of circulant graphs. J. Combin. Theory Ser. B, 136:154–169, 2019.arxiv.org/abs/1802.04921
  15. [15]Yan-Li Qin, Binzhou Xia, and Sanming Zhou. Canonical double covers of generalized Petersen graphs, and double generalized Petersen graphs. J. Graph Theory, 97(1):70–81, 2021.DOI
  16. [16]Steve Wilson. Unexpected symmetries in unstable graphs. Journal of Combinatorial Theory, Series B, 98(2):359–383, 2008.DOI
  17. [17]Dave Witte Morris. On automorphisms of direct products of cayley graphs on abelian groups. The Electronic Journal of Combinatorics, page P3.5, 2021.
  18. [18]Dave Witte Morris. Automorphisms of the canonical double cover of a toroidal grid. Art Discrete Appl. Math., 6(3):Paper No. 3.07, 25, 2023.
  19. [19]Binzhou Xia, Zhishuo Zhang, and Shasha Zheng. Asymptotic stability of cayley graphs on abelian groups. arXiv:2601.20214, 2026.

Paper details

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

views · 0

downloads · 0

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

  • Mathematics

AI

View statement
Looking for related papers…
Contents