Abstract | ||
---|---|---|
We give an arithmetic version of the recent proof of the triangle removal lemma by Fox [Fox11], for the group $\mathbb{F}_2^n$. A triangle in $\mathbb{F}_2^n$ is a triple $(x,y,z)$ such that $x+y+z = 0$. The triangle removal lemma for $\mathbb{F}_2^n$ states that for every $\epsilon > 0$ there is a $\delta > 0$, such that if a subset $A$ of $\mathbb{F}_2^n$ requires the removal of at least $\epsilon \cdot 2^n$ elements to make it triangle-free, then it must contain at least $\delta \cdot 2^{2n}$ triangles. This problem was first studied by Green [Gre05] who proved a lower bound on $\delta$ using an arithmetic regularity lemma. Regularity based lower bounds for triangle removal in graphs were recently improved by Fox and we give a direct proof of an analogous improvement for triangle removal in $\mathbb{F}_2^n$. The improved lower bound was already known to follow (for triangle-removal in all groups), using Fox's removal lemma for directed cycles and a reduction by Kr\'{a}l, Serra and Vena [KSV09] (see [Fox11,CF13]). The purpose of this note is to provide a direct Fourier-analytic proof for the group $\mathbb{F}_2^n.$ |
Year | Venue | Field |
---|---|---|
2013 | CoRR | Graph,Discrete mathematics,Combinatorics,Tuple,Upper and lower bounds,Arithmetic,Lemma (mathematics),Mathematics,Direct proof |
DocType | Volume | Citations |
Journal | abs/1304.4921 | 2 |
PageRank | References | Authors |
0.39 | 4 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Pooya Hatami | 1 | 94 | 14.40 |
Sushant Sachdeva | 2 | 171 | 16.90 |
Madhur Tulsiani | 3 | 358 | 24.60 |