Tight bounds for hypercube λ(d,s)

Open problem on tight bounds for $\lambda(d,s)$ · arXiv:2410.20498

arXiv Problem medium confidence— first stated 2024-10-27

Authors: Noga Alon, Maria Axenovich, John Goldwasser

Status partial high confidence

The open problem of obtaining tight bounds for $\lambda(d,s)$ for essentially all admissible $(d,s)$ remains open in general. Bodnár and Pikhurko (2025) made partial progress by determining exact values for the three specific pairs $(3,2)$, $(4,2)$, and $(4,4)$ using flag algebras, with lower bounds coming from blowups of small Hamming codes. The general asymptotic characterisation for all admissible $d$ and $s$ is unresolved.

Cited literature (1)

partial Some exact values of the inducibility and statistics constants for hypercubes (2025)

Levente Bodnár, Oleg Pikhurko · arXiv preprint · arXiv:2503.03408

Determines exact values of $\lambda(d,s)$ for the specific pairs $(d,s) \in \{(3,2),(4,2),(4,4)\}$ via flag algebras, with lower bounds from blowups of small Hamming codes.

Reviewer notes. Exact values for three small pairs established by Bodnár–Pikhurko (arXiv:2503.03408), but the general tight-bounds question remains open. A related paper arXiv:2604.13402 (Xu, 2026) studies an analogous quantity $\lambda^*(d,s)$ for affine subspaces rather than axis-aligned subcubes and does not directly resolve the original open problem.

Auto-reviewed 2026-05-14 with claude-sonnet-4-6 (web search enabled).

Problem. Obtain tight bounds for $\lambda(d,s)$ for essentially all admissible values of $d$ and $s$.

Context

The paper proves several upper and lower bounds on $\lambda(d,s)$ and determines the exact set of $s$ for which $\lambda(d,s)=1$, but tight asymptotic characterisation of $\lambda(d,s)$ for general $s$ remains open.

Notes. Stated implicitly in the abstract alongside the conjecture on $\lambda(d,1)$; no labelled problem environment.

Source paper

On hypercube statistics
Noga Alon, Maria Axenovich, John Goldwasser · 2024-10-27
https://arxiv.org/abs/2410.20498