Erdős problem #552: a certified one-branch reduction at \(n=39\)

Audit and computation date: 2026-07-26 UTC.

Result

The uniform Erdős problem remains open. I obtained a concrete finite reduction at the first value not settled in the current small-Ramsey table:

Every possible 46-vertex witness is necessarily 7-regular and every vertex lies in either two or three triangles. After a complete symmetry normalization, the case in which the distinguished vertex lies in two triangles is UNSAT. I generated a 360,378-line DRAT certificate and independently checked it with drat-trim. Consequently, if a witness exists, every vertex lies in three triangles. Such a witness is exactly a 6-regular triangle graph arising from a linear \(46_3\) configuration, augmented by a perfect matching, with the union still \(C_4\)-free. The existence of this object is the remaining finite question.

This is a clean reduction, not a solution of the infinitely-many-\(n\) question.

Claim labels used below are:

• [a] elementary-rigorous;
• [b] rigorous modulo the explicitly named published theorem;
• [c] plausible or structural but unverified;
• [d] computational-only (including certificate-checked computation).

Step 0: page and collision audit

LIVE ORIGIN UNAVAILABLE — RECENT INDEXED PAGE SNAPSHOT, NOT LIVE-ORIGIN VERIFIED

[d] I used the required Bright Data browser route four times. Cloudflare reported that the browser and Cloudflare were working but the origin host failed with HTTP 522; the independent exits shown were Chicago, Atlanta, Newark, and Miami. A direct fetch returned 403, and the text-proxy route also timed out. The last Bright Data attempt was at 2026-07-26 23:50:40 UTC. Therefore I could not honestly call any copy a live-origin read.

[d] The freshest retrievable search-engine snapshot of the problem page, indexed within the preceding month, says that the page was last edited on 2026-02-01. I also checked the site's upstream repository at commit e5145a87748092babd7b4f990c493c0ab46edf10, dated 2026-07-26 19:08:01 UTC; its generated index still records problem 552 as open. The repository metadata is only corroboration and does not replace the page.

The snapshot's verbatim problem statement is:

Determine the Ramsey number \[ > R(C_4,S_n), > \] where \(S_n=K_{1,n}\) is the star on \(n+1\) vertices. In particular, is it true that, for any \(c>0\), there are infinitely many \(n\) such that \[ > R(C_4,S_n)\leq n+\sqrt{n}-c? > \]

[d] Collision check. The snapshot has status OPEN, offers \$100 (so the supplied no-prize tracker metadata is stale), and says that no partial or complete solution is claimed in the comments. It shows one comment, no unincorporated comment activity, and None for each of the participation fields: likes, interested in collaborating, currently working, difficult, tractable, results could be formalised, and working on formalisation. Thus the freshest checkable data contains neither a claimed proof nor a current worker. The page also classifies the uniform problem as not resolvable by a finite computation.

[d] Comment audit. The sole comment is by StijnC, dated 2025-10-27. It points out Parsons' two infinite exact families, mentions an unpublished Füredi result, and points to the Wu--Sun--Zhang--Radziszowski work for \(n=q^2-2\). It claims no proof of the problem; the page says the comment has been incorporated.

Results listed on the page

The following are page-reported results, not new claims here.

• [b] Burr--Erdős--Faudree--Rousseau--Schelp and Parsons give

\[ n+\sqrt n-6n^{11/40}\le R(C_4,S_n) \le n+\lceil\sqrt n\rceil+1. \] The lower bound uses prime gaps; under Cramér's conjecture the page states the lower error as \(n^{o(1)}\).

• [b] For every prime power \(q\), Parsons proved

\[ R(C_4,S_{q^2+1})=(q^2+1)+\lceil\sqrt{q^2+1}\rceil \] and \[ R(C_4,S_{q^2})=q^2+\lceil\sqrt{q^2}\rceil+1. \] Hence both offsets in \(n+\lceil\sqrt n\rceil+\{0,1\}\) occur infinitely often.

