PreprintarXiv licencearXiv
Quadratic bounds for intersecting hypergraphs: An affirmative answer to a question of Duke and Erdős
Abstract
Let m(k,b) denote the minimum number of edges in an intersecting k-uniform hypergraph in which every (k−1)-set of vertices is disjoint from at least b edges, with m(k,b)=+∞ if no such hypergraph exists. Duke and Erdős [Congressus Numerantium (1980)] asked whether m(k,k)=o(k4) is possible. In this paper, we answer this question affirmatively and determine the order of growth of m(k,k) by proving that k2+1≤ m(k,k)≤ Ck2 for all sufficiently large k, where C is an absolute constant. More generally, we show that m(k,b)=Θ(kb) for all sufficiently large odd k and every integer b with k≤ b≤ (k−1)(k−3)/2, where the implied constants are independent of k and b.
Related
- The Assouad Dimension of Graphs: An Affirmative Answer to Fraser's Question
- Intersecting integer partitions: star bounds and counterexamples at every scale
- The quadratic Brown--Erdős--Sós problem for 3-uniform hypergraphs with 8 and 9 edges
- The upper bounds on occupancy fraction and variance fraction for linear regular uniform hypergraphs
- Polynomial-in-r bounds for forbidden traces of uniform hypergraphs
BibTeX
@misc{wang2026quadratic,
title = {{Quadratic bounds for intersecting hypergraphs: An affirmative answer to a question of Duke and Erdős}},
author = {Guoqing Wang and Linlin Wang and Jun Yue},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.01915},
eprint = {2611.01915},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.01915},
}
RIS
TY - UNPB
TI - Quadratic bounds for intersecting hypergraphs: An affirmative answer to a question of Duke and Erdős
AU - Guoqing Wang
AU - Linlin Wang
AU - Jun Yue
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.01915
UR - https://arxiv.org/abs/2611.01915
AB - Let m(k,b) denote the minimum number of edges in an intersecting k-uniform hypergraph in which every (k−1)-set of vertices is disjoint from at least b edges, with m(k,b)=+∞ if no such hypergraph exists. Duke and Erdős [Congressus Numerantium (1980)] asked whether m(k,k)=o(k^4) is possible. In this paper, we answer this question affirmatively and determine the order of growth of m(k,k) by proving that k^2+1≤ m(k,k)≤ Ck^2 for all sufficiently large k, where C is an absolute constant. More generally, we show that m(k,b)=Θ(kb) for all sufficiently large odd k and every integer b with k≤ b≤ (k−1)(k−3)/2, where the implied constants are independent of k and b.
ER -