A new proof of the graph removal lemma

• 成果类型: Article
• 署名作者: Fox, Jacob
• 刊物名称: ANNALS OF MATHEMATICS
• ISSN/ISSBN: 0003-486X
• DOI: 10.4007/annals.2011.174.1.17
• 发表日期: 2011
• 页码: 561-579
• 关键词: regularity lemma

摘要

Let H be a fixed graph with h vertices. The graph removal lemma states that every graph on n vertices with o(n(h)) copies of H can be made H-free by removing o(n(2)) edges. We give a new proof which avoids Szemeredi's regularity lemma and gives a better bound. This approach also works to give improved bounds for the directed and multicolored analogues of the graph removal lemma This answers questions of Alon and Gowers.