• [b] The page says subsequent exact results concern

\(n=q^2\pm t\), \(0\le t\le q\), citing Parsons, Wu--Sun--Zhang--Radziszowski, and two Zhang--Chen--Cheng papers. Every exact case currently listed has offset 0 or 1. Zhang--Chen--Cheng speculate that this holds for every \(n\ge2\); that speculation would give a negative answer to the displayed Erdős question.

• [b] The page also records the questions whether, for

\(f(n)=R(C_4,S_n)\), equality \(f(n+1)=f(n)\) occurs infinitely often and with density zero, and whether \(f(n+1)\le f(n)+2\) always.

The page cites [BEFRS89], [Er93, p.345], [Er94b], [Er95], and [Er96] for the problem, identifies it as question 19 in the Ramsey Theory part of the graphs problem collection, links OEIS A006672, and marks the statement as not formalised.

Primary-source and current-literature audit

1. [b] Original source. Burr, Erdős, Faudree, Rousseau, and Schelp,

Some Complete Bipartite Graph--Tree Ramsey Numbers, Annals of Discrete Mathematics 41 (1989), 79--89, is available as the Erdős archive PDF and at DOI 10.1016/S0167-5060(08)70452-770452-7). Section 4 contains the asymptotic question and the \$100 offer. I inspected the PDF rather than relying on a secondary citation.

1. [b] General bound and designs. Parsons,

Ramsey Graphs and Block Designs. I, Transactions of the AMS 209 (1975), 33--44, DOI 10.2307/1997368, is the primary design-theoretic source behind the page's general upper bound and prime-power cases.

1. [b] Star--wheel equality. Zhang, Broersma, and Chen,

A remark on star-\(C_4\) and wheel-\(C_4\) Ramsey numbers, EJGTA 2(2) (2014), 110--114 (primary PDF), proves the star--wheel equality for the relevant range. Care is essential: their \(W_n=K_1+C_n\) has \(n+1\) vertices, whereas later tables also use wheel subscripts for the order.

1. [b] Bounds near the present finite case. Wu, Sun, and Radziszowski,

Wheel and Star-critical Ramsey Numbers for Quadrilateral, Discrete Applied Mathematics 186 (2015), 260--271, DOI 10.1016/j.dam.2015.01.003 and author PDF, gives in Table 2 the bounds \(m+6\) and \(m+7\) for wheels of order \(38\le m\le43\). Applying the star--wheel index shift at \(m=40\) gives \(46\le R(C_4,K_{1,39})\le47\).

1. [b] Current table. Radziszowski's

Small Ramsey Numbers, revision DS1.18, dated 2026-04-24, explicitly lists \[ R(C_4,K_{1,39})=46\text{--}47 \] in Table IVa and says all values through \(n=38\) are known.

1. [b] 2026 exact-value preprint. Boza,

arXiv:2409.12770v2, revised 2026-06-12, determines the formerly unknown values through \(n=38\) and embeds explicit House of Graphs certificates.

1. [c] Indexing discrepancy, deliberately not used. Boza v1 printed

\(f(39)\le46\), and v2's compressed table prints /46 in that cell while citing the wheel paper. This conflicts with both DS1.18's explicit \(46\)--\(47\) entry and the underlying wheel table after the necessary \(W_{n+1}\) order shift. The most likely explanation is a one-step wheel indexing error, but I have not treated that diagnosis as a theorem and have not used the apparent upper bound.

1. [b] Recent survey. Chen, Zhang, Zhang, et al.,

Star-quadrilateral Ramsey Number and Beyond, Advances in Mathematics (China) 54(2) (2025), 292--314, is a directly relevant recent survey. It predates Boza's June 2026 revision; DS1.18 is the newer small-value table.

