Numero di Turán bipartito di cammini e altri alberi

Informazioni di base

• ID articolo: 2511.07374
• Titolo: Bipartite Turán number of paths and other trees
• Autori: Marthe Bonamy, Théotime Leclere, Timothé Picavet
• Istituzioni: CNRS, LaBRI, Université de Bordeaux; ENS Paris-Saclay
• Classificazione: math.CO (Matematica combinatoria), cs.DM (Matematica discreta)
• Data di pubblicazione: 11 novembre 2025
• Link articolo: https://arxiv.org/abs/2511.07374

Riassunto

Questo articolo risolve completamente un problema recentemente proposto da Caro, Patkós e Tuza: determinare il valore massimo esatto del numero di spigoli in grafi bipartiti connessi, valore che è una funzione della lunghezza del cammino più lungo nel grafo e del numero di vertici su ciascun lato della bipartizione. Precedentemente questo problema era noto solo nel caso di bipartizione equilibrata e lunghezza del cammino più lungo al massimo 5. L'articolo discute inoltre possibili generalizzazioni sostituendo "cammini" con specifici tipi di alberi.

Contesto di ricerca e motivazione

Contesto del problema

1. Problema classico di Turán: Il teorema di Turán determina il numero massimo di spigoli in un grafo con n vertici che non contiene un sottografo completo di ordine fissato, inaugurando lo studio sistematico dei problemi di estremalità con sottografi proibiti.
2. Limitazioni del teorema di Erdős-Stone: Questo teorema fornisce asintoticamente il numero di Turán per tutti i grafi proibiti non bipartiti, ma non fornisce alcuna informazione nel caso di grafi bipartiti.
3. Particolarità dei grafi bipartiti: Il problema di Turán per grafi bipartiti rimane aperto, generando diverse congetture fondamentali, la più celebre delle quali è la congettura di Erdős-Sós: un grafo con n vertici che esclude un albero di k vertici ha al massimo (k-2)n/2 spigoli.
4. Studio di grafi bipartiti connessi: Caro, Patkós e Tuza CPT25 hanno recentemente considerato il caso in cui il grafo ospite è sia bipartito che connesso, introducendo la notazione exb,c(a,b,H) per indicare il numero massimo di spigoli in un grafo bipartito connesso con parti di dimensione a e b che non contiene H come sottografo.

Motivazione della ricerca

• Limitazioni dei risultati noti: CPT25 ha risolto solo il caso di tutti gli alberi con 6 o meno vertici, stelle doppie e alcuni grafi ragno, in particolare si conosce solo exb,c(n,n,P₅) = exb,c(n,n,P₆) = 2n-1
• Problema aperto: È necessario determinare exb,c(n,n,Pₖ) per cammini arbitrari Pₖ, almeno fornendo valori asintotici
• Esigenza di generalizzazione: È necessario studiare i valori di exb,c per specifiche famiglie di alberi

Contributi principali

1. Risoluzione completa del problema dei cammini: Per tutti i cammini Pₖ, fornisce i valori esatti di exb,c(a,b,Pₖ), non solo valori asintotici, ma applicabili anche a grafi bipartiti non equilibrati (Teorema principale 1.5)
2. Estensione ai grafi scopa: Per i grafi scopa Sp,d* (combinazione di un cammino di lunghezza p e una stella con d rami), fornisce valori esatti quando la stella è più grande del cammino (Teorema 1.6)
3. Risultati di limitazione superiore: Quando la stella è al massimo la metà della dimensione del cammino, fornisce limitazioni superiori (Teorema 1.7)
4. Innovazione tecnica: Sviluppa nuove tecniche per affrontare grafi bipartiti connessi, inclusi lemmi di esistenza di vertici critici e un framework induttivo

Spiegazione dettagliata dei metodi

Definizione del compito

Definizione 1.1: Per interi fissati a, b e grafo H, exb,c(a,b,H) è il numero massimo di spigoli in un grafo bipartito connesso con parti di dimensione a e b che non contiene H come sottografo.

Questo articolo studia principalmente:

• Input: Lunghezza del cammino k, dimensioni della bipartizione a, b
• Output: Valore esatto di exb,c(a,b,Pₖ)
• Vincoli: Il grafo deve essere connesso, bipartito e non contenere Pₖ come sottografo

Teoremi fondamentali

Teorema 1.5 (Risultato principale): Per tutti k ≥ 3 e b ≥ a ≥ k, $\text{ex}_{b,c}(a,b,P_{2k}) = \text{ex}_{b,c}(a,b,P_{2k-1}) = (k-2)(b-1) + a$

Questa formula mostra che:

• I cammini di lunghezza dispari e pari hanno lo stesso numero di Turán
• Il numero di spigoli cresce linearmente con la parte più grande b, con coefficiente (k-2)
• Esiste un termine di correzione additivo a

Architettura della dimostrazione

1. Costruzione del limite inferiore (Sezione 2)

Proposizione 2.1 fornisce una dimostrazione costruttiva:

Costruisce un grafo G con bipartizione A = {u₁,...,uₐ} e B = {v₁,...,vᵦ}:

• I primi k-2 vertici in A sono completamente connessi a tutti i vertici in B (formando Kₖ₋₂,ᵦ)
• I rimanenti a-(k-2) vertici in A agiscono come foglie, tutti connessi a un vertice specifico in B

Calcolo del numero di spigoli: $|E(G)| = b(k-2) + (a-(k-2)) = (k-2)(b-1) + a$

Proprietà P₂ₖ₋₁-free:

• Il grafo bipartito completo Kₖ₋₂,ᵦ ha cammino più lungo con 2k-3 vertici
• Le foglie aggiunte non possono estendere il cammino, poiché hanno tutte grado 1

2. Dimostrazione del limite superiore (Sezione 3)

Utilizza il metodo induttivo, con tre lemmi chiave:

Lemma 3.2 (Esistenza di vertici di piccolo grado): Nella parte più grande B esiste un vertice x di grado ≤ k-2 la cui rimozione mantiene la connessione.

Strategia di dimostrazione:

• Utilizza un albero DFS per trovare una foglia b in B
• Se d(b) ≤ k-2, pone x = b
• Se d(b) = k-1, allora la lunghezza del cammino deve essere 2k-2, formando un ciclo
• In questo caso è possibile trovare un altro vertice b' di grado ≤ k-2

Lemma 3.3 (Coppie di vertici cancellabili in grafi equilibrati): Per un grafo bipartito equilibrato, esistono due vertici x, y tali che d(x) + d(y) ≤ k-1 e la loro rimozione mantiene la connessione e l'equilibrio.

La dimostrazione utilizza l'analisi dei punti finali del cammino più lungo P:

• Se i punti finali sono in parti diverse, possono essere utilizzati direttamente
• Altrimenti utilizza l'albero DFS per trovare un accoppiamento appropriato di foglie

Lemma 3.4 (Caso base): Quando a = b = k, |E(G)| ≤ (k-1)² + 1.

La dimostrazione utilizza il metodo induttivo, con osservazione chiave:

• Trova un vertice di grado minimo che non è un punto di taglio x
• Analizza la struttura del grafo rimanente dopo la rimozione di x
• Utilizza la proprietà P₂ₖ-free per limitare il grado e la struttura

Dimostrazione del teorema principale:

• Se b > a: utilizza il Lemma 3.2 per rimuovere un vertice, quindi induzione
• Se a = b > k: utilizza il Lemma 3.3 per rimuovere due vertici, quindi induzione
• Se a = b = k: utilizza il Lemma 3.4

Risultati per grafi scopa

Teorema 1.6: Per k, d ≥ 2, quando n ≥ d²/2 e d > 2k, $\text{ex}_{b,c}(n,n,S_{2k,d}) = \text{ex}_{b,c}(n,n,S_{2k+1,d}) = nd$

Lemmi tecnici chiave:

Lemma 4.1: Se il grafo contiene un vertice che non è punto finale di un cammino di lunghezza 2k, allora |E(G)| ≤ (k-1)(b+a)

Lemma 4.2: Se |E(G)| ≥ k(b+a)+1, allora ogni vertice ha grado al massimo k+d-1

La dimostrazione combina questi lemmi, rimuovendo il vertice di grado massimo e i suoi vicini, utilizzando la connessione e i vincoli di grado per ottenere una contraddizione.

Configurazione sperimentale

Essendo un articolo di matematica pura teorica, questo lavoro non contiene una sezione sperimentale; tutti i risultati sono ottenuti attraverso dimostrazioni matematiche rigorose.

Risultati sperimentali

Verifica dei risultati principali

Formula esatta per cammini:

• Per P₅ e P₆: exb,c(n,n,P₅) = exb,c(n,n,P₆) = 2n-1
  • Utilizzando la formula: k=3, (3-2)(n-1)+n = n-1+n = 2n-1 ✓
• Per Pₖ generale: la formula fornisce valori esatti per tutti i casi, inclusi grafi bipartiti non equilibrati

Risultati per grafi scopa:

• Quando la parte stella è dominante (d > 2k), il numero di Turán è nd
• Questo è coerente con i vincoli di grado massimo

Confronto con risultati noti

1. Generalizzazione della Proposizione 1.2: I risultati di questo articolo includono completamente e generalizzano exb,c(n,n,P₅) = 2n-1 da CPT25
2. Miglioramento della generalità:
   • Estensione da grafi equilibrati a grafi non equilibrati
   • Estensione da cammini specifici piccoli a cammini arbitrari
   • Estensione da risultati asintotici a formule esatte

Lavori correlati

Risultati classici

1. Teorema di Turán Tur45: Problema di estremalità per grafi completi
2. Teorema di Erdős-Stone ES46: Numero di Turán asintotico per grafi non bipartiti
3. Gallai-Erdős GE59: Risultati asintotici per grafi connessi che escludono cammini di dimensione fissa
4. Gyárfás-Rousseau-Schelp GRS84: Numero di Turán esatto per grafi bipartiti che escludono cammini di dimensione fissa

Lavori direttamente correlati

Caro-Patkós-Tuza CPT25:

• Introduce la notazione exb,c
• Risolve il caso di alberi piccoli (≤ 6 vertici)
• Risolve stelle doppie e alcuni grafi ragno
• Propone i problemi risolti in questo articolo

Lavoro indipendente

He-Salia-Zhu HSZ25: Gli autori menzionano che è stato presentato lavoro indipendente con progressi simili nello stesso giorno

Conclusioni e discussione

Conclusioni principali

1. Risposta completa alla Domanda 1.3: Fornisce il valore esatto di exb,c(n,n,Pₖ) per tutti i cammini Pₖ, superando il valore asintotico richiesto dal problema
2. Risposta parziale alla Domanda 1.4: Per la famiglia dei grafi scopa, fornisce valori esatti o limitazioni superiori in specifici intervalli di parametri
3. Contributo metodologico: Sviluppa un nuovo framework tecnico per affrontare problemi di estremalità in grafi bipartiti connessi

Limitazioni

1. Restrizioni per grafi scopa:
   • Il Teorema 1.6 richiede d > 2k e n ≥ d²/2
   • Il Teorema 1.7 fornisce solo limitazioni superiori, non valori esatti
   • I casi intermedi (d ≈ k) non sono completamente risolti
2. Caso generale di alberi: Affronta solo cammini e grafi scopa, famiglie di alberi più generali rimangono aperte
3. Limitazioni tecniche: Alcuni passaggi della dimostrazione dipendono da proprietà strutturali specifiche, che potrebbero essere difficili da generalizzare a sottografi proibiti più complessi

Direzioni future

1. Perfezionamento dei risultati per grafi scopa: Determinare valori esatti per tutti gli intervalli di parametri
2. Estensione ad altre famiglie di alberi:
   • Caratterizzazione completa di grafi ragno
   • Altre strutture di alberi speciali
3. Studio approfondito del caso non equilibrato: Sebbene questo articolo affronti il caso a ≠ b, potrebbero esistere risultati più raffinati
4. Complessità computazionale: Studiare problemi algoritmici per determinare se un dato grafo raggiunge il limite di Turán

Valutazione approfondita

Punti di forza

1. Risoluzione completa di un problema aperto:
   • Non solo risponde alla Domanda 1.3, ma fornisce una formula esatta più forte di quanto richiesto
   • Estende a grafi bipartiti non equilibrati, aumentando la generalità dei risultati
2. Tecniche di dimostrazione eleganti:
   • La costruzione del limite inferiore è semplice e chiara
   • La struttura induttiva della dimostrazione del limite superiore è ben organizzata
   • I lemmi chiave (3.2, 3.3, 3.4) sono enunciati e dimostrati in modo conciso
3. Completezza dei risultati:
   • Per i cammini, fornisce formule esatte per tutti i parametri
   • La forma della formula è semplice: (k-2)(b-1)+a
   • Affronta uniformemente cammini di lunghezza dispari e pari
4. Qualità della presentazione:
   • La struttura dell'articolo è chiara e la logica è rigorosa
   • I passaggi chiave sono supportati da proposizioni dettagliate
   • Le figure (come la Figura 1) aiutano a comprendere le costruzioni
