Conjecture on the expected size of the two-fold automorphism group of a random graph

Expected two-fold automorphism groups of random graphs are asymptotically trivial

In Conjecture 6.6 of Constructions of graphs with any possible two-fold automorphism and automorphism groups, Bartłomiej Bychawski asks whether a uniformly random labeled graph $\Gamma_n$ satisfies

$$\lim_{n\to\infty}\mathbb E\bigl[|\operatorname{Aut}^{\pi}(\Gamma_n)|\bigr]=1. \tag{1}$$

We prove a stronger statement: the same limit holds for the entire two-fold automorphism group, not merely its projection, and for every Erdős–Rényi random graph with fixed edge probability $0<p<1$.

There is a small domain issue in the original formulation that needs to be made explicit. Its Definition 1.4 defines $\operatorname{Aut}^{\pi}(G)$ only for reduced graphs, meaning graphs with pairwise distinct open neighborhoods, whereas Conjecture 6.6 averages over all labeled graphs. For every graph, reduced or otherwise, the two-fold automorphism group is unambiguously defined by

$$\operatorname{Aut}^{\mathrm{TF}}(G) =\left\{(\alpha,\beta)\in S_n^2: A_{ij}=A_{\alpha(i),\beta(j)}\text{ for all }i,j\in[n] \right\}, \tag{2}$$

where $A$ is the symmetric zero-diagonal adjacency matrix of $G$. Its first-coordinate image

$$\Pi(G)=\operatorname{pr}_1\operatorname{Aut}^{\mathrm{TF}}(G) \tag{3}$$

is the canonical all-graphs extension of the two-fold projection group. By Proposition 1.6 of the cited paper,

$$\Pi(G)=\operatorname{Aut}^{\pi}(G) \quad\text{and}\quad |\Pi(G)|=|\operatorname{Aut}^{\mathrm{TF}}(G)| \qquad\text{if }G\text{ is reduced}. \tag{4}$$

For arbitrary graphs we always have

$$1\leq |\Pi(G)|\leq |\operatorname{Aut}^{\mathrm{TF}}(G)|. \tag{5}$$

We will prove

$$\boxed{ \mathbb E\bigl[|\operatorname{Aut}^{\mathrm{TF}}(G(n,p))|\bigr] \longrightarrow 1 \qquad(0<p<1\text{ fixed}). } \tag{6}$$

In particular, (5) proves the conjecture under its canonical all-graphs interpretation. We will also obtain the same conclusion when the expectation is conditioned on reduced graphs, so the result covers the original definition without any extension at all.

1. Equality constraints for a prescribed permutation pair

Write

$$\rho=\max\{p,1-p\}<1. \tag{7}$$

The random variables $X_{\{i,j\}}=A_{ij}$ for unordered pairs $\{i,j\}$ are independent Bernoulli variables of parameter $p$, and $A_{ii}=0$ deterministically.

Fix $(\alpha,\beta)\in S_n^2$. For every ordered pair $i\neq j$, condition (2) requires

$$X_{\{i,j\}}= \begin{cases} X_{\{\alpha(i),\beta(j)\}},&\alpha(i)\neq\beta(j),\\ 0,&\alpha(i)=\beta(j). \end{cases} \tag{8}$$

An instance of (8) is called changed if its right-hand side is either zero or an edge variable different from $X_{\{i,j\}}$. Denote by $D(\alpha,\beta)$ the number of changed ordered-pair constraints. Conditions arising from $i=j$ are additional restrictions; we may omit those when obtaining an upper bound, but the zero-valued right-hand sides in (8) are retained.

Construct a constraint multigraph whose ordinary vertices are the edge variables occurring in changed constraints, together with one distinguished ground vertex $0$. Each changed equality contributes an edge between its two variables or between its variable and $0$.

Each edge variable can occur as the left-hand side of at most two changed constraints, corresponding to the two orientations of its underlying edge. It can also occur as the right-hand side of at most two changed constraints: prescribing either orientation of its target uniquely determines $(i,j)$ because $\alpha$ and $\beta$ are bijections. Thus every ordinary vertex has degree at most four. If $V_*$ is the number of ordinary vertices in nontrivial components, then

$$D(\alpha,\beta)\leq4V_*. \tag{9}$$

An ungrounded component with $k\geq2$ ordinary vertices requires all its bits to agree. Its probability is

$$p^k+(1-p)^k\leq \rho^{k-1}. \tag{10}$$

A grounded component containing $k$ ordinary vertices forces all of them to be zero and has probability

$$(1-p)^k\leq\rho^k. \tag{11}$$

The components involve disjoint sets of independent edge variables. Their total number of independent equality or grounding constraints is therefore