[c] Search miss. Searches by exact Ramsey expression, title, citations, wheel-equivalence terminology, arXiv, the current dynamic survey, and the problem discussion found no claimed solution to the uniform question and no post-DS1.18 determination of the \(n=39\) value. This is evidence, not a proof that no unindexed result exists.

Ramsey translation and the known \(n=39\) interval

Let \(G\) be the graph formed by one color on \(N\) vertices. Its complement contains no \(K_{1,n}\) exactly when

or equivalently

Thus a coloring witnessing

is exactly a \(C_4\)-free \(N\)-vertex graph with \(\delta(G)\ge N-n\). [a]

For \(n=39\), the published upper bound gives

[b]

Explicit lower-bound certificate

I fetched House of Graphs graph 52632, a 43-vertex \(C_4\)-free graph used as \(H_{43}\) in Boza's paper. The full adjacency list is embedded in erdos552_wave5z_verify.py, so verification does not depend on the network. Its degree distribution is 37 vertices of degree 6 and 6 of degree 7.

Add two nonadjacent vertices 43 and 44 with respective neighborhoods

The resulting graph has:

• 45 vertices and 144 edges;
• degree histogram \(\{6:27,\,7:18\}\);
• maximum pair-codegree 1;
• no \(C_4\), checked independently by pair-codegrees and by enumerating all

four-sets and all three cyclic orders;

• \(\Delta(\overline G)=38<39\).

The SHA-256 of the canonical edge text u-v\n, in lexicographic vertex order, is 9197c5369534fc94766792f2e5134dd24088777725b7e017dbab396b1d4856f5. These are [d] exhaustive checks. The Ramsey translation then gives

[a+d] This reproduces the known lower endpoint; it is an explicit independently checkable certificate, not a new numerical bound.

Combining (1) and (2) yields the current interval \(46\)--\(47\). [b+d]

Elementary reduction of the 46-vertex question

Assume that \(G\) is a \(C_4\)-free graph on 46 vertices with \(\delta(G)\ge7\). Fix \(v\), put

Lemma 1: \(G\) is 7-regular

For any \(u\in A\), \(u\) has at most one neighbor in \(A\): two such neighbors together with \(u,v\) would form a \(C_4\). Also, distinct vertices of \(A\) have disjoint neighborhoods in \(B\): a common \(B\)-neighbor together with \(v\) would form a \(C_4\). Since every \(u\in A\) has degree at least 7, it has at least

neighbors in \(B\). Therefore

Hence \(d\le7\). Since \(d\ge\delta(G)\ge7\), \(d=7\). This applies to every vertex, so \(G\) is 7-regular. [a]

Lemma 2: every vertex lies in two or three triangles

The graph \(G[A]\) has maximum degree at most 1, hence is a matching. Write

Because \(G\) is 7-regular, the number of edges from \(A\) to \(B\) is

No \(B\)-vertex is counted twice, while \(|B|=38\), so

As \(G[A]\) is a matching on seven vertices, \(t_v\le3\). Thus

Each edge of \(G[A]\) is exactly one triangle through \(v\), proving the claim. [a]

Exhaustive normalization

Relabel \(v=0\) and \(A=\{1,\ldots,7\}\). Any matching of a fixed size on seven labeled-afterward vertices is isomorphic to the canonical matching below. The disjoint \(A\)-to-\(B\) neighborhoods can then be relabeled as consecutive groups. This loses no graphs. [a]

The exact labels used by the checker are:

• \(t_0=2\): groups

\(8\!:\!12,13\!:\!17,18\!:\!22,23\!:\!27,28\!:\!33,34\!:\!39,40\!:\!45\);

• \(t_0=3\): groups

\(8\!:\!12,13\!:\!17,18\!:\!22,23\!:\!27,28\!:\!32,33\!:\!37,38\!:\!43\), with vertices 44 and 45 adjacent to no vertex of \(A\).

Here each range is inclusive.

SAT encoding and checked certificate

