2024/11/12 by Miao Liu, Liu, Miao, Chong Shangguan +3
Engineering · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2411.07908
openalex publication_date 2024/11/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An r-graph is called t-cancellative if for arbitrary 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 arbitrary 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) and Ut(n,r) denote the maximum number of edges that can be contained in an n-vertex t-cancellative and t-union-free r-graph, respectively. The study of Ct(n,r) and Ut(n,r) has a long history, dating back to the classic works of Erdős and Katona, and Erdős and Moser in the 1970s. In 2020, Shangguan and Tamo showed that C2(t-1)(n,tk)=Θ(nk) and Ut+1(n,tk)=Θ(nk) for all t≥ 2 and k≥ 2. In this paper, we determine the asymptotics of these two functions up to a lower order term, by showing that for all t≥ 2 and k≥ 2, \textlimn→∞\fracC2(t-1)(n,tk)nk=limn→∞\fracUt+1(n,tk)nk=(1)/(k!)⋅ \frac1\binomtk-1k-1. Previously, it was only known by a result of Füredi in 2012 that limn→∞\fracC2(n,4)n2=(1)/(6). To prove the lower bounds of the limits, we utilize a powerful framework developed recently by Delcourt and Postle, and independently by Glock, Joos, Kim, Kühn, and Lichev, which shows the existence of near-optimal hypergraph packings avoiding certain small configurations, and to prove the upper bounds, we apply a novel counting argument that connects C2(t-1)(n,tk) to a classic result of Kleitman and Frankl on a special case of the famous Erdős Matching Conjecture.