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

Technische Zusammenfassung: $K_{2,t+1}$-freie Graphen, die eine optimale Anzahl an $K_{t,t}$ enthalten

Problemstellung
Die Arbeit befasst sich mit der verallgemeinerten Turán-Zahl, bezeichnet als $\text{ex}(n, H, F)$, welche die maximale Anzahl an Kopien eines Graphen $H$ darstellt, die in einem $F$-freien Graphen auf $n$ Knoten existieren können. Speziell untersuchen die Autoren den Fall, in dem $H = K_{t,t}$ und $F = K_{2,t+1}$ ist. Ziel ist es, das asymptotische Verhalten von $\text{ex}(n, K_{t,t}, K_{2,t+1})$ zu bestimmen.

Während die jüngere Arbeit von Pohoata, Tidor und Yu etablierte, dass $\text{ex}(n, K_{t,t}, K_{2,t+1}) = \Theta_t(n^2)$ für alle ganzen Zahlen $t \ge 3$ gilt, stützte sich ihr Beweis auf probabilistische Methoden und subspace-evasive Mengen, was eine untere Schranke mit einem Koeffizienten ergab, der nicht notwendigerweise optimal war. Diese Arbeit strebt danach, eine präzise asymptotische Formel für spezifische Werte von $n$ und $t$ unter Verwendung einer expliziten Konstruktion zu liefern.

Methodik
Die Autoren verwenden eine deterministische, algebraische Konstruktion von Graphen basierend auf endlichen Körpern und linearisierten Polynomen.

1. Graph-Konstruktion ($\Gamma_{t,e}$):

   • Sei $t$ eine Primzahlpotenz und $e > 1$ eine ganze Zahl. Definiere $q = t^e$.
   • Sei $L$ ein $\mathbb{F}_t$-linearisiertes Polynom über $\mathbb{F}_q[x]$, sodass die Dimension seines Kerns 1 ist. Der Bildraum $R_L$ hat die Größe $t^{e-1}$.
   • Die Knotenmenge ist definiert als $V = \mathbb{F}_q \times R_L$, woraus $n = q \cdot t^{e-1} = t^{2e-1}$ Knoten resultieren.
   • Zwei distinkte Knoten $(v_1, v_2)$ und $(w_1, w_2)$ sind genau dann adjazent, wenn $v_2 + w_2 = L(v_1 w_1)$. Durch die Gleichung implizierte Selbstschleifen werden entfernt, um einen einfachen Graphen zu gewährleisten.

2. Ableitung der oberen Schranke:

   • Die Autoren etablieren zunächst eine präzise obere Schranke für $\text{ex}(n, K_{t,t}, K_{2,t+1})$.
   • Das Argument beruht auf der Tatsache, dass in einem $K_{2,t+1}$-freien Graphen zwei beliebige Knoten höchstens $t$ gemeinsame Nachbarn besitzen.
   • Durch das Zählen von Paaren von Knoten und die Analyse, wie oft eine $K_{t,t}$ über ihre konstituierenden Paare gezählt wird, leiten sie die Schranke ab:
     $$\text{ex}(n, K_{t,t}, K_{2,t+1}) \le \frac{\binom{n}{2}}{2\binom{t}{2}}$$

3. Strukturelle Analyse der Konstruktion:

   • $K_{2,t+1}$-Freiheit: Die Autoren beweisen, dass $\Gamma_{t,e}$ kein $K_{2,t+1}$ enthält. Für zwei beliebige Knoten wird die Anzahl der gemeinsamen Nachbarn durch die Anzahl der Lösungen einer linearen Gleichung unter Verwendung von $L$ bestimmt. Da $L$ eine $t$-zu-1-Abbildung ist, gibt es höchstens $t$ gemeinsame Nachbarn.
   • $K_{t,t}$-Bildung: Der Kern des Beweises liegt in der Analyse nicht-adjazenter Knoten. Die Autoren zeigen, dass zwei nicht-adjazente Knoten mit unterschiedlichen ersten Koordinaten eindeutig zwei Mengen, $M$ und $N$, der Kardinalität $t$ definieren.
     • $N$ ist die Menge der gemeinsamen Nachbarn (eine $\mathbb{F}_t$-Gerade).
     • $M$ ist die $\mathbb{F}_t$-Gerade, die die beiden Knoten enthält.
     • Jeder Knoten in $M$ ist algebraisch adjazent zu jedem Knoten in $N$.
   • Wenn $M \cap N = \emptyset$, bildet der durch $M \cup N$ induzierte Subgraph ein $K_{t,t}$. Wenn $|M \cap N| = 1$, bildet die Struktur einen tripartiten vollständigen Graphen $K_{1, t-1, t-1}$.

Wesentliche Beiträge und Ergebnisse
Der primäre Beitrag ist die Bereitstellung einer expliziten Graphfamilie, die die theoretische obere Schranke für die Anzahl der $K_{t,t}$-Kopien, modulo Terme niedrigerer Ordnung, für eine unendliche Menge von $n$ erreicht.

• Theorem 1.1: Für $t$ als Primzahlpotenz und $n = t^{2e-1}$ (wobei $e > 1$ eine ganze Zahl ist), erfüllt die verallgemeinerte Turán-Zahl:
  $$\text{ex}(n, K_{t,t}, K_{2,t+1}) = (1 + o(1)) \frac{n^2}{2t(t-1)}$$
• Vergleich mit bisherigen Schranken: Die Arbeit stellt fest, dass die bisher beste untere Schranke aus [5] der Form $(1-o(1)) \frac{n^2}{4t^2 t!}$ war. Das neue Ergebnis verbessert diesen Koeffizienten signifikant für Primzahlpotenzen $t > 5$.
• Vernachlässigbarkeit nicht-optimaler Fälle: Die Autoren zeigen, dass die Anzahl der Konfigurationen, die zu einem $K_{1, t-1, t-1}$ führen (wo $|M \cap N| = 1$), im Vergleich zur Gesamtzahl der $K_{t,t}$ ($O(n^2)$) vernachlässigbar ist ($O(n)$), was die asymptotische Dominanz der $K_{t,t}$-Zählung sicherstellt.

Bedeutung und Behauptungen
Die Arbeit behauptet, eine „einfache und vollständig explizite Konstruktion“ für eine unendliche, wenn auch spärliche Menge von $n$'s bereitzustellen, was im Gegensatz zu den zuvor verfügbaren probabilistischen Existenzbeweisen steht. Die Konstruktion ist isomorph zu Graphen, die zuvor von Lazebnik und Mubayi im Kontext von mehrfarbigen Ramsey-Zahlen untersucht wurden, wenngleich diese Arbeit sie spezifisch auf das Problem der verallgemeinerten Turán-Zahl anwendet.

Die Autoren schließen mit der Vermutung, dass die abgeleitete obere Schranke für alle $n$ gilt, nicht nur für die spezifischen Primzahlpotenz-Fälle der Konstruktion:
$$\text{ex}(n, K_{t,t}, K_{2,t+1}) = (1 + o(1)) \frac{n^2}{2t(t-1)}$$
Die Arbeit dient dazu, das Verständnis der Wachstumsrate verallgemeinerter Turán-Zahlen für bipartite Graphen zu verfeinern, indem sie von Größenordnungsschätzungen zu präzisen asymptotischen Konstanten für spezifische Regime übergeht.