Extremale grafentheorie

Extremale grafentheorie is een tak van de combinatoriek, dat op het raakvlak ligt van de extremale combinatoriek en de grafentheorie.

De Turán-graaf T ( n, r ) is een voorbeeld van een extremale graaf. Het heeft het maximaal mogelijke aantal bogen voor een graaf op n knopen zonder ( r + 1)-cliques. Dit is T (13,4).

In wezen bestudeert de extremale grafentheorie hoe globale eigenschappen van een graaf de lokale substructuur beïnvloeden. Resultaten in de extremale grafentheorie hebben betrekking op kwantitatieve verbanden tussen verschillende graafeigenschappen, zowel globaal (zoals het aantal knopen en bogen) als lokaal (zoals het bestaan van specifieke subgrafen).

Problemen in de extremale grafentheorie kunnen vaak worden geformuleerd als optimalisatieproblemen: hoe groot of klein kan een parameter van een graaf zijn, gegeven een aantal beperkingen waaraan de graaf moet voldoen? Een graaf die een optimale oplossing is voor een dergelijk optimalisatieprobleem, wordt een extremale graaf genoemd. Deze extremale grafen zijn belangrijke studieobjecten in de extremale grafentheorie.

De extremale grafentheorie is nauw verwant aan vakgebieden als Ramsey-theorie, spectrale grafentheorie, computationele complexiteitstheorie en additieve combinatoriek.

Geschiedenis

De stelling van Mantel (1907) en de stelling van Turán (1941) waren enkele van de eerste mijlpalen in de studie van de extremale grafentheorie. In het bijzonder zou de stelling van Turán later een motivatie worden voor het vinden van resultaten zoals de stelling van Erdős-Stone (1946). Dit resultaat is verrassend omdat het het chromatische getal verbindt met het maximale aantal bogen in een ${\displaystyle H}$-vrije graaf. Een alternatief bewijs van Erdős-Stone werd gegeven in 1975, en maakte gebruik van het Szemerédi-regulariteitslemma, een essentiële techniek bij het oplossen van extremale grafentheoretische problemen.

Onderwerpen en concepten

Grafenkleuring

De Petersen-graaf heeft chromatisch getal 3.

Een juiste (knoop)kleuring van een graaf ${\displaystyle G}$ is een kleuring van de knopen van ${\displaystyle G}$ zodanig dat geen twee aangrenzende knopen dezelfde kleur hebben. Het minimum aantal kleuren dat nodig is om goed te kleuren ${\displaystyle G}$ wordt het chromatische getal van genoemd ${\displaystyle G}$. Het wordt aangegeven met ${\displaystyle \chi (G)}$. Het bepalen van het chromatische aantal van specifieke grafen is een fundamentele vraag in de extremale grafentheorie, omdat veel problemen op dit gebied en aanverwante gebieden kunnen worden geformuleerd in termen van grafenkleuring.

Twee eenvoudige ondergrenzen voor het chromatische getal van een graaf ${\displaystyle G}$ wordt gegeven door het cliquegetal ${\displaystyle \omega (G)}$ – alle knopen van een kliek moeten verschillende kleuren hebben – en door ${\displaystyle |V(G)|/\alpha (G)}$, waar ${\displaystyle \alpha (G)}$ is het onafhankelijkheidsgetal, omdat de reeks knopen met een bepaalde kleur een onafhankelijke reeks moet vormen.

Over het algemeen is het het bepalen of een bepaalde graaf een kleuring heeft met een voorgeschreven aantal kleuren een probleem dat NP-moeilijk is.

Naast knoopkleuring worden ook andere soorten kleuring bestudeerd, zoals boogkleuringen. De chromatische index ${\displaystyle \chi '(G)}$ van een graaf ${\displaystyle G}$ is het minimum aantal kleuren in een juiste boogkleuring van een graaf, en de stelling van Vizing stelt dat de chromatische index van een graaf ${\displaystyle G}$ oftewel ${\displaystyle \Delta (G)}$ of ${\displaystyle \Delta (G)+1}$ is.

Verboden subgrafen

Het verboden subgraafprobleem is een van de centrale problemen in de extremale grafentheorie. Gegeven een graaf ${\displaystyle G}$, vraagt het verboden subgraafprobleem om het maximale aantal bogen ${\displaystyle \operatorname {ex} (n,G)}$ in een ${\displaystyle n}$-vertexgraaf die geen subgraaf bevat die isomorf is met ${\displaystyle G}$ .

Wanneer ${\displaystyle G=K_{r}}$ een volledige graaf is, geeft de stelling van Turán een exacte waarde voor ${\displaystyle \operatorname {ex} (n,K_{r})}$ en karakteriseert de stelling alle grafen die dit maximum bereiken. Dergelijke grafen staan bekend als Turán-grafen. Voor niet-bipartiete grafen ${\displaystyle G}$, geeft de stelling van Erdős-Stone een asymptotische waarde van ${\displaystyle \operatorname {ex} (n,G)}$ in termen van het chromatische getal van ${\displaystyle G}$. Een open probleem is het bepalen van de asymptotiek van ${\displaystyle \operatorname {ex} (n,G)}$ wanneer ${\displaystyle G}$ bipartiete graaf is. Wanneer ${\displaystyle G}$ een volledige bipartiete graaf is, staat dit bekend als het Zarankiewicz-probleem.

Homomorfismedichtheid

De homomorfismedichtheid ${\displaystyle t(H,G)}$ van een graaf ${\displaystyle H}$ in een graaf ${\displaystyle G}$ beschrijft de waarschijnlijkheid dat een willekeurig gekozen afbeelding uit de knopenverzameling van ${\displaystyle H}$ naar de knopenverzameling van ${\displaystyle G}$ ook een graafhomomorfisme is. Het hangt nauw samen met de subgraafdichtheid, die beschrijft hoe vaak een graaf voorkomt ${\displaystyle H}$ wordt gevonden als een subgraaf van ${\displaystyle G}$.

Het verboden subgraafprobleem kan worden herformuleerd als het maximaliseren van de boogdichtheid van een graaf met ${\displaystyle G}$-dichtheid nul, en dit leidt uiteraard tot veralgemening in de vorm van graafhomomorfisme-ongelijkheden. Dit zijn ongelijkheden die betrekking hebben op ${\displaystyle t(H,G)}$ voor diverse grafen ${\displaystyle H}$.

Een groot open probleem met betrekking tot homomorfismedichtheden is het vermoeden van Sidorenko, dat een strakke ondergrens stelt voor de homomorfismedichtheid van een bipartiete graaf in een graaf ${\displaystyle G}$ in termen van de boogdichtheid van ${\displaystyle G}$.

Graafregulariteit

De bogen tussen delen in een reguliere partitie gedragen zich op een "willekeurige" manier.

Het regulariteitslemma van Szemerédi stelt dat alle grafen 'regulier' zijn in de volgende zin: de knopenverzameling van een bepaalde graaf kan worden opgedeeld in een begrensd aantal delen, zodat de bipartiete graaf tussen de meeste paren delen zich gedraagt als willekeurige bipartiete grafen. Deze partitie geeft een structurele benadering van de originele graaf, die informatie onthult over de eigenschappen van de originele graaf.

Het regulariteitslemma is een centraal resultaat in de extremale grafentheorie en heeft ook talrijke toepassingen in de aangrenzende velden van additieve combinatoriek en computationele complexiteitstheorie.

Zie ook

• Extremale combinatoriek