Große Cliquen in Graphen mit verbotenen halbinduzierten Strukturen

Grundinformationen

• Papier-ID: 2511.13073
• Titel: Large cliques in graphs with forbidden semi-induced structures
• Autoren: Nannan Chen (Shandong University & IBS), Yulai Ma (Nankai University), Fan Yang (Shandong University & IBS)
• Klassifikation: math.CO (Kombinatorik)
• Einreichungszeit: 17. November 2025
• Papierlink: https://arxiv.org/abs/2511.13073

Zusammenfassung

Dieses Papier untersucht die Existenz großer Cliquen in Graphen mit verbotenen halbinduzierten Substrukturen. Holmsen bewies 2022, dass jeder Graph mit mindestens $c\binom{n}{r}$ $r$-Cliquen, der keinen induzierten vollständigen $r$-partiten Graph $K_{2,\ldots,2}$ enthält, eine Clique der Ordnung $Ω(c^{2^{r-1}}n)$ enthalten muss. Durch das Verbot von halbinduzierten Substrukturen, die mit $K_{2,\ldots,2}$ verwandt sind, wird bewiesen, dass jeder $n$-Knoten-Graph $G$ mit mindestens $c\binom{n}{r}$ Kopien von $K_r$ eine Clique der Ordnung $Ω(cn)$ enthalten muss. Dieses Ergebnis verbessert die Abhängigkeit von $c$ in Holmsens Schranke von $c^{2^{r-1}}$ zu linear in $c$ und erfordert nur das Verbot einer beschränkten Anzahl von Strukturen. Darüber hinaus verbindet sich die Methode natürlich mit dem Konzept der VC-Dimension.

Forschungshintergrund und Motivation

Problemhintergrund

1. Klassische Turán-Theorie: Der Satz von Turán und seine Verallgemeinerungen (Erdős-Stone-Simonovits-Satz) untersuchen Extremalprobleme für verbotene nicht-induzierte Subgraphen. Für Graphen $H$ mit chromatischer Zahl $χ(H) ≥ 3$ führt das Verbot von $H$ als Subgraph dazu, dass der Extremalgraph asymptotisch $(χ(H)-1)$-partit ist, wodurch die Cliquenzahl durch eine Konstante begrenzt wird.
2. Der Fall induzierter Subgraphen: Wenn induzierte Subgraphen verboten sind, ist die Situation völlig unterschiedlich. Gyárfás, Hubenko und Solymosi (2002) bewiesen, dass wenn ein $n$-Knoten-Graph $G$ mindestens $c\binom{n}{2}$ Kanten hat und keinen induzierten $K_{2,2}$ enthält, dann $ω(G) ≥ \frac{c^2}{10}n$.
3. Enge Schranken für Chordalgraphen: Chordalgraphen (die keine induzierten Zyklen der Länge mindestens 4 enthalten) erreichen bessere Schranken: $ω(G) ≥ (1-\sqrt{1-c})n$, was für kleine $c$ gleich $Ω(cn)$ ist.
4. Holmsens Verallgemeinerung: Holmsen (2020) verallgemeinerte den Fall $K_{2,2}$ auf die Mehrteile-Version und bewies, dass Graphen, die den induzierten $K_r[2]$ (die 2-Erweiterung von $K_r$) verbieten, eine Clique der Ordnung $Ω(c^{2^{r-1}}n)$ enthalten.

Forschungsmotivation

Obwohl Holmsens Ergebnis linear in $n$ ist, verschlechtert sich seine Schranke für $c$ schnell mit wachsendem $r$. Die Kernfrage dieses Papiers lautet: Kann man ähnlich wie die Verbesserung von Satz 1.1 zu Satz 1.2 Holmsens Schranke durch das Verbot von mehr (aber beschränkt vielen) Strukturen verbessern?

Bedeutung

• Das Problem verbindet Extremalgraphtheorie mit abstrakten Helly-Sätzen
• Es ist grundlegend für das Verständnis der Beziehung zwischen induzierten Subgraph-Verboten und der Cliquenzahl
• Es offenbart die Rolle der VC-Dimension in Graphstrukturen

Kernbeiträge