5. Innovazione tecnica:
   • Il Lemma 3.2 sull'esistenza di vertici di piccolo grado non di taglio è un'intuizione chiave
   • La caratterizzazione di coppie di vertici cancellabili in grafi equilibrati (Lemma 3.3) ha valore indipendente
   • L'uso dell'albero DFS permea la dimostrazione, mostrando l'efficacia di strumenti classici

Insufficienze

1. Risultati incompleti per grafi scopa:
   • Esiste un vuoto di parametri tra il Teorema 1.6 e il Teorema 1.7
   • Il Teorema 1.7 fornisce solo limitazioni superiori 2nk+1, con distanza dal valore esatto possibile sconosciuta
   • La condizione n ≥ d²/2 sembra piuttosto tecnica, potrebbe non essere ottimale
2. Complessità della dimostrazione del caso base:
   • La dimostrazione del Lemma 3.4 (caso a=b=k) occupa uno spazio considerevole
   • Richiede più sottoaffermazioni (Claims 3.11-3.13)
   • Potrebbe esistere un argomento più diretto
3. Generalizzabilità limitata:
   • Il metodo dipende fortemente dalle proprietà strutturali specifiche di cammini e grafi scopa
   • Per alberi generali, non è chiaro come applicare queste tecniche
   • Non viene discusso un possibile framework unificato
4. Relazione con il lavoro indipendente:
   • Viene menzionato il lavoro indipendente HSZ25 ma non viene effettuato un confronto dettagliato
   • Non è chiaro se i metodi tecnici dei due articoli sono identici

Impatto

1. Contributo teorico:
   • Risolve completamente un problema chiaramente formulato e aperto
   • Fornisce nuovi strumenti tecnici per il problema di Turán bipartito connesso
   • L'esattezza dei risultati li rende un punto di riferimento nel campo
2. Valore metodologico:
   • Il framework induttivo potrebbe essere applicabile ad altri problemi di sottografi proibiti
   • I lemmi chiave potrebbero essere utili in altri contesti
3. Ricerca successiva:
   • Naturalmente solleva la questione della caratterizzazione completa dei grafi scopa
   • Motiva lo studio dei valori di exb,c per altre famiglie di alberi
   • Potrebbe ispirare la ricerca nel caso non connesso
4. Verificabilità:
   • Come risultato puramente teorico, può essere verificato controllando la dimostrazione
   • Le costruzioni sono esplicite e facili da comprendere e verificare
   • La formula è semplice, facilitando l'applicazione e la citazione

Scenari di applicazione

1. Ricerca teorica:
   • Risultato di riferimento per ricercatori in teoria dei grafi estremalista
   • Fonte di tecniche per problemi di tipo Turán
   • Studio di caso di problemi di estremalità sotto vincoli di connessione
2. Problemi correlati:
   • Potrebbe fornire intuizioni per la ricerca sulla congettura di Erdős-Sós
   • Fornisce confronti per il numero di Turán di altri alberi
   • Studio delle proprietà strutturali di grafi bipartiti connessi
3. Valore didattico:
   • Dimostra l'applicazione del metodo induttivo in combinatoria estremalista
   • Esempio di analisi di cammini e alberi DFS
   • Caso completo di corrispondenza tra limiti superiori e inferiori

Riferimenti bibliografici (letteratura chiave)

1. CPT25 Caro, Patkós, Tuza: Bipartite Turán number of trees - Propone i problemi risolti in questo articolo
2. Tur45 Turán: On an extremal problem in graph theory - Pone le fondamenta del problema di Turán
3. ES46 Erdős, Stone: On the structure of linear graphs - Teorema di Erdős-Stone
4. GRS84 Gyárfás, Rousseau, Schelp: An extremal problem for paths in bipartite graphs - Numero di Turán esatto per cammini in grafi bipartiti (senza vincolo di connessione)
5. HSZ25 He, Salia, Zhu: The connected bipartite Turán problem for long cycles and paths - Lavoro correlato indipendente

Valutazione complessiva

Questo è un articolo di alta qualità in matematica combinatoria che risolve completamente un problema chiaramente formulato e aperto, fornendo risultati più forti di quanto richiesto. Le tecniche di dimostrazione sono eleganti e innovative, e i risultati possiedono completezza ed esattezza. Sebbene rimanga ancora lavoro da fare nella generalizzazione a famiglie di alberi più generali, l'articolo fornisce una risposta definitiva nel caso dei cammini. Questo lavoro fornisce un contributo sostanziale alla ricerca sul problema di Turán bipartito connesso ed è destinato a diventare un riferimento importante nel campo.