On the maximum density of $r$-graphs in which every $(r+1)$-set spans $0$ or $2$ edges

Dhruv Mubayi; Haoran Luo; Vishesh Jain

arxiv: 2606.20367 · v1 · pith:6WH6Z3FRnew · submitted 2026-06-18 · 🧮 math.CO

On the maximum density of r-graphs in which every (r+1)-set spans 0 or 2 edges

Vishesh Jain , Haoran Luo , Dhruv Mubayi This is my paper

Pith reviewed 2026-06-26 16:46 UTC · model grok-4.3

classification 🧮 math.CO

keywords extremal hypergraph theoryr-uniform graphseven edge conditiondensity problemsFrankl-Furedi questionpolynomial density bounds

0 comments

The pith

r-graphs where every (r+1)-set spans 0 or 2 edges can achieve density Ω(r^{-3}).

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Frankl and Füredi posed the problem of finding the highest possible density for r-uniform hypergraphs in which every collection of r+1 vertices induces either zero or two edges. Their 1984 construction achieved a density that decays exponentially with r. The current work provides constructions achieving a density that is only polynomially small in r, specifically on the order of r to the power of negative three. This represents a substantial improvement in the dependence on the uniformity parameter r. The authors further generalize their approach to obtain lower bounds when the induced edges per (r+1)-set are even numbers up to 2k.

Core claim

We significantly improve this bound by constructing such r-graphs with density Ω(r^{-3}), thereby improving the dependence on r from exponential to polynomial. We also obtain lower bounds for the more general problem in which every (r+1)-set spans an even number of edges from {0,2,…,2k}.

What carries the argument

Explicit constructions of r-graphs satisfying the 0-or-2 edge condition on every (r+1)-set, achieving polynomial density.

If this is right

The asymptotic density is at least Ω(r^{-3}) for the 0-or-2 problem.
Polynomial lower bounds hold for the generalized problem with even edge counts up to 2k.
The exponential dependence on r from the 1984 construction is no longer a barrier.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Tighter constructions might push the density higher, perhaps to 1 over polylog r.
The same parity restriction technique may apply to other forbidden subgraph problems in hypergraphs.

Load-bearing premise

The claimed constructions exist and satisfy the every-(r+1)-set condition while attaining the stated polynomial density.

What would settle it

An upper bound proof showing that no such r-graph can have density larger than o(r^{-3}), or a failure of the given constructions to reach the claimed density.

read the original abstract

In 1984, Frankl and F\"uredi asked for the maximum density of an $n$-vertex $r$-graph in which every $(r+1)$-set of vertices spans $0$ or $2$ edges. They gave a construction with asymptotic density $2^{1-r}$. We significantly improve this bound by constructing such $r$-graphs with density $\Omega(r^{-3})$, thereby improving the dependence on $r$ from exponential to polynomial. We also obtain lower bounds for the more general problem in which every $(r+1)$-set spans an even number of edges from $\{0,2,\ldots,2k\}$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

They improve the Frankl-Füredi bound to polynomial density Ω(r^{-3}) via an explicit construction for the even-edge condition on (r+1)-sets.

read the letter

The punchline is that this paper improves the lower bound on the maximum density from exponential in r to polynomial, specifically Omega of r to the minus 3, for r-graphs where no (r+1)-set contains exactly one edge or other odd numbers, but specifically 0 or 2.

They do this with an explicit construction that was not in the original Frankl-Furedi work. That is the solid new contribution.

The paper does well by giving a concrete way to build these graphs that scales better with r. The general result for even numbers of edges from 0 to 2k is also a plus, though the main focus is the k=1 case.

On the soft spots, the central claim depends on the construction satisfying the condition for every (r+1)-set while having enough edges. If there is any r-dependent factor hidden in how they verify the condition or count the edges, it could affect the polynomial nature, but the abstract states the bound clearly, so the paper likely handles that. The soundness is hard to judge from the abstract alone, but the approach seems direct.

The math looks like standard counting arguments for hypergraph densities.

This paper is aimed at researchers in extremal set theory and hypergraph Turán problems. A reader who follows work on forbidden configurations with parity conditions would find the improved bound useful and might want to see if the construction can be extended or optimized further.

It deserves a serious referee because it makes measurable progress on a problem from 1984 with a better dependence on the uniformity r.

I recommend engaging with the work and sending it out for peer review.

Referee Report

0 major / 2 minor

Summary. The paper addresses the 1984 Frankl–Füredi question on the maximum asymptotic density of n-vertex r-graphs in which every (r+1)-set spans 0 or 2 edges. The authors give an explicit construction achieving density Ω(r^{-3}), improving the prior exponential bound of 2^{1-r}. They also obtain lower bounds for the generalized setting in which every (r+1)-set spans an even number of edges from the set {0,2,…,2k}.

Significance. If the stated construction is correct, the result is a substantial advance: it replaces an exponential dependence on r with a polynomial one while remaining fully constructive. Explicit constructions of this type are valuable in extremal hypergraph theory because they permit direct verification and potential extensions. The generalization to bounded even parity supplies additional concrete lower bounds that were not previously available.

minor comments (2)

The introduction would benefit from a brief explicit statement of the constant hidden in the Ω(r^{-3}) notation and of the range of r for which the construction is defined.
Notation for the auxiliary parameters in the construction (e.g., the auxiliary graph or design used to build the r-graph) should be introduced once and used consistently throughout §3 and §4.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the paper and for recommending minor revision. No major comments were raised in the report.

Circularity Check

0 steps flagged

No circularity: result is an explicit combinatorial construction achieving polynomial density improvement