For every unordered pair \(0\le u<v<46\), introduce the edge variable \(x_{uv}\), giving \(\binom{46}{2}=1035\) primary variables.

1. At each vertex, a sequential-counter cardinality encoding imposes degree

exactly 7.

1. For every four-set \(a<b<c<d\), the three possible undirected cyclic

orders are forbidden:

cnf.append([-x(a,b), -x(b,c), -x(c,d), -x(a,d)])
cnf.append([-x(a,b), -x(b,d), -x(c,d), -x(a,c)])
cnf.append([-x(a,c), -x(b,c), -x(b,d), -x(a,d)])

1. Unit clauses impose one of the two exhaustive normal forms above.

There are

\(C_4\)-clauses. With the sequential-counter auxiliaries and normalization, both cases have exactly 25,507 variables and 538,831 clauses. The complete executable encoding, including all unit clauses, is in the companion Python file. The graph-to-CNF reduction and the three cycle clauses are [a]; the exact-degree clauses are [b], modulo PySAT's standard CardEnc.equals(..., EncType.seqcounter) cardinality encoder; the generated counts and solver results are [d].

\(t_0=2\): UNSAT, proof checked

PySAT 1.9.dev7 with cadical195 returned UNSAT in 0.85 seconds without proof logging and 1.66 seconds while regenerating the proof. The generated files were:

The workspace drat-trim binary has SHA-256 f8d971dc5956a73fa37e655a44ba8f6d128976acfedff7129f2ed251b234af1a; it returned s VERIFIED. The companion script regenerates both files, asserts their hashes, invokes the independent checker, and requires the word VERIFIED. [d]

Because any vertex with \(t_v=2\) could be relabeled as vertex 0, this certificate excludes every graph having even one such vertex. Therefore every surviving graph must satisfy

[a+d]

\(t_0=3\): unresolved

The identical base CNF with the second normalization did not terminate under a 150-second cadical195 cap or a separate 130-second kissat404 cap. No result is inferred from either timeout. [d]

Exact structure of the remaining case

Assume (4).

1. Every vertex lies in exactly three triangles. Two distinct triangles

cannot share an edge, since their two third vertices and the shared edge's endpoints would contain a \(C_4\). [a]

1. Counting vertex--triangle incidences gives

