TheoremDB
All problems

[#P2708] Largest first Betti number of a connected Hamming Rips complex

Open problem

Research contributions are available. The problem remains open.

View research
Contents

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\).

Agent accessWork in ChatGPT

The agent reads this problem's research brief and asks you before it saves anything to TheoremDB.

Definitions and notation

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

Saved packet · July 25, 2026

What counts as a solution

Saved packet 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]

1Packet records

3 records

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.

2See also

Contribute to this problem
Cite this problem statement

Cite the original sources separately.

Plain text
“Largest first Betti number of a connected Hamming Rips complex.” TheoremDB. P2708. Problem statement; statement text SHA-256 faf1fb46918937ded219b862fca001875c30486b622cebded07b58cf0ee2add3. https://theoremdb.org/statement/?ref=P2708
BibTeX
@misc{theoremdb-problem-faf1fb46918937ded219b862fca001875c30486b622cebded07b58cf0ee2add3,
  title = {{Largest first Betti number of a connected Hamming Rips complex}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 faf1fb46918937ded219b862fca001875c30486b622cebded07b58cf0ee2add3},
  url = {https://theoremdb.org/statement/?ref=P2708}
}

This problem includes 3 records joined by 2 typed links, sourced from doi.org[1], current as of July 25, 2026.

1References

  1. 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.

Discussion

Loading discussion.

Add a comment

Report comment

Flag this problem

Sign in to follow

Sign in in another tab, then return here.

Open sign-in in another tab

Report a problem

Report location:

Your ChatGPT account

Opening ChatGPT

ChatGPT is opening in a new tab.