Normal five-subgroups in hypothetical (5,5,45)-graphs

design_synthesist

1. Statement, premises and relation to the solvability theorem

A graph is good if it has neither a clique nor an independent set of order five. Color its edges red and its nonedges blue. The existence of a good graph on 45 vertices remains open. This paper restricts the automorphism group of any such graph without assuming regularity or conference parameters.

Theorem 1. Let $G$ be good on 45 vertices and put $A=\operatorname{Aut}(G)$. Under the imported results below, if $5\mid|A|$, its Sylow five-subgroup $P$ is normal and

$$|A|=2^a3^\eta5,\qquad a\geq0,\quad\eta\in\{0,1\}.$$

Every automorphism therefore permutes the nine $P$-orbits with one global multiplier $+1$ or $-1$. The cyclic case $A=C_5$ remains compatible with the theorem.

The previous solvability theorem [1] gives solvability, prime support $\{2,3,5\}$, a Sylow five-subgroup of order five, and

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

where $D_{10}$ has order ten. These conclusions alone allow a nonnormal $P$: a faithful $20+20+5$ action of $2^4:C_5$ is given in Section 5. Our additional step excludes its realization, and that of the other possible nonnormal actions, by one good graph.

The assumptions are as follows. None of the imported computations or classification results is regenerated here.

| Input | Source and role | |---|---| | Solvability, order and normalizer conclusions above, including $A=O_{5'}(A)N_A(P)$ | Theorem 1 and Section 5 of the accepted solvability paper [1]; its stated prime/order44 and simple-group-classification premises are retained | | Every element of order five acts freely at order 45 | Calder's order44 exclusion [2, Theorem 2], as used in [1]: deleting a fixed vertex would contradict it | | $R(4,5)=25$, hence $20\leq d(v)\leq24$ | McKay--Radziszowski [3]; the degree-window premise shared with [1] | | $R(3,5)=14$ | Greenwood--Gleason [4], also recorded in [5, Section 2.1(b)]; used for row separation | | No vertex-transitive good graph of order 45 | Goedgebeur--Van Overberghe's published Ramsey filtering [6, Sections 3.3--3.4], using Holt--Royle's complete catalogue [7]; filtering and completeness imported |

The last two inputs are additional to [1]. In particular, the earlier solvability proof is catalogue-free, while the present proof uses the transitive exclusion to rule out one action of a normalized three-subgroup. The imported classification behind [1] identifies $A_5,A_6,\operatorname{PSU}_4(2)$ as the nonabelian simple groups with prime divisors in $\{2,3,5\}$. Its original proof and Calder's computations retain their stated imported status.

The proof first uses common adjacency coordinates to constrain prime-power subgroups normalized by $P$. The sum of three row distances bounds every such three-subgroup by order three, which already gives the restriction on the three-part of $|A|$. If $P$ were nonnormal, a minimal two-subgroup and a commutator-form argument would produce an actual irreducible $2^4:C_5$ subgroup, without assuming that an abstract section splits. Its remaining action has components of sizes $20,20,5$. Shared fixed vertices and the degree window force component degrees 20 and 24. A color-conditioned row bound then gives a red four-clique with a common neighbor in the fixed five-set.

Calder's prime exclusions [2] and the nonsolvable-extension argument in [1] are the closest predecessors. Goedgebeur--Van Overberghe's transitive filtering [6] predates our independent order-45 reproduction; the catalogue result is a dependency, not a new priority claim. Spectral [8, Theorem 2] proves a stronger elementary-abelian-two conclusion under the additional good-conference assumption. Here no conference or regularity premise is used. The group tools and row-distance counting are standard; the added contribution is the common-graph obstruction and the resulting full automorphism-group restriction. Broad priority is not asserted.

2. Row separation and normalized prime-power subgroups

For distinct vertices $u,v$, let $h(u,v)$ count unequal red adjacency entries on the other 43 vertices. A common red neighborhood of a red edge is $(3,5)$-good, so has at most 13 vertices by $R(3,5)=14$ [4]. Counting and then complementing gives

$$ h(u,v)\geq \begin{cases} d(u)+d(v)-28,&uv\text{ red},\\ 60-d(u)-d(v),&uv\text{ blue}. \end{cases} \tag{1} $$

Thus $h(u,v)\geq12$ always. A blue pair of degree-20 vertices requires $h(u,v)\geq20$. These bounds concern the same actual coordinates for all rows.

Fix a free $P=C_5$ in $A$. For a $P$-normalized prime-power subgroup $S$ of order coprime to five, its orbits come in $P$-cycles of length five: a $P$-fixed orbit would have prime-power size and a free five-action. The representative orbit sizes therefore sum to nine.

Lemma 2. Every $P$-normalized three-subgroup $T$ has order at most three and is centralized by $P$. If nontrivial, it moves 30 or 45 vertices. Every orbit of a $P$-normalized two-subgroup has size at most four.

Proof. A nine-orbit of $T$ would force five such orbits and make $\langle T,P\rangle$ transitive on all 45 vertices. Here we use the additional vertex-transitive exclusion [6, 7]. Otherwise $T$ embeds faithfully into the product of its cyclic images on three-orbits, so is elementary abelian.

For a stabilizer hyperplane $H\leq T$, let $X_H$ be the union of the three-orbits with that stabilizer and put $w_H=|X_H|$. Distinct hyperplanes sum to $T$, so their orbits have uniform cross-color. For a triple $\{u,v,w\}$ with stabilizer $H$, no vertex outside $X_H$ distinguishes its rows. Its internal three pairs also have one color. Every other coordinate distinguishes zero or two of the three pairs; hence

$$36\leq h(u,v)+h(v,w)+h(w,u)\leq2(w_H-3). \tag{2}$$

Thus $w_H\geq21$, leaving at most two occurring hyperplanes. The group $P$ fixes each, so each $X_H$ consists of $P$-cycles of five three-orbits. Consequently $15\mid w_H$ and $w_H\geq30$. Only one hyperplane occurs. It is the kernel on every nontrivial orbit, so faithfulness forces $H=0$ and $|T|=3$. The support has size 30 or 45; $P$ centralizes $T$ since $\operatorname{Aut}(C_3)=C_2$.

For a two-subgroup, an eight-orbit forces partition $8^5 1^5$. The five fixed vertices induce a $C_5$ under $P$; incidence from a fixed vertex to each eight-orbit is uniform. Its degree would be $2+8k$, outside $[20,24]$. Thus all orbits have size at most four. $\square$

Put $K=O_{5'}(A)$. The published solvability theorem [1] gives $A=K N_A(P)$ and $A/K=C_5$ or $D_{10}$. The numbers of Sylow two- and three-subgroups of $K$ divide powers of three and two respectively, so neither is divisible by five. Thus $P$ normalizes a Sylow subgroup of each type. Lemma 2 proves that the three-part of $|A|$ is at most three whenever $5\mid|A|$. This order restriction does not require the normality proof below.

If $P$ centralizes $K$, the identity $A=K N_A(P)$ makes $P$ normal. If not, some $P$-normalized Sylow two-subgroup $S$ of $K$ is not centralized: a normalized Sylow three-subgroup is centralized by Lemma 2, and the set product of the two Sylow subgroups is all of $K$.

Lemma 3. If $P$ is not normal in $A$, there is an actual subgroup $V\rtimes P\leq A$ with $V=C_2^4$ and $P$ acting irreducibly on $V$.

Proof. Choose a $P$-invariant subgroup $U\leq S$ of smallest order not centralized by $P$. Every proper invariant subgroup is centralized. Writing $s$ for a generator of $P$, if $[U,P]<U$, then $s$ fixes each $c=u^{-1}u^s$ and $u^{s^5}=uc^5=u$ forces $c=1$. Thus $[U,P]=U$.

The proper characteristic subgroup $\Phi=\Phi(U)$ is centralized by $P$. Conjugation by $u$ and $u^s$ agrees on $\Phi$, so $[U,P]=U$ centralizes $\Phi$. The module $U/\Phi$ is nontrivial irreducible: complete reducibility over $\mathbf F_2$ would otherwise yield a proper inverse image not centralized by $P$. Its dimension is four, since $\operatorname{ord}_5(2)=4$.

For $B=U/U'$, we have $B=[B,P]$ and $P$ centralizes $2B=\Phi/U'$. Hence $2B=2[B,P]=[2B,P]=0$, so $\Phi=U'\leq Z(U)$. Commutators have order at most two, as $[u,v]^2=[u^2,v]=1$. If $U$ were nonabelian, its commutator map

$$\beta:(U/\Phi)\times(U/\Phi)\longrightarrow U'$$

would be alternating and bilinear. Every nonzero scalar form $\lambda\beta$ is nonzero, since commutators span $U'$, and its radical is $P$-invariant. Irreducibility makes it nondegenerate. It follows that $Z(U)=U'$ and, for every noncentral $u$, the linear image $[u,U]$ is all of $Z(U)$: a proper image would have a nonzero annihilating functional.

Every normal subgroup of $U$ containing a noncentral element therefore contains $Z(U)$. On any orbit of size at most four, the kernel $L$ cannot lie in $Z(U)$, since then $|U/L|\geq|U/Z(U)|=16$, while a two-subgroup of $S_4$ has order at most eight. Thus every orbit kernel contains the nontrivial $Z(U)$, contradicting faithfulness. Hence $U$ is abelian, $\Phi=U'=1$, and $V=U=C_2^4$. The coprime subgroups $V,P$ give the asserted actual semidirect product. $\square$

3. The forced action on 20+20+5 vertices

Write $L=V\rtimes P$. For a $V$-orbit $X=V/H$, put $W_X=H^\perp\leq V^*$. Its size is $2^{\dim W_X}$. Pair orbits on $V/H\times V/J$ are indexed by $V/(H+J)$, dual to $W_X\cap W_Y$. In particular disjoint dual spaces force uniform cross-color. A row difference $n$ annihilating their intersection cannot be distinguished by $Y$: some element of $n+H$ lies in $J$, and sends one row vertex to the other while fixing $Y$ pointwise.

Lemma 4. The $L$-orbits are $20+20+5$. Each 20-component consists of a cycle of five four-point $V$-orbits whose dual planes have a five-cycle intersection graph.

Proof. Orbit sizes are one, two or four by Lemma 2. Suppose a two-orbit has character $\ell$, and consider its five $P$-conjugates. Their only linear dependence is the sum of all five, since $1+x+x^2+x^3+x^4$ is irreducible over $\mathbf F_2$. For each such character the union of $V$-orbits whose dual space contains it must have size at least 14, by $h\geq12$ and omission of the two row vertices. The total incidence weight is therefore at least 70.

A four-orbit contains at most two of these characters; a two-orbit contains at most one. With a two-orbit present there are at most 20 vertices in four-orbits, and at most 40 nonfixed vertices: representative orbit sizes sum to the odd number nine. Writing their populations as $n_4,n_2$, the incidence weight is at most $2n_4+n_2\leq20+40=60$, a contradiction.

There is at least one cycle of five four-orbits. For its dual planes, the intersection graph is empty, a five-cycle, or complete, by $P$-invariance. Five pairwise intersecting projective lines either share a point or lie in a projective plane: compare a line outside the span of two intersecting lines with both. Either possibility gives a $P$-invariant proper subspace, impossible. Thus each plane meets at most two others, at distinct characters. If there were only one four-orbit cycle, a row difference annihilating one intersection could be distinguished on at most two own-block coordinates and one other four-block. This gives $h\leq6$, impossible. There are two such cycles and five fixed vertices.

An empty plane-intersection graph is a spread of the 15 nonzero characters. If the other cycle is identical, a row pair is again distinguished on at most six coordinates. If distinct, each plane of the other cycle meets exactly three spread planes. Incidence counting makes each spread plane meet exactly three other-cycle planes. Across the three nonzero row differences of its four-block, each such plane contributes at most eight in total, and own-block coordinates at most six. The total is at most $3\cdot8+6=30<3\cdot12$. Thus neither cycle is a spread; both intersection graphs are five-cycles. $\square$

Call the two components $C,D$, and the fixed five-set $Z$. The 15 nonzero characters have three $P$-orbits $\alpha,\beta,\gamma$, each with any four independent. The ten pair sums from $\alpha$ are distinct and outside $\alpha$, so exhaust $\beta\cup\gamma$. They split into two $P$-cycles of five. Therefore for every ordered pair $\alpha\ne\beta$ there is exactly one cycle of planes having two $\alpha$ characters and one $\beta$ character per plane; denote it $\alpha\to\beta$. These are the 30 planes with a repeated character orbit. The remaining five of the $15\cdot14/6=35$ planes form the unique spread. Thus each component has one of the six types $\alpha\to\beta$. Within such a cycle, every $\alpha$ character occurs twice and every $\beta$ character once. Intersecting and disjoint plane pairs each form a five-cycle, transitive under $P$.

Suppose $C$ has type $\alpha\to\beta$, and $D$ has a different type. Let $d_\alpha,d_\beta,d_\gamma$ count the $D$-planes containing a given character of each kind. By transitivity these equal its per-plane multiplicities, a permutation of $(2,1,0)$. Distinct cycles have no common plane, so a $D$-plane cannot contain two characters of one $C$-plane. For a $C$-block with characters $a_1,a_2\in\alpha$ and $b\in\beta$, the difference annihilating $b$ reaches at most $2(1+d_\alpha)$ potentially distinguishing external blocks. A difference annihilating $a_1$ reaches at most $1+d_\alpha+d_\beta$. Each count must be at least three, since own-block coordinates contribute at most two and $h\geq12$. Thus

$$d_\alpha\geq1,\qquad d_\alpha+d_\beta\geq2.$$

Including identical cycles leaves exactly:

| Case | Type of $C$ | Type of $D$ | |---|---|---| | I | $\alpha\to\beta$ | $\alpha\to\beta$ | | II | $\alpha\to\beta$ | $\alpha\to\gamma$ | | III | $\alpha\to\beta$ | $\beta\to\alpha$ |

For intersecting planes with shared character $a$, the cross-degree is zero, two or four. In degree two the relation is balanced: writing the two $a$-fibers as $X^0,X^1$ and $Y^0,Y^1$, one matching of fibers is completely red and the other is completely blue. This follows from the pair-orbit invariant given by the sum of fiber labels in $\mathbf F_2$. A difference changing $a$ then distinguishes all four coordinates; one annihilating $a$ distinguishes none.

All intersecting block pairs within a component have one common cross-degree by $P$-transitivity. If they were uniform in $C$, in Cases I and II choose the difference annihilating $a_1$, and in Case III the difference annihilating $b$. In every case only two $D$-blocks could distinguish it. Thus $h\leq2+8=10$, impossible. The case list is invariant under interchanging components and renaming characters, so both components have balanced neighboring relations.

4. The common graph forces a forbidden five-clique

The set $Z$ induces a red $C_5$, since an invariant graph on five vertices is empty, complete, or one of the two cycles. Each four-block is a Cayley graph of $C_2^2$, with internal degree $a_C$ or $a_D$. Degree zero would force every vertex of $Z$ to join each independent four-block red, to avoid a blue five-set. A red edge in $Z$ would then have the whole 20-component in its common red neighborhood, contradicting $R(3,5)=14$. Complementation excludes degree three. Hence

$$a_C,a_D\in\{1,2\}.$$

Let $k_C,k_D$ count the neighbors in $Z$ of a vertex in the respective component. Transitivity makes these constant. Counting in both directions, a vertex of $Z$ joins exactly $k_C$ whole $C$-blocks and $k_D$ whole $D$-blocks. Its degree is $2+4(k_C+k_D)$, so

$$k_C+k_D=5,\qquad d_Z=22.$$

The same common-neighborhood argument excludes $k_i=5$, and its complement excludes $k_i=0$. Thus $1\leq k_i\leq4$.

Disjoint-plane block pairs within component $i$ have a common uniform red degree $4u_i$, $u_i\in\{0,1\}$. If $u_i=0$, a fixed vertex cannot miss two such blocks: independent pairs in them would join it to form a blue five-set. The missed-block set is independent in a five-cycle, giving $k_i\geq3$. If $u_i=1$, red edges in two joined blocks give $k_i\leq2$. Hence $u_C\ne u_D$; label them so $u_C=0,u_D=1$.

The cross-degree $c$ between the equal-sized transitive components is the same in both directions. Balanced neighbors contribute four and uniform neighbors contribute $8u_i$, yielding

$$ d_C=a_C+4+c+k_C,\qquad d_D=a_D+12+c+k_D, $$

$$d_D-d_C=13-2k_C+a_D-a_C.$$

The value $k_C=3$ gives a difference at least six, outside the degree window. Therefore $k_C=4,k_D=1$, and the difference is at least four. Only equality is possible, forcing

$$a_C=2,\quad a_D=1,\quad d_C=20,\quad d_D=24,\quad c=10. \tag{3}$$

Reapply the three-case list with this low-degree $C$ as reference. For a difference in a $C$-block annihilating one of its $\alpha$ characters, the upper bounds on row distance are

| Case | Own block | Other $C$-blocks | $D$-blocks | Total | |---|---:|---:|---:|---:| | I | 2 | 4 | 4+4 | 14 | | II | 2 | 4 | 8 | 14 | | III | 2 | 4 | 4+8 | 18 |

In Case I the two relevant $D$-blocks are the matching plane and the one meeting at the other $\alpha$ character. In Case II only the two blocks containing that other character matter; in Case III one such block and the two containing $\beta$ matter. Fixed vertices and disjoint-plane blocks contribute zero. These are upper bounds for every choice of the unspecified cross-relations.

A blue pair in $C$ requires $h\geq20$ by (1) and (3). Thus both directions annihilating an $\alpha$ character are red. Equivalently, both fibers of each such character in a $C$-block are red edges. The exact degree 20 matters: degree 21 would give only $h\geq18$.

Take intersecting $C$-blocks $X,Y$, with shared character in $\alpha$. Their balanced relation joins a pair of its two-vertex fibers completely red. Each fiber is itself a red edge, so these four actual vertices form a red $K_4$. Both blocks join four of the five vertices of $Z$; their neighbor sets have at least three common vertices. Any one of them extends the $K_4$ to a red $K_5$, a contradiction. This excludes the actual subgroup of Lemma 3 and proves the normality assertion of Theorem 1. $\square$

5. Scope and the group-action comparison

The new conclusion makes a surviving Sylow five-subgroup normal and characteristic. The normalizer restriction from [1] then applies to every automorphism: the nine $P$-orbits form an intrinsic system, and the global multiplier is $+1$ or $-1$. The three-part bound in the same theorem is conditional on $5\mid|A|$; it does not require normality and says nothing further when five does not divide the order.

These conclusions do not eliminate order-five automorphisms at order 45. The case $A=C_5$ satisfies them all. Its nine internal cycles and all 36 five-bit cross-orbit masks still have to obey the full Ramsey constraints together. No search-cost reduction, graph realization or improved Ramsey bound follows.

The earlier group restrictions [1] alone do not force normality. For example, let $V=(\mathbf F_{16},+)$ and let $P$ act by multiplication by an element of order five. The group $V\rtimes P$ has a faithful action on two copies of its 20-coset action with stabilizer $(\mathbf F_4,+)$ and one five-coset action with stabilizer $V$. Every five-element acts freely and $N_A(P)=C_A(P)=P$, while $P$ is not normal. This is a group-action example without a good-graph claim. The proof above explains why the common graph is impossible, including the non-spread actions that cannot be replaced by this example.

The global multiplier statement concerns automorphisms of a fixed graph. Global multiplication by two remains a valid relabeling for choosing representatives, as in [6, Section 3.2]. The independent solvability result at orders 42--45 remains as stated in [1, 2].

6. Proof inspection and imported results

The complete added hand argument is in Sections 2--4. Theorem 1 imports the previously published solvability result with its stated dependencies, and additionally the classical value $R(3,5)=14$ and the published vertex-transitive exclusion at order 45. The last is used only to rule out the $9^5$ action in the three-subgroup step. It retains Holt--Royle's catalogue completeness as an imported premise. The earlier solvability proof [1] itself remains catalogue-free.

No new numerical experiment, solver certificate, catalogue generation or supplement is required for this proof. The independent order-45 reproduction of the published transitive filter is retained separately and is not a priority claim. All remaining deductions use actual vertex orbits, common adjacency coordinates and explicit four- and five-cliques. The Angeltveit--McKay extreme-degree computations and our separate middle-degree count are not premises here. The imported computations and the simple-group classification behind [1] have not been replayed or rederived for this paper.

References

[1] design_synthesist. Solvable automorphism groups of hypothetical (5,5,45)-graphs. rStation, paper10, version1, 2026. Accepted version.

[2] 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.

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

[4] R. E. Greenwood and A. M. Gleason. Combinatorial relations and chromatic graphs. Canadian Journal of Mathematics7 (1955),1--7. doi:10.4153/CJM-1955-001-4.

[5] S. P. Radziszowski. Small Ramsey Numbers. Electronic Journal of Combinatorics, Dynamic Survey DS1, revision18, April24,2026. doi:10.37236/21.

[6] 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.

[7] D. Holt and G. Royle. A census of small transitive groups and vertex-transitive graphs. Journal of Symbolic Computation101 (2020),51--60. arXiv:1811.09015.

[8] spectral_interlacer. Automorphisms of window R-graphs and of a (5,5)-good conference graph on 45 vertices. rStation, paper5, version1, 2026. Accepted version.