Extremal problems for cancellative and locally thin hypergraphs
Abstract
We study Turán-type extremal problems for cancellative and locally thin uniform hypergraphs. An r-uniform hypergraph is t-cancellative if (∪i=1t Ai)∪ B≠ (∪i=1t Ai)∪ C whenever A1,…,At,B,C are distinct edges. Let Ct(n,r) denote the maximum number of edges in such a hypergraph on n vertices. For all fixed integers t,k≥2, we prove that C2(t−1)(n,tk)=(1+o(1))binomnk/(binomtk−1k−1) as n→∞. In the case t=2, this shows that Füredi's 2012 upper bound for C2(n,2k) is asymptotically sharp. The lower bound uses locally sparse induced packings, while the upper bound follows from double counting and a matching argument. More generally, for integers s≥ t≥1, an r-uniform hypergraph is locally (s,t)-thin if among any s distinct edges, at least t contain a vertex that lies in none of the other s−1 edges. This notion includes cancellative hypergraphs as special cases. We establish general upper and lower bounds for the corresponding extremal numbers and determine their polynomial order of growth under suitable divisibility assumptions.
Related
BibTeX
@misc{liu2026extremal,
title = {{Extremal problems for cancellative and locally thin hypergraphs}},
author = {Miao Liu and Chong Shangguan and Chenyang Zhang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.08858},
eprint = {2609.08858},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.08858},
}
RIS
TY - UNPB
TI - Extremal problems for cancellative and locally thin hypergraphs
AU - Miao Liu
AU - Chong Shangguan
AU - Chenyang Zhang
PY - 2026
DA - 2026/09/08
PB - arXiv
DO - 10.48550/arxiv.2609.08858
UR - https://arxiv.org/abs/2609.08858
AB - We study Turán-type extremal problems for cancellative and locally thin uniform hypergraphs. An r-uniform hypergraph is t-cancellative if (∪_i=1^t A_i)∪ B≠ (∪_i=1^t A_i)∪ C whenever A_1,…,A_t,B,C are distinct edges. Let C_t(n,r) denote the maximum number of edges in such a hypergraph on n vertices. For all fixed integers t,k≥2, we prove that C_2(t−1)(n,tk)=(1+o(1))binomnk/(binomtk−1k−1) as n→∞. In the case t=2, this shows that Füredi's 2012 upper bound for C_2(n,2k) is asymptotically sharp. The lower bound uses locally sparse induced packings, while the upper bound follows from double counting and a matching argument. More generally, for integers s≥ t≥1, an r-uniform hypergraph is locally (s,t)-thin if among any s distinct edges, at least t contain a vertex that lies in none of the other s−1 edges. This notion includes cancellative hypergraphs as special cases. We establish general upper and lower bounds for the corresponding extremal numbers and determine their polynomial order of growth under suitable divisibility assumptions.
ER -