$K_{2, t+1}$-free graphs containing an optimal number of $K_{t, t}$'s

Technische Samenvatting: $K_{2,t+1}$-vrije grafen die een optimaal aantal $K_{t,t}$'s bevatten

Probleemstelling
Het artikel behandelt het gegeneraliseerde Turán-getal, aangeduid als $\text{ex}(n, H, F)$, wat de maximale hoeveelheid kopieën van een graaf $H$ vertegenwoordigt die kan voorkomen in een $F$-vrije graaf met $n$ knopen. Specifiek onderzoeken de auteurs het geval waarbij $H = K_{t,t}$ en $F = K_{2,t+1}$. Het doel is om het asymptotische gedrag van $\text{ex}(n, K_{t,t}, K_{2,t+1})$ te bepalen.

Hoewel recent werk door Pohoata, Tidor en Yu vaststelde dat $\text{ex}(n, K_{t,t}, K_{2,t+1}) = \Theta_t(n^2)$ voor alle gehele getallen $t \ge 3$, vertrouwde hun bewijs op probabilistische methoden en subspace-evasieve verzamelingen, wat resulteerde in een ondergrens met een coëfficiënt die niet noodzakelijkerwijs optimaal was. Dit artikel streeft ernaar een precieze asymptotische formule te bieden voor specifieke waarden van $n$ en $t$ met behulp van een expliciete constructie.

Methodologie
De auteurs maken gebruik van een deterministische, algebraïsche constructie van grafen gebaseerd op eindige velden en lineaire polynomen.

1. Grafconstructie ($\Gamma_{t,e}$):

   • Laat $t$ een macht van een priemgetal zijn en $e > 1$ een geheel getal. Definieer $q = t^e$.
   • Laat $L$ een $\mathbb{F}_t$-lineaire polynoom zijn over $\mathbb{F}_q[x]$ zodanig dat de dimensie van de kern 1 is. De beeldruimte $R_L$ heeft grootte $t^{e-1}$.
   • De verzameling knopen wordt gedefinieerd als $V = \mathbb{F}_q \times R_L$, wat resulteert in $n = q \cdot t^{e-1} = t^{2e-1}$ knopen.
   • Twee verschillende knopen $(v_1, v_2)$ en $(w_1, w_2)$ zijn aangrenzend indien en slechts indien $v_2 + w_2 = L(v_1 w_1)$. Zelflussen die door de vergelijking worden geïmpliceerd, worden verwijderd om een enkelvoudige graaf te waarborgen.

2. Afleiding van de bovengrens:

   • De auteurs stellen eerst een nauwkeurige bovengrens vast voor $\text{ex}(n, K_{t,t}, K_{2,t+1})$.
   • Het argument berust op het feit dat in een $K_{2,t+1}$-vrije graaf, elke twee knopen maximaal $t$ gemeenschappelijke buren delen.
   • Door paren knopen te tellen en te analyseren hoe vaak een $K_{t,t}$ wordt geteld via de constituerende paren, leiden zij de grens af:
     $$\text{ex}(n, K_{t,t}, K_{2,t+1}) \le \frac{\binom{n}{2}}{2\binom{t}{2}}$$

3. Structurele Analyse van de Constructie:

   • $K_{2,t+1}$-vrijheid: De auteurs bewijzen dat $\Gamma_{t,e}$ geen $K_{2,t+1}$ bevat. Voor elke twee knopen wordt het aantal gemeenschappelijke buren bepaald door het aantal oplossingen van een lineaire vergelijking met betrekking tot $L$. Aangezien $L$ een $t$-op-1 afbeelding is, zijn er maximaal $t$ gemeenschappelijke buren.
   • $K_{t,t}$ Vorming: De kern van het bewijs betreft het analyseren van niet-aangrenzende knopen. De auteurs tonen aan dat elke twee niet-aangrenzende knopen met verschillende eerste coördinaten uniek twee verzamelingen definiëren, $M$ en $N$, met kardinaliteit $t$.
     • $N$ is de verzameling gemeenschappelijke buren (een $\mathbb{F}_t$-lijn).
     • $M$ is de $\mathbb{F}_t$-lijn die de twee knopen bevat.
     • Elke knoop in $M$ is algebraïsch aangrenzend aan elke knoop in $N$.
   • Indien $M \cap N = \emptyset$, vormt de door $M \cup N$ geïnduceerde subgraaf een $K_{t,t}$. Indien $|M \cap N| = 1$, vormt de structuur een tripartiete volledige graaf $K_{1, t-1, t-1}$.

Belangrijkste Bijdragen en Resultaten
De primaire bijdrage is een expliciete constructie van een grafenfamilie die de theoretische bovengrens voor het aantal $K_{t,t}$ kopieën bereikt, modulo lagere-orde termen, voor een oneindige verzameling van $n$'s.

• Stelling 1.1: Voor $t$ als een macht van een priemgetal en $n = t^{2e-1}$ (waarbij $e > 1$ een geheel getal is), voldoet het gegeneraliseerde Turán-getal aan:
  $$\text{ex}(n, K_{t,t}, K_{2,t+1}) = (1 + o(1)) \frac{n^2}{2t(t-1)}$$
• Vergelijking met Vorige Grenzen: Het artikel merkt op dat de voorheen beste ondergrens uit [5] van de vorm $(1-o(1)) \frac{n^2}{4t^2 t!}$ was. De nieuwe resultaat verbetert deze coëfficiënt aanzienlijk voor priemmacht $t > 5$.
• Verwaarloosbaarheid van Niet-Optimale Gevallen: De auteurs demonstreren dat het aantal configuraties die resulteren in $K_{1, t-1, t-1}$ (waar $|M \cap N| = 1$) verwaarloosbaar is ($O(n)$) vergeleken met het totaal aantal $K_{t,t}$'s ($O(n^2)$), wat de asymptotische dominantie van de $K_{t,t}$ telling waarborgt.

Betekenis en Claims
Het artikel claimt een "eenvoudige en volledig expliciete constructie" te bieden voor een oneindige, zij het ijle, verzameling van $n$'s, wat contrasteert met de eerder beschikbare probabilistische existentiebewijzen. De constructie is isomorf aan grafen die eerder door Lazebnik en Mubayi zijn bestudeerd in de context van multicolor Ramsey-getallen, hoewel dit artikel hen specifiek toepast op het gegeneraliseerde Turán-probleem.

De auteurs concluderen door te vermoeden dat de afgeleide bovengrens nauwkeurig (tight) is voor alle $n$, niet alleen voor de specifieke machten van priemgetallen die geconstrueerd zijn:
$$\text{ex}(n, K_{t,t}, K_{2,t+1}) = (1 + o(1)) \frac{n^2}{2t(t-1)}$$
Het werk dient om het begrip van de groeisnelheid van gegeneraliseerde Turán-getallen voor bipartiete grafen te verfijnen, van orde-grootte schattingen naar precieze asymptotische constanten voor specifieke regimes.