The arbitrary-group induced removal conjecture

Fix a bipartite graph FF, and let GG be a finite group. A subset AGA \subseteq G is ϵ\epsilon-far from bi-induced-FF-free if changing fewer than ϵG\epsilon |G| elements of AA cannot make it bi-induced-FF-free. A uniform random map is a map ϕ ⁣:V(F)G\phi \colon V(F) \to G chosen uniformly from all such maps, and it bi-induces FF when

ϕ(u)+ϕ(v)AuvE(F)\phi(u)+\phi(v) \in A \quad\Longleftrightarrow\quad uv \in E(F)

for every edge-pair (u,v)U×V(u,v) \in U \times V of the bipartition of FF.

Arbitrary-group induced removal conjecture. For every 0<ϵ<1/20 < \epsilon < 1/2, if AGA \subseteq G is ϵ\epsilon-far from bi-induced-FF-free, then

Prϕ ⁣:V(F)G[ϕ bi-induces F]ϵOF(1).\Pr_{\phi \colon V(F) \to G}[\phi\text{ bi-induces }F] \geq \epsilon^{O_F(1)}.

This would extend the removal lemma from abelian groups to arbitrary groups. The claim is stated as open even for general abelian groups, and therefore remains open in the full arbitrary-group setting.

Sources & referencesView supporting material

Primary source

Noga Alon, Jacob Fox and Yufei Zhao, “Efficient arithmetic regularity and removal lemmas for induced bipartite patterns”, arXiv:1801.04675 (2019).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.