Sobre el número de Ramsey r(K3 , ... , K3 , K 1 , 2 , . . . , K 1 , 2)

Sobre el n ú mero de Ramsey r { K $ , K 3 , ^ 1 , 2 , ^ 1 , 2 ) L . Boza , M . p . Revuelta Departamento de Matem á tica Aplicada I , Untrerstdad de Semita . E - mail : bozaSus . es , pastoraQas . es Resumen . Se denotar á como r ( I < 3 , . .. , A 3 , Al 2 , Al 2 ) o m á s brevemente , r ( m , n ) , al n ú mero menor de v é rtices que tiene un grato completo de manera que en cualquier coloraci ó n de aristas de 771 + 71 colores necesariamente hay un / < 3 de uno de los 771 primeros colores 0 un Ai . 2 de uno de los 71 ú ltimos colores . El resultado principal de este trabajo es que si 1 , entonces r ( m , n ) = 2 L ٠ ( ٢ ( m ) 0 ) - l ) + l . Palabras clare . Teor í a de Ramsep , coloraci ó n de aristas , snbgrajos prohibidos . INTRODUCCI ó N 1 En este trabajo se prueba que si 771 , 77 > 1 , entonces r ( 77 i , n ) = 2 LfJ ( 71 ( 777 , 0 ) - 1 ) 1 , 0 ؛ lo que es lo mismo , si fc 1 , r ( 7 T 7 , 2 k ) = r ( T 77 , 2 k — 1 ) 2 ت k { r { m , 0 ) _ 1 ) + 1 . El resultado es tambi é n cierto para m = 0 si consideramos el convenio de tomar 71 ( 0 , 0 ) = 2 . Todas las coloraciones ser á n de aristas . Llamaremos ( 777 , 77 ) — coloraci ó n a , una coloraci ó n de un grato de menos de 71 ( 777 , 77 ) v é rtices con 777 + 77 colores , de manera que no haya un ^ 3 de uno de los 777 primeros colores 0 un K 2 اا de uno de los 77 ú ltimos colores . Notaremos como \ A \ al cardinal del conjunto A . Tambi é n denotaremos como di , ... , Am a los colores en los que est á prohibido un K 3 y como Bh ... , 5 „ alos colores en los que est á prohibido un AI ٠2١ A los colores Ai los llamaremos primarios y a los Bj secundarios . 2 RESULTADO PRINCIPAL El resultado principal de este trabajo es el siguiente : 71 + 1 Teorema 1 . Si 777 , 77 > 1 , entonces 71 ( 777 , 77 ) = 2 ( . 1 ب ( 1 — ( 777 , 0 ) 71 ) [ 2 56 Sobre el n ú mero de Ramsey r ( K ٠ Z ) / { 3 , 7 ( 12 , K \ ¿ ) Para caso m = 0 es f á cil comprobar que r ( 0 , ^ ) = 2 [ f \ + 1 , ya que + 1 y W { K 2 [ n ± i } ) = ( ver [ 6 ] ) , donde N ' es el indice crom á tico . Probemos en primer lugar una de las desigualdades del Teorema 1 : Lema 1 . Si 771 ) 71 1 , entonces r ( m , n ) 2 Lfj ( r ( m , 0 ) - 1 ) + 1 . Demostraci ó n . Consideremos el grafo / f 2 [ i ؛ ± ij ( r ( m 0 ) - i ) y distribuyamos sus v é r - tices en los conjuntos ( اا . . . , Vr ( m , 0 ) - اا cada uno de ellos con 2 [ f \ v é rtices . Una ( ra , () ) - coloraci ó n de Kr { m , 0 ) ~ 1 induce una ( m , 0 ) - coloraci ó n de las aristas entre v é rtices de Vi y Vj . Considerando esta ( m , 0 ) - coloraci ó n y una misma ( 0 , ) - coloraci ó n en cada uno de los Knyn + Ij inducidos por cada Vi ) se tiene una ( m , ) - coloraci ó n de K 2 [ f \ { r ( m 0 ) - ا ) y el resultado . Veamos en la siguiente la otra desigualdad del resultado principal . En primer lugar se prueba el caso en que sea impar . Proposici ó n 1 . r ( m , 2 A : — 1 ) 2 fcr ( m , 0 ) - 2 fc + 1 . Demostraci ó n . Se considera una ( m , 2 k — ! ) - coloraci ó n del grafo completo con r ( r , 2 / c — 1 ) - 1 v é rtices . Consideremos tambi é n un v é rtice cualquiera u ¡ ) todos los adyacentes a é l mediante un color secundario y otros v é rtices cualesquiera hasta tener un total de 2 & v é rtices . Llamemos V \ a este conjunto de v é rtices . Vamos a recolorear algunas aristas . Si w i V ¡ y V e V ¡ a la arista { V ) W } le asignamos el mismo color que a { u ¡ ) W } . Este color necesariamente es primario . Por otro lado las aristas del grafo I < 2 k inducido por los v é rtices de Vi admiten una ( 0 , 2 k — ! ) - coloraci ó n con los colores secundarios . Al hacer esto , como las aristas que unen v é rtices de Vi con v é rtices que no son de Vi tienen un color primario , no se crean K 1١2 de un color secundario , mientras que tampoco se van a crear ning ú n K 3 de un color primario , ya que si hubiese alguno , este tendr í a que contener alguna arista de las que se le ha cambiado el color y por tanto un v é rtice V de Vi distinto de U \ . Como las aristas que unen v é rtices de Vi tienen colores secundarios , de los tres v é rtices que inducen un K 3 de color primario Ai ) s ó lo uno , V ) esta en V ¿ . Sean w ¡ y W 2 los otros dos . Como { V ) W 1 } y { V ) V 2٧ } tienen los mismos colores que { u ¡ ) Wi } y { 2 ﺎﺳ ) respectivamente , resulta que originalmente se tenia que el ^ 3 inducido por los v é rtices U \ ) w 1 y ^ 2 tambi é n tenia el color Ai ) lo cual es una contradicci ó n . Por tanto seguimos teniendo una ( m , 2 / c - ! ) - coloraci ó n . De los v é rtices que no pertenecen a Vi se escoge uno cualquiera U 2 ) los adya - centes a é l mediante los colores secundarios y se completa , si hiciera falta , con otros v é rtices hasta tener 2 & , para formar V 2 . Se repite el proceso anterior y se contin ú a hasta terminar con todos los v é rtices . Si para formar el Ultimo conjunto K ' C ^ Lfj + i ) = TI L . Boza , M . p . Revuelta 57 Vh no quedasen v é rtices suficientes , se podr í an crear v é rtices nuevos , coloreando las aristas incidentes con ellos de la forma antes descrita , con lo cual tendr í amos una ( m , 2 k — ! ) - coloraci ó n de un grafo completo con un n ú mero de v é rtices mayor que r ( m , 2 k — 1 ) — 1 , lo cual es una contradicci ó n . Por tanto existe un n ú mero natural h tal que r ( m , 22 = 1 — ( 1 - ه kh . Tenemos por tanto el grafo I < 2 kh con una ( m , 2 fc - ! ) - coloraci ó n de manera que para cada 1 < i ¡ < 2 أ h existe un color primario 2 ي ١ ﻲﻟ 4 د que une cualquier v é rtice de con cualquier v é rtice de v ¿ 2 . Consideremos el grafo Kh , con v é rtices denotados como u ' ¡ ) ... , u ' h ٠ A la arista p , u ' q } le asignamos el mismo color que al de las aristas que unen v é rtices de Vp con v é rtices de Vq en la ( m , 2 k - ! ) - coloraci ó n de Kikh . ! Si en Kh hubiese un K 3 de color primario Ai tambi é n lo habr í a en Kikh ) lo cual es una contradicci ó n y , por tanto tenemos una ( m , 0 ) - coloraci ó n de Kh - Luego h r ( m , 0 ) r ( m , 2 fc - 1 ) 2 kh 4 - 1 < 2 kr { m , 0 ) — 2 k 1 ب . { < l y Para probar el caso n par se necesitan algunos resultados previos : lema ، 2 ، . Sea G 1 grajo conexo ta ! que su ، uatencxa maxima es a ! o mas n ، y que ع ١ ut ... existe un rertiee u ^ con ratencta a ! o mas n — 1 , entonces existen u ، 2١ V ^ G ١١ y W \ ١ . . ٠٦ wt ( ث V ! G ١ tates que , ! os conjuntos Wi son dtsjuntos dos a dos , j ٠ ; \ w 3 es e ! conjunto de todos ! os . tices de G , para todo t = 1٦ . . . ٦ t - L se tiene que \ Wi \ < n , \ wt \ < n — ly para todo i ١ ... 1٦ ا t se tiene que Ui esta en y todos ! os rCrtices adyacentes au ؛ estdn en 3٠ ىدﺬﺒﺴﻤﻟ t ٠ ش Wi Demostraci ó n . Veamos el resultado por inducci ó n en el n ú mero de v é rtices de G . Si G tiene a lo m á s n — 1 v é rtices , se tiene el resultado tomando como w ¡ al conjunto de todos los v é rtices de G . Si G tiene al menos n v é rtices , sea W \ el conjunto formado por la uni ó n de U \ y los v é rtices adyacentes a U \ . Cada componente conexa del grafo G — W \ verifica las condiciones del Lema , ya que cada una de estas componentes conexas contiene al menos a un vecinos de los vecinos de en G , y estos v é rtices tendr í an valencia a lo m á s n - 1 en G — W \ . Aplicando la hip ó tesis de inducci ó n enG — W \ se tiene el resultado . Lema ٠ ﻵ Sea G 1 grajo conexo ta ! que su ra ! eneta mdxtma es a ! o mds n , entonces existen u \ y .. , ut 6 V ( G ) yW \ ) .. . ) WtgV ( G ) tales que , los conjuntos Wi son disjuntos dos a dos , UjZiWj es el conjunto de todos los v é rtices de G , \ w ¡ \ < n 1 ب , para todo 2 = 2 , 1 se tiene que \ Wi \ < ny \ wt \ < n — ly para todo ! = 1٦ . . ٠٠ ٦ t se ttene que U ؛ esta en w ؛ y todos ! os r é rttces adyacentes a est á n en u ] : ¡ [ Wj . Ui , K 1 , 2 ) Sobre el n ú mero de Ramsey r ( K 3 , ^ 3 , K 1 58 Demostraci ó n . Es exactamente an á loga a la demostraci ó n del Lema 2 , excepto en que si todos los v é rtices de G tienen valencia n y por tanto U i no puede ser elegido con valencia a lo m á s n — 1 y \ w ¡ \ = n + 1 Probemos ahora , para concluir la demostraci ó n del Teorema 1 , la desigualdad que falta del caso par : Proposici ó n 2 . r ( m , 2 k ) 2 / cr ( ra , 0 ) - 21 + ه . Demostraci ó n . Consideremos una ( m , 2 ^ ) - coloraci ó n del grafo completo que tiene r ( m , 2 k ) — 1 v é rtices . Sea G el grafo formado por las aristas con colores secun - darios y sean Gi , ... , Gp las componentes conexas de G . Aplicando a estas com - ponentes el Lema 3 , se tiene que los v é rtices de G ¿ , con í = l ١ . M , p , se pueden descomponer en Wi ) 1 , Wiji , en las condiciones del enunciado de dicho lema . Podemos ahadir a cada uno de esos conjuntos Wij v é rtices nuevos , no perte - necientes al grafo completo con r ( m , 2 k ) - 1 v é rtices de manera que se obtenga un conjunto w ' í j con 2 fc + 2 v é rtices . Se puede hacer , a partir de la ( m , 2 ^ ) - coloraci ó n del grafo completo inicial E ؟ ; ؛ E ؛ ^ ؛ i = r ( m , 2 ^ ) — 1 v é rtices , una ( m , 2 ^ + ! ) - coloraci ó n del grafo completo cuyos v é rtices son la uni ó n ٧ ii utjLi w ' j ) de la misma forma que en la demostraci ó n de la Proposici ó n 1 , asignando colores secundarios a las aristas entre v é rtices de un mismo w ' j y colores primarios a ٠ l resto . Como por el Lema 3 se tiene que si ٠ , 1 = ؛ .. , p , se tiene que \ Wi ) ¡ \ 2 fc + 1 , 2 fc - 1 y si 1 ~ , 2 = * و , \ Wi ] j \ 2 ^ , se tiene que el n ú mero de v é rtices que se han a ñ adido al grafo completo de r ( m , 21 — ( ﻊﺗ v é rtices se puede acotar inferiormente de la siguiente manera : tPxti ( \ Wlj \ - \ Wij \ ) = ti ( \ WLi \ - \ Wiix \ ) + ti ^ : t 2 Í ( \ Wlj \ - \ Wid \ ) + 1 ) ﺔﯿﺗا Wj / ؛ ، rI — IWj ٠ t ، | ) > s ، z 2 )) ؟ fc + 2 ) — ( 2 fc + 1 )) + 2 ) ) 1 - 2 ﺔﯿﻟاﺔﻘﻟ fc + 2 ) — 2 fc ) - f S ، I 2 )) ؟ fc + 2 ) - ( 2 k - l )) = p + 2 tiiu - 2 ) + 3 p = 2 ﺊﺗإو ، ، . Por otro lado dicho n ú mero de v é rtices que se han a ñ adido es : ( 2 k + 2 ) E ¡ iZiti - ( r ( m , 2 k ) - 1 ) . Por tanto se tiene que ( 2 k + 2 ) ي ، ﺔﺨﻟ — ( r ( m , 2 / c ) — 1 ) 2 E - IV \ ti ٠ Luego E ] Ziti - y por consiguiente el n ú mero de v é rtices que se han a ñ adido r ( m , 2 fe ) — l con es a lo m á s De ah í se deduce que el n ú mero de v é rtices del grafo con la ( m , 2 k + 1 ) - coloraci ó n es r ( m , 2 / c ) — 1 + ! ٢٥ , que es a lo m á s r { rri ) 2 k + 1 ) = ( 2 k + 2 )( r ( rn , 0 ) — 1 ) y por tanto r ( m , 2 k ) 2 fc ( r ( m , 0 ) - 1 ) 11 , por lo que se tiene probado esta proposici ó n y el Teorema 1 . fe 59 L . Boza , M . p . Revuelta Usando los valores exactos y cotas de r ( m , 0 ) que nos da la literatura para valores peque ñ os de ra , podemos obtener valores exactos y cotas de r ( ra , n ) . Asi tenemos que , dado que es trivial que r ( l , 0 ) = 3 , se tiene que si n 1 , r ( l , n ) = 4 [ if \ + 1 . Tambi é n es f á cil comprobar que r ( 2 , 0 ) = 6 ( ver [ 5 ] ) , luego se tiene que si n > 1 , r ( 2 , n ) = 10 | | fJ + 1 . Greenwood y Gleason [ 5 ] probaron que r ( 3 , 0 ) = 17 . De ah í se deduce que si n 1 , r ( 3 , n ) = 32 [ | fJ + 1 . A partir de m 4 , no se conocen valores exactos de r ( m , 0 ) . Se tiene que [ 1 ] 51 r ( 4 , 0 ) 62 [ 3 ] , luego 1001 1 ل ^ ؛ r ( 4 , n ) 122 [ fJ + 1 . Tambi é n esta probado que 2 ] 162 r ( 5 , 0 ) 307 [ 7 ] , por tanto si n 1 , 322 | ifJ 1 ب < r ( 5 , n ) < 612 [ f 1 ب ل . Se puede observar que para valores mayores de m las diferencias entre las cotas superiores e inferiores conocidas de r ( m , 0 ) aumenta . Se tiene que [ 4 ] 538 r ( 6 , 0 ) 1838 [ 7 ] , luego si n 1 , 1074 . + 1 r ( 6 , n ) 3674 . + 1 . Finalmente esta probado que [ 4 ] 1682 r ( 7 , 0 ) 12861 [ 7 ] , por tanto si n > 1 , 3362 Lf 1 + ل r ( 7 , n ) 25720 . + 1 . REFERENCIAS 1 ؛ ] Chung F . R . K . On the Ramsey Numbers iV ( 3 , 3 , . .. , 32 ًا ) , Discrete Mathe - matics , 5 ( 1973 ) 317 - 321 . [ 2 ] Exoo G . A Lower Boud for Schur Numbers and Multicolor Ram - sey l ïï krs 0 أ K ؟ n The Electronic Journal oj Combinatorics , http : // www . combinatorics . org / , 1 ( 1994 ) , # R 8 . [ 3 ] Fettes s . , Kramer R . L . y Radziszowski s . p . An Upper Bound of 62 on the Classical Ramsey Number R ( 3 , 3 , 3 , 3 ) , Ars Combinatoria , 72 ( 2004 ) , 41 - 63 . [ 4 ] Fredricksen H . y Sweet M . M . Symmetric Sum - Free Partitions and Lower Froids loi Scki Inkis , The Electronic Journal , of Combinatorics , http : // www . combinatorics . org / , 7 ( 2000 ) , # R 32 . [ 5 ] Greenwood , R . E . y Gleason , A . M . Combinatorial Relations and Chromatic Graphs , Canadian Journal of Mathematics , 7 ( / ¡ ٦ - \ ٦١١ ل . [ 6 ] Harary , F . Graph Theory . Srpinger - Verlag , Reading , Mass . , 1969 . [ 7 ] Radziszowski , s . p . Small Ramsey Numbers , The Electronic Journal of Com - binatorics , http : / / www . combinatorics . org / . Dynamic Surveys ( 2006 ) , DSl . ( ا 1 ﻞﻛ ... Sobre el n ú mero de Ramsey r { Kh ^ 3 , K \ 60 2