Zakázaný problém podgrafu - Forbidden subgraph problem

v teorie extrémních grafů, zakázaný problém s podgrafem je následující problém: daný graf ${displaystyle G}$, vyhledejte maximální počet hran ${displaystyle operatorname {ex} (n, G)}$ v ${displaystyle n}$-vertexový graf, který nemá a podgraf izomorfní na ${displaystyle G}$. V tomto kontextu, ${displaystyle G}$ se nazývá a zakázaný podgraf.^[1]

Ekvivalentním problémem je, kolik hran v ${displaystyle n}$-vrcholový graf zaručuje, že má izografický podgraf ${displaystyle G}$?^[2]

Definice

The extrémní číslo ${displaystyle operatorname {ex} (n, G)}$ je maximální počet hran v ${displaystyle n}$-vertexový graf neobsahující žádný podgraf izomorfní ${displaystyle G}$. ${displaystyle K_ {r}}$ je kompletní graf na ${displaystyle r}$ vrcholy. ${displaystyle T (n, r)}$ je Turánův graf: kompletní ${displaystyle r}$-část graf na ${displaystyle n}$ vrcholy, přičemž vrcholy jsou rozděleny mezi části co nejrovnoměrněji. The chromatické číslo ${displaystyle chi (G)}$ z ${displaystyle G}$ je minimální počet barev potřebných k vybarvení vrcholů ${displaystyle G}$ takže žádné dva sousední vrcholy nemají stejnou barvu.

Výsledek

Non-bipartitní grafy

'Turánova věta '. Pro kladná celá čísla ${displaystyle n, r}$ uspokojující ${displaystyle ngeq rgeq 3}$,^[3] ${extstyle operatorname {ex} (n, K_ {r}) = left (1- {frac {1} {r-1}} ight) {frac {n ^ {2}} {2}}.}$

Tím se vyřeší problém zakázaného podgrafu pro ${displaystyle G = K_ {r}}$. Případy rovnosti pro Turánovu větu pocházejí z Turánův graf ${displaystyle T (n, r-1)}$.

Tento výsledek lze zobecnit na libovolné grafy ${displaystyle G}$ zvážením chromatické číslo ${displaystyle chi (G)}$ z ${displaystyle G}$. Všimněte si, že ${displaystyle T (n, r)}$ lze obarvit pomocí ${displaystyle r}$ barvy, a proto nemá žádné podgrafy s chromatickým číslem větším než ${displaystyle r}$. Zejména, ${displaystyle T (n, chi (G) -1)}$ nemá žádné podgrafy izomorfní ${displaystyle G}$. To naznačuje, že obecné případy rovnosti pro zakázaný problém podgrafu mohou souviset s případy rovnosti pro ${displaystyle G = K_ {r}}$. Ukázalo se, že tato intuice je správná, až ${displaystyle o (n ^ {2})}$ chyba.

'Erdős – kamenná věta '. Pro všechna kladná celá čísla ${displaystyle n}$ a všechny grafy ${displaystyle G}$,^[4]${extstyle operatorname {ex} (n, G) = left (1- {frac {1} {chi (G) -1}} + o (1) ight) {frac {n ^ {2}} {2}} .}$

Když ${displaystyle G}$ není bipartitní, což nám dává aproximaci prvního řádu ${displaystyle operatorname {ex} (n, G)}$.

Bipartitní grafy

Pro bipartitní grafy ${displaystyle G}$, to nám říká jen Erdős – Stoneova věta ${displaystyle operatorname {ex} (n, G) = o (n ^ {2})}$. Problém zakázaného podgrafu pro bipartitní grafy je známý jako Zarankiewiczův problém, a to je obecně nevyřešené.

Pokrok v Zarankiewiczově problému zahrnuje následující větu:

Věta Kővári – Sós – Turán. Pro každou dvojici kladných celých čísel ${displaystyle s, t}$ s ${displaystyle tgeq sgeq 1}$, existuje nějaká konstanta ${displaystyle C}$ (nezávislý na ${displaystyle n}$) takové, že ${extstyle operatorname {ex} (n, K_ {s, t}) leq Cn ^ {2- {frac {1} {s}}}}$ pro každé kladné celé číslo ${displaystyle n}$.^[5]

Dalším výsledkem pro bipartitní grafy je případ sudých cyklů, ${displaystyle G = C_ {2k}, kgeq 2}$. Dokonce i cykly jsou zpracovány s ohledem na kořenový vrchol a cesty odbočující z tohoto vrcholu. Pokud dvě cesty stejné délky ${displaystyle k}$ mají stejný koncový bod a nepřekrývají se, pak vytvoří cyklus délky ${displaystyle 2k}$. To dává následující větu.