1. Hauptsatz: Beweis, dass für induzierte $K_r^{[2]}$-freie Graphen $G$ mit mindestens $c\binom{n}{r}$ Kopien von $K_r$ gilt: $ω(G) ≥ \frac{c}{18r}n$ (Satz 1.5)
2. Verbesserung der Schranke: Verbesserung von Holmsens $Ω(c^{2^{r-1}}n)$-Schranke zu $Ω(cn)$, was lineare Abhängigkeit von $c$ erreicht
3. Beschränkte verbotene Strukturen: Nur das Verbot von höchstens $2^{\binom{r}{2}}$ induzierten Substrukturen erforderlich (im Vergleich zu unendlich vielen bei Chordalgraphen)
4. VC-Dimension-Methode: Etablierung einer natürlichen Verbindung zwischen halbinduzierten Subgraphen und VC-Dimension, Verallgemeinerung der bestehenden Theorie doppelt-induzierter Subgraphen
5. Strukturelle Einsichten: Offenbarung, dass selbst bei Verbot von weit weniger Strukturen als bei Chordalgraphen lineare Cliquengröße garantiert ist

Methodische Details

Aufgabendefinition

Eingabe: $n$-Knoten-Graph $G$, der erfüllt:

• Enthält mindestens $c\binom{n}{r}$ Kopien von $K_r$ ($c > 0$ ist eine Konstante)
• Ist induziert $K_r^{[2]}$-frei (enthält keinen Graph aus $K_r^{[2]}$ als induzierten Subgraph)

Ausgabe: Beweis, dass $G$ eine Clique der Ordnung mindestens $\frac{c}{18r}n$ enthält

Schlüsseldefinitionen:

• $K_r[2]$: Die 2-Erweiterung von $K_r$, wobei jeder Knoten durch eine unabhängige Menge der Größe 2 ersetzt wird
• $K_r^{[2]}$: Die Familie von Subgraphen von $K_r[2]$, deren Kantenmenge die Form $(E(K_r[2])\backslash E(K_{U'})) \cup E'$ hat, wobei $U' = \{u'_1, \ldots, u'_r\}$ die zweite Knotenmenge jedes Teils ist und $E' \subseteq E(K_{U'})$

Kernarchitektur

Der Beweis wird in drei Schlüsselschritte unterteilt:

1. VC-Dimension-Schranke (Claim 2.3)

Kernlemma: Die VC-Dimension der Familie maximaler Cliquen $MC(G)$ eines induzierten $K_r^{[2]}$-freien Graphen ist höchstens $r-1$.

Beweisskizze:

• Annahme: Es existiert eine Menge $S = \{u_1, \ldots, u_r\}$ der Größe $r$, die von $MC(G)$ zerschlagen wird
• Für jedes $i \in [r]$ existiert eine maximale Clique $K_i$ mit $K_i \cap S = S \backslash \{u_i\}$
• Nach Maximalität existiert $u'_i \in K_i \backslash S$ mit $u_i u'_i \notin E(G)$
• Dann induziert $\{u_1, u'_1, \ldots, u_r, u'_r\}$ einen bestimmten Graph aus $K_r^{[2]}$, Widerspruch

2. Anwendung des Sauer-Shelah-Lemmas

Für ein Mengensystem $\mathcal{F}$ mit VC-Dimension $k$ gilt für jede Menge $S$ der Größe $m$: $|\mathcal{F}|_S| \leq \sum_{i=0}^{k} \binom{m}{i}$

Für diesen Fall mit $k = r-1$ und Wahl von $m = \lfloor\frac{9r}{c}\rfloor$ erhalten wir: $|MC(G)|_{S_m}| \leq \sum_{i=0}^{r-1} \binom{m}{i} < \frac{1}{4}c\binom{m}{r}$

3. Probabilistisches Argument

Beweis durch Widerspruch: Annahme $ω(G) < c'n$, wobei $c' = \frac{c}{18r}$

Zufällige Auswahl: Wähle zufällig $S_r \subseteq S_m$, wobei $|S_r| = r$, $|S_m| = m$

Wahrscheinlichkeitsanalyse:

• Die Wahrscheinlichkeit, dass $S_r$ eine Clique induziert, ist mindestens $c$
• Wenn $S_r$ eine Clique induziert und in einer maximalen Clique $K$ der Größe $< c'n$ enthalten ist, dann ist die Wahrscheinlichkeit, dass $S_m$ $S_r$ enthält, aber $S_m \backslash S_r$ keinen Knoten aus $K$ enthält, mindestens: $\frac{\binom{n-c'n}{m-r}}{\binom{n-r}{m-r}} \geq \left(\frac{n-c'n-m}{n-m}\right)^m \geq e^{-2c'm} \geq \frac{1}{4}$
• Daher ist die Wahrscheinlichkeit, dass $S_r = S_m \cap K$ mindestens $\frac{1}{4}c$
• Die erwartete Anzahl von $S_r$, die die Bedingungen erfüllen, ist mindestens $\frac{1}{4}c\binom{m}{r}$

Widerspruch: Dies widerspricht der oberen Schranke aus dem Sauer-Shelah-Lemma.

Technische Innovationen

1. Einführung halbinduzierter Strukturen: Die Familie $K_r^{[2]}$ balanciert geschickt die Stärke der Strukturbeschränkung mit ihrer Anzahl und bietet sowohl ausreichende Einschränkung als auch beschränkte verbotene Strukturen
2. Natürliche Verbindung zur VC-Dimension: Direkte Verknüpfung der VC-Dimension des Systems maximaler Cliquen mit den induzierten Substrukturen des Graphen, was neue analytische Perspektiven bietet
3. Verfeinerte Wahrscheinlichkeitsschätzungen: Unter dem Rahmen zufälliger Auswahl wird durch sorgfältige probabilistische Berechnungen eine quantitative Beziehung zwischen Cliquendichte und Cliquengröße etabliert
4. Parameteroptimierung: Die Wahl von $m = \lfloor\frac{9r}{c}\rfloor$ führt dazu, dass die Sauer-Shelah-Schranke und die probabilistische Untergrenze genau einen Widerspruch erzeugen

Experimentelle Einrichtung

Dieses Papier ist ein rein theoretisches mathematisches Papier ohne experimentelle Verifikation. Alle Ergebnisse werden durch strenge mathematische Beweise erhalten.

Theoretische Verifikation

• Extremale Beispiele: Für den Fall $r=2$ zeigt das Papier, dass induzierte $K_2^{[2]}$-freie Graphen (die induzierten $P_4$ und $K_{2,2}$ verbieten) eine Unterklasse von Chordalgraphen bilden
• Engheitsanalyse: Obwohl keine exakte extremale Konstruktion gegeben wird, wird gezeigt, dass die Größenordnung der Schranke angemessen ist

Experimentelle Ergebnisse

Haupttheoretische Ergebnisse

Satz 1.5 (Hauptergebnis): Sei $r ≥ 2$, $0 < c < 1$, und $G$ ein $n$-Knoten-Graph mit mindestens $c\binom{n}{r}$ Kopien von $K_r$. Wenn $G$ induziert $K_r^{[2]}$-frei ist, dann gilt für hinreichend großes $n$: $ω(G) ≥ \frac{c}{18r}n$

Vergleich mit bestehenden Ergebnissen

Schlüsselverbesserungen

1. Exponentiell zu linear: Abhängigkeit von $c$ verbessert sich von $c^{2^{r-1}}$ zu $c/r$
   • Wenn $r=3$: von $c^4$ zu $c/3$
   • Wenn $r=5$: von $c^{16}$ zu $c/5$
2. Beschränkte Strukturanzahl: Nur $2^{\binom{r}{2}}$ Strukturen erforderlich
   • $r=2$: 2 Strukturen
   • $r=3$: 8 Strukturen
   • $r=4$: 64 Strukturen
3. Optimalität: Für $r=2$ stimmt das Ergebnis dieses Papiers mit der Chordalgraphen-Schranke in der Größenordnung überein (beide $Ω(cn)$), verbietet aber weniger Strukturen

Verwandte Arbeiten

Klassische Extremalgraphtheorie

1. Turán-Satz (1941): Bestimmt den exakten Wert von $ex(n, K_k)$ und den Extremalgraphen
2. Erdős-Stone-Simonovits-Satz (1946, 1966): $ex(n,H) = \left(1 - \frac{1}{χ(H)-1}\right)\binom{n}{2} + o(n^2)$
   • Für nicht-bipartite Graphen $H$ wird das asymptotische Verhalten vollständig gelöst
   • Für bipartite Graphen wird nur $ex(n,H) = o(n^2)$ gegeben

Extremaltheorie induzierter Subgraphen

3. Gyárfás-Hubenko-Solymosi (2002):
   • Induziert $K_{2,2}$-freie Graphen: $ω(G) ≥ \frac{c^2}{10}n$
   • $C_4$-freie Graphen (Chordalgraphen): $ω(G) ≥ (1-\sqrt{1-c})n$
4. Abbott-Katchalski (1979): Unabhängiger Beweis der engen Schranke für Chordalgraphen
5. Loh et al. (2018): Verallgemeinerung auf induziert $K_{2,t}$-freie Graphen
6. Holmsen (2020):
   • Verallgemeinerung auf Hypergraphen und Mehrteile-Versionen
   • Beweis, dass abstraktes colorful Helly abstraktes fractional Helly impliziert
   • Dieses Papier verbessert direkt Holmsens graphentheoretisches Ergebnis

Anwendungen der VC-Dimension in der Graphtheorie

7. Nguyen-Scott-Seymour (2025): Etablierung der Verbindung zwischen doppelt-induzierter Subgraph-Dichte und VC-Dimension
8. Sauer (1972), Shelah (1972): Unabhängiger Beweis der fundamentalen VC-Dimension-Schranke (Sauer-Shelah-Lemma)

Positionierung dieses Papiers

Basierend auf Holmsens Arbeit erreicht dieses Papier durch die Einführung halbinduzierter Substrukturen und der VC-Dimension-Methode eine quantitative Verbesserung. Die Verbindung zur Chordalgraphen-Theorie bietet eine natürliche Erklärung für den Fall $r=2$.

Schlussfolgerungen und Diskussion

Hauptschlussfolgerungen

1. Quantitative Verbesserung: Durch das Verbot der Familie $K_r^{[2]}$ (höchstens $2^{\binom{r}{2}}$ Strukturen) wird die Cliquenschranke von $Ω(c^{2^{r-1}}n)$ zu $Ω(cn)$ verbessert
2. Methodologischer Beitrag: Etablierung einer natürlichen Verbindung zwischen halbinduzierten Subgraphen und VC-Dimension, Verallgemeinerung des bestehenden theoretischen Rahmens
3. Strukturelle Einsichten: Offenbarung, dass endliche Strukturverbote ausreichen, um lineare Cliquengröße zu garantieren, ohne wie bei Chordalgraphen unendlich viele Strukturen zu verbieten

Einschränkungen

1. Konstante Faktoren: Die Konstante $\frac{1}{18r}$ in der Schranke ist möglicherweise nicht optimal; das Papier diskutiert ihre Engheit nicht
2. Anzahl verbotener Strukturen: Obwohl beschränkt, wächst $2^{\binom{r}{2}}$ exponentiell mit $r$; für größere $r$ sind es immer noch viele
3. Fehlende extremale Konstruktionen: Das Papier bietet keine extremalen Graphkonstruktionen, die die Untergrenze erreichen
4. Asymptotische Eigenschaften: Ergebnisse erfordern hinreichend großes $n$; konkrete Schwellenwerte werden nicht angegeben

Zukünftige Richtungen

Das Papier stellt in der Schlussfolgerung explizit offene Probleme dar:

Kernfrage: Wann findet der Übergang von $c^{2^{r-1}}$ zu linearer Abhängigkeit von $c$ statt? Präziser: Wie viele verbotene Strukturen sind minimal erforderlich, um eine lineare Schranke in $c$ zu erzwingen?

Mögliche Forschungsrichtungen:

1. Bestimmung der minimalen Familie verbotener Strukturen zur Erreichung der linearen Schranke
2. Verbesserung der Konstante $\frac{1}{18r}$
3. Konstruktion extremaler Beispiele oder Beweis der Engheit der Schranke
4. Verallgemeinerung auf Hypergraphen
5. Erforschung anderer halbinduzierter Strukturverbote

Tiefgreifende Bewertung

Stärken

1. Wichtige quantitative Verbesserung:
   • Verbesserung von exponentieller zu linearer Abhängigkeit ist substantieller Fortschritt
   • Wichtig für Anwendungen (wie abstrakte Helly-Sätze)
2. Elegante Beweistechniken:
   • VC-Dimension-Methode bietet einheitlichen Analyserahmen
   • Probabilistisches Argument ist prägnant und kraftvoll
   • Beweis ist vollständig in sich geschlossen und benötigt nur grundlegende Werkzeuge
3. Konzeptionelle Innovation:
   • Definition der Familie $K_r^{[2]}$ balanciert geschickt Einschränkungsstärke und -anzahl
   • Einführung halbinduzierter Strukturen ist natürliche Verallgemeinerung
4. Klare Darstellung:
   • Ausreichende Motivationserläuterung
   • Vollständige technische Details
   • Klare Beziehung zu bestehenden Arbeiten
5. Theoretische Tiefe:
   • Offenbarung der tieferen Struktur der Theorie induzierter Subgraphen
   • Verbindung mehrerer mathematischer Zweige (Extremalgraphtheorie, VC-Dimension-Theorie, kombinatorische Geometrie)

Schwächen

1. Konstanten-Optimierung:
   • Die Konstante $\frac{1}{18r}$ könnte feiner sein
   • Engheit der Schranke oder Konstruktion einer passenden Obergrenze wird nicht diskutiert
2. Abhängigkeit der Strukturanzahl:
   • $2^{\binom{r}{2}}$ wächst immer noch schnell mit $r$
   • Nicht untersucht, ob ähnliche Ergebnisse mit weniger verbotenen Strukturen erreicht werden können
3. Fehlende konkrete Schwellenwerte:
   • "Hinreichend großes $n$" wird nicht quantifiziert
   • Könnte praktische Anwendungen beeinflussen
4. Unzureichende Verallgemeinerungsdiskussion:
   • Nicht diskutiert, ob die Methode auf andere verbotene Strukturen anwendbar ist
   • Verbindung zum Hypergraph-Fall wird nur in der Einleitung erwähnt
5. Mangelnde Spezifität offener Probleme:
   • Obwohl wichtige Fragen gestellt werden, werden keine Vermutungen oder Teilergebnisse gegeben

Einflussreichkeits-Bewertung

Theoretischer Einfluss:

• Bietet neue Werkzeuge für Extremaltheorie induzierter Subgraphen
• VC-Dimension-Methode könnte weitere Anwendungen inspirieren
• Direkter Beitrag zur Forschung abstrakter Helly-Sätze

Praktischer Wert:

• Hauptsächlich theoretischer Natur
• Mögliche Anwendungen in algorithmischer Graphtheorie und Computergeometrie

Reproduzierbarkeit:

• Beweis vollständig verifizierbar
• Keine Computerexperimente erforderlich

Potentieller Zitationswert:

• Erwartet hohe Zitationen im Bereich Extremale Kombinatorik
• Könnte Standard-Referenz in diesem Forschungsbereich werden

Anwendungsszenarien

1. Theoretische Forschung:
   • Probleme mit verbotenen induzierten Subgraphen in der Extremalgraphtheorie
   • Anwendungen der VC-Dimension in kombinatorischen Strukturen
   • Abstrakte Helly-Sätze und ihre Verallgemeinerungen
2. Verwandte Probleme:
   • Forschung zu anderen halbinduzierten Strukturen
   • Beziehungen zwischen Cliquenzahl und anderen Graphparametern
   • Clique-Strukturen in Zufallsgraphen
3. Potentielle Anwendungen:
   • Algorithmendesign (unter Ausnutzung von Struktureigenschaften)
   • Rechenkomplexitätstheorie
   • Kombinatorische Optimierungsprobleme

Literaturverzeichnis

Das Papier zitiert die folgenden Schlüsselwerke:

1. Abbott & Katchalski (1979): Turán-Typ-Probleme für Intervallgraphen
2. Erdős & Simonovits (1966), Erdős & Stone (1946): ESS-Satz
3. Gyárfás, Hubenko & Solymosi (2002): Große Cliquen in $C_4$-freien Graphen
4. Holmsen (2020): Große Cliquen in Hypergraphen mit verbotenen Substrukturen (direkt verbessertes Werk)
5. Loh et al. (2018): Induzierte Turán-Zahlen
6. Nguyen, Scott & Seymour (2025): Induzierte Subgraph-Dichte und VC-Dimension
7. Sauer (1972), Shelah (1972): Fundamentale VC-Dimension-Schranken
8. Turán (1941): Klassischer Turán-Satz

Gesamtbewertung: Dies ist ein hochqualitatives kombinatorisches Mathematik-Papier, das substantielle Fortschritte bei einem wichtigen Problem der Extremalgraphtheorie erzielt. Durch die Einführung halbinduzierter Strukturen und der VC-Dimension-Methode gelang es den Autoren, Holmsens exponentielle Schranke zu einer linearen Schranke zu verbessern, während die Beschränktheit der Strukturanzahl erhalten bleibt. Die Beweistechniken sind elegant und aufschlussreich und bieten neue Forschungswerkzeuge und Richtungen für das Feld. Der Hauptbeitrag liegt auf theoretischer Ebene, aber die Methoden und Ideen könnten weitreichende Auswirkungen auf verwandte Bereiche haben.