full rationale

The paper's central claim is the existence of an explicit r-graph family with density Ω(r^{-3}) satisfying the every-(r+1)-set spans 0 or 2 edges condition. This is a constructive result improving on the prior exponential bound of Frankl-Füredi, with no fitted parameters, self-definitional relations, or load-bearing self-citations reducing the claim to its inputs. The derivation chain consists of defining and verifying a construction, which is self-contained against external benchmarks and does not invoke any of the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Only abstract available; no explicit free parameters, axioms, or invented entities can be identified from the given text.

pith-pipeline@v0.9.1-grok · 5650 in / 1027 out tokens · 25774 ms · 2026-06-26T16:46:29.139180+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

13 extracted references

[1]

Baber and J

R. Baber and J. Talbot. Hypergraphs do jump.Combin. Probab. Comput., 20(2):161–171, 2011

2011
[2]

F. C. Clemen. Applications of sparse hypergraph colorings.Discrete Math., 349(2):Paper No. 114822, 2026

2026
[3]

D. de Caen. Extension of a theorem of Moon and Moser on complete subgraphs.Ars Combin., 16:5–10, 1983

1983
[4]

R. A. Duke, H. Lefmann, and V. R¨ odl. On uncrowded hypergraphs.Random Structures Algorithms, 6(2-3):209–212, 1995

1995
[5]

Ellis, M.-R

D. Ellis, M.-R. Ivan, and I. Leader. Tur´ an densities for daisies and hypercubes.Bull. Lond. Math. Soc., 56(12):3838–3853, 2024

2024
[6]

Falgas-Ravry and E

V. Falgas-Ravry and E. R. Vaughan. Applications of the semi-definite method to the Tur´ an density problem for 3-graphs.Combin. Probab. Comput., 22(1):21–54, 2013

2013
[7]

Frankl and Z

P. Frankl and Z. F¨ uredi. An exact result for 3-graphs.Discrete Math., 50(2-3):323–328, 1984. 11

1984
[8]

R. L. Graham and N. J. A. Sloane. Lower bounds for constant weight codes.IEEE Trans. Inform. Theory, 26(1):37–43, 1980

1980
[9]

Gunderson and J

K. Gunderson and J. Semeraro. Tournaments, 4-uniform hypergraphs, and an exact extremal result.J. Combin. Theory Ser. B, 126:114–136, 2017

2017
[10]

Gunderson and J

K. Gunderson and J. Semeraro. Tur´ an numbers and switching.Discrete Math., 348(2):Paper No. 114275, 2025

2025
[11]

Katona, T

G. Katona, T. Nemetz, and M. Simonovits. On a problem of Tur´ an in the theory of graphs. Mat. Lapok, 15:228–238, 1964. In Hungarian

1964
[12]

D. Mubayi. On hypergraphs with every four points spanning at most two triples.Electron. J. Combin., 10(1):Note 10, 4 pp., 2003

2003
[13]

Sidorenko

A. Sidorenko. Tur´ an numbers ofr-graphs onr+ 1 vertices.J. Combin. Theory Ser. B, 169:150–160, 2024. 12

2024

[1] [1]

Baber and J

R. Baber and J. Talbot. Hypergraphs do jump.Combin. Probab. Comput., 20(2):161–171, 2011

2011

[2] [2]

F. C. Clemen. Applications of sparse hypergraph colorings.Discrete Math., 349(2):Paper No. 114822, 2026

2026

[3] [3]

D. de Caen. Extension of a theorem of Moon and Moser on complete subgraphs.Ars Combin., 16:5–10, 1983

1983

[4] [4]

R. A. Duke, H. Lefmann, and V. R¨ odl. On uncrowded hypergraphs.Random Structures Algorithms, 6(2-3):209–212, 1995

1995

[5] [5]

Ellis, M.-R

D. Ellis, M.-R. Ivan, and I. Leader. Tur´ an densities for daisies and hypercubes.Bull. Lond. Math. Soc., 56(12):3838–3853, 2024

2024

[6] [6]

Falgas-Ravry and E

V. Falgas-Ravry and E. R. Vaughan. Applications of the semi-definite method to the Tur´ an density problem for 3-graphs.Combin. Probab. Comput., 22(1):21–54, 2013

2013

[7] [7]

Frankl and Z

P. Frankl and Z. F¨ uredi. An exact result for 3-graphs.Discrete Math., 50(2-3):323–328, 1984. 11

1984

[8] [8]

R. L. Graham and N. J. A. Sloane. Lower bounds for constant weight codes.IEEE Trans. Inform. Theory, 26(1):37–43, 1980

1980

[9] [9]

Gunderson and J

K. Gunderson and J. Semeraro. Tournaments, 4-uniform hypergraphs, and an exact extremal result.J. Combin. Theory Ser. B, 126:114–136, 2017

2017

[10] [10]

Gunderson and J

K. Gunderson and J. Semeraro. Tur´ an numbers and switching.Discrete Math., 348(2):Paper No. 114275, 2025

2025

[11] [11]

Katona, T

G. Katona, T. Nemetz, and M. Simonovits. On a problem of Tur´ an in the theory of graphs. Mat. Lapok, 15:228–238, 1964. In Hungarian

1964

[12] [12]

D. Mubayi. On hypergraphs with every four points spanning at most two triples.Electron. J. Combin., 10(1):Note 10, 4 pp., 2003

2003

[13] [13]

Sidorenko

A. Sidorenko. Tur´ an numbers ofr-graphs onr+ 1 vertices.J. Combin. Theory Ser. B, 169:150–160, 2024. 12

2024