Extremal 3-uniform hypergraphs without generalized 4-cycles
Abstract
Let fr(n) be the maximum number of edges in an n-vertex r-uniform hypergraph in which all disjoint pairs of edges have distinct unions. In 1977, Erdős posed the problem of determining fr(n) and, in particular, asked whether f3(n)=O(n2). Füredi later proved that binomn−1r−1+⌊ (n−1)/r⌋ ≤ fr(n)<7/2binomnr−1 for r≥3 and n≥2r. Motivated by his constructions, he further conjectured that f3(n)≤binomn2 for all sufficiently large n, and that, for each fixed r≥4, the lower bound is exact for all sufficiently large n. This is known as the Erdős--Füredi conjecture. In a recent breakthrough, Huang, Ma and Yang proved the conjecture for every fixed r≥4 and characterized all extremal hypergraphs. In this paper, we settle the remaining $3$-uniform case for every n. The bound is sharp whenever n≥5 and n≡1,5pmod20. Our proof uses a local weight inequality and a transfer argument.
Related
- Extremal hypergraphs without generalized 4-cycles
- Spectral extremal hypergraphs without long Berge cycles
- A Chvátal-type codegree condition for Hamiltonian cycles in k-uniform hypergraphs
- A Fan-Type Theorem for Hamiltonian Berge Cycles in 3-Uniform Hypergraphs
- Extremal graphs without cycles of length 0 modulo 4
BibTeX
@misc{zhang2026extremal,
title = {{Extremal 3-uniform hypergraphs without generalized 4-cycles}},
author = {Leilei Zhang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.34038},
eprint = {2610.34038},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.34038},
}
RIS
TY - UNPB
TI - Extremal 3-uniform hypergraphs without generalized 4-cycles
AU - Leilei Zhang
PY - 2026
DA - 2026/10/25
PB - arXiv
DO - 10.48550/arxiv.2610.34038
UR - https://arxiv.org/abs/2610.34038
AB - Let f_r(n) be the maximum number of edges in an n-vertex r-uniform hypergraph in which all disjoint pairs of edges have distinct unions. In 1977, Erdős posed the problem of determining f_r(n) and, in particular, asked whether f_3(n)=O(n^2). Füredi later proved that binomn−1r−1+⌊ (n−1)/r⌋ ≤ f_r(n)<7/2binomnr−1 for r≥3 and n≥2r. Motivated by his constructions, he further conjectured that f_3(n)≤binomn2 for all sufficiently large n, and that, for each fixed r≥4, the lower bound is exact for all sufficiently large n. This is known as the Erdős--Füredi conjecture. In a recent breakthrough, Huang, Ma and Yang proved the conjecture for every fixed r≥4 and characterized all extremal hypergraphs. In this paper, we settle the remaining $3$-uniform case for every n. The bound is sharp whenever n≥5 and n≡1,5pmod20. Our proof uses a local weight inequality and a transfer argument.
ER -