$$r= \sum_{\substack{C\text{ ungrounded}}}(|C|-1) +\sum_{\substack{C\text{ grounded}}}|C| \geq\frac{V_*}{2} \geq\frac{D(\alpha,\beta)}8. \tag{12}$$

Consequently,

$$\mathbb P\bigl((\alpha,\beta) \in\operatorname{Aut}^{\mathrm{TF}}(G(n,p))\bigr) \leq\rho^{D(\alpha,\beta)/8}. \tag{13}$$

2. Lower bounds from the permutation supports

Let

$$a=|\operatorname{supp}(\alpha)|, \qquad b=|\operatorname{supp}(\beta)|, \qquad s=a+b. \tag{14}$$

An ordered pair $i\neq j$ contributes an unchanged constraint only when

$$\{\alpha(i),\beta(j)\}=\{i,j\}. \tag{15}$$

There are two possibilities. First, $\alpha(i)=i$ and $\beta(j)=j$, giving at most $(n-a)(n-b)$ ordered pairs. Second, $\alpha(i)=j$ and $\beta(j)=i$; since $j$ is determined by $i$, there are at most $n$ such ordered pairs. Therefore

$$\begin{aligned} D(\alpha,\beta) &\geq n(n-1)-(n-a)(n-b)-n\\ &=ns-ab-2n. \end{aligned} \tag{16}$$

Because $a,b\leq n$, we have

$$2ab\leq n(a+b)=ns. \tag{17}$$

Hence, whenever $s\geq8$,

$$D(\alpha,\beta) \geq\frac{n(s-4)}2 \geq\frac{ns}{4}. \tag{18}$$

For $3\leq s\leq7$, the sharper estimate $ab\leq s^2/4$ gives

$$D(\alpha,\beta) \geq n(s-2)-\frac{s^2}{4} \geq n-\frac{49}{4}. \tag{19}$$

There are no permutations with support of size one. Thus the remaining nonidentity case $s=2$ consists of a transposition in one coordinate and the identity in the other. Every ordered pair whose first coordinate is moved, or whose second coordinate is moved in the symmetric case, produces a changed constraint, whereas all remaining ordered pairs are unchanged. Consequently,

$$D(\alpha,\beta)=2(n-1) \qquad(s=2). \tag{20}$$

3. Summing over every possible two-fold automorphism

The number of permutations with support size exactly $a$ is at most $n^a$. Hence the number of permutation pairs with total support $s$ is at most

$$(s+1)n^s. \tag{21}$$

The identity pair contributes exactly $1$ to the expectation. By (13), (18)–(21), and linearity of expectation,

$$\begin{aligned} 0 &\leq \mathbb E\bigl[|\operatorname{Aut}^{\mathrm{TF}}(G(n,p))|\bigr]-1\\ &\leq n^2\rho^{(n-1)/4} +30n^7\rho^{(n-49/4)/8} +\sum_{s=8}^{2n}(s+1) \left(n\rho^{n/32}\right)^s. \end{aligned} \tag{22}$$

Set

$$q_n=n\rho^{n/32}. \tag{23}$$

Since $0<\rho<1$ is fixed, $q_n\to0$, and for all sufficiently large $n$,

$$\sum_{s=8}^{2n}(s+1)q_n^s \leq \sum_{s=8}^{\infty}(s+1)q_n^s =\frac{q_n^8(9-8q_n)}{(1-q_n)^2} \longrightarrow0. \tag{24}$$

Both preceding terms in (22) also tend to zero exponentially. This proves (6).

Finally, let $R_n$ be the event that $G(n,p)$ is reduced. For two vertices $u\neq v$ to have identical open neighborhoods, the edge $uv$ must be absent and all $n-2$ pairs of incident edges must agree. Therefore

$$\mathbb P(R_n^c) \leq\binom n2(1-p) \bigl(p^2+(1-p)^2\bigr)^{n-2} \longrightarrow0. \tag{25}$$

On $R_n$, equation (4) identifies the source's original two-fold projection group with the full two-fold automorphism group. Thus

$$1 \leq \mathbb E\bigl[ |\operatorname{Aut}^{\pi}(G(n,p))|\mid R_n \bigr] \leq \frac{ \mathbb E[|\operatorname{Aut}^{\mathrm{TF}}(G(n,p))|] }{\mathbb P(R_n)} \longrightarrow1. \tag{26}$$

Taking $p=1/2$ proves Conjecture 6.6 both for its canonical all-graphs projection (3) and, without any extension of the author's definition, for random reduced graphs. The separate graph-modification Conjecture 6.5 is not asserted here.