Binary focal family upper bound non-tightness

Informal conjecture on non-tightness of upper bound for binary focal families · arXiv:2010.05992

arXiv Informal medium confidence— first stated 2020-10-12

Authors: Noga Alon, Ron Holzman

Status partial medium confidence

A 2024 follow-up by Huang, Shangguan, Zhang, and Zhao (arXiv:2410.23611) establishes asymptotically optimal bounds on the maximum size of focal-free uniform hypergraphs and codes, proving that the Alon–Holzman multiplicative constant (r-1) in the upper bound is not tight in general (specifically showing the true constant is strictly smaller as q→∞). This supports the spirit of the conjecture that the binary (q=2) bound is not tight, but the paper's sharpest results are in the large-q regime; whether the full q=2 conjecture is resolved for all large n remains unclear from available abstracts.

Cited literature (1)

partial Focal-free uniform hypergraphs and codes (2024)

Xinqi Huang, Chong Shangguan, Xiande Zhang, Yuhao Zhao · arXiv preprint · arXiv:2410.23611

Proves asymptotically optimal bounds on focal-free codes, showing the Alon–Holzman multiplicative constant (r-1) is not tight (the true limit is strictly smaller), thereby confirming non-tightness of the upper bound; the sharpest explicit result concerns q→∞ rather than q=2 specifically.

Reviewer notes. The 2024 paper arXiv:2410.23611 is the main follow-up and clearly improves the Alon–Holzman bound, establishing non-tightness in general via an asymptotic argument. However, the conjecture specifically targets q=2 (binary vectors) for large n; the most explicit result in the follow-up holds as q→∞, so it is not clear whether the binary case is fully settled. Status is therefore 'partial' rather than 'solved'.

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

Informal. For $q = 2$ and large $n$, the upper bound $g^{q\text{-ff}}_r(n) \leq (r-1)\, q^{\lceil (r-2)n/(r-1) \rceil}$ of Theorem 1.3 is not tight.

Context

Proposition 3.2 shows via Reed-Solomon codes that the upper bound is essentially tight when $q \geq n$ and $q$ is a prime power. The authors believe the binary case ($q = 2$) behaves differently, and support this belief by proving in Section 4 that the bound can be significantly improved when the family of binary vectors forms a linear code (closed under addition modulo 2).

Notes. PDF source — math notation may be garbled.

Source paper

Near-sunflowers and focal families
Noga Alon, Ron Holzman · 2020-10-12
https://arxiv.org/abs/2010.05992 PDF source