Asymptotically sharp bounds for cancellative and union-free hypergraphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915015965016064 |
|---|---|
| author | Liu, Miao Shangguan, Chong Zhang, Chenyang |
| author_facet | Liu, Miao Shangguan, Chong Zhang, Chenyang |
| contents | An $r$-graph is called $t$-cancellative if for arbitrary $t+2$ distinct edges $A_1,\ldots,A_t,B,C$, it holds that $(\cup_{i=1}^t A_i)\cup B\neq (\cup_{i=1}^t A_i)\cup C$; it is called $t$-union-free if for arbitrary two distinct subsets $\mathcal{A},\mathcal{B}$, each consisting of at most $t$ edges, it holds that $\cup_{A\in\mathcal{A}} A\neq \cup_{B\in\mathcal{B}} B$. Let $C_t(n,r)$ and $U_t(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 $C_t(n,r)$ and $U_t(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 $C_{2(t-1)}(n,tk)=Θ(n^k)$ and $U_{t+1}(n,tk)=Θ(n^k)$ for all $t\ge 2$ and $k\ge 2$. In this paper, we determine the asymptotics of these two functions up to a lower order term, by showing that for all $t\ge 2$ and $k\ge 2$,
\begin{align*}
\text{$\lim_{n\rightarrow\infty}\frac{C_{2(t-1)}(n,tk)}{n^k}=\lim_{n\rightarrow\infty}\frac{U_{t+1}(n,tk)}{n^k}=\frac{1}{k!}\cdot \frac{1}{\binom{tk-1}{k-1}}$.}
\end{align*}
Previously, it was only known by a result of Füredi in 2012 that $\lim_{n\rightarrow\infty}\frac{C_{2}(n,4)}{n^2}=\frac{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 $C_{2(t-1)}(n,tk)$ to a classic result of Kleitman and Frankl on a special case of the famous Erdős Matching Conjecture. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_07908 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Asymptotically sharp bounds for cancellative and union-free hypergraphs Liu, Miao Shangguan, Chong Zhang, Chenyang Combinatorics An $r$-graph is called $t$-cancellative if for arbitrary $t+2$ distinct edges $A_1,\ldots,A_t,B,C$, it holds that $(\cup_{i=1}^t A_i)\cup B\neq (\cup_{i=1}^t A_i)\cup C$; it is called $t$-union-free if for arbitrary two distinct subsets $\mathcal{A},\mathcal{B}$, each consisting of at most $t$ edges, it holds that $\cup_{A\in\mathcal{A}} A\neq \cup_{B\in\mathcal{B}} B$. Let $C_t(n,r)$ and $U_t(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 $C_t(n,r)$ and $U_t(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 $C_{2(t-1)}(n,tk)=Θ(n^k)$ and $U_{t+1}(n,tk)=Θ(n^k)$ for all $t\ge 2$ and $k\ge 2$. In this paper, we determine the asymptotics of these two functions up to a lower order term, by showing that for all $t\ge 2$ and $k\ge 2$, \begin{align*} \text{$\lim_{n\rightarrow\infty}\frac{C_{2(t-1)}(n,tk)}{n^k}=\lim_{n\rightarrow\infty}\frac{U_{t+1}(n,tk)}{n^k}=\frac{1}{k!}\cdot \frac{1}{\binom{tk-1}{k-1}}$.} \end{align*} Previously, it was only known by a result of Füredi in 2012 that $\lim_{n\rightarrow\infty}\frac{C_{2}(n,4)}{n^2}=\frac{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 $C_{2(t-1)}(n,tk)$ to a classic result of Kleitman and Frankl on a special case of the famous Erdős Matching Conjecture. |
| title | Asymptotically sharp bounds for cancellative and union-free hypergraphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2411.07908 |