Erdős-Hajnals hypotes

Olösta problem i matematik : Är det sant att grafer med en fast förbjuden inducerad subgraf nödvändigtvis har stora klickar eller stora oberoende uppsättningar?

Erdős-Hajnals förmodan säger att familjer av grafer som definieras av förbjudna inducerade subgrafer har antingen stora klickar eller stora oberoende uppsättningar . Mer exakt, för en godtycklig oriktad graf , låt vara en familj av grafer som inte innehåller som en genererad subgraf . Sedan, enligt hypotesen, finns det en konstant sådan att grafer med hörn i har antingen en klick eller en oberoende uppsättning storlek .

Ett likvärdigt uttalande av den ursprungliga gissningen: för alla grafer innehåller icke-innehållande grafer godtyckligt stora perfekta genererade subgrafer .

Grafer utan stora klick eller oberoende uppsättningar

Som jämförelse, för slumpmässiga grafer i Erdős-Rényi-modellen med kantsannolikhet 1/2, är både den största klicken och den största oberoende uppsättningen mycket mindre - deras storlek är proportionell mot logaritmen av , och växer inte polynomiellt. Ramseys teorem bevisar att ingen graf har både storleken på den största klicken och storleken på den största oberoende mängden mindre än logaritmisk [1] [2] . Ramsey-satsen antyder också ett specialfall av Erdős-Hajnal-hypotesen, när själva grafen är en klick eller en oberoende mängd [1] .

Delresultat

Gissningen tillhör Pal Erdős och András Hajnal , som bevisade det för fallet när är en kograf . De visade också för en godtycklig graf att storleken på den största klicken eller oberoende uppsättningen växer superlogaritmiskt. Närmare bestämt, för vilken graf som helst finns det en konstant så att grafer utan hörn har klicker eller oberoende uppsättningar som innehåller åtminstone hörn [1] . Graferna för vilka gissningen är sann inkluderar också en bana [1] [3] med fyra hörn, ett tjurhuvud [1] [4] med fem hörn, och vilken graf som helst som kan erhållas från dessa grafer och kografer med hjälp av en modulär sönderdelning [1] [2] . Från och med 2021 har hypotesen dock inte bevisats helt och förblir ett öppet problem [5] .

En tidigare formulering av gissningen, också på grund av Erdős och Hajnal, gäller det speciella fallet där grafen är en 5-vertex grafcykel [3] . Enligt förtrycket 2021 är gissningen sann i det här fallet [5] . Icke-innehållande grafer inkluderar perfekta grafer , som nödvändigtvis har antingen en klick eller en oberoende uppsättning med en storlek som är proportionell mot kvadratroten av deras antal hörn. Omvänt är varje klick eller oberoende uppsättning i sig en perfekt graf. Av denna anledning är en bekväm och symmetrisk formulering av Erdős-Hajnal-förmodan påståendet att för vilken graf som helst , innehåller icke-innehållande grafer nödvändigtvis en genererad perfekt subgraf av polynomstorlek [1] [6] .

Anteckningar

  1. ↑ 1 2 3 4 5 6 7 Erdős, Hajnal, 1989 , sid. 37–52.
  2. ↑ 1 2 Alon, Pach, Solymosi, 2001 , sid. 155–170.
  3. ↑ 1 2 Gyárfás, 1997 , sid. 93–98.
  4. ↑ Chudnovsky, Safra, 2008 , sid. 1301–1310.
  5. ↑ 12 Steve Nadis . Nytt bevis avslöjar att grafer utan femhörningar är fundamentalt annorlunda . Quanta (26 april 2021). Hämtad 26 april 2021. Arkiverad från originalet 26 april 2021.
  6. ↑ Chudnovsky, 2014 , sid. 178–179.

Litteratur

Länkar