Concentration of the largest induced tree size of $G_{n,p}$ around the standard expectation threshold

Dit artikel breidt de resultaten uit over de concentratie van de grootte van de grootste geïnduceerde boom in een binomiale willekeurige graaf uit naar een breder bereik van kansen $p$, en toont bovendien aan dat voor kleinere waarden van $p$ geen concentratie rond de standaard verwachtingsdrempel optreedt.

De kern

Stel je voor dat je een gigantische, willekeurige stad bouwt. Deze stad heeft $n$ inwoners (de punten in het grafiekje). Tussen elke twee inwoners is er een kans $p$ dat ze vrienden worden (een lijntje tussen de punten). Soms is de kans heel groot (iedereen kent elkaar), soms heel klein (niemand kent iemand).

De vraag die deze wiskundige, Jakob Hofstad, zich stelt, is: Hoe groot is het grootste "boom-achtige" groepje vrienden dat je in deze stad kunt vinden, waarbij niemand in dat groepje met iemand buiten het groepje verbonden is?

In de wiskundetaal noemen we zo'n groepje een "geïnduceerde boom". De paper gaat over hoe groot zo'n groepje precies is, afhankelijk van hoe vaak mensen vrienden worden (de waarde van $p$).

Hier is de uitleg in simpele taal, met een paar creatieve vergelijkingen:

1. Het probleem: De zoektocht naar de perfecte boom

Stel je voor dat je in deze stad op zoek bent naar een groep mensen die een perfecte boom vormen:

• Iedereen in de groep is met elkaar verbonden (geen losse eilanden).
• Er zijn geen "rondes" of cirkels (als A vriend is van B, en B van C, dan mag A niet direct vriend zijn van C, anders is het geen boom).
• Belangrijk: Niemand buiten deze groep mag met iemand in de groep bevriend zijn. Als dat wel zo is, is het geen "geïnduceerde" boom meer.

De onderzoekers willen weten: Hoe groot is zo'n groepje precies? Is het altijd precies 10 mensen, of kan het 10 of 11 zijn? Of is het een heel willekeurig getal?

2. Wat wisten we al?

Vroeger wisten wiskundigen dat als de kans $p$ groot is (veel vrienden), het grootste groepje ongeveer twee keer zo groot is als de logaritme van het totaal aantal mensen. Later ontdekten ze dat als $p$ constant is, het antwoord altijd op twee opeenvolgende getallen valt (bijvoorbeeld altijd 10 of 11, nooit 12 of 9).

Onlangs hebben anderen bewezen dat dit ook geldt als $p$ heel klein wordt, maar alleen tot een bepaald punt.

3. Wat doet deze paper? (De nieuwe ontdekkingen)

Jakob Hofstad heeft dit onderzoek uitgebreid naar nog kleinere kansen ($p$). Hij heeft twee belangrijke dingen ontdekt:

A. Het "Magische Getal" (Wanneer het antwoord vastligt)

Als de kans $p$ niet te klein is (maar wel kleiner dan 1), dan is het antwoord nog steeds heel precies. Het grootste groepje zal altijd ofwel getal $X$ zijn, ofwel getal $X+1$.

• De analogie: Stel je voor dat je een toren bouwt met blokken. Als je genoeg blokken hebt, weet je precies dat je toren ofwel 100 blokken hoog is, of 101. Je kunt niet zomaar ineens 105 blokken hebben. De paper bewijst dat dit "twee-mogelijkheden-regel" geldt voor een veel breder scala aan situaties dan voorheen bekend was.

B. Het "Verdwaalde Moment" (Wanneer het antwoord loslaat)

Maar! Als de kans $p$ heel erg klein wordt (mensen maken bijna geen vrienden meer), dan gebeurt er iets raars. Het antwoord is niet meer vast te pinnen op twee getallen rond een "verwachte waarde".

• De analogie: Stel je voor dat je probeert een toren te bouwen met blokken die je uit de lucht laat vallen. Als de wind (de kans $p$) heel zacht is, kun je nog een redelijk stabiele toren bouwen. Maar als de wind bijna stopt, wordt het onmogelijk om te voorspellen hoe hoog je toren wordt. Je toren kan plotseling veel korter zijn dan je zou denken op basis van de gemiddelde windkracht.
• De paper bewijst dat in dit "zeer kleine kans"-gebied, het grootste groepje kleiner is dan wat je op basis van simpele wiskundige verwachtingen zou denken. Het "verwachte" punt waarop je zou denken dat een groepje groot genoeg is, werkt hier niet meer.

