| dbo:abstract
|
- A matematika, azon belül a gráfelmélet területén az Erdős–Gyárfás-sejtés az 1995-ben Erdős Pál és Gyárfás András által megfogalmazott, bizonyítatlan állítás, mely szerint minden, legalább 3 minimális fokszámú gráf tartalmaz hosszúságú egyszerű kört. Erdős 100 dollárt ajánlott a sejtés bizonyításáért, 50 dollárt egy ellenpéldáért; a sejtés Erdős számos sejtésének egyike. Ha a sejtés hamis, az ellenpéldának olyan gráfnak kell lennie, melynek minimális fokszáma 3, és nem tartalmaz kettőhatvány hosszúságú kört. és Klas Markström számítógépes kereséseiből tudjuk, hogy bármely ellenpéldának legalább 17 csúcsból kell állnia, egy 3-reguláris gráf esetén pedig legalább 30 csúcsból. Markström talál négy olyan, 24 csúcsú gráfot, melyben kizárólag 16 hosszú kettőhatvány-körök voltak. A négy gráf egyike síkbarajzolható; az Erdős–Gyárfás-sejtést azonban a 3-szorosan összefüggő, 3-reguláris síkbarajzolható gráfok esetére már sikerült belátni. Születtek gyengébb eredmények, melyek a gráf fokszámát és az elkerülhetetlen körhosszúságokat kapcsolják össze: létezik hosszúságok olyan S halmaza, ahol |S| = O(n0,99), hogy minden 10 vagy magasabb átlagos fokszámú gráf tartalmaz S-ben lévő hosszúságú kört ; pedig felső korlátot ad a kettőhatvány hosszúságú kört nem tartalmazó, n csúcsú gráfok átlagos fokszámára: , ahol log* a bináris jelenti. A sejtést igazolta síkbarajzolható karommentes gráfokra, pedig olyan gráfokra, melyek nem tartalmaznak nagyméretű feszített csillagokat és néhány más, fokszámra vonatkozó követelménynek eleget tesznek. (hu)
- A matematika, azon belül a gráfelmélet területén az Erdős–Gyárfás-sejtés az 1995-ben Erdős Pál és Gyárfás András által megfogalmazott, bizonyítatlan állítás, mely szerint minden, legalább 3 minimális fokszámú gráf tartalmaz hosszúságú egyszerű kört. Erdős 100 dollárt ajánlott a sejtés bizonyításáért, 50 dollárt egy ellenpéldáért; a sejtés Erdős számos sejtésének egyike. Ha a sejtés hamis, az ellenpéldának olyan gráfnak kell lennie, melynek minimális fokszáma 3, és nem tartalmaz kettőhatvány hosszúságú kört. és Klas Markström számítógépes kereséseiből tudjuk, hogy bármely ellenpéldának legalább 17 csúcsból kell állnia, egy 3-reguláris gráf esetén pedig legalább 30 csúcsból. Markström talál négy olyan, 24 csúcsú gráfot, melyben kizárólag 16 hosszú kettőhatvány-körök voltak. A négy gráf egyike síkbarajzolható; az Erdős–Gyárfás-sejtést azonban a 3-szorosan összefüggő, 3-reguláris síkbarajzolható gráfok esetére már sikerült belátni. Születtek gyengébb eredmények, melyek a gráf fokszámát és az elkerülhetetlen körhosszúságokat kapcsolják össze: létezik hosszúságok olyan S halmaza, ahol |S| = O(n0,99), hogy minden 10 vagy magasabb átlagos fokszámú gráf tartalmaz S-ben lévő hosszúságú kört ; pedig felső korlátot ad a kettőhatvány hosszúságú kört nem tartalmazó, n csúcsú gráfok átlagos fokszámára: , ahol log* a bináris jelenti. A sejtést igazolta síkbarajzolható karommentes gráfokra, pedig olyan gráfokra, melyek nem tartalmaznak nagyméretű feszített csillagokat és néhány más, fokszámra vonatkozó követelménynek eleget tesznek. (hu)
|
| prop-hu:képaláírás
|
- Markström az Erdős–Gyárfás-sejtés ellenpéldáinak számítógépes keresése során talált, 24 csúcsú, 3-reguláris síkbarajzolható gráfja, ami nem tartalmaz 4, illetve 8 hosszúságú köröket. A sejtést nem cáfolja, mivel 16 hosszúságú köröket viszont tartalmaz. (hu)
- Markström az Erdős–Gyárfás-sejtés ellenpéldáinak számítógépes keresése során talált, 24 csúcsú, 3-reguláris síkbarajzolható gráfja, ami nem tartalmaz 4, illetve 8 hosszúságú köröket. A sejtést nem cáfolja, mivel 16 hosszúságú köröket viszont tartalmaz. (hu)
|