Věta (Bondy a Simonovits, 1974). Existuje nějaká konstanta ${displaystyle C}$ takhle ${extstyle operatorname {ex} (n, C_ {2k}) leq Cn ^ {1+ {frac {1} {k}}}}$ pro každé kladné celé číslo ${displaystyle n}$ a kladné celé číslo ${displaystyle kgeq 2}$.^[6]

Silné lemma v teorie extrémních grafů je závislá náhodná volba. Toto lemma nám umožňuje zpracovávat bipartitní grafy s omezeným stupněm v jedné části:

Věta (Alon, Krivelevich, a Sudakov, 2003). Nechat ${displaystyle G}$ být bipartitní graf s vrcholovými částmi ${displaystyle A}$ a ${displaystyle B}$ tak, že každý vrchol v ${displaystyle A}$ má titul nanejvýš ${displaystyle r}$. Pak existuje konstantní konstanta ${displaystyle C}$ (závisí pouze na ${displaystyle G}$) takové, že ${extstyle operatorname {ex} (n, G) leq Cn ^ {2- {frac {1} {r}}}}$pro každé kladné celé číslo ${displaystyle n}$.^[7]

Obecně máme následující domněnku:

Rational Exponent Conjecture (Erdős and Simonovits). Pro každou konečnou rodinu ${displaystyle {mathcal {L}}}$ grafů, pokud existuje bipartita ${displaystyle Lin {mathcal {L}}}$, pak existuje racionální ${displaystyle alfa v [0,1)}$ takhle ${displaystyle operatorname {ex} (n, {mathcal {L}}) = Theta (n ^ {1 + alpha})}$.^[8]

Průzkum od Füredi a Simonovits podrobněji popisuje postup v zakázaném problému podgrafu.^[8]

Dolní hranice

Pro jakýkoli graf ${displaystyle G}$, máme následující dolní mez:

Tvrzení. ${displaystyle operatorname {ex} (n, G) geq cn ^ {2- {frac {v (G) -2} {e (G) -1}}}}$ pro nějakou konstantu ${displaystyle c}$.^[9]

Důkaz. Používáme techniku pravděpodobnostní metoda „metoda úprav“. Zvažte Erdős – Rényi náhodný graf ${displaystyle G (n, p)}$, tj. graf s ${displaystyle n}$ vrcholy a mezi libovolnými dvěma vrcholy je hrana nakreslena s pravděpodobností ${displaystyle p}$nezávisle. Můžeme najít očekávaný počet kopií ${displaystyle G}$ v ${displaystyle G (n, p)}$ podle linearita očekávání. Poté z každé takové kopie odstraníte jeden okraj ${displaystyle G}$, nám zbývá ${displaystyle G}$-bezplatný graf. Očekávaný počet zbývajících hran lze zjistit ${displaystyle operatorname {ex} (n, G) geq cn ^ {2- {frac {v (G) -2} {e (G) -1}}}}$ pro nějakou konstantu ${displaystyle c}$. Proto alespoň jeden ${displaystyle n}$-vertexový graf existuje alespoň s tolik hranami, kolik je očekávaného počtu.

V konkrétních případech byla vylepšena hledání algebraických konstrukcí.

Věta (Erdős, Rényi a Sős, 1966). ${displaystyle operatorname {ex} (n, K_ {2,2}) geq left ({frac {1} {2}} - o (1) ight) n ^ {3/2}.}$^[10]

Důkaz.^[11] Nejprve předpokládejme, že ${displaystyle n = p ^ {2} -1}$ pro některé prime ${displaystyle p}$. Zvažte graf polarity ${displaystyle G}$ s vrcholy prvky ${displaystyle mathbb {F} _ {p} ^ {2} - {0,0}}$ a hrany mezi vrcholy ${displaystyle (x, y)}$ a ${displaystyle (a, b)}$ kdyby a jen kdyby ${displaystyle ax + by = 1}$ v ${displaystyle mathbb {F} _ {p}}$. Tento graf je ${displaystyle K_ {2,2}}$- zdarma, protože soustava dvou lineárních rovnic v ${displaystyle mathbb {F} _ {p}}$ nemůže mít více než jedno řešení. Vrchol ${displaystyle (a, b)}$ (převzít ${displaystyle beq 0}$) je připojen k ${displaystyle left (x, {frac {1-ax} {b}} right)}$ pro všechny ${displaystyle xin mathbb {F} _ {p}}$, celkem minimálně ${displaystyle p-1}$ okraje (odečteno 1 v případě ${displaystyle (a, b) = left (x, {frac {1-ax} {b}} right)}$). Existují tedy minimálně ${displaystyle {frac {1} {2}} (p ^ {2} -1) (p-1) = left ({frac {1} {2}} - o (1) ight) p ^ {3} = vlevo ({frac {1} {2}} - o (1) ight) n ^ {3/2}}$ okraje, jak je požadováno. Obecně ${displaystyle n}$, můžeme vzít ${displaystyle p = (1-o (1)) {sqrt {n}}}$ s ${displaystyle pleq {sqrt {n + 1}}}$ (což je možné, protože existuje prvočíslo ${displaystyle p}$ v intervalu${displaystyle [k-k ^ {0,525}, k]}$ pro dostatečně velké ${displaystyle k}$^[12]) a pomocí takových sestavte graf polarity ${displaystyle p}$, pak přidejte ${displaystyle n-p ^ {2} +1}$ izolované vrcholy, které neovlivňují asymptotickou hodnotu.

