OliForum Matematico

...e infatti questo non dimostra nulla.
 A parte che quel (n-1)! dovrebbe essere un (n 2), quello che avresti dimostrato è solo che se A è massimo e k è massimo, esiste un c che verifichi la disuguaglianza. Ma questo non dice nulla su tutti gli altri casi.

Il problema non è evidentemente semplice... Ma il suo opposto penso sia ancora più complesso:
 Dato k nell\'intervallo [0; Bin(n, 2)], qual\'è il minimo numero di triangoli in un grafo con n vertici e k lati?
 
 Che ne pensate?
 
 ---
 \"Le vite degli uomini famosi ci ricordano
 Che possiamo rendere sublimi le noste esistenze
 E, morendo, lasciare dietro di noi
 Le nostre impronte sulle sabbie del tempo\"
 Henry Wadsworth Longfellow [ Questo Messaggio è stato Modificato da: DB85 il 02-10-2004 18:21 ]

Ciao.
 
 Boh, mezze idee per mezze soluzioni:
 
 Innanzitutto il testo del problema ha senso (con l\'interpretazione \"Esite c t.c. per ogni grafo bla... bla...\"). L\'esponente 3/2 è quello ottimale (o meglio, più giù di così non si può scendere).
 
 Inoltre la congettura è quella che penso abbiano fatto tutti: il caso peggiore è quello dei grafi completi. Seguendo la successione dei grafi completi, si trova che l\'esponente è almeno 3/2 e che la costante c è limitata dal basso a \\sqrt(2) / 3 (ricontrollate i conti!!).
 
 Lemmino di dimostrazione immediata, che forse serve a ridurre il problema: Non è restrittivo supporre che il grafo che massimizza T / minimizza K sia connesso.
 
 La strategia dimostrativa che seguirei per arrivare alla tesi è cercare di ridurre via via il grafo \"impaccando\" i triangoli sempre più fino a ridurre il tutto a un grafo completo o circa completo. Detto in termini formali, dato il grafo, trovare un a serie di regolette di sostituzione che 1) non facciano diminuire T / k^(2/3); 2) terminino in tempo finito verso un grafo completo (o circa tale).
 
 Per finire, vi elargisco una bella congettura improvvisata, cosicché potete divertirvi a confutarla:
 
 Guess:
 
 Tra tutti i grafi con K spigoli, uno che massimizza T (il numero di triangoli) è fatto così:
 
 i) E\' un grafo completo con N vertici, se K = Bin(N, 2).
 
 ii) E\' un grafo completo con N-1 vertici, più un vertice \"extra\" collegato solo ad alcuni degli altri vertici, in modo che il conto degli archi torni, altrimenti.
 
 [il guess implica la tesi]
 
 Ciao.
 
 M.[addsig]

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-10-04 10:00, I wrote:
 Guess:
 
 Tra tutti i grafi con K spigoli, uno che massimizza T (il numero di triangoli) è fatto così:
 
 i) E\' un grafo completo con N vertici, se K = Bin(N, 2).
 
 ii) E\' un grafo completo con N-1 vertici, più un vertice \"extra\" collegato solo ad alcuni degli altri vertici, in modo che il conto degli archi torni, altrimenti.
 
 [il guess implica la tesi]
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 Ciao, banda.
 
 Beh, le mie mezze idee non erano poi così malaccio. Ecco le altre mezze.
 
 Prima di tutto: non è mai restrittivo suppore che tutti i vertici abbiano grado positivo (ricordo che il grado è il numero di spigoli che giungono in un vertice). Altrimenti, basta cancellare i vertici senza spigoli.
 
 Dato un intrego positivo k, definisco v(k) come quell\'unico intrego positivo t.c.
 Bin( v(k), 2 ) <= k < Bin( v(k)+1, 2 ). v(k) è il numero di vertici del più grande grafo completo con non più di k archi.
 
 Dato che, come ormai sapete, mi piacciono i lemmi con nomi fantasiosi, cominciamo con un paio di essi...
 
 Lemma del Massimo Grado Minimo
 Dato un grafo con k archi, sia m il minimo dei gradi dei vari vertici del grafo. Allora m < v(k).
 
 Dim.: Un grafo con un vertice di grado m deve avere almeno m+1 vertici (il vertice iniziale, più tutti i suoi vicini). Ognuno di essi ha grado almeno m, quindi la somma di tutti i gradi, che è ben noto essere il doppio degli spigoli del grafo, è almeno m(m+1). Allora il grafo ha almeno Bin( m+1, 2 ) grafi, da cui la tesi. []
 
 Lemma del Buon Vicinato
 Un vertice di grado d appartiene al massimo a Bin( d, 2 ) triangoli.
 
 Dim.: Chiamo V il vertice che sto considerando. Sia il vicinato di V l\'insieme dei vertici congiunti a V. Sia G_V il sottografo ottenuto considerando solo vertici del vicinato di V e gli archi che li congiungono. I triangoli per V sono ovviamente in corrispondenza biunivoca con gli spigoli di G_V. Ma G_V ha d vertici e quindi al più Bin( d, 2 ) archi. []
 
 Ora dimostro il Guess per induzione su k.
 
 k fino a [put your favorite small number here!] si vede enumerando i casi.
 
 Suppongo quindi il Guess dimostrato per tutti i k\' < k. Sia G un grafo con k vertici. Ora userò l\'idea di trasformare G in modo che il numero di triangoli non scenda. Sia V un vertice di grado minimo (ma positivo!) e sia m il suo grado. Sia G\' il grafo ottenuto cancellando V e gli m spigoli che ne escono. I triangoli di G sono () anche triangoli di G\' oppure () triangoli passanti per V. Considero ora il grafo G\' con k\' = k - m spigoli, e lo trasformo in un grafo H\', sempre con k\' vertici, ma massimizzando i triangoli così come mi insegna la tesi del Guess (ossia con un grafo completo con v(k\') vertici e al più un vertice extra).
 
 Ora voglio completare H\' ad un grafo con H vertici, aggiungendo m spigoli che escono da V.
 
 Dico che v(k\') >= m. Infatti, m è al massimo v(k) - 1 (per Lemma M.G.M.); facendo il conto ammodino si vede che v(k\') può essere solo v(k) o v(k) - 1. In entrambi i casi il \"dico che\" è vero.
 
 Definisco H come H\', completato collegando V con un po\' di vertici del grafo completo con v(k\') vertici contenuto in H\' (ho abbastanza spazio, dato che vale il \"dico che\").
 
 Dico che H ha almeno tanti triangoli quanto G. Infatti, ho osservato che i triangoli di G sono i triangoli di G\' + quelli che passano da V. Analogamente i triangoli di H sono i triangoli di H\' + quelli che passano da V. Per ipotesi induttiva, i triangoli di H\' sono almeno tanti quanti quelli di G\'. Invece i triangoli per V in H sono Bin( m, 2 ), che è il numero massimo possibile (per il Lemma del Buon Vicinato) e quindi sono almeno tanti quanti i trangoli per V in G.
 
 Ricapitoliamo: ho dimostrato che non è restrittivo supporre G in una forma particolare: G contiene un grafo completo K e al più due vertici extra, collegati con alcuni, ma non con tutti, i vertici di K (e solo quelli). Se i vertici extra sono 0 o 1, il grafo è già nella forma prescritta dal Guess e ho finito.
 
 Supponiamo allora che i vertici extra siano 2; li chiamo V e V\' e suppongo che deg V = d >= deg V\' = d\'. Si vede che togliendo uno spigolo a V\' e aggiungendo uno spigolo a V che lo congiunge a uno dei vertici di K non ancora collegati a V, il numero di triangoli aumenta di d - (d\'-1) > 0. Applico questa osservazione ripetutamente, finché V smette di essere extra, dato che risulta congiunto a tutti i vertici di K; oppure V\' smette di essere extra, perché ha grado 0 e lo posso cancellare. In entrambi i casi, mi sono ricondotto al caso in cui G ha al più un vertice extra. []
 
 Eh, eh, eh...
 Marco: 1 - Quismulta: 0. <IMG SRC="images/forum/icons/icon21.gif">
 
 Ciao.
 
 M. [addsig]

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-10-05 16:22, marco wrote:
 Dato un intrego positivo k, definisco v(k) come quell\'unico intrego positivo [...]
 Dato che, come ormai sapete, mi piacciono i lemmi con nomi fantasiosi,
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 E non solo i lemmi! Chissà cosa ne direbbe Freud. <IMG SRC="images/forum/icons/icon_wink.gif">

Ciao.
 
 @MindFryer: è un gioco di parole in dialetto cremonese: \"intrego\" (o meglio, l\'analogo in dialetto) può ben siginificare \"intero\", ma più spesso assume il significato in senso traslato di \"imbranato\" (chissà perché, poi).
 
 @Quismulta: possiamo avere anche la tua soluzione? Eventualmente, se è grande, puoi spedirla a [iniziale del nome]_[cognome]@yahoo.it.
 
 Ciao. M.[addsig]

OliForum Matematico

ff