Erdős–Hajnal gissning

Olöst problem i matematik :

Har graferna med en fast förbjuden inducerad subgraf nödvändigtvis stora klick eller stora oberoende uppsättningar?

(fler olösta problem i matematik)

Inom grafteorin , en gren av matematiken, säger Erdős–Hajnal-förmodan att familjer av grafer som definieras av förbjudna inducerade subgrafer har antingen stora klickar eller stora oberoende uppsättningar . Den är uppkallad efter Paul Erdős och András Hajnal .

Mer exakt, för en godtycklig oriktad graf $H$ , låt ${\mathcal {F}}_{H}$ vara familjen av grafer som inte har $H$ som en inducerad subgraf . Sedan, enligt gissningen, finns det en konstant $\delta _{H}>0$ så att $n$ -vertexgraferna i ${\mathcal {F} }_{H}$ har antingen en klick eller en oberoende uppsättning av storleken $\Omega (n^{\delta _{H}})$ .

Ett ekvivalent uttalande till den ursprungliga gissningen är att för varje graf ${\displaystyle H} innehåller$ de $H$ -fria graferna alla polynomiskt stora perfekta inducerade subgrafer .

Grafer utan stora klick eller oberoende uppsättningar

Däremot, för slumpmässiga grafer i Erdős–Rényi-modellen med kantsannolikhet 1/2, är både den maximala klicken och den maximala oberoende mängden mycket mindre: deras storlek är proportionell mot logaritmen för $n$ , snarare än att växa polynomiellt. Ramseys teorem bevisar att ingen graf har både sin maximala klickstorlek och maximala oberoende mängdstorlek mindre än logaritmisk. Ramseys teorem antyder också specialfallet med Erdős–Hajnal-förmodan när $H$ i sig är en klick eller oberoende mängd.

Delvis resultat

Denna gissning beror på Paul Erdős och András Hajnal , som bevisade att det är sant när $H$ är en kograf . De visade också, för godtycklig $H$ , att storleken på den största klicken eller oberoende uppsättningen växer superlogaritmiskt. Mer exakt, för varje $H$ finns det en konstant $c$ så att $n$ -vertex $H$ -fria grafer har klickar eller oberoende uppsättningar som innehåller minst $\exp c{\sqrt {\log n}}$ hörn. Graferna $H$ för vilka gissningen är sann inkluderar också de med fyra hörn eller mindre, alla fem-verex-grafer utom fem-vertex-banan och dess komplement, och alla grafer som kan erhållas från dessa och kograferna genom modulär nedbrytning . Från och med 2021 har dock den fullständiga gissningen inte bevisats och förblir ett öppet problem.

En tidigare formulering av gissningen, också av Erdős och Hajnal, gäller det speciella fallet när $H$ är en 5-vertex cykelgraf . Detta fall har lösts av Maria Chudnovsky , Alex Scott, Paul Seymour och Sophie Spirkl 2021. De $C_{5}$ -fria graferna inkluderar de perfekta graferna , som nödvändigtvis har antingen en klick eller en oberoende uppsättning av storlek proportionell mot kvadratroten av deras antal hörn. Omvänt är varje klick eller oberoende uppsättning i sig perfekt. Av denna anledning är en bekväm och symmetrisk omformulering av Erdős–Hajnal-förmodan att för varje graf ${\displaystyle H} innehåller$ de $H$ -fria graferna nödvändigtvis en inducerad perfekt subgraf med polynomstorlek.

Förhållande till det kromatiska antalet turneringar

Alon et al. visade att följande uttalande om turneringar motsvarar Erdős-Hajnals förmodan.

Gissa. För varje turnering $T$ finns det $\varepsilon (T)>0$ och $c>0$ så att för varje $T$ -fri turnering $G$ med $n$ hörn $\chi (G)\leq c\cdot n^{1-\varepsilon }$ .

Här betecknar $\chi (G)$ det kromatiska talet för $G$ , som är den minsta $k\in \mathbb {N}$ så att det finns en $k$ -färgning för $G$ . En färgläggning av en turnering $G$ är en mappning $\phi :V(G)\rightarrow \{1,\ldots ,k\}$ så att färgklasserna $\{v\in V(T):\phi (v)=i\}$ är transitiva för alla $i=1,\ldots ,k$ .

Klassen av turneringar $H$ med egenskapen att varje $H$ -fri turnering $G$ har $\chi (G)\leq c(H)$ för någon konstant $c(H)$ uppfyller denna ekvivalenta Erdős-Hajnal-förmodan (med $\varepsilon =1$ ). Sådana turneringar $H$ , kallade hjältar, övervägdes av Berger et al. Där är det bevisat att en hjälte har en speciell struktur som är följande:

Sats. En turnering är en hjälte om och bara om alla dess starka komponenter är hjältar. En stark turnering med mer än ett hörn är en hjälte om och bara om den är lika med $\Delta (H,k,1)$ eller $\Delta (H,1,k)$ för någon hjälte $H$ och något heltal $k\geq 0$ .

Här betecknar $\Delta (H,k,1)$ turneringen med de tre komponenterna $H$ , den transitiva turneringen av storlek $k$ och en singel nod $q$ . Bågarna mellan de tre komponenterna definieras enligt följande: $A=\{(v,w):(v\in H\wedge w\in T_{k})\vee (v\in T_{k}\wedge w=q)\vee (v =q\kil w\in H)\}$ . Turneringen $\Delta (H,1,k)$ definieras analogt.

externa länkar

• Erdös-Hajnal-förmodan , Den öppna problemträdgården