Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Graph removal lemma
Summary
In graph theory, the graph removal lemma states that when a graph contains few copies of a given subgraph, then all of the copies can be eliminated by removing a small number of edges.
The special case in which the subgraph is a triangle is known as the triangle removal lemma.
The graph removal lemma can be used to prove Roth's theorem on 3-term arithmetic progressions, and a generalization of it, the hypergraph removal lemma, can be used to prove Szemerédi's theorem. It also has applications to property testing.
Let be a graph with vertices. The graph removal lemma states that for any
there exists a constant such that for any -vertex graph with fewer than subgraphs isomorphic to , it is possible to eliminate all copies of by removing at most edges from .
An alternative way to state this is to say that for any -vertex graph with subgraphs isomorphic to , it is possible to eliminate all copies of by removing edges from . Here, the indicates the use of little o notation.
In the case when is a triangle, resulting lemma is called triangle removal lemma.
The original motivation for the study of triangle removal lemma was Ruzsa–Szemerédi problem. Initial formulation due to Imre Z. Ruzsa and Szemerédi from 1978 was slightly weaker than the triangle removal lemma used nowadays and can be roughly stated as follows: every locally linear graph on vertices contains edges. This statement can be quickly deduced from a modern triangle removal lemma. Ruzsa and Szemerédi provided also an alternative proof of Roth's theorem on arithmetic progressions as a simple corollary.
In 1986 during their work on generalizations of Ruzsa–Szemerédi problem to arbitrary -uniform graphs, Erdős, Frankl, and Rödl provided statement for general graphs very close to the modern graph removal lemma: if graph is a homomorphic image of , then any -free graph on vertices can be made -free by removing edges.
The modern formulation of graph removal lemma was first stated by Füredi in 1994.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.