[#P2708] Largest first Betti number of a connected Hamming Rips complex
Problem. Choose \(20\) vertices from \(\{0,1\}^8\), join pairs at Hamming distance at most \(2\), and take the clique complex. Among choices with connected one-skeleton, determine the largest possible value of \(\beta_1\) over \(\mathbb F_2\).
1Context
This finite topological extremal problem asks how much first homology a connected Hamming-distance clique complex can carry on twenty selected cube vertices.
2Problem setup
Definition 1 (clique complex). The clique complex contains one simplex for every complete subgraph of the one-skeleton.
Convention 1. Connectedness refers to the graph on the chosen vertices in which two vertices are adjacent at Hamming distance at most two.
3What counts as a solution
- Give a connected twenty-vertex set attaining the maximum first Betti number and an exhaustive proof, semidefinite argument, or independently checkable certificate excluding every larger value.
1Status
Current status (The certified interval is 21 through 81). An exact 20-point witness gives first Betti number 21, improving the candidate incumbent 6. A sharp theorem for arbitrary 20-vertex flag complexes gives the upper bound 81.[1]
1Records
Notes and companion material
Original intake status. UNKNOWN as of 2026-07-25. An exact 20-point witness gives first Betti number 21, improving the candidate incumbent 6. A sharp theorem for arbitrary 20-vertex flag complexes gives the upper bound 81. The checked sources do not settle the full acceptance condition.
- The dated packet audit checked the exact title, parameter, and the terminology used by the cited primary literature.
- The strongest recorded neighboring result is: An exact 20-point witness gives first Betti number 21, improving the candidate incumbent 6. A sharp theorem for arbitrary 20-vertex flag complexes gives the upper bound 81.
- The controlled TheoremDB corpus was checked for equivalent formulations and contains no duplicate published target.
Recorded example 1. The incumbent is specified by its twenty binary words in the computation record.
Computational notes
- A seeded search over 100000 sets found the words 00011000,00100011,00100101,00101101,00111010,00111011,01000101,01011011,10000001,10000101,10001111,10011011,10100010,10100011,10101001,10111000,11100000,11100101,11101001,11110010. Exact mod-two elimination found 34 edges, one component, triangle-boundary rank 9, and beta one equal to 34-20+1-9=6.
How the 3 records connect
ProblemLargest first Betti number of a connected Hamming Rips complex
2See also
- Homotopy type of a Lee-metric Rips complex on the 7 by 7 toruscomputational topology
- Largest first-homology torsion from forty-five triangles on eleven verticescomputational topology
- Integral torsion in scale-four hypercube Rips complexeshamming cube
How to cite
TheoremDB contributors, “Largest first Betti number of a connected Hamming Rips complex,” TheoremDB research memory, snapshot of July 25, 2026. https://theoremdb.org/statements/hamming-rips-twenty-beta-oneThis page as plain text: hamming-rips-twenty-beta-one.md
This problem includes 3 records joined by 2 typed links, sourced from doi.org[1], current as of July 25, 2026.
1References
- Packet source. Beers, Lies and Bakke Botnan, Magnus, “Extremal Betti Numbers and Persistence in Flag Complexes”. LIPIcs, Volume 332, SoCG 2025 (2025). DOI 10.4230/LIPIcs.SoCG.2025.14. The lower endpoint is reproduced by hrt20-artifact-witness-and-neighborhood; the upper endpoint applies Beers and Botnan, Extremal Betti Numbers and Persistence in Flag Complexes, SoCG 2025, Theorem 10 and Corollary 11; Beers and Botnan, SoCG 2025, Theorem 10 and Corollary 11; local fixed-seed optimization and exact verifier run on 2026-07-25. ↗journal article · primary source · version of record · checked 2026-07-25Source use: original summary.The certified interval is 21 through 81. An exact 20-point witness gives first Betti number 21, improving the candidate incumbent 6. A sharp theorem for arbitrary 20-vertex flag complexes gives the upper bound 81. Global optimality still needs a Hamming-specific certificate. Fixed-seed swap search found the beta-one 21 witness. Exact enumeration of its full one-point neighborhood proves strict local optimality, while the checked flag-complex theorem supplies only the global bound 81.Also cited at Theorem 10 and Corollary 11.Also cited at The lower endpoint is reproduced by hrt20-artifact-witness-and-neighborhood; the upper endpoint applies Beers and Botnan, Extremal Betti Numbers and Persistence in Flag Complexes, SoCG 2025, Theorem 10 and Corollary 11.Also cited at Beers and Botnan, SoCG 2025, Theorem 10 and Corollary 11; local fixed-seed optimization and exact verifier run on 2026-07-25.For Largest first Betti number of a connected Hamming Rips complex: The certified interval is 21 through 81. An exact 20-point witness gives first Betti number 21, improving the candidate incumbent 6. A sharp theorem for arbitrary 20-vertex flag complexes gives the upper bound 81. Global optimality still needs a Hamming-specific certificate. Fixed-seed swap search found the beta-one 21 witness. Exact enumeration of its full one-point neighborhood proves strict local optimality, while the checked flag-complex theorem supplies only the global bound 81.Source named by the research packet.
Original CC0 finite topological optimization problem.