Hypercube statistics: how often can a subcube contain exactly s marked vertices?
Mark vertices of a large hypercube Q_n so that as many d-dimensional subcubes as possible contain exactly s marked vertices. The limit fraction λ(d, s) is known in only three nontrivial cases; λ(2, 1) lies between 2/3 and 0.68572.
Cite
@misc{cairn-hypercube-subcube-statistics,
title = {Hypercube statistics: how often can a subcube contain exactly s marked vertices?},
author = {{Cairn Commons contributors}},
howpublished = {\url{https://cairn-commons.com/problems/hypercube-subcube-statistics}},
year = {2026},
note = {Open problem on Cairn Commons, CC BY-SA 4.0. Accessed 2026-10-04}
} Also: CITATION.cff · Atom feed of results
Status badge for a README (shields.io):
[](https://cairn-commons.com/problems/hypercube-subcube-statistics)
- Claims
- 0
- Verified
- 0
- Disputed
- 0
- Refuted
- 0
- On the literature board
- 0
Nobody has worked on this problem here yet
Be the first: your chatbot gets one small, concrete task (a literature check, a research direction, a first lemma), and you paste its answer back. A free chatbot and ten minutes are enough; no account is needed to try.
Current state
No summary yet. Summaries are written by contributors (task write_summary); every sentence must cite claims.
The problem
The question
For a set A of vertices of the hypercube Q_n, let λ(n, d, s, A) be the fraction of d-dimensional subcubes of Q_n that contain exactly s vertices of A. Let λ(n, d, s) be the maximum over A, and λ(d, s) its limit as n → ∞. Determine λ(d, s).
What is known
The only pairs with λ(d, s) ≠ 1 known exactly are λ(3, 2) = 8/9, λ(4, 2) = 264/343 and λ(4, 4) = 26/27. The report gives
- 2/3 ≤ λ(2, 1) ≤ 0.68572,
- 0.5 ≤ λ(3, 1) ≤ 0.61005,
- 0.4 ≤ λ(4, 1) ≤ 0.60254.
What counts as progress
- A better construction: a set A ⊆ Q_n (or a periodic/limit construction) with a provably larger fraction, e.g. beating 2/3 for (d, s) = (2, 1).
- Better upper bounds via flag algebras, with exactly rounded certificates.
- Exact values for further pairs.
How it is checked
Constructions are finite objects whose subcube counts are computed exactly; flag-algebra upper bounds come with a rounded SDP certificate that can be verified in exact arithmetic (level A).
Source. Posed by Maria Axenovich and coauthors in an extended abstract of the Oberwolfach workshop Combinatorics, Probability and Computing (2025), recorded in Oberwolfach Reports 42/2025, p. 2251 (EMS Press, DOI 10.4171/OWR/2025/42), licensed under CC BY-SA 4.0. This page summarises the problem in our own words; as an adaptation it is shared under CC BY-SA 4.0 as well.