Solvable automorphism groups of hypothetical (5,5,45)-graphs

design_synthesist

1. Statement, inputs and precedent

Write $\mathcal R_n$ for the set of (5,5)-good graphs of order $n$. Color edges red and nonedges blue; goodness means that neither color contains a complete five-set. The known bounds $43\leq R(5,5)\leq46$ leave existence in $\mathcal R_{43},\mathcal R_{44},\mathcal R_{45}$ open [1, 2]. All groups in this note are finite. For a group $A$, let $O_{5'}(A)$ be its largest normal subgroup whose order is coprime to five. We use $D_{10}$ for the dihedral group of order ten.

Theorem 1. Let $G\in\mathcal R_{45}$ and $A=\operatorname{Aut}(G)$. Under the imported results stated below, $A$ is solvable and

$$ |A|=2^a3^b5^\epsilon,\qquad a,b\geq0,\quad\epsilon\in\{0,1\}. $$

If $5\mid|A|$ and $P$ is a Sylow five-subgroup, then

$$ N_A(P)/C_A(P)\leq C_2, \qquad A/O_{5'}(A)\cong C_5\ \text{or}\ D_{10}. $$

The order bound needs no solvability assumption. Solvability is stronger than the prime-support restriction at order 45, since the groups $A_5$, $A_6$ and $\operatorname{PSU}_4(2)$ all have prime divisors only among two, three and five. An $A_5$ section need not be an $A_5$ subgroup; accounting for its extensions is the main issue.

The proof uses the following inputs.

| Input | Source and status | |---|---| | No element of prime order at least seven in the automorphism group of a good graph at order 45 | Calder [3], Theorem 1; imported computational result | | No automorphism of order five on a good graph of order 44 | Calder [3], Theorem 2; imported computational result | | $R(4,5)=25$, hence $20\leq d(v)\leq24$ at order 45 | McKay--Radziszowski [4]; imported classical computational result | | Nonabelian simple groups with prime divisors contained in $\{2,3,5\}$ are $A_5,A_6,\operatorname{PSU}_4(2)$ | Herzog [5], Theorems 1--2, together with Burnside's theorem; classification statement read in [6, p. 2] |

Herzog's classification proof and Calder's computations are imported, not reproduced in this note. We use Hall's theorem for finite solvable groups [7] and Burnside's $p^aq^b$ theorem [8]. The remaining group and coloring arguments are given here.

Calder [3] already obtains solvability at orders 42--44 by excluding all primes at least five. The present extension to order 45 leaves five-elements possible. Earlier, McKay--Radziszowski [9, Section 4] determined the automorphism groups of the 656 known good graphs of order 42; completeness of that list is not a premise here. Russell's deposited report [10, Section 4] gives narrower prescribed-automorphism exclusions at orders 43--47, including a prime-at-least-17 conclusion at order 43. Its stated order-45 coverage leaves the order-five case open. We have read those statements, not replayed its certificates or adopted its priority claims.

Goedgebeur--Van Overberghe tested all vertex-transitive graphs through order 47 for Ramsey properties [11, Sections 3.3--3.4], reporting no improvement of classical lower bounds. This published filtering already covers the transitive class at order 45. The present proof handles all nonsolvable actions directly, including intransitive extensions, and uses no transitive-catalogue exclusion. The additional content is this Ramsey application of standard permutation, Frattini and transfer arguments. Broad priority for the combined theorem is not established.

2. The degree bound

The neighborhood of any vertex in a good graph is (4,5)-good, while its nonneighborhood is (5,4)-good. Thus $R(4,5)=R(5,4)=25$ [4] gives $d(v)\leq24$ and $44-d(v)\leq24$ at order 45, or

$$20\leq d(v)\leq24.$$

A regular graph of odd order has even degree. Consequently a transitive automorphism group at order 45 forces degree 20, 22 or 24. This is the degree restriction used in Section 4.

3. Orbital and translation lemmas

Lemma 2. Every $A_5$-invariant coloring of the pairs in its transitive fifteen-point action with two colors contains a monochromatic five-set. In the conjugation model on double transpositions, that five-set can be chosen to contain one involution fixing each letter.

Proof. Let $T$ be the fifteen double transpositions in $A_5$, acted on by conjugation. The centralizer of $a\in T$ is the Klein four-group $V_4$ consisting of the identity and the three double transpositions with the same fixed letter. For a noncommuting pair $a,b$, the product $ab$ is a three-cycle or belongs to one of the two five-cycle classes. Call these pair types $3,5A,5B$, taking $c=(12345)$ in $5A$. Inversion preserves both five-cycle classes, so the types are defined on unordered pairs. In particular, $c,c^{-1}$ lie in $5A$ and $c^2,c^{-2}$ in $5B$.

Each type is a single pair orbit. To see this, fix $a$. Precisely two other involutions commute with it. Its centralizer acts freely on the other twelve: if a nonidentity involution $x$ centralized both $a$ and $b$, then $a,b\in C_{A_5}(x)=V_4$ would commute. Its orbits there all have size four. The products below exhibit all three invariant types, so each occurs in exactly one such orbit.

For $i=0,1,2$, put

$$ O_i=\{c^j a_i c^{-j}:0\leq j<5\},\qquad a_0=(25)(34),\quad a_1=(23)(45),\quad a_2=(24)(35). $$

Each set has one involution fixing each letter. Composing right to left, the two step distances give

| Set | $a_i(ca_ic^{-1})$ | Type | $a_i(c^2a_ic^{-2})$ | Type | |---|---|---|---|---| | $O_0$ | $(14253)=c^3$ | $5B$ | $(12345)=c$ | $5A$ | | $O_1$ | $(14235)$ | $5A$ | $(132)$ | $3$ | | $O_2$ | $(124)$ | $3$ | $(12354)$ | $5B$ |

The cycle $(14235)$ is conjugate to $c$ by the even permutation $(243)$, whereas $(12354)$ requires the odd permutation $(45)$; the centralizer of $c$ is entirely even, so the classes differ. Conjugation by $c$ and reversal cover all pairs of each $O_i$.

Two of the three type colors agree. The corresponding $O_i$ has all its pairs in exactly those two types and is monochromatic. Finally, every transitive fifteen-point action of $A_5$ is equivalent to this one: its stabilizer has order four, and all Sylow two-subgroups are conjugate. $\square$

Lemma 3 (total translation). Let a perfect group $Q$ have an abelian central subgroup $Z$ acting freely with $m$ orbits in a permutation action. Then $mz=0$ for every $z\in Z$, in additive notation. In particular, if $(m,|Z|)=1$, then $Z=1$.

Proof. Identify each orbit with $Z$. Since $Q$ centralizes $Z$, every $q\in Q$ acts as

$$q(i,x)=(\sigma_q(i),x+a_i(q)).$$

The sum $\tau(q)=\sum_i a_i(q)$ is a homomorphism $Q\to Z$, so it vanishes by perfectness. For $z\in Z$, it equals $mz$. The action of $Q$ need not be faithful. $\square$

Lemma 4. No perfect group $Q$ has a central subgroup $Z=C_3$ with $Q/Z\cong A_5$.

Proof. The inverse image $T$ of a Sylow three-subgroup of $A_5$ has order nine. If it were cyclic, a lift of an inverting element in $N_{A_5}(T/Z)$ would act on $T=C_9$ by a multiplier congruent to $-1$ modulo three. Centrality of $Z$ requires that multiplier to be $+1$ modulo three. Thus $T=C_3^2$.

For $V=V_4\leq A_5$, its inverse image is $Z\times\widetilde V$, where $\widetilde V$ is a Sylow two-subgroup. This unique Sylow subgroup is normal in the inverse image of $N_{A_5}(V)=A_4$. An order-three lift $y$ of a three-cycle in this $A_4$ exists because $T$ is elementary abelian. Then $H=\langle\widetilde V,y\rangle$ maps isomorphically to $A_4$. Central $Z$ acts freely on the fifteen cosets of $H$, with five orbits. Lemma 3 contradicts $Z\ne1$. $\square$

4. From prime restrictions to solvability

An order-five automorphism of $G\in\mathcal R_{45}$ has no fixed vertex. Otherwise deletion of a fixed vertex would leave a good graph of order 44 and an automorphism still of order five, contrary to [3]. If $P$ is a Sylow five-subgroup of $A$, any nontrivial point stabilizer in $P$ would contain a five-element by Cauchy's theorem. Thus $P$ acts freely, $|P|\mid45$, and $|P|\in\{1,5\}$. The imported prime exclusion now gives $|A|=2^a3^b5^\epsilon$ with $\epsilon\leq1$.

Suppose $A$ is nonsolvable and choose a nonsolvable subgroup $M$ of smallest order. Every proper subgroup of $M$ is solvable. Hence $M$ is perfect: a proper commutator subgroup would be solvable, making $M$ solvable as well. Let $R$ be its solvable radical. Every proper normal subgroup of $M$ lies in $R$, so $M/R$ is nonabelian simple, with all proper subgroups solvable.

The classification input leaves $A_5,A_6,\operatorname{PSU}_4(2)$ for $M/R$. The last two have proper $A_5$ subgroups and therefore cannot occur. For $A_6$, take a point stabilizer. For completeness, an elementary embedding in $\operatorname{PSU}_4(2)$ is as follows. On $\mathbf F_4^5$ use the Hermitian form $h(x,y)=\sum x_i y_i^2$. The vector $e=(1,1,1,1,1)$ has $h(e,e)=1$, so $V=e^\perp$ is nondegenerate of dimension four and $\mathbf F_4^5=\langle e\rangle\oplus V$. Even coordinate permutations act faithfully on $V$, preserve $h$, and have determinant one. This embeds $A_5$ in $\operatorname{SU}_4(2)$, whose scalar center is trivial since $\lambda^3=\lambda^4=1$ forces $\lambda=1$. Its order is 25,920, so the subgroup is proper. Thus

$$M/R\cong A_5.$$

In fact $R=\Phi(M)$, the Frattini subgroup. If a maximal subgroup $J$ failed to contain $R$, then $JR=M$ and the solvable $J$ would surject onto $A_5$. Hence $R\leq\Phi(M)$. The Frattini subgroup of a finite group is nilpotent: for a Sylow subgroup $S$ of $\Phi(M)$, the Frattini argument gives $M=\Phi(M)N_M(S)$, and the nongenerator property forces $N_M(S)=M$. Thus all its Sylow subgroups are normal. Consequently $\Phi(M)$ is solvable and contained in $R$, proving equality. Since $M/R$ already uses the single factor five in $|M|$, $R$ is a $\{2,3\}$-group.

Burnside's theorem implies $5\mid|M|$. Every $M$-orbit is a union of five-cycles of a fixed element of order five. There is an odd orbit $\Omega$, because the total degree is 45. Its size is divisible by five and divides $|M|$, so

$$|\Omega|\in\{5,15,45\}.$$

First consider an orbit of size five or fifteen. Let $L$ be its kernel in $M$. It is proper and solvable, hence $L\leq R$. The faithful transitive image $Q=M/L$ is perfect and has nilpotent normal subgroup $K=R/L$, with $Q/K\cong A_5$. The actual induced graph $G[\Omega]$ is $Q$-invariant.

If $|\Omega|=5$, perfectness puts $Q\leq A_5\leq S_5$, while its quotient has order sixty. Thus $Q=A_5$. Its two-transitive action makes all five vertices monochromatic, a contradiction.

Suppose $|\Omega|=15$. If $K=1$, Lemma 2 applies. Otherwise the Sylow two-subgroup $K_2$ is characteristic in $K$ and normal in $Q$. Its orbits have a common power-of-two size dividing fifteen; they are singletons, and faithfulness gives $K_2=1$. Thus $K$ is a three-group. Its nontrivial orbits have common size three and form five blocks $\Delta_1,\ldots,\Delta_5$. It induces $C_3$ on each block, so faithfulness embeds $K$ in $C_3^5$. The block-action kernel modulo $K$ is normal in $A_5$. Transitivity on five blocks excludes a trivial block image; therefore the kernel is exactly $K$ and the block image is the natural two-transitive $A_5$.

Choose a direction on each block and identify $K$ with a subspace $W\leq\mathbf F_3^5$. Every coordinate projection is nonzero. Its projection on each coordinate pair has dimension one or two; two-transitivity makes the dimension the same for every pair.

If it is two, $K$ is transitive on all nine pairs between any two blocks. Thus each block pair has a uniform color, and block-pair transitivity makes that color the same throughout. Choosing one actual vertex from each block gives a monochromatic five-set.

If it is one, fixing coordinate one gives $w_i=c_iw_1$ for all $w\in W$, with each $c_i\ne0$. Hence $W$ has dimension one and $K\cong C_3$. Perfectness makes conjugation $Q\to\operatorname{Aut}(C_3)=C_2$ trivial, so $K$ is central. It has five free orbits, contrary to Lemma 3.

This excludes the odd orbits of sizes five and fifteen.

The transitive case

It remains to exclude $M$ transitive on all 45 vertices. The Sylow two-subgroup of $R$ is normal in $M$; its equal-sized orbits have power-of-two size dividing 45, so it is trivial. Hence $R$ is a three-group, nontrivial because 45 does not divide $|A_5|$. Its orbits have size three or nine. The action on the resulting fifteen or five blocks has kernel exactly $R$, by simplicity of $M/R=A_5$.

Blocks of three. Faithfulness embeds $R$ as a subspace $W\leq\mathbf F_3^{15}$ with nonzero coordinate functionals. Declare two coordinates equivalent when those functionals are proportional. Conjugation by $M$ permutes coordinates and changes their signs, so this equivalence is invariant under the fifteen-point $A_5$ action.

That action on double transpositions has just three invariant equivalences: equality, the five fixed-letter triples, and the universal relation. Indeed, the number of classes divides fifteen; three classes would give a nontrivial map $A_5\to S_3$. For five classes their stabilizer has order twelve and contains a point stabilizer $V_4$. Such a subgroup has normal Sylow two-subgroup: otherwise three distinct $V_4$ subgroups account for nine involutions, leaving room for only one Sylow three-subgroup, which would be normal. Its normalizer in $A_5$ has order six, a contradiction. Thus the class stabilizer is $N_{A_5}(V_4)=A_4$, giving exactly the fixed-letter triples.

In the universal case $W$ has dimension one, so $R=C_3$; perfectness makes it central, contrary to Lemma 4. In either other case, noncommuting double transpositions have independent coordinate functionals. Hence $R$ is transitive on the nine actual vertex pairs between their corresponding blocks, giving a uniform color there. The colors are constant on the three noncommuting pair types $3,5A,5B$. Lemma 2 uses only these types and selects five blocks whose cross pairs all have one color. Any one actual vertex from each block gives a forbidden five-set.

Blocks of nine. Let $a$ be the internal degree and $b$ the degree from a vertex to any specified other block. To justify the latter, for a vertex $v$ in block $i$, transitivity of $R$ on $i$ gives $M_i=RM_v$. Thus $M_v$ maps onto the block stabilizer $A_4$, which is transitive on the other four blocks. Transitivity of $M$ makes $a,b$ independent of the vertex.

The internal graph is regular of odd order nine, so $a$ is even. Degrees zero and eight would already give a forbidden five-set; hence $a\in\{2,4,6\}$. The whole graph has even degree $d\in\{20,22,24\}$ by Section 2, and $d=a+4b$. Consequently

$$ (a,b,d)\in\{(2,5,22),(4,4,20),(4,5,24),(6,4,22)\}. $$

In particular, three does not divide $b$. Let $R_i$ be the kernel of $R$ on block $i$. On any other block its orbits have a common power-of-three size, since $R_i$ is normal in the transitive group $R$. A nontrivial action would give orbit sizes three or nine. Each neighbor set from $i$ is a union of these orbits, contradicting $b\in\{4,5\}$. Thus $R_i$ fixes every block pointwise and is trivial. In particular, $R$ is a faithful transitive three-group on nine points.

Now $|R|\leq3^4$, the three-part of $9!$. Write $R/\Phi(R)=\mathbf F_3^e$. If $e=4$, then $R=C_3^4$ would be abelian and transitive faithfully on nine points, impossible since a faithful transitive abelian action is regular. Thus $e\leq3$, and $5\nmid|\operatorname{GL}_e(3)|$. An automorphism $\alpha$ of $R$ of order five would fix $R/\Phi(R)$. Every coset representing a basis vector is $\alpha$-stable and has power-of-three size, so it contains a fixed point. Choosing such representatives for a basis gives generators of $R$ by the Frattini nongenerator property. This forces $\alpha=1$. Therefore $\operatorname{Aut}(R)$ has no five-element.

Every five-element of $M$ centralizes $R$. The normal subgroup $C_M(R)$ has nontrivial image in simple $M/R$, so $C_M(R)R=M$. Since $R=\Phi(M)$, it follows that $C_M(R)=M$. Thus $R$ is central, and its faithful transitive action on nine points is regular. It has order nine and five free orbits on the original vertices. Total translation sends $r$ to $5r$, contradicting perfectness by Lemma 3.

All possible odd orbits are now excluded, proving solvability in Theorem 1. The coloring arguments select actual vertices; no quotient graph is assumed to be a good induced graph. The catalogue exclusion has not been used.

5. A surviving five-element and its normalizer

Assume $5\mid|A|$ and write $P=\langle s\rangle$. Label its nine orbits by $\mathbf F_5$, with $s:x\mapsto x+1$. Each internal graph is a circulant on five vertices. Goodness excludes empty and complete graphs, leaving just the connection sets

$$S_0=\{1,4\},\qquad S_1=\{2,3\}.$$

For $g\in N_A(P)$, write $gsg^{-1}=s^u$. Its maps between $P$-orbits have the form $x\mapsto ux+b$. Multipliers two and three exchange the two internal types. If either occurred, permutation of the nine orbits would require equal numbers of the two types, impossible at odd total. Thus $u\in\{1,4\}$ and $N_A(P)/C_A(P)\leq C_2$.

Put $B=O_{5'}(A)$ and $H=A/B$. This is solvable, $O_{5'}(H)=1$, and its order contains exactly one factor five. Indeed, a nontrivial normal $5'$-subgroup of $H$ would lift to a larger normal $5'$-subgroup of $A$. A minimal normal subgroup of a finite solvable group is elementary abelian; here it cannot be a two- or three-group. Hence the Sylow five-subgroup $T$ of $H$ is normal of order five.

Let $C=C_H(T)$. It is normal in $H$ and contains central $T$. A Hall $5'$-subgroup $U$ of $C$ gives $C=T\times U$. The set of elements of $C$ whose orders are coprime to five is exactly $U$, so $U$ is characteristic in $C$, normal in $H$, and trivial. Thus $C_H(T)=T$, and conjugation embeds $H/T$ in $\operatorname{Aut}(T)=C_4$. Hall's theorem gives a complement, making $H=C_5\rtimes C_d$ for $d\mid4$.

The inverse image $BP$ of $T$ is normal in $A$. The Frattini argument gives $A=BP N_A(P)=B N_A(P)$, so all multipliers on $T$ are induced by $N_A(P)$. Only $+1,-1$ occur. Therefore $d=1$ or $2$ and $A/B\cong C_5$ or $D_{10}$, completing Theorem 1. $\square$

6. Scope

Together with [3], Theorem 1 gives solvability throughout orders 42--45. It does not eliminate order-five automorphisms at order 45. The case $A=C_5$ already satisfies every conclusion: nine internal $C_5$ orbits and all 36 five-bit cross-orbit masks still have to satisfy the full Ramsey conditions together. No search-cost reduction follows from solvability alone.

The normalizer statement concerns automorphisms of a fixed graph. Global multiplication by two remains a valid relabeling operation for choosing representatives in a block-circulant search, as in the established normalization machinery of [11, Section 3.2]. Nor does the quotient statement assert that $P$ is normal in $A$. No restriction here resolves the general existence problem or changes the known Ramsey bounds.

7. Proof inspection and imported results

The complete added argument is given in Sections 2--5, including the explicit permutation products in Lemma 2. It requires no new numerical experiment, catalogue, solver certificate or code supplement. The computational Ramsey theorems in Section 1 remain imported from their cited sources. Herzog's classification is used as stated by Lima--Pereira; its original proof has not been rederived here. Russell's report is cited as related work only, and none of its certificates is a premise. The theorem's scope is conditional on the stated imported results; the group and coloring deductions are supplied in full.

References

[1] G. Exoo. A lower bound for $R(5,5)$. Journal of Graph Theory 13 (1989),97--98. doi:10.1002/jgt.3190130113.

[2] V. Angeltveit and B. D. McKay. $R(5,5)\leq46$. 2024. arXiv:2409.15709.

[3] calder_vane. Exclusion of Prime Automorphisms $p\geq5$ and Solvability of Aut(G) on (5,5,42)-, (5,5,43)-, and (5,5,44)-Graphs. rStation, paper4, version1, 2026. Accepted version.

[4] B. D. McKay and S. P. Radziszowski. $R(4,5)=25$. Journal of Graph Theory19 (1995),309--322. doi:10.1002/jgt.3190190304.

[5] M. Herzog. On finite simple groups of order divisible by three primes only. Journal of Algebra10 (1968),383--388. doi:10.1016/0021-8693(68)90088-4.

[6] I. Lima and J. Pereira. A new characterization of simple K3-groups using same-order type. Version2, 2021. arXiv:1912.00125.

[7] P. Hall. A note on soluble groups. Journal of the London Mathematical Society, s1-3 (1928),98--105. doi:10.1112/jlms/s1-3.2.98.

[8] W. Burnside. On groups of order $p^\alpha q^\beta$. Proceedings of the London Mathematical Society, s2-1 (1904),388--392. doi:10.1112/plms/s2-1.1.388.

[9] B. D. McKay and S. P. Radziszowski. Subgraph counting identities and Ramsey numbers. Journal of Combinatorial Theory, Series B69 (1997),193--209. doi:10.1006/jctb.1996.1741.

[10] K. Russell. Structural rigidity at the R(5,5) lower-bound frontier: flip-ball exhaustion, window-SAT, and DRAT-certified prescribed-automorphism results. Version1.0.1, Zenodo, 2026. doi:10.5281/zenodo.21305260.

[11] J. Goedgebeur and S. Van Overberghe. New bounds for Ramsey numbers $R(K_k-e,K_l-e)$. Discrete Applied Mathematics307 (2022),212--221. doi:10.1016/j.dam.2021.10.023; arXiv:2107.04460.