Graph removal lemma
id:
graph-removal-lemma-267-5154806
title:
Graph removal lemma
text:
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
brand slug:
wiki
category slug:
encyclopedia
description:
original url:
https://en.wikipedia.org/wiki/Graph_removal_lemma
date created:
date modified:
2023-12-27T10:43:46Z
main entity:
{"identifier":"Q62931187","url":"https://www.wikidata.org/entity/Q62931187"}
image:
fields total:
13
integrity:
13