Věta (Brown, 1966). ${displaystyle operatorname {ex} (n, K_ {3,3}) geq left ({frac {1} {2}} - o (1) ight) n ^ {5/3}.}$^[13]

Důkazní obrys.^[14] Stejně jako v předchozí větě můžeme vzít ${displaystyle n = p ^ {3}}$ pro prime ${displaystyle p}$ a nechte vrcholy našeho grafu být prvky ${displaystyle mathbb {F} _ {p} ^ {3}}$. Tentokrát vrcholy ${displaystyle (a, b, c)}$ a ${displaystyle (x, y, z)}$ jsou připojeny právě tehdy, když ${displaystyle (x-a) ^ {2} + (y-b) ^ {2} + (z-c) ^ {2} = u}$ v ${displaystyle mathbb {F} _ {p}}$, pro některé konkrétně vybrané ${displaystyle u}$. Tak to je ${displaystyle K_ {3,3}}$- zdarma, protože maximálně dva body leží v průsečíku tří koulí. Pak od hodnoty ${displaystyle (x-a) ^ {2} + (y-b) ^ {2} + (z-c) ^ {2}}$ je napříč téměř jednotný ${displaystyle mathbb {F} _ {p}}$, každý bod by měl mít kolem ${displaystyle p ^ {2}}$ hran, takže celkový počet hran je ${displaystyle left ({frac {1} {2}} - o (1) ight) p ^ {2} cdot p ^ {3} = left ({frac {1} {2}} - o (1) ight) n ^ {5/3}}$.

Zůstává však otevřenou otázkou pro zpřísnění dolní hranice ${displaystyle operatorname {ex} (n, K_ {t, t})}$ pro ${displaystyle tgeq 4}$.

Věta (Alon et al., 1999) pro ${displaystyle tgeq (s-1)! + 1}$, ${displaystyle operatorname {ex} (n, K_ {s, t}) = Theta (n ^ {2- {frac {1} {s}}}).}$^[15]

Zobecnění

Problém lze zobecnit pro sadu zakázaných podgrafů ${displaystyle S}$: najít maximální počet hran v ${displaystyle n}$-vertexový graf, který nemá podgraf izomorfní s žádným grafem z ${displaystyle S}$.^[16]

Jsou tu také hypergraf verze zakázaných problémů s podgrafem, které jsou mnohem obtížnější. Například Turánův problém lze zobecnit na požadavek na největší počet hran v ${displaystyle n}$-vertexový 3 uniformní hypergraf, který neobsahuje žádné čtyřstěny. Analogií konstrukce Turán by bylo rozdělení vrcholů na téměř stejné podmnožiny ${displaystyle V_ {1}, V_ {2}, V_ {3}}$a spojit vrcholy ${displaystyle x, y, z}$ o 3 hrany, pokud jsou všechny odlišné ${displaystyle V_ {i}}$s, nebo pokud jsou dva z nich ${displaystyle V_ {i}}$ a třetí je v ${displaystyle V_ {i + 1}}$ (kde ${displaystyle V_ {4} = V_ {1}}$). To je bez čtyřstěnů a hustota hran je ${displaystyle 5/9}$. Nejznámější horní mez je však 0,562 pomocí techniky algebry vlajky.^[17]

Viz také

• Bezblikový graf
• Erdős – Hajnalův dohad
• Turánova věta
• Turánovo číslo
• Problém izomorfismu podgrafu
• Zakázaná charakterizace grafu
• Erdős-Stoneova věta
• Zarankiewiczův problém
• Extrémní teorie grafů

Reference