Grandi clique in grafi con strutture semi-indotte proibite

Informazioni di base

• ID articolo: 2511.13073
• Titolo: Large cliques in graphs with forbidden semi-induced structures
• Autori: Nannan Chen (Shandong University & IBS), Yulai Ma (Nankai University), Fan Yang (Shandong University & IBS)
• Classificazione: math.CO (Combinatoria)
• Data di presentazione: 17 novembre 2025
• Link articolo: https://arxiv.org/abs/2511.13073

Riassunto

Questo articolo studia l'esistenza di grandi clique in grafi con strutture semi-indotte proibite. Holmsen ha dimostrato nel 2022 che qualsiasi grafo contenente almeno $c\binom{n}{r}$ clique di $r$ elementi ma non contenente il grafo completo $r$-partito indotto $K_{2,\ldots,2}$ deve contenere una clique di ordine $Ω(c^{2^{r-1}}n)$. Questo articolo, proibendo strutture semi-indotte correlate a $K_{2,\ldots,2}$, dimostra che ogni grafo $G$ su $n$ vertici contenente almeno $c\binom{n}{r}$ copie di $K_r$ deve contenere una clique di ordine $Ω(cn)$. Questo risultato migliora la dipendenza da $c$ nel limite di Holmsen da $c^{2^{r-1}}$ a lineare in $c$, richiedendo solo di proibire una quantità limitata di strutture. Inoltre, questo metodo si collega naturalmente al concetto di dimensione VC.

Contesto di ricerca e motivazione

Sfondo del problema

1. Teoria classica di Turán: Il teorema di Turán e le sue generalizzazioni (teorema di Erdős-Stone-Simonovits) studiano problemi estremali con sottografi non indotti proibiti. Per grafi $H$ con numero cromatico $χ(H) ≥ 3$, proibire $H$ come sottografo rende il grafo estremale asintoticamente $(χ(H)-1)$-partito, limitando così il numero di clique da una costante.
2. Caso di sottografi indotti: Quando si proibiscono sottografi indotti, la situazione è completamente diversa. Gyárfás, Hubenko e Solymosi (2002) hanno dimostrato che se un grafo $G$ su $n$ vertici ha almeno $c\binom{n}{2}$ spigoli e non contiene $K_{2,2}$ indotto, allora $ω(G) ≥ \frac{c^2}{10}n$.
3. Limiti stretti per grafi cordali: I grafi cordali (proibendo cicli indotti di lunghezza almeno 4) raggiungono limiti migliori: $ω(G) ≥ (1-\sqrt{1-c})n$, che è $Ω(cn)$ quando $c$ è piccolo.
4. Generalizzazione di Holmsen: Holmsen (2020) ha generalizzato il caso $K_{2,2}$ alla versione multipartita, dimostrando che grafi proibendo $K_r[2]$ indotto (l'espansione 2 di $K_r$) contengono una clique di ordine $Ω(c^{2^{r-1}}n)$.

Motivazione della ricerca

Sebbene il risultato di Holmsen sia lineare in $n$, il suo limite in $c$ si deteriora rapidamente con l'aumentare di $r$. La questione centrale di questo articolo è: È possibile, in modo simile al miglioramento dal Teorema 1.1 al Teorema 1.2, migliorare il limite di Holmsen proibendo più strutture (ma in quantità limitata)?

Importanza

• Questo problema collega la teoria estremale dei grafi ai teoremi astratti di Helly
• Ha importanza fondamentale per comprendere la relazione tra condizioni di proibizione di sottografi indotti e il numero di clique
• Rivela il ruolo della dimensione VC nelle strutture grafiche

Contributi principali

1. Teorema principale: Dimostra che per grafi $G$ indotto $K_r^{[2]}$-free contenenti almeno $c\binom{n}{r}$ copie di $K_r$, si ha $ω(G) ≥ \frac{c}{18r}n$ (Teorema 1.5)
2. Miglioramento dei limiti: Migliora il limite di Holmsen da $Ω(c^{2^{r-1}}n)$ a $Ω(cn)$, realizzando una dipendenza lineare da $c$
3. Strutture proibite limitate: Richiede solo di proibire al massimo $2^{\binom{r}{2}}$ strutture indotte (rispetto alle infinite dei grafi cordali)
4. Metodo della dimensione VC: Stabilisce un collegamento naturale tra sottografi semi-indotti e dimensione VC, generalizzando la teoria dei sottografi doppiamente indotti esistente
5. Intuizioni strutturali: Rivela che anche proibendo significativamente meno strutture rispetto ai grafi cordali, si garantisce comunque una clique di dimensione lineare

Spiegazione dettagliata del metodo

Definizione del compito

Input: Grafo $G$ su $n$ vertici, soddisfacente:

• Contiene almeno $c\binom{n}{r}$ copie di $K_r$ ($c > 0$ costante)
• È indotto $K_r^{[2]}$-free (non contiene alcun grafo da $K_r^{[2]}$ come sottografo indotto)

Output: Dimostrare che $G$ contiene una clique di ordine almeno $\frac{c}{18r}n$

Definizioni chiave:

• $K_r[2]$: L'espansione 2 di $K_r$, sostituendo ogni vertice con un insieme indipendente di dimensione 2
• $K_r^{[2]}$: La famiglia di sottografi di $K_r[2]$ con insieme di spigoli della forma $(E(K_r[2])\backslash E(K_{U'})) \cup E'$, dove $U' = \{u'_1, \ldots, u'_r\}$ è il secondo insieme di vertici di ogni parte, $E' \subseteq E(K_{U'})$

Architettura principale

La dimostrazione si articola in tre passaggi chiave:

1. Limite della dimensione VC (Claim 2.3)

Lemma centrale: L'insieme delle clique massimali $MC(G)$ di un grafo indotto $K_r^{[2]}$-free ha dimensione VC al massimo $r-1$.

Idea della dimostrazione:

• Supponiamo esista un insieme di dimensione $r$, $S = \{u_1, \ldots, u_r\}$, frantumato da $MC(G)$
• Per ogni $i \in [r]$, esiste una clique massimale $K_i$ tale che $K_i \cap S = S \backslash \{u_i\}$
• Per massimalità, esiste $u'_i \in K_i \backslash S$ tale che $u_i u'_i \notin E(G)$
• Allora $\{u_1, u'_1, \ldots, u_r, u'_r\}$ induce un certo grafo da $K_r^{[2]}$, contraddizione

2. Applicazione del lemma di Sauer-Shelah

Per un sistema di insiemi $\mathcal{F}$ con dimensione VC $k$, qualsiasi insieme di dimensione $m$ soddisfa: $|\mathcal{F}|_S| \leq \sum_{i=0}^{k} \binom{m}{i}$

Nel nostro caso, $k = r-1$, scegliendo $m = \lfloor\frac{9r}{c}\rfloor$, otteniamo: $|MC(G)|_{S_m}| \leq \sum_{i=0}^{r-1} \binom{m}{i} < \frac{1}{4}c\binom{m}{r}$

3. Argomento probabilistico

Prova per contraddizione: Supponiamo $ω(G) < c'n$, dove $c' = \frac{c}{18r}$

Scelta casuale: Selezioniamo casualmente $S_r \subseteq S_m$, dove $|S_r| = r$, $|S_m| = m$

Analisi probabilistica:

• La probabilità che $S_r$ induca una clique è almeno $c$
• Se $S_r$ induce una clique e è contenuta in una clique massimale di dimensione $< c'n$, allora la probabilità che $S_m$ contenga $S_r$ ma $S_m \backslash S_r$ non contenga alcun vertice dalla clique è almeno: $\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}$
• Quindi la probabilità che $S_r = S_m \cap K$ esiste è almeno $\frac{1}{4}c$
• Il numero atteso di $S_r$ soddisfacenti le condizioni è almeno $\frac{1}{4}c\binom{m}{r}$

Contraddizione: Questo contraddice il limite superiore dal lemma di Sauer-Shelah.

Punti di innovazione tecnica

1. Introduzione di strutture semi-indotte: La famiglia $K_r^{[2]}$ bilancia abilmente l'intensità della limitazione strutturale con la quantità, garantendo sia vincoli sufficienti che un numero limitato di strutture proibite
2. Collegamento naturale con la dimensione VC: Associa direttamente la dimensione VC del sistema di clique massimali alle strutture indotte proibite del grafo, fornendo una nuova prospettiva analitica
3. Stime probabilistiche raffinate: Nel quadro della selezione casuale, stabilisce relazioni quantitative tra la densità di clique e la dimensione della clique attraverso calcoli probabilistici accurati
4. Ottimizzazione dei parametri: La scelta di $m = \lfloor\frac{9r}{c}\rfloor$ fa sì che il limite di Sauer-Shelah e il limite probabilistico inferiore producano esattamente una contraddizione

Configurazione sperimentale

Questo articolo è un articolo di matematica pura teorica e non comporta verifiche sperimentali. Tutti i risultati sono ottenuti attraverso dimostrazioni matematiche rigorose.

Verifica teorica

• Esempi estremali: Per il caso $r=2$, l'articolo osserva che i grafi indotto $K_2^{[2]}$-free (proibendo $P_4$ e $K_{2,2}$ indotti) formano una sottoclasse dei grafi cordali
• Analisi della stretta: Sebbene non fornisca costruzioni estremali precise, si dimostra che l'ordine di grandezza dei limiti è ragionevole

Risultati sperimentali

Risultati teorici principali

Teorema 1.5 (Risultato principale): Sia $r ≥ 2$, $0 < c < 1$, e $G$ un grafo su $n$ vertici contenente almeno $c\binom{n}{r}$ copie di $K_r$. Se $G$ è indotto $K_r^{[2]}$-free, allora per $n$ sufficientemente grande, $ω(G) ≥ \frac{c}{18r}n$

Confronto con risultati esistenti

Miglioramenti chiave

1. Da esponenziale a lineare: La dipendenza da $c$ migliora da $c^{2^{r-1}}$ a $c/r$
   • Quando $r=3$: da $c^4$ a $c/3$
   • Quando $r=5$: da $c^{16}$ a $c/5$
2. Numero limitato di strutture: Solo $2^{\binom{r}{2}}$ strutture da proibire
   • $r=2$: 2 strutture
   • $r=3$: 8 strutture
   • $r=4$: 64 strutture
3. Ottimalità: Per $r=2$, il risultato di questo articolo è coerente in ordine di grandezza con il limite dei grafi cordali (entrambi $Ω(cn)$), ma proibisce meno strutture

Lavori correlati

Teoria estremale dei grafi classica

1. Teorema di Turán (1941): Determina il valore esatto di $ex(n, K_k)$ e il grafo estremale
2. Teorema di Erdős-Stone-Simonovits (1946, 1966): $ex(n,H) = \left(1 - \frac{1}{χ(H)-1}\right)\binom{n}{2} + o(n^2)$
   • Per grafi non bipartiti $H$, risolve completamente il comportamento asintotico
   • Per grafi bipartiti, fornisce solo $ex(n,H) = o(n^2)$

Teoria estremale dei sottografi indotti

3. Gyárfás-Hubenko-Solymosi (2002):
   • Grafi $K_{2,2}$ indotto-free: $ω(G) ≥ \frac{c^2}{10}n$
   • Grafi $C_4$-free (grafi cordali): $ω(G) ≥ (1-\sqrt{1-c})n$
4. Abbott-Katchalski (1979): Dimostrazione indipendente del limite stretto per grafi cordali
5. Loh et al. (2018): Generalizzazione a grafi $K_{2,t}$ indotto-free
6. Holmsen (2020):
   • Generalizzazione a ipergrafi e versioni multipartite
   • Dimostra che Helly colorato astratto implica Helly frazionario astratto
   • Questo articolo migliora direttamente il risultato di Holmsen sulla teoria dei grafi

Applicazioni della dimensione VC nella teoria dei grafi

7. Nguyen-Scott-Seymour (2025): Stabilisce il collegamento tra densità di sottografi doppiamente indotti e dimensione VC
8. Sauer (1972), Shelah (1972): Dimostrazione indipendente del limite fondamentale della dimensione VC (lemma di Sauer-Shelah)

Posizionamento di questo articolo

Questo articolo, basandosi sul lavoro di Holmsen, realizza miglioramenti quantitativi introducendo strutture semi-indotte e il metodo della dimensione VC. Il collegamento con la teoria dei grafi cordali fornisce una spiegazione naturale per il caso $r=2$.

Conclusioni e discussione

Conclusioni principali

1. Miglioramento quantitativo: Proibendo la famiglia $K_r^{[2]}$ (al massimo $2^{\binom{r}{2}}$ strutture), migliora il limite inferiore della clique da $Ω(c^{2^{r-1}}n)$ a $Ω(cn)$
2. Contributo metodologico: Stabilisce un collegamento naturale tra sottografi semi-indotti e dimensione VC, generalizzando il quadro teorico esistente
3. Intuizioni strutturali: Rivela che condizioni di proibizione di strutture finite sono sufficienti per garantire una clique di dimensione lineare, senza necessità di proibire infinite strutture come nei grafi cordali

Limitazioni

1. Fattori costanti: La costante $\frac{1}{18r}$ nel limite potrebbe non essere ottimale, e l'articolo non discute la sua stretta
2. Numero di strutture proibite: Sebbene limitato, $2^{\binom{r}{2}}$ cresce esponenzialmente con $r$, rimanendo numeroso per $r$ grande
3. Mancanza di costruzioni estremali: L'articolo non fornisce costruzioni di grafi estremali che raggiungono il limite inferiore
4. Proprietà asintotiche: I risultati richiedono $n$ sufficientemente grande, senza specificare la soglia esatta

Direzioni future

L'articolo identifica chiaramente problemi aperti nella sezione conclusiva:

Problema centrale: Quando avviene la transizione da $c^{2^{r-1}}$ a dipendenza lineare in $c$? Più precisamente, qual è il numero minimo di strutture proibite necessario per forzare un limite lineare in $c$?

Possibili direzioni di ricerca:

1. Determinare la famiglia minima di strutture proibite per raggiungere il limite lineare
2. Migliorare il fattore costante $\frac{1}{18r}$
3. Costruire esempi estremali o provare la stretta dei limiti
4. Generalizzare a ipergrafi
5. Esplorare altre condizioni di proibizione di strutture semi-indotte

Valutazione approfondita

Punti di forza

1. Miglioramento quantitativo significativo:
   • Il miglioramento da dipendenza esponenziale a lineare rappresenta un progresso sostanziale
   • Ha importanza significativa per le applicazioni (come i teoremi astratti di Helly)
2. Tecniche di dimostrazione eleganti:
   • Il metodo della dimensione VC fornisce un quadro analitico unificato
   • L'argomento probabilistico è conciso e potente
   • La dimostrazione è completamente autosufficiente, dipendendo solo da strumenti fondamentali
3. Innovazione concettuale:
   • La definizione della famiglia $K_r^{[2]}$ bilancia abilmente l'intensità dei vincoli e la quantità
   • L'introduzione di strutture semi-indotte è una generalizzazione naturale
4. Chiarezza della presentazione:
   • La motivazione è ampiamente illustrata
   • I dettagli tecnici sono completi
   • Le relazioni con i lavori esistenti sono esplicite
5. Profondità teorica:
   • Rivela la struttura profonda della teoria dei sottografi indotti
   • Collega più rami della matematica (teoria estremale dei grafi, teoria della dimensione VC, geometria combinatoria)

Insufficienze

1. Ottimizzazione delle costanti:
   • La costante $\frac{1}{18r}$ potrebbe non essere sufficientemente raffinata
   • Non discute la stretta dei limiti o fornisce costruzioni di limiti superiori corrispondenti
2. Dipendenza dal numero di strutture:
   • $2^{\binom{r}{2}}$ cresce ancora rapidamente con $r$
   • Non esplora se risultati simili possono essere raggiunti con meno strutture proibite
3. Mancanza di soglie concrete:
   • "$n$ sufficientemente grande" non è quantificato
   • Potrebbe avere implicazioni per le applicazioni pratiche
4. Discussione insufficiente sulla generalizzabilità:
   • Non discute se il metodo può applicarsi ad altre strutture proibite
   • Il collegamento con il caso degli ipergrafi è solo menzionato nell'introduzione
5. Specificità dei problemi aperti:
   • Sebbene pone importanti questioni, non fornisce congetture o risultati parziali

Valutazione dell'impatto

Impatto teorico:

• Fornisce nuovi strumenti per la teoria estremale dei sottografi indotti
• Il metodo della dimensione VC potrebbe ispirare ulteriori applicazioni
• Contribuisce direttamente alla ricerca sui teoremi astratti di Helly

Valore pratico:

• Principalmente di natura teorica
• Potrebbe trovare applicazioni nella teoria dei grafi algoritmici e nella geometria computazionale

Riproducibilità:

• La dimostrazione è completamente verificabile
• Non comporta esperimenti computazionali

Valore di citazione potenziale:

• Previsto di avere elevate citazioni nel campo della combinatoria estremale
• Potrebbe diventare un riferimento standard in questo ambito

Scenari applicabili

1. Ricerca teorica:
   • Problemi di sottografi indotti proibiti nella teoria estremale dei grafi
   • Applicazioni della dimensione VC in strutture combinatorie
   • Teoremi astratti di Helly e loro generalizzazioni
2. Problemi correlati:
   • Ricerca su altre strutture semi-indotte
   • Relazioni tra il numero di clique e altri parametri grafici
   • Strutture di clique in grafi casuali
3. Applicazioni potenziali:
   • Progettazione di algoritmi (sfruttando proprietà strutturali)
   • Teoria della complessità computazionale
   • Problemi di ottimizzazione combinatoria

Bibliografia

L'articolo cita le seguenti opere fondamentali:

1. Abbott & Katchalski (1979): Problemi di tipo Turán per grafi di intervalli
2. Erdős & Simonovits (1966), Erdős & Stone (1946): Teorema ESS
3. Gyárfás, Hubenko & Solymosi (2002): Grandi clique in grafi $C_4$-free
4. Holmsen (2020): Grandi clique in ipergrafi con sottostrutture proibite (lavoro direttamente migliorato da questo articolo)
5. Loh et al. (2018): Numeri di Turán indotti
6. Nguyen, Scott & Seymour (2025): Densità di sottografi indotti e dimensione VC
7. Sauer (1972), Shelah (1972): Limiti fondamentali della dimensione VC
8. Turán (1941): Teorema classico di Turán

Valutazione complessiva: Questo è un articolo di alta qualità in matematica combinatoria che realizza progressi sostanziali su un importante problema nella teoria estremale dei grafi. Introducendo strutture semi-indotte e il metodo della dimensione VC, gli autori migliorano con successo il limite esponenziale di Holmsen a un limite lineare, mantenendo al contempo la limitatezza del numero di strutture proibite. Le tecniche di dimostrazione sono eleganti e ricche di intuizioni, fornendo nuovi strumenti e direzioni di ricerca per il campo. Il contributo principale è di natura teorica, ma i metodi e le idee potrebbero avere un ampio impatto su aree correlate.