# Verification report — OPG-60013 (Morrison–Noel: weak saturation of the cube in the clique) Verification date: 2026-10-19 (three independent verification runs; the third on the text of the note). **Verdict.** The note gives a **partial answer**; every statement it makes is proved, the lower bounds of the exact values with a computer-assisted proof, and the scope is as follows. Notation: wsat(n) = wsat(K_n, Q_3). - **Settled.** wsat(n) = C(n,2) for n <= 7 (no copy of Q_3, trivial), and wsat(n) = 15, 16, 18, 19, 21, 23 for n = 8, 9, 10, 11, 12, 13 (Theorem 1.2). Upper bounds: explicit graphs with step lists printed in the note (Tables 2, 3); lower bounds: exhaustive searches (Proposition 5.1), each case with at least two independent programs; the decisive case n = 13, k = 11 with VB (run twice) and VC (third verification run), with identical weighted counts (35,276,745,720 labelled sets R, none works). The values for n <= 11 were obtained earlier in two unrefereed Zenodo preprints (see "Not new"). - **Proved for all n.** wsat(n+4) <= wsat(n) + 7 (n >= 8) and wsat(n) <= floor((7n+2)/4) (n >= 9) (Theorem 1.3); wsat(n) >= (5n-7)/3 (n >= 8) (Theorem 1.4); hence 5/3 <= lim wsat(n)/n <= 7/4 (Corollary 1.5). - **Not new.** Carptopus, "Small exact values and a dense-anchor bound for weak cube saturation", Zenodo v0.1-beta, 2 September 2026, doi:10.5281/zenodo.22254558: wsat(8), wsat(9), wsat(10) = 15, 16, 18, the same four-vertex seven-edge gadget on a complete 7-set, Theorem 1.3 (wsat(n+4) <= wsat(n) + 7, wsat(n) <= floor((7n+2)/4) for n >= 9) and 11/7 <= lim <= 7/4. V. Saha and N. Saha, "Weak saturation of the 3-cube in complete graphs: exact values at orders 9, 10, 11", Zenodo v1.0.0, 3 October 2026, doi:10.5281/zenodo.23121234: wsat(9), wsat(10), wsat(11) = 16, 18, 19, wsat(n) <= 2n - 3 for n >= 11, and Corollary 2.3 (their Proposition 7.1). Both unrefereed; found by the third verification run after the note was written, and credited in the note. The method of Theorem 1.4 is the cluster method of Terekhov and Zhukovskii (JCTB 172 (2025)), including clusters sharing one vertex (their Section 5.3, proof of their Theorem 5.3). Corollary 2.3 is the argument of their (1) and a lemma on the PCMI slides. The existence of the limit is due to Alon (1985), as reported by Terekhov and Zhukovskii. **New** (not found elsewhere): wsat(12) = 21, wsat(13) = 23, Theorem 1.4 and hence the lower end 5/3, Conjecture 1.6. - **Open.** wsat(n) for n >= 14; the value of the limit (only [5/3, 7/4] is proved). Conjecture 1.6, wsat(n) = floor((7n+2)/4) for n >= 9, is supported by computation only (proved for 9 <= n <= 13). The note is unrefereed. ## Statement checked - **Primary source.** N. Morrison and J. A. Noel, "Weak saturation of the cube in the clique", Open Problem Garden, posted 6 April 2016 by J. Noel, http://www.openproblemgarden.org/op/weak_saturation_of_the_cube_in_the_clique (fetched 2026-10-19, 13,862 bytes). The page asks: determine wsat(K_n, Q_3); it defines wsat(G, H) as the minimum number of edges of a subgraph F of G such that the edges of E(G) \ E(F) can be added one at a time so that each completes a copy of H; it names wsat(K_n, Q_m) for all m as a natural next step and cites Morrison–Noel–Scott for wsat(Q_d, Q_m). Importance "low", recommended for undergraduates; no comments, no reported solution. - **Corpus record.** ulamai/UnsolvedMath OPG-60013 (dataset v1.8.0), statement "Determine wsat(K_n, Q_3)", status partially_solved (literature triage citing the PCMI 2025 slides). The record reproduces the page. - **Conventions (Section 1.1 of the note).** Copies are subgraphs, not induced. Requiring F to be Q_3-free does not change the minimum (repeated deletion of an edge of a copy until the graph is Q_3-free, then adding the deleted edges back in reverse order; in particular a minimum F is Q_3-free). The order of the additions is irrelevant (Lemma 2.1). For n <= 7 nothing can be added. ## Readings | Reading | Answer | Where | |---|---|---| | Determine wsat(K_n, Q_3) for every n (an exact formula) | not given; exact for n <= 13; (5n-7)/3 <= wsat(n) <= floor((7n+2)/4) for all n; conjecture floor((7n+2)/4) | Theorems 1.2–1.4, Conjecture 1.6 | | The same with F required to be Q_3-free | same minimum | Section 1.1, convention (b) | | Induced copies of Q_3 | a different problem, not treated | Section 1.1 | | Host graph Q_d instead of K_n | solved by Morrison–Noel–Scott (CPC 26 (2017)); not this problem | Section 1.1 | | wsat(K_n, Q_m) for all m (the page's "next step") | not treated | — | ## Results in the paper - **Lemmas 2.1–2.6** (proved): closure well defined and monotone; absorption (a complete set K, |K| >= 7, absorbs a vertex with two neighbours in K; explicit cube); Corollary 2.3 wsat(n+1) <= wsat(n) + 2; deadlock (two adjacent vertices of degree 2 block percolation; degree <= 1 is frozen); the face gadget (four new vertices, seven edges, a path and a matching into a complete K with |K| >= 7; two explicit cubes, then absorption); the first copy (wsat(n) = 11 + min |R| over sets R of pairs outside a fixed cube Q with cl(Q + R) = K_n; monotone). - **Proposition 3.1** (proved with printed certificates): the seeds S_8, S_9, S_11 (15, 16, 19 edges) are weakly saturated; Table 3 lists 11, 12, 15 steps with certificates, then an absorption order. - **Theorem 1.3** (proved; obtained earlier by Carptopus with the same gadget): (a) by the face gadget; (b) from S_9, S_11, Corollary 2.3 for n = 10, 12, and the identity floor((7(n+4)+2)/4) = floor((7n+2)/4) + 7. - **Theorem 1.4** (proved): clusters of size >= 8 with disjoint tallies, sharing at most one vertex; constants alpha = 5/3, c = 7/3, f(8) = 11, slacks alpha w - c - ex(w) = 0, 2/3, 1/3, 1, 2/3, 1/3 (w = 2..7) with ex(2..7) = 1, 2, 4, 5, 7, 9 (Lemma 4.1); merging loses at most 2 alpha - c = 1 >= 0; end game with small blocks of size 2 and w(x) >= 15/8. Remark 4.2: e_i = 11 - ex(8-i) = 2, 4, 6, 7, 9, 10, 11; TZ Theorem 2.1 gives slope 11/7; their Section 5.3 slope 5/3 under a hypothesis that fails for Q_3 (13 < 16 = wsat(9)); within the scheme no slope above 5/3 is possible. - **Proposition 5.1** (computer-assisted): no R with |R| = k = 3, 4, 6, 7, 9, 11 works for n = 8, ..., 13. - **Section 6** (evidence only, not proved): simulated annealing for 12 <= n <= 18; gadget searches up to seven new vertices (24 labelled percolating configurations for (t, E) = (4, 7), 2 up to isomorphism); a heuristic remark on counting arguments, labelled as such. ## Computations (programs and outputs in reproducibility/) What rests on computation: the lower bounds of Theorem 1.2 (Proposition 5.1). The step lists of Table 3 were found by computer but are printed and can be checked directly. Nothing else depends on a computation. - **Programs written with the note** (`writing_stage/check_note.py`, standard library only; 8 s, or 78 s with `--n10`; ALL CHECKS PASSED): the tuples of Lemmas 2.2 and 2.5 and both lemmas on K_7, K_8; Lemma 4.1 over all subsets of the cube; e_1..e_7, the slopes 11/7 and 5/3, the identities (2) in exact arithmetic; the end game (minimum weight 15/8 for 8 <= n <= 80); Table 1 and the arithmetic of Theorem 1.3; Table 2 and the certificates of Table 3 as printed, plus an independent closure of each seed; the instances of Corollary 2.3; the explicit 23-edge graph for n = 13; the graphs with gadgets for 13 <= n <= 24 (step lists in `composite_steps.txt`, 1624 certified steps); the searches of Proposition 5.1 for n = 8, 9, 10 with positive controls (560/0, 1820/768, 4326/0, 23576/6864, 272048/0), with a cube test of its own. - **Program VC of the third verification run** (`independent_run_2/`, r2search.c; generic cube test; chord sets over orbit representatives under Aut(Q), order 48): n = 13, k = 11 in four parts of 685 s, 35,276,745,720 labelled sets R (the weighted count of VB), none works; n = 13, k = 10: 2,424,592,215 (as VB), none; all smaller cases of Table 4 with the counts of VB (R1+R2) and of P1 (R1 only); positive controls 768, 6,864, 554,712, 428,832 and 111,021,696 (n = 12, k = 10) working labelled sets; mutated cube test gives false positives. `check_run2.py` (standard library) parses Tables 1-3 and the graph for n = 13 from main.tex and checks them as printed, with Lemmas 2.2, 2.5, Corollary 2.3, Lemma 4.1, (2), Remark 4.2, the graphs with gadgets for 13 <= n <= 28 and the end game for n <= 120: ALL CHECKS PASSED. - **New runs of program VB** (`writing_stage/rerun_VB_*.txt`): n = 13, k = 11 in three parts (799 s each; the three summary lines are identical to the recorded ones; 35,276,745,720 labelled sets R, none works), and the smaller cases of Table 4 and the positive controls (all numbers as recorded by the second verification run). - **Decisive runs (Table 4 of the note).** | n | k | conclusion | P1 | P2 | P3 | VA | VB | VC | |---|---|---|---|---|---|---|---|---| | 8 | 3 | wsat(8) >= 15 | 560 | 560 | 560 | 560 | 560 | as VB | | 9 | 4 | wsat(9) >= 16 | 4,326 | 4,326 | 4,326 | 4,326 | 4,326 | as VB | | 10 | 6 | wsat(10) >= 18 | 272,048 | 172,984 | 272,048 | both | 236,208 | as VB | | 11 | 7 | wsat(11) >= 19 | 3,116,702 | 884,272 | – | both | 1,942,704 | as VB | | 12 | 9 | wsat(12) >= 21 | – | 51,502,128 | – | as P2 | 225,604,296 | as VB | | 13 | 11 | wsat(13) >= 23 | – | – | – | – | 35,276,745,720 | as VB | | 13 | 10 | only wsat(13) >= 22 | – | 270,778,851 | – | as P2 | 2,424,592,215 | as VB | Counts are numbers of sets R tested (none works); they depend on the enumeration (P1, P3, VA mode 0: all R with outside degrees >= 2; P2, VA mode 1: structured; VB, VC: weighted numbers of labelled R with both filters). Positive controls (k = wsat(n) - 11): 768 (n = 8), 6,864 (n = 9), 554,712 (n = 10), 428,832 (n = 11) working sets, equal across the programs that ran them. A mutated cube test (one edge omitted) yields false positives. ## Independent verification runs The results were first obtained with the programs in `original/` (P1, P2, P3, certify_upper.py and others). Three independent verification runs, all AI-assisted, followed (2026-10-19), each with its own programs. Run A examined the statement and the proofs; run B the computations, the literature and novelty. The note was then written, and VB and check_note.py were run. Run C (the third run; folder `independent_run_2/`) examined the text of the note: it re-derived every proof line by line (first the parts written or changed at the writing stage: Corollary 2.3 for n = 10, 12, the shortened step lists of Table 3, Lemma 2.5 and the induction of Theorem 1.3, the full proof of Theorem 1.4, the provenance of each entry of Table 4, check_note.py), read the sources again (problem page; PCMI slides; Terekhov–Zhukovskii Sections 1, 2, 5.2, 5.3 and (1); Morrison–Noel–Scott definitions; Kronenberg–Martins–Morrison abstract; Alon could not be fetched), wrote its own programs VC and check_run2.py, re-ran the package from an extracted copy of source.zip (all recorded outputs reproduced), and repeated the literature search, finding the two Zenodo preprints. It found no mathematical error. | Item | Run A | Run B | Writing stage | Run C (third run) | |---|---|---|---|---| | Statement, definitions, conventions against the source | CONFIRMED (with the fix to convention (b)) | CONFIRMED | — | CONFIRMED (sources read again) | | Lemmas 2.1–2.6 | CONFIRMED (re-derived) | CONFIRMED (re-derived) | tuples of 2.2, 2.5 re-checked by check_note.py | CONFIRMED (re-derived; tuples checked by check_run2.py) | | Theorem 1.3 (gadget, seeds, induction) | CONFIRMED (own closure code; 172 recorded certificates replayed) | CONFIRMED (own certificate checker; seeds and graphs with gadgets to n = 24) | seeds re-certified by Table 3 | CONFIRMED (Table 3 parsed from main.tex and checked; gadgets to n = 28); earlier in Carptopus | | Theorem 1.4 | CONFIRMED (re-derived in full; ex(w) directly and by program) | CONFIRMED (re-derived; ex(w) by program) | constants and end game checked | CONFIRMED (re-derived in full; end game n <= 120) | | Theorem 1.2, n <= 12 | CONFIRMED (own program VA, counts identical to P1, P2) | CONFIRMED (own program VB) | VB rerun | CONFIRMED (own program VC, counts as VB and P1) | | Theorem 1.2, n = 13 | k = 10 only (identical counts; gives only >= 22) | gap found: k = 11 needed; CONFIRMED by own k = 11 run | VB k = 11 rerun, identical | CONFIRMED by own k = 11 run (VC), same weighted count | | Novelty | no novelty claim endorsed | TZ Section 5.3 found (clusters sharing one vertex) | cited; no novelty claimed | two earlier Zenodo preprints found (n <= 11, Theorem 1.3); credited | | Conjecture 1.6, Section 6 | TESTED only; t = 4 gadget recount | gadget cross-check t <= 5 on K_8; annealing not rerun | labelled as evidence | gadget summaries reproduced (t <= 6); statements qualified to the cores examined | ## Corrections made after the verification runs - (A1) Convention (b): the deletion is repeated until F is Q_3-free; the deleted edges are added back in reverse order. - (A2) The graphs with gadgets for 13 <= n <= 24: described as certified by the program's per-step assertions; the step lists are now recorded (`writing_stage/composite_steps.txt`). They are not used in any proof. - (A3) The note names the programs behind each lower bound (Table 4) and says that they were recomputed in the verification runs; for n = 13 the bound rests on VB alone. - (A4) Section 6: the 24 percolating (4, 7)-gadgets are labelled configurations (12 Hamiltonian paths with four matched vertices, 12 labelled 4-cycles with three), 2 up to isomorphism. - (B1) n = 13: the lower bound 23 needs k = 11; the first computation used k = 10 (proves only >= 22). The note uses the k = 11 run of VB (copied into the package with its outputs, and rerun); the list of k values and the table were corrected. - (B2) Terekhov–Zhukovskii Section 5.3 (proof of their Theorem 5.3) is cited for clusters sharing one vertex; no novelty is claimed for the method. - (B3) The remark that counting arguments cannot pass 5/3 is labelled as a heuristic; its exact form for the scheme of Section 4 is Remark 4.2. - (B4) Journal versions added, DOIs checked with Crossref on 2026-10-19: Morrison–Noel–Scott, CPC 26 (2017) 78–98, 10.1017/S0963548316000122; Terekhov–Zhukovskii, JCTB 172 (2025) 146–167, 10.1016/j.jctb.2024.12.007; Terekhov–Zhukovskii, Combinatorica 45 (2025), no. 5, paper 45, 10.1007/s00493-025-00174-y; Kronenberg–Martins–Morrison, JCTA 178 (2021) 105357, 10.1016/j.jcta.2020.105357; Alon, JCTA 40 (1985) 82–89, 10.1016/0097-3165(85)90048-2. - Also: the upper bounds for n = 10, 12 now follow from S_9, S_11 by Corollary 2.3, and the certificates of S_8, S_9, S_11 are printed in shortened form (steps until a 7-set is complete, then absorption), so that the upper bounds can be checked without a computer. ## Corrections made after the third verification run (run C) - (C1) Credit to the two earlier Zenodo preprints (Carptopus 2026; V. Saha and N. Saha 2026) in the abstract, Sections 1.2, 1.3, Corollary 2.3, after Lemma 2.5, Theorem 1.3, Corollary 1.5 and Section 7; the claims "the only source specific to the problem is the slides" and "not in print" for n <= 11 and Theorem 1.3 were removed. - (C2) n = 13: the lower bound now rests on two independent programs (VB and VC); Table 4, Section 5, abstract. - (C3) Corollary 2.3: Terekhov–Zhukovskii (1) is the construction from n = v; cited as "the argument of (1)". - (C4) Remark 4.2: their Theorem 5.3 (Section 5.2, proof in 5.3) cited precisely; its hypothesis fails already for n = 8 without computation (no chord of Q is addable in Q, so wsat(8) >= 12 > 11); wording of the binding case. - (C5) Ranges of the bounds in the abstract and the Scope paragraph (upper bound for n >= 9). - (C6) PCMI slides: "state" (the lower bound is quoted from Terekhov–Zhukovskii) instead of "prove". - (C7) Section 6: "no gadget percolates" and the 7/4 sentence restricted to the cores examined. - (C8) Table 3 in the order S_8, S_9, S_11; README notes on recorded outputs; folder independent_run_2/. - (C9) Alon: the statement is taken from Terekhov–Zhukovskii (Sections 1, 2); said where it is used. ## Relation to the literature, novelty and scope - **Searches (2026-10-19).** arXiv (titles and abstracts with "weak saturation" or "weakly saturated", the 100 newest; and with cube or hypercube: only Morrison–Noel–Scott and Morrison–Noel, arXiv 1506.04686, both with hypercube host), Crossref, zbMATH (32 titles with "weak saturation", none on cubes), the works citing Morrison–Noel–Scott in OpenAlex (7, CPC version) and Semantic Scholar (20, arXiv version), two web searches, and the full texts of ten arXiv papers on weak saturation searched for "cube", "Q_3", "hypercube": 2305.11043 (Terekhov–Zhukovskii), 2405.17857 (Terekhov–Zhukovskii), 2501.15686 (Ascoli–He), 2508.19435 (Akhmejanova–Vorobyev–Zhukovskii), 2604.07104 (Terekhov), 2609.01851 (Vasquez), 2306.10375 (Kalinichenko–Miralaei–Mohammadian–Tayfeh-Rezaie), 2004.01289 (Kronenberg–Martins–Morrison), 2607.04185 (Chen–Xie), 2410.24130 (Morrison–Ogden). They mention cubes only when citing Morrison–Noel–Scott. - Run C added: arXiv API (abstracts with weak saturation / weakly saturated, newest 120; saturation with cube or hypercube and clique or complete graph), Crossref (two bibliographic queries; DOIs re-verified), OpenAlex (search, works citing Morrison–Noel–Scott, recent works on weak saturation), DataCite (two queries), zbMATH (titles with "weak saturation", 2024–2026: 17, none on cubes), one web search (Open Problem Garden pages; a 2019 AKCE paper of Cui and Pu on complete bipartite graphs, checked via OpenAlex). - Problem-specific sources found: slides of a PCMI 2025 student project (Trakulthongchai, Xu, Zhu; IAS-hosted PDF, 11 slides, read in full), same definition: wsat(8) = 15 and wsat(9) = 17 by computer (slide 5), wsat(n) <= 2n - 1 (slide 6), (3/2)n - 1 <= wsat(n) (slide 8, quoting Terekhov–Zhukovskii), conjecture wsat(n) = 2n - 1 for n >= 8 (slide 11); and the Zenodo preprints of Carptopus (2 September 2026) and of V. Saha and N. Saha (3 October 2026), both read in full (see the verdict), found by run C through OpenAlex and DataCite. The note reports the slides in neutral sentences and credits both preprints. - Not found anywhere: wsat(12), wsat(13), a lower bound with slope above 11/7, the conjecture floor((7n+2)/4). A search that finds nothing is not a proof of novelty; no priority is claimed. - Terekhov–Zhukovskii (JCTB 2025): Theorem 1.1 gives (3/2)(n-8) + 11 for Q_3; Theorem 2.1 (disjoint clusters) slope 11/7; Section 5.3 clusters may share one vertex, under the hypothesis of their Theorem 5.3. - Kronenberg–Martins–Morrison: wsat(K_n, K_{t,t}) = (t-1)(n+1-t/2) for n >= 3t-3 (abstract); hence wsat(n) <= 3(n-1) for n >= 9. - **What was read.** The problem page; the PCMI slides in full; the two Zenodo preprints in full; Terekhov–Zhukovskii in the arXiv version 2305.11043v2 (Sections 1, 2, 5.2, 5.3), the journal version not compared; Morrison–Noel–Scott (arXiv 1408.5488v2: abstract and the definitions of Section 1); the abstracts of the Combinatorica paper and of Kronenberg–Martins–Morrison. Alon (1985) was not read; the attribution of the existence of the limit is taken from Terekhov–Zhukovskii (abstract and Section 2). Faudree–Gould–Jacobson (2013): zbMATH summaries only. - **Scope.** The note determines wsat(K_n, Q_3) for n <= 13 (new for n = 12, 13) and proves linear bounds (the upper one known before); it does not settle the problem. The method of the lower bound is not new. ## Public release and license This paper, its source files, and this verification report are licensed under the Creative Commons Attribution 4.0 International License (CC BY 4.0): https://creativecommons.org/licenses/by/4.0/