2020/04/07 by Chong Shangguan, Shangguan, Chong, Itzhak Tamo +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Optimization Algorithms Research #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Limits and Structures in Graph Theory #Mathematical Approximation and Integration #Optimization and Variational Analysis #math.CO
paper · pdf · doi:10.48550/arxiv.2004.03099
8 pages, SIAM Journal on Discrete Mathematics, to appear
openalex publication_date 2020/04/07 · arxiv created 2020/08/21 · arxiv updated 2020/08/24 · openalex created_date 2024/04/11 · openalex updated_date 2026/07/28
An r-uniform hypergraph is called t-cancellative if for any t+2 distinct edges A1,…,At,B,C, it holds that (∪i=1t Ai)∪ B≠ (∪i=1t Ai)∪ C. It is called t-union-free if for any two distinct subsets A,B, each consisting of at most t edges, it holds that ∪A\inA A≠ ∪B\inB B. Let Ct(n,r) (resp. Ut(n,r)) denote the maximum number of edges of a t-cancellative (resp. t-union-free) r-uniform hypergraph on n vertices. Among other results, we show that for fixed r≥ 3,t≥ 3 and n→∞ Ω(n^\lfloor(2r)/(t+2)\rfloor+\frac2r\pmodt+2t+1)=Ct(n,r)=O(n\lceil(r)/(\lfloor t/2\rfloor+1)\rceil) and Ω(n(r)/(t-1))=Ut(n,r)=O(n\lceil(r)/(t-1)\rceil), thereby significantly narrowing the gap between the previously known lower and upper bounds. In particular, we determine the Turán exponent of Ct(n,r) when 2| t and (t/2+1)| r, and of Ut(n,r) when (t-1)| r. The main tool used in proving the two lower bounds is a novel connection between these problems and sparse hypergraphs.