4. Hoe hebben ze dit bewezen? (De gereedschapskist)

Om dit te bewijzen, gebruikte de auteur drie verschillende "tellers" (wiskundige hulpmiddelen):

1. De simpele teller ($X_k$): Telt gewoon hoeveel boom-groepjes er zijn. Dit gaf de bovenste grens (hoe hoog het niet kan zijn).
2. De strenge teller ($Y_k$): Telt alleen die groepjes waarbij iedereen buiten de groep minstens 3 vrienden in de groep heeft. Dit klinkt streng, maar het helpt om te bewijzen dat er wel een grote groep is (de onderste grens).
3. De "Maximale" teller ($W_k$): Telt groepjes die je niet kunt uitbreiden zonder de regels te breken. Dit werd gebruikt om te bewijzen dat bij heel kleine kansen, de groepjes kleiner zijn dan verwacht.

Samenvatting in één zin

Deze paper laat zien dat in een willekeurige wereld van vrienden, het grootste "gesloten" groepje vrienden meestal heel precies voorspelbaar is (altijd 2 opties), maar als de wereld heel leeg wordt (niemand kent elkaar), valt die voorspelbaarheid weg en worden de groepjes kleiner dan je zou verwachten.

Het is als het verschil tussen een drukke stad waar je altijd een perfecte kring vrienden kunt vinden, en een verlaten eiland waar je soms helemaal geen kring kunt vormen, en de wiskunde precies uitlegt waar dat punt ligt.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het paper "Concentration of the largest induced tree size of $G_{n,p}$ around the standard expectation threshold" van Jakob Hofstad, geschreven in het Nederlands.

1. Probleemstelling

Het paper onderzoekt de grootte van de grootste geïnduceerde boom (induced tree) in een binomiale willekeurige graaf $G_{n,p}$.

• Definitie: Laat $T(G)$ de grootte zijn van de grootste geïnduceerde boom in een graaf $G$. Een geïnduceerde boom is een deelgraaf die een boom is en die alle kanten bevat tussen de geselecteerde knopen die ook in de oorspronkelijke graaf aanwezig zijn.
• Context: De studie van $T(G_{n,p})$ is nauw verwant aan de bestudering van het onafhankelijkheidsgetal $\alpha(G)$ en de grootte van de grootste geïnduceerde bos ($F(G)$).
• Bestaande resultaten:
  • Voor constante $p$ is bewezen dat $T(G_{n,p})$ geconcentreerd is op twee opeenvolgende waarden (Kamaldinov et al.).
  • Oropeza breidde dit uit naar vervagende $p$ (waarbij $p \to 0$), specifiek voor $p > n^{-e^{-2}/(3e^{-2}) + \epsilon}$.
• Het doel: Het paper heeft tot doel dit concentratie-resultaat uit te breiden naar een bredere reeks van vervagende $p$-waarden en te analyseren wat er gebeurt wanneer $p$ nog kleiner wordt, specifiek in de buurt van de "verwachtingsdrempel" (expectation threshold).

2. Methodologie

De auteur gebruikt een combinatie van momentenmethoden (first en second moment method) en introduceert geavanceerde tellende variabelen om de concentratie van $T(G_{n,p})$ te bewijzen.

• Variabelen:

  • $X_k$: Het aantal geïnduceerde bomen van grootte $k$.
  • $Y_k$: Het aantal geïnduceerde bomen van grootte $k$ waarbij elke knoop buiten de boom minstens 3 buren heeft binnen de boom. Deze restrictie helpt bij het controleren van de variantie in de tweede moment-methode.
  • $W_k$: Het aantal maximale geïnduceerde bomen van grootte $k$ (bomen waar geen enkele knoop buiten de boom precies één buur in de boom heeft). Deze wordt gebruikt voor het bewijzen van het ontbreken van concentratie bij zeer kleine $p$.

