A Removal Lemma for Kneser Graphs and Product Graphs
summary
Proves a removal lemma for sparse product-type graphs (notably the Kneser graph layer and the triangle-power product graph): any vertex subset that spans at most Δ fraction of host edges can be made independent by deleting an ε fraction of vertices. Main tools are the weak DFR structural theorem, the MOO/invariance argument to find influential coordinates, a shattering lemma and an entropy/potential iteration in the style of Fox plus a crucial maximal matching trick. Gives effective quantitative bounds (original tower 1/ε, improved to tower height ~log(1/ε)); the construction resists small spectral/regularity changes (e.g. adding a random matching).
AI-written summary · about