gpt 6 astra ultra attempt on Math-510

The Ramsey Number R$5,5$

Definitions and mathematical statement

Shared notation.

Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

For positive integers $s,t$, $R(s,t)$ is the least $N$ such that every red--blue colouring of the unordered pairs of an $N$-element set contains either a red complete graph on $s$ vertices or a blue complete graph on $t$ vertices. Edges inside the chosen vertices must all have the specified colour. Determine the integer $R(5,5)$, not merely its order of magnitude. [S1] [S2]

Statement recorded in the supplied source.

What is the exact value of $R(5,5)$, the smallest number $n$ such that any 2-coloring of the edges of $K_n$ contains a monochromatic $K_5$? [S1]

Residual task reported by the archive.

The embedded review $2026-08-17$ records: Construct a $5,5$-Ramsey graph on 43--45 vertices or rule out each such order. [S1]

Short English statement

How many vertices force five mutually connected vertices of one colour, regardless of how every edge is coloured red or blue?

Research attempt

Status: UNRESOLVED. We derive degree and triangle constraints on any candidate Ramsey graph and an exact finite satisfiability formulation. We prove a small explicit lower-bound construction and identify the precise certification needed at the unresolved orders. The results do not improve the published bound.

Context and chosen attack.

The primary abstract of Angeltveit--McKay [S2], consulted 1 October 2026, reports $R(5,5)\le46$ using linear programming and independently implemented computations. That large computation was not rerun here. We attack the candidate graph directly by neighborhood constraints and double counting, then test why the resulting numerical conditions do not decide existence. We use a deliberately weaker elementary bound where it makes the derivation self-contained.

Graph formulation and the elementary recursion.

Colour edges of a graph $G$ red and its nonedges blue. The required candidate has both clique number and independence number at most four. If $R(s-1,t)\le a$ and $R(s,t-1)\le b$, then $R(s,t)\le a+b$: at a vertex of a graph on $a+b$ vertices either its neighborhood has at least $a$ elements, or its nonneighborhood has at least $b$. In the first case a clique of size $s-1$ can be extended by the vertex, and in the second case an independent $(t-1)$-set can be extended. The alternative monochromatic set already has the required size.

The initial values $R(2,t)=t$ and symmetry give successively \[ R(3,3)\le6,\quad R(3,4)\le10,\quad R(3,5)\le15, \quad R(4,4)\le20,\quad R(4,5)\le35, \quad R(5,5)\le70. \] These upper bounds require no computation, but their final value is weaker than [S2]. The recursion does not keep correlations among overlapping neighborhoods, which is one reason its inequalities can be far from sharp.

Necessary degree intervals.

Let $n=|G|$ and suppose neither $G$ nor its complement contains $K_5$. A neighborhood cannot contain $K_4$ or an independent five-set. Therefore, using only the elementary $R(4,5)\le35$, every degree is at most $34$. Apply the same statement in the complement to obtain \[ n-35\le d(v)\le34. \] For comparison, if one imports the sharper value $R(4,5)=25$ from the small-Ramsey survey [S3], the identical argument gives $n-25\le d(v)\le24$. This latter numerical input is a literature dependency, not derived here. At order 43 it confines degrees to $18,\ldots,24$ but does not specify the edges.

The same principle applies to common neighborhoods: the common neighborhood of a red edge has no red triangle and no blue $K_5$. Thus it has fewer than $R(3,5)$ vertices, and the elementary bound above gives at most 14. Complementing gives the corresponding blue restriction. These are necessary pairwise intersection constraints, stronger than degree data alone.

A triangle identity valid for every colouring.

Let $M$ be the number of monochromatic triples. Every nonmonochromatic triple has exactly two vertices incident to one edge of each colour. Count such incidences at vertices to obtain \[ M=\binom n3-\frac12\sum_v d(v)(n-1-d(v)). \] This is an equality, not a probabilistic approximation. Since $d(n-1-d)\le (n-1)^2/4$, it gives \[ M\ge \binom n3-\frac{n(n-1)^2}{8}. \] For $n=43$ the right side is $3085.25$, so the integer $M$ is at least 3086. This abundant supply of monochromatic triangles still does not force a monochromatic five-clique: extending triangles requires intersections among three same-colour neighborhoods. The identity controls a total count without their distribution.

In particular, an argument that every triangle has many common neighbors would need a separate proof. Average graph degree, or the triangle identity alone, supplies no such pointwise lower bound. This is the first failure of the simple density-based attack.

A concrete small construction.

Partition 16 vertices into four parts of size four. Put red edges within parts and blue edges between parts. A red clique is contained in one part and has size at most four. A blue clique contains at most one vertex from each part and also has size at most four. Hence $R(5,5)\ge17$. This weaker lower bound is proved explicitly to verify the formulation; it is not a competitor to the source's much larger known constructions. Blowing up a part further immediately creates a red $K_5$, while adding a fifth nonempty part immediately creates a blue $K_5$. The most direct enlargement of this construction is therefore blocked.

Exact certification formulation.

For each unordered pair $\{u,v\}$ introduce a Boolean variable $x_{uv}$, true for a red edge. For every five-set $S$, impose both clauses \[ \bigvee_{\{u,v\}\subset S} x_{uv},\qquad \bigvee_{\{u,v\}\subset S}\neg x_{uv}. \] There are $\binom n2$ variables and $2\binom n5$ clauses, each of length ten. A satisfying assignment is exactly a graph with neither type of five-clique: each clause excludes one of the two monochromatic colourings on its five-set. Conversely every desired graph supplies a satisfying assignment. Degree and common-neighborhood inequalities are additional necessary constraints, never replacements for these clauses.

Colour complementation allows one fixed edge to be red in any search with $n\ge2$, because a colouring or its complement satisfies this restriction. Arbitrarily fixing several neighborhoods would not be a valid symmetry reduction without a proof that every isomorphism class has such a representative. A proposed counterexample must be checked on all five-sets; an unsatisfiability claim must certify completeness of the search and correctness of any symmetry restrictions.

Verification and exact remaining gap.

The construction and identities above are proved directly and require no machine output. No SAT solver or exhaustive 43-vertex search was run. The missing result is existence or nonexistence of the candidate graphs at the remaining orders, not the ability to encode that question. Coupling neighborhood types through their shared edges is the next concrete task; feasible degree sequences and aggregate triangle counts need not be realizable by any graph. The global exact value remains unresolved by this attempt.

Sources

• S1 ULAM.AI, UnsolvedMath, supplied problems.json, record 29 (COMB-003), statement and background. The embedded literature-review date is 2026-08-17; that is the archive’s review date, not a fresh certification. Dataset landing page: https://huggingface.co/datasets/ulamai/UnsolvedMath.

• S2 V. Angeltveit and B. D. McKay, R$5,5$ <= 46, arXiv:2409.15709 $2024$. https://arxiv.org/abs/2409.15709. Bibliographic information from the supplied record.

• S3 S. Radziszowski, Small Ramsey Numbers, Dynamic Survey DS1, Electronic Journal of Combinatorics (updated 2026). https://www.cs.rit.edu/~spr/ElJC/ejcram18.pdf. Bibliographic information from the supplied record.