Partial Symmetries and Symmetry Levels of Graphs - A Census

NEW

Problem: For a finite simple graph $\Gamma$, interpret a partial automorphism as an isomorphism between induced subgraphs. Its rank is the size of its domain. The symmetry level is

$$\lambda(\Gamma)=\frac1{|V(\Gamma)|}\max\{\operatorname{rank}(\phi):\phi \text{ is a non-identity partial automorphism of }\Gamma\}.$$

This is the formalization supported by the paper title/context on partial symmetries and asymmetric graphs. The question asks whether, for arbitrarily large $k\ge2$, there is a graph of order $n$ with $\lambda(\Gamma)=(n-k)/n$.

Result: Yes. In fact, for every $k\ge2$ such a graph exists.

We use the following standard random-graph fact: for every fixed $k$ and sufficiently large $s$, there is a graph $F$ on $s$ vertices such that

1. $\delta(F)>2k$;
2. $F-U$ is connected for every $|U|<k$;
3. if $|U|,|W|<k$, then every isomorphism $F-U\to F-W$ is the identity; in particular $U=W$.

This follows by a union bound in $G(s,1/2)$: the probability of a low-degree vertex or a cut of size $<k$ tends to $0$, and the probability that a fixed non-identity near-spanning partial bijection preserves all adjacencies is exponentially small, while there are only $s^{O(k)}$ near-identity choices and $2^{O(s\log s)}$ total choices.

Now choose $k^2$ distinct vertices of $F$, denoted $a_{i,j}$ for $1\le i,j\le k$. Take two disjoint copies $F^0,F^1$ of $F$, and add vertices $r_1,\dots,r_k$. Make the $r_i$ independent, and join $r_i$ exactly to the $k$ vertices $a^1_{i,1},\dots,a^1_{i,k}$ in the copy $F^1$. Add no edges from any $r_i$ to $F^0$.

Let

$$X=V(F^0)\cup V(F^1),\qquad |X|=2s.$$

The induced graph on $X$ is two disjoint copies of $F$, so swapping the two copies is a nontrivial partial automorphism of rank $2s$. The full graph has order

$$n=2s+k,$$

so this gives level at least

$$\frac{2s}{2s+k}=\frac{n-k}{n}.$$

We show no larger nontrivial partial automorphism exists. Let $\phi:D\to E$ be a partial automorphism with $|D|=|E|>2s$. Since only $k$ vertices lie outside $X$, both $D$ and $E$ contain at least one $r_i$, and each omits fewer than $k$ vertices of $X$.

A vertex $r_i$ has degree at most $k$ inside any induced subgraph, while every vertex of $X\cap D$ has induced degree $>k$, because $\delta(F)>2k$ and fewer than $k$ vertices of $X$ are omitted. Hence $\phi$ maps the $r_i$’s to $r_i$’s and $X\cap D$ to $X\cap E$.

The restriction of $\phi$ to $X$ is therefore an isomorphism between two induced subgraphs obtained from two copies of $F$ by deleting fewer than $k$ vertices. By the rigidity property of $F$, it either preserves the two copies pointwise or swaps them canonically.

If it preserves the copies, then $r_i\mapsto r_j$ with $i\ne j$ is impossible: fewer than $k$ vertices of $X$ were deleted, so some neighbor $a^1_{i,h}$ of $r_i$ remains, but $r_j$ is not adjacent to $a^1_{i,h}$. Thus every $r_i$ in the domain is fixed, and $\phi$ is the identity.

If it swaps the copies, take any $r_i\in D$. Some neighbor $a^1_{i,h}$ of $r_i$ remains in $D$. Its image is $a^0_{i,h}$, but no $r_j$ is adjacent to any vertex of $F^0$, contradiction.

Thus no nontrivial partial automorphism has rank $>2s=n-k$. Therefore

$$\lambda(\Gamma)=\frac{n-k}{n}.$$

Since $k\ge2$ was arbitrary, the requested graphs exist for arbitrarily large $k$.

Citation: No known published resolution is being invoked; the construction above is self-contained, using only standard Erdős–Rényi random-graph estimates.