PreprintarXiv licencearXiv
Extremal hypergraphs without generalized 4-cycles
Abstract
In 1977, Erdős posed the problem of determining the maximum number fr(n) of edges in an n-vertex r-uniform hypergraph in which all disjoint pairs of edges have distinct unions. Füredi later conjectured that, for every fixed r≥ 4 and all sufficiently large n, fr(n)=binomn−1r−1+⌊ (n−1)/r⌋. In this paper, we prove this conjecture and determine all extremal configurations. Our proof combines a stability theorem for such dense hypergraphs with a delicate deletion argument applied to an associated bipartite $3$-graph. The stability theorem also resolves a conjecture of Mubayi.
Related
- Extremal 3-uniform hypergraphs without generalized 4-cycles
- Spectral extremal hypergraphs without long Berge cycles
- Extremal graphs without cycles of length 0 modulo 4
- Counting hypergraphs without linear cycles of fixed length
- A Chvátal-type codegree condition for Hamiltonian cycles in k-uniform hypergraphs
BibTeX
@misc{huang2026extremal,
title = {{Extremal hypergraphs without generalized 4-cycles}},
author = {Hao Huang and Jie Ma and Tianchi Yang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.37744},
eprint = {2609.37744},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.37744},
}
RIS
TY - UNPB
TI - Extremal hypergraphs without generalized 4-cycles
AU - Hao Huang
AU - Jie Ma
AU - Tianchi Yang
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2609.37744
UR - https://arxiv.org/abs/2609.37744
AB - In 1977, Erdős posed the problem of determining the maximum number f_r(n) of edges in an n-vertex r-uniform hypergraph in which all disjoint pairs of edges have distinct unions. Füredi later conjectured that, for every fixed r≥ 4 and all sufficiently large n, f_r(n)=binomn−1r−1+⌊ (n−1)/r⌋. In this paper, we prove this conjecture and determine all extremal configurations. Our proof combines a stability theorem for such dense hypergraphs with a delicate deletion argument applied to an associated bipartite $3$-graph. The stability theorem also resolves a conjecture of Mubayi.
ER -