An efficient asymmetric removal lemma and its limitations
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916619479941120 |
|---|---|
| author | Gishboliner, Lior Shapira, Asaf Wigderson, Yuval |
| author_facet | Gishboliner, Lior Shapira, Asaf Wigderson, Yuval |
| contents | The triangle removal states that if $G$ contains $\varepsilon n^2$ edge-disjoint triangles, then $G$ contains $δ(\varepsilon)n^3$ triangles. Unfortunately, there are no sensible bounds on the order of growth of $δ(\varepsilon)$, and at any rate, it is known that $δ(\varepsilon)$ is not polynomial in $\varepsilon$. Csaba recently obtained an asymmetric variant of the triangle removal, stating that if $G$ contains $\varepsilon n^2$ edge-disjoint triangles, then $G$ contains $2^{-\mathrm{poly}(1/\varepsilon)}\cdot n^5$ copies of $C_5$. To this end, he devised a new variant of Szemerédi's regularity lemma. We obtain the following results:
- We first give a regularity-free proof of Csaba's theorem, which improves the number of copies of $C_5$ to the optimal number $\mathrm{poly}(\varepsilon)\cdot n^5$.
- We say that $H$ is $K_3$-abundant if every graph containing $\varepsilon n^2$ edge-disjoint triangles has $\mathrm{poly}(\varepsilon)\cdot n^{|V(H)|}$ copies of $H$. It is easy to see that a $K_3$-abundant graph must be triangle-free and tripartite. Given our first result, it is natural to ask if all triangle-free tripartite graphs are $K_3$-abundant. Our second result is that assuming a well-known conjecture of Ruzsa in additive number theory, the answer to this question is negative.
Our proofs use a mix of combinatorial, number-theoretic, probabilistic, and Ramsey-type arguments. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2301_07693 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | An efficient asymmetric removal lemma and its limitations Gishboliner, Lior Shapira, Asaf Wigderson, Yuval Combinatorics The triangle removal states that if $G$ contains $\varepsilon n^2$ edge-disjoint triangles, then $G$ contains $δ(\varepsilon)n^3$ triangles. Unfortunately, there are no sensible bounds on the order of growth of $δ(\varepsilon)$, and at any rate, it is known that $δ(\varepsilon)$ is not polynomial in $\varepsilon$. Csaba recently obtained an asymmetric variant of the triangle removal, stating that if $G$ contains $\varepsilon n^2$ edge-disjoint triangles, then $G$ contains $2^{-\mathrm{poly}(1/\varepsilon)}\cdot n^5$ copies of $C_5$. To this end, he devised a new variant of Szemerédi's regularity lemma. We obtain the following results: - We first give a regularity-free proof of Csaba's theorem, which improves the number of copies of $C_5$ to the optimal number $\mathrm{poly}(\varepsilon)\cdot n^5$. - We say that $H$ is $K_3$-abundant if every graph containing $\varepsilon n^2$ edge-disjoint triangles has $\mathrm{poly}(\varepsilon)\cdot n^{|V(H)|}$ copies of $H$. It is easy to see that a $K_3$-abundant graph must be triangle-free and tripartite. Given our first result, it is natural to ask if all triangle-free tripartite graphs are $K_3$-abundant. Our second result is that assuming a well-known conjecture of Ruzsa in additive number theory, the answer to this question is negative. Our proofs use a mix of combinatorial, number-theoretic, probabilistic, and Ramsey-type arguments. |
| title | An efficient asymmetric removal lemma and its limitations |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2301.07693 |