Szemerédi's regularity lemma is one of the most powerful tools in extremal graph theory, particularly in the study of large dense graphs. It states that the vertices of every large enough graph can be partitioned into a bounded number of parts so that the edges between different parts behave almost randomly.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Lemme de régularité de Szemerédi (fr)
- Szemerédi regularity lemma (en)
- Лемма регулярности Семереди (ru)
- 塞邁雷迪正則性引理 (zh)
|
| rdfs:comment
| - En théorie des graphes, le lemme de régularité de Szemerédi ou simplement lemme de régularité, est un résultat de partitionnement de graphe. Il exprime qu'un graphe assez grand peut toujours être découpé en un petit nombre de morceaux de telle sorte que les arêtes entre ces morceaux se comportent de façon très régulière. (fr)
- 數學上，塞邁雷迪正則性引理（Szemerédi regularity lemma）斷言，給定任意一個足夠大的圖，都可以將其頂點集劃分成若干個差不多一樣大的子集，使得幾乎每兩個不同的子集之間的邊，都具有隨機二部圖的性質。塞邁雷迪於 1975 年引入了該引理較弱的版本，其只適用於二部圖，用作證明塞邁雷迪定理，後來再於 1978 年證明了完整的版本。 及其合作者和高爾斯將正則性方法推廣到超圖上。 (zh)
- Szemerédi's regularity lemma is one of the most powerful tools in extremal graph theory, particularly in the study of large dense graphs. It states that the vertices of every large enough graph can be partitioned into a bounded number of parts so that the edges between different parts behave almost randomly. (en)
- Лемма регулярности Семереди — лемма из общей теории графов, утверждающая, что вершины любого достаточно большого графа можно разбить на конечное число групп таких, что почти во всех двудольных графах, соединяющих вершины из двух разных групп, рёбра распределены между вершинами почти равномерно. При этом минимальное требуемое количество групп, на которые нужно разбить множество вершин графа, может быть сколь угодно большим, но количество групп в разбиении всегда ограничено сверху. Лемма была доказана Эндре Семереди в 1975 году. (ru)
|
| foaf:depiction
| |
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| Link from a Wikipage to an external page
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| thumbnail
| |
| has abstract
| - En théorie des graphes, le lemme de régularité de Szemerédi ou simplement lemme de régularité, est un résultat de partitionnement de graphe. Il exprime qu'un graphe assez grand peut toujours être découpé en un petit nombre de morceaux de telle sorte que les arêtes entre ces morceaux se comportent de façon très régulière. (fr)
- Szemerédi's regularity lemma is one of the most powerful tools in extremal graph theory, particularly in the study of large dense graphs. It states that the vertices of every large enough graph can be partitioned into a bounded number of parts so that the edges between different parts behave almost randomly. According to the lemma, no matter how large a graph is, we can approximate it with the edge densities between a bounded number of parts. Between any two parts, the distribution of edges will be pseudorandom as per the edge density. These approximations provide essentially correct values for various properties of the graph, such as the number of embedded copies of a given subgraph or the number of edge deletions required to remove all copies of some subgraph. (en)
- Лемма регулярности Семереди — лемма из общей теории графов, утверждающая, что вершины любого достаточно большого графа можно разбить на конечное число групп таких, что почти во всех двудольных графах, соединяющих вершины из двух разных групп, рёбра распределены между вершинами почти равномерно. При этом минимальное требуемое количество групп, на которые нужно разбить множество вершин графа, может быть сколь угодно большим, но количество групп в разбиении всегда ограничено сверху. Говоря неформально, лемма утверждает наличие большого количества больших псевдослучайных структур в абсолютно любом графе достаточно большого размера. Лемма была доказана Эндре Семереди в 1975 году. (ru)
- 數學上，塞邁雷迪正則性引理（Szemerédi regularity lemma）斷言，給定任意一個足夠大的圖，都可以將其頂點集劃分成若干個差不多一樣大的子集，使得幾乎每兩個不同的子集之間的邊，都具有隨機二部圖的性質。塞邁雷迪於 1975 年引入了該引理較弱的版本，其只適用於二部圖，用作證明塞邁雷迪定理，後來再於 1978 年證明了完整的版本。 及其合作者和高爾斯將正則性方法推廣到超圖上。 (zh)
|
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
