| dbo:abstract
|
- 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. (en)
- Лемма об удалении графа утверждает, что если граф содержит несколько копий данного подграфа, то все его копии могут быть исключены путём удаления малого числа рёбер.Лемму иногда называют леммой об удалении треугольников в случае, когда подграф является треугольником. (ru)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 32034 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdfs:comment
|
- 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. (en)
- Лемма об удалении графа утверждает, что если граф содержит несколько копий данного подграфа, то все его копии могут быть исключены путём удаления малого числа рёбер.Лемму иногда называют леммой об удалении треугольников в случае, когда подграф является треугольником. (ru)
|
| rdfs:label
|
- Graph removal lemma (en)
- Лемма об удалении графа (ru)
- Лема про видалення графа (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