\[ \#\{\text{triangles}\}=\frac{46\cdot3}{3}=46. \] These edge-disjoint triangles use \(46\cdot3=138\) edges. A 7-regular graph on 46 vertices has \(46\cdot7/2=161\) edges, leaving 23. At each vertex the three triangles use six incident edges, so the remaining edges form a perfect matching \(M\). [a]

1. Regard the 46 graph triangles as 3-element blocks on the 46 vertices.

Every point lies in three blocks and any pair is in at most one block. Thus they form a linear symmetric \(46_3\) configuration. Its bipartite Levi graph is cubic on 92 vertices and has girth at least 10:

• a Levi 4-cycle repeats a point-pair in two blocks;
• a Levi 6-cycle creates a graph triangle whose three edges already belong

to other blocks, contradicting edge-disjointness of graph triangles;

• a Levi 8-cycle creates a graph \(C_4\).

[a]

1. Let \(L\) be the 6-regular graph consisting of all block-triangle edges.

Every matched pair in \(M\) has \(L\)-distance at least 4: distances 1 and 2 would make the edge a triangle edge (distance 2 also directly forces a \(C_4\) using its two incident blocks), while a distance-3 path plus the matching edge is a \(C_4\). In addition, the entire union \(L\cup M\) must remain \(C_4\)-free. [a]

Conversely, constructing such a \(46_3\) configuration and perfect matching with \(L\cup M\) 7-regular and \(C_4\)-free gives the missing 46-vertex Ramsey witness; the SAT encoding is an exact direct search for the same object. [a]

Therefore the residual decision has an unambiguous consequence:

• a SAT model proves \(R(C_4,K_{1,39})=47\);
• an independently checked UNSAT certificate for the \(t_0=3\) case proves

\(R(C_4,K_{1,39})=46\).

This is the precise finite computation still needed.

Why this does not settle the Erdős question

Even a determination of \(R(C_4,K_{1,39})\) is one isolated value. The page's question requires infinitely many \(n\), for every fixed \(c>0\), so no finite table can close it. [a]

The existing standard mechanisms point in opposite but insufficient directions:

• projective-plane/polarity witnesses, paired with known upper-bound

arguments, explain many exact values with offset 0 or 1 from \(n+\lceil\sqrt n\rceil\), but do not furnish an infinite family satisfying the required strict upper inequality;

• the prime-gap construction gives the page's asymptotic lower bound, but its

present error term is unbounded and therefore does not prove \(R(C_4,S_n)\ge n+\sqrt n-O(1)\).

Thus a uniform solution still needs one of two genuinely new lemmas:

1. positive direction: an infinite construction/upper-bound mechanism

forcing \(R(C_4,S_n)\le n+\sqrt n-c\) for arbitrarily prescribed fixed \(c\); or

1. negative direction: a uniform lower bound strong enough to exclude

that, for example \(R(C_4,S_n)\ge n+\sqrt n-O(1)\) with the constant controlled sharply enough.

Neither the local \(n=39\) classification nor the checked literature supplies such a lemma. This is the theoretical wall. [c]

For the finite residual search, a sensible next experiment is triangle-aware cube-and-conquer on the \(46_3\) incidence structure rather than the raw edge CNF. An illustrative budget of 512 cubes at five minutes each is \(42.7\) core-hours, roughly \$2--\$5 at \$0.05--\$0.10 per core-hour; 4096 such cubes is \(341.3\) core-hours, roughly \$17--\$34. These are budget calculations, not runtime predictions. A full UNSAT run may also need multi-gigabyte proof storage. I did not launch it here.

Reproduction

The standalone verifier is runs/erdos552_wave5z_verify.py, SHA-256 9fbdf2f6f1880298ed6cf092c183a4023cfdee8ceef2facdaba6b224dcc29152. Its default mode uses only the Python standard library and is network-free:

python3 runs/erdos552_wave5z_verify.py

It recomputes the elementary reduction arithmetic, reconstructs the explicit 45-vertex graph, checks the graph data, and performs two independent exhaustive \(C_4\) checks.

Optional SAT mode requires python-sat:

python3 runs/erdos552_wave5z_verify.py --sat-case 2

To regenerate and independently check the DRAT proof:

proof_tmp=$(mktemp -d /tmp/erdos552-recheck.XXXXXX)
python3 runs/erdos552_wave5z_verify.py \
  --sat-case 2 \
  --proof-dir "$proof_tmp" \
  --drat-trim sitting_ducks_tierB/hadamard_668/.external-audit.va1jUb/repo/lp333/proof_phase2/tools/drat-trim/drat-trim

The final tested output included:

feasible degrees in the 46-vertex reduction: [7]
feasible t_v values before SAT: [2, 3]
all-t_v=3 counts: 46 triangles, 138 triangle edges, 23 residual edges
base degree histogram: {6: 37, 7: 6}
degree histogram: {6: 27, 7: 18}
maximum pair-codegree: 1
explicit C4 witnesses: 0
maximum complement degree: 38
normalized SAT case t=2: 25507 variables, 538831 clauses
SAT result: UNSAT
DRAT-trim: VERIFIED

python3 -m py_compile passed. git diff --check reports no whitespace error in either deliverable. Unrelated pre-existing worktree changes were not modified.

PARTIAL: Reduced the unresolved value \(R(C_4,S_{39})\in\{46,47\}\) to the all-\(t_v=3\) case, DRAT-verified the \(t_v=2\) case impossible, and isolated the remaining \(46_3\)-configuration search; the uniform Erdős question remains open.