Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Graph removal lemma
Résumé
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.