Erdős–Gyárfás-sejtés

A matematika megoldatlan problémája:
Tartalmaz-e minden, 3 minimális fokszámú gráf olyan egyszerű kört, aminek hosszúsága kettő hatványa?
(A matematika további megoldatlan problémái)
Markström-gráf
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.
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.

Csúcsok száma24
Élek száma36
Sugár5
Átmérő6
Derékbőség3
Automorfizmusok3

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 kettőhatvány 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. Gordon Royle é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.(Heckman & Krakovski 2013)

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 (Verstraëte 2005); (Sudakov & Verstraëte 2008) 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 iterált logaritmust jelenti. A sejtést (Daniel & Shauger 2001) igazolta síkbarajzolható karommentes gráfokra, (Shauger 1998) 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.

Kapcsolódó kérdések

Vajon tartalmaz-e minden végtelen kromatikus számú gráf páratlan négyzetszám hosszúságú kört? Vajon minden, legalább 4 kromatikus számú gráf tartalmaz kettőhatványnál eggyel nagyobb hosszúságú kört?[1]

Fordítás

  • Ez a szócikk részben vagy egészben az Erdős–Gyárfás conjecture című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

  1. P. Erdős, Some old and new problems in various branches of combinatorics. Graphs and combinatorics (Marseille, 1995). Discrete Math. 165/166 (1997), 227–231.

További információk