• Technieken:

  • Eerste momentmethode: Gebruikt om bovengrenzen te bepalen en om te laten zien dat $T(G_{n,p})$ niet groter kan zijn dan een bepaalde drempel.
  • Tweede momentmethode (Chebyshev's ongelijkheid): Gebruikt om te bewijzen dat $T(G_{n,p})$ met hoge waarschijnlijkheid (whp) minstens een bepaalde waarde bereikt. Dit vereist het aantonen dat $\text{Var}[Y_k] / E[Y_k]^2 = o(1)$.
  • Combinatorische analyse: De analyse van de variantie vereist een zorgvuldige splitsing van de sommatie over paren bomen $(A, T_A)$ en $(B, T_B)$ gebaseerd op de grootte van hun overlap ($\ell = |A \cap B|$) en het aantal componenten ($m$) in de overlap.
  • Stirling's benadering: Gebruikt voor het schatten van faculteiten en gamma-functies in de asymptotische analyse.

3. Belangrijkste Resultaten

Het paper presenteert Stelling 1, die de volgende resultaten bevat voor $p$ in het bereik $n^{-1} \ll p \ll (\ln n)^{-2}$:

1. Definitie van de drempel $k_0$: Er bestaat een functie $k_0(n, p)$ zodanig dat de verwachte waarde $E[X_k]$ overgaat van $\omega(1)$ naar $o(1)$ rond $k_0$. Specifiek voldoet $k_0$ aan de asymptotische vergelijking:
   $$k_0 \approx \frac{2 \ln(np) + 2}{p}$$
   De grootste $k$ waarvoor $E[X_k] \geq 1$ is ofwel $k_0$ of $k_0 + 1$.

2. Twee-punts concentratie (Voor grotere $p$):
   Als $p = \omega(n^{-1/2} \ln^{3/2} n)$, dan is $T(G_{n,p})$ met hoge waarschijnlijkheid geconcentreerd op de twee waarden $\{k_0, k_0 + 1\}$.

   • Bewijsstrategie: De tweede momentmethode wordt toegepast op $Y_k$. De auteur toont aan dat de variantie verwaarloosbaar is ten opzichte van het kwadraat van het gemiddelde, mits $p$ boven deze drempel ligt.

3. Ontbrekende concentratie (Voor kleinere $p$):
   Als $p = o(n^{-1/2})$, dan kan $T(G_{n,p})$ niet geconcentreerd zijn rond de standaard verwachtingsdrempel $k_0$.

   • Specifiek geldt: $T(G_{n,p}) < k_0 - \frac{1}{4np^2}$ met hoge waarschijnlijkheid.
   • Bewijsstrategie: De auteur gebruikt de variabele $W_k$ (maximale bomen). Voor zeer kleine $p$ is de verhouding $E[W_k]/E[X_k]$ zo klein dat de verwachte waarde van het aantal maximale bomen in het kritieke bereik verwaarloosbaar wordt, wat impliceert dat de werkelijke grootte lager ligt dan de theoretische drempel $k_0$.

4. Significatie en Bijdrage

• Uitbreiding van de geldigheidsgebied: Het paper breidt het gebied van $p$ waarvoor twee-punts concentratie geldt aanzienlijk uit, van $p > n^{-0.15...}$ (Oropeza) naar $p \gg n^{-1/2} \ln^{3/2} n$. Dit is een significante stap dichter bij de kritieke drempel $p \sim 1/n$.
• Identificatie van een "Drift": Het paper toont aan dat er een fundamenteel verschil is in het gedrag van $T(G_{n,p})$ afhankelijk van de grootte van $p$. Voor $p$ onder de drempel $n^{-1/2} \ln^{3/2} n$ "drijft" de werkelijke grootte van de grootste boom weg van de standaard verwachtingsdrempel. Dit betekent dat de simpele telling van bomen ($X_k$) niet meer voldoende is om de concentratie te voorspellen.
• Methodologische inzichten: De analyse van de variantie via de restrictie op buren (minimaal 3) en de behandeling van de overlap tussen bomen biedt een robuust raamwerk voor het bestuderen van geïnduceerde subgrafieken in willekeurige grafen.
• Toekomstperspectief: De auteur suggereert dat voor nog kleinere $p$-waarden (dichter bij $1/n$) geavanceerdere technieken nodig zijn, zoals het tellen van "clusters" (groepen knopen die meerdere bomen bevatten) in plaats van individuele bomen. Dit zou vergelijkbaar moeten zijn met de methoden die zijn gebruikt voor het onafhankelijkheidsgetal$\alpha(G_{n,p})$.

Conclusie

Jakob Hofstad bewijst dat de grootte van de grootste geïnduceerde boom in $G_{n,p}$ scherp geconcentreerd is op twee waarden voor een breed scala aan vervagende $p$-waarden, maar dat deze concentratie faalt zodra $p$ te klein wordt ($p = o(n^{-1/2})$), waarbij de werkelijke grootte dan significant afwijkt van de verwachte drempel. Dit paper legt een cruciale brug tussen de bekende resultaten voor constante $p$ en het complexe gedrag in de zeer dunne regime van willekeurige grafen.