In mathematics, the Burr–Erdős conjecture was a problem concerning the Ramsey number of sparse graphs. The conjecture is named after Stefan Burr and Paul Erdős, and is one of many conjectures named after Erdős; it states that the Ramsey number of graphs in any sparse family of graphs should grow linearly in the number of vertices of the graph. The conjecture was proven by Choongbum Lee. Thus it is now a theorem.
Attributes | Values |
---|
rdfs:label
| - Burr–Erdős conjecture (en)
- Conjecture d'Erdős-Burr (fr)
- Гипотеза Эрдёша — Бура (ru)
|
rdfs:comment
| - In mathematics, the Burr–Erdős conjecture was a problem concerning the Ramsey number of sparse graphs. The conjecture is named after Stefan Burr and Paul Erdős, and is one of many conjectures named after Erdős; it states that the Ramsey number of graphs in any sparse family of graphs should grow linearly in the number of vertices of the graph. The conjecture was proven by Choongbum Lee. Thus it is now a theorem. (en)
- Гипотеза Эрдёша — Бура — математическая проблема, касающаяся числа Рамсея на разреженных графах.Гипотеза названа в честь Пала Эрдёша и .Гипотеза утверждает, что число Рамсея в любом семействе разреженных графов должно иметь почти линейный рост в зависимости от числа вершин графа. Эта гипотеза была полностью доказана Choongbum Lee в 2017 году (и таким образом теперь она является теоремой) (ru)
- En théorie des graphes, la conjecture d'Erdős-Burr, proposée en 1973 par Paul Erdős et (en), concerne la croissance du nombre de Ramsey d'un graphe non orienté de degré de dégénérescence donné, en fonction de son nombre de sommets. Elle a été démontrée par Choongbum Lee en 2015. Il découle du théorème de Ramsey qu'il existe un plus petit entier r(G), le nombre de Ramsey de G, tel que tout graphe complet d'au moins r(G) sommets dont les arêtes sont coloriées en rouge et bleu contienne une copie monochromatique de G. La conjecture est : (fr)
|
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
| |
has abstract
| - In mathematics, the Burr–Erdős conjecture was a problem concerning the Ramsey number of sparse graphs. The conjecture is named after Stefan Burr and Paul Erdős, and is one of many conjectures named after Erdős; it states that the Ramsey number of graphs in any sparse family of graphs should grow linearly in the number of vertices of the graph. The conjecture was proven by Choongbum Lee. Thus it is now a theorem. (en)
- En théorie des graphes, la conjecture d'Erdős-Burr, proposée en 1973 par Paul Erdős et (en), concerne la croissance du nombre de Ramsey d'un graphe non orienté de degré de dégénérescence donné, en fonction de son nombre de sommets. Elle a été démontrée par Choongbum Lee en 2015. Il découle du théorème de Ramsey qu'il existe un plus petit entier r(G), le nombre de Ramsey de G, tel que tout graphe complet d'au moins r(G) sommets dont les arêtes sont coloriées en rouge et bleu contienne une copie monochromatique de G. Un graphe est dit p-dégénéré si tout sous-graphe contient un sommet de degré inférieur ou égal à p. La conjecture est : pour tout entier p, il existe une constante cp telle que tout graphe p-dégénéré à n sommets ait son nombre de Ramsey majoré par cp n. Avant d'être démontrée, elle a été vérifiée dans certains cas particuliers :
* pour les graphes de degré maximal borné ;
* pour les graphes p-arrangeables et, en particulier, les graphes planaires et les graphes sans subdivisions de ;
* pour les graphes subdivisés. (fr)
- Гипотеза Эрдёша — Бура — математическая проблема, касающаяся числа Рамсея на разреженных графах.Гипотеза названа в честь Пала Эрдёша и .Гипотеза утверждает, что число Рамсея в любом семействе разреженных графов должно иметь почти линейный рост в зависимости от числа вершин графа. Эта гипотеза была полностью доказана Choongbum Lee в 2017 году (и таким образом теперь она является теоремой) (ru)
|
prov:wasDerivedFrom
| |
page length (characters) of wiki page
| |
foaf:isPrimaryTopicOf
| |
is Link from a Wikipage to another Wikipage
of | |
is Wikipage redirect
of | |
is foaf:primaryTopic
of | |