OliForum Matematico

riformulazione del problema del thread SFIDA
 Let A be a graph then the number of triangles in the graph is less or equal to ck3/2 where k is the number of edges in the graph.
 A triangle in a graph is simply a set of 3 vertices that is completely connected
 ( k elevato alla 3/2) [ Questo Messaggio è stato Modificato da: quismulta il 29-09-2004 22:47 ]

E cos\'e\' c?

Secondo quello che ha scritto nel thread \"sfida\", è semplicemente un numero maggiore di zero. Una specie di coefficiente... Mah! [ Questo Messaggio è stato Modificato da: DB85 il 30-09-2004 11:07 ]

Cioe\', ditemi se e\' corretto:
 ---------------
 Dimostrare che esiste un numero c>0 tale che su ogni grafo
 G_3<= c E^{3/2}
 dove E e\' il numero dei lati del grafo e G_3 e\' il numero dei sottografi completi di tre vertici.
 ---------------
 
 E\' lui oppure sto misinterpretando? In particolare, c dipende dal grafo scelto o no?
 
 ciao,
 --federico

Per quanto mi riguarda, ho interpretato il problema come te, fph. Per c, quismulta l\'ha definito solo come numero positivo e non ha scritto altro.
 
 Comunque non è possibile che un problema si debba interpretare, non stiamo leggendo La Divina Commedia, questa è Matematica!
 
 Visto che ci sono, perdonatemi se invito tutti a scrivere testi univoci e chiari (soprattutto se i problemi sono stati ideati dalla vostra mente). [ Questo Messaggio è stato Modificato da: DB85 il 30-09-2004 12:45 ]

Dato che non ho chiarissimo il problema io stesso speravo qualcuno (leggi imo 93) abile coi grafi mi illuminasse.Ho cercato di allegare il paper con soluzione ( sono presenti anche altri problemi interessanti) ma data la estensione ...
 Per chi fosse interessato al problema ho pronto il file formato .ps.
 
 Caro db85 l\' interpretazione di un problema è e sarà sempre essenziale! [ Questo Messaggio è stato Modificato da: quismulta il 30-09-2004 14:59 ]

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-09-28 20:27, quismulta scrisse:
 Il livello è pre-imo o imo comunque un livello tale da discriminare tra intelligenti e... [..]
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 <TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-09-30 14:56, quismulta scrisse:
 Dato che non ho chiarissimo il problema io stesso [..]
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 <IMG SRC="images/forum/icons/icon_eek.gif">

uhm...
 
 <TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 quisimulta sul thread sfida (parlando di questo stesso problema):
 (Caro Mind Flyer non perdere tempo a cercarlo in internet o sull\' american mathematical monthly o nei tuoi ricordi perchè non lo troveresti chè lo ho elaborato e scritto di mio pugno)
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 <TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 quisimulta su questo thread:
 Dato che non ho chiarissimo il problema io stesso speravo qualcuno (leggi imo 93) abile coi grafi mi illuminasse.Ho cercato di allegare il paper con soluzione ( sono presenti anche altri problemi interessanti) ma data la estensione ...
 Per chi fosse interessato al problema ho pronto il file formato .ps.
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 --f

avrà una doppia personalità!

Mi volete portare OT!
 Ribadisco che:
 1)Il livello è almeno imo 6 (ovvero il più ostico dei sei problemi di una gara)
 2)Il file non è in internet o sul AMM
 3)Ho solo cercato un interessato
 Non siete obbligati ad interessarvi ma se vi interessaste vi manderei il file (ditelo subito perchè sono gli ultimi giorni che ho un pò di tempo da perdere giocando in internet)
 Grazie

EDIT: Stavo ri-vaneggiando. Pare che il problema abbia senso, che figo! <IMG SRC="images/forum/icons/icon_biggrin.gif">

<IMG SRC="images/forum/icons/icon_eek.gif"> <IMG SRC="images/forum/icons/icon_eek.gif"> <IMG SRC="images/forum/icons/icon_eek.gif"> <IMG SRC="images/forum/icons/icon_eek.gif"> <IMG SRC="images/forum/icons/icon_eek.gif"> <IMG SRC="images/forum/icons/icon_eek.gif"> <IMG SRC="images/forum/icons/icon_eek.gif">
 
 [ Questo Messaggio è stato Modificato da: quismulta il 30-09-2004 22:53 ] [ Questo Messaggio è stato Modificato da: quismulta il 30-09-2004 23:24 ]

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-09-30 12:17, fph wrote:
 Cioe\', ditemi se e\' corretto:
 ---------------
 Dimostrare che esiste un numero c>0 tale che su ogni grafo
 G_3<= c E^{3/2}
 dove E e\' il numero dei lati del grafo e G_3 e\' il numero dei sottografi completi di tre vertici.
 ---------------
 
 E\' lui oppure sto misinterpretando? In particolare, c dipende dal grafo scelto o no?
 
 ciao,
 --federico
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 Beh, penso che sia lui. Per avere un senso, il problema, c deve essere una specie di \"costante universale di triangolabilità dei grafi\". Altrimenti, se dipendesse dal grafo, conti G_3, conti E, e c che vada bene lo trovi...
 
 Mah, in effetti non ha l\'aria di essere semplice...
 
 Alla prox.
 
 M.[addsig]

Detto n il numero dei nodi del grafo e indicando con (a b) il coefficente binomiale di a su b, e sqr(x) la radice quadrata di x:
 
 A vale al più (n 3)
 k vale al più (n-1)!
 
 dobbiamo dimostrare che
 
 A<= ck^3/2
 
 perciò
 
 c>= A/k^3/2
 
 c >= (n 3) / (((n-1)!)^3/2)
 
 da cui:
 
 c>= n/(6*(n-3)!*sqr((n-1)!)) (1)
 
 poichè per ogni n>=3
 n/(6*(n-3)!*sqr((n-1)!)) >= (n+1)/(6*(n-2)!*sqr((n)!))
 
 ne segue che il valore del termine destro della disuguaglianza (1) è massimo per n=3 perciò
 
 c>= sqr(2)/4. [ Questo Messaggio è stato Modificato da: psion_metacreativo il 02-10-2004 16:40 ]

cmq non mi sembra un IMO 6... <IMG SRC="images/forum/icons/icon_biggrin.gif">