Árboles inevitables en torneos

FACULTAD DE MATEM´ ATICAS DEPARTAMENTO DE GEOMETR´ IA Y TOPOLOG´ IA GRADO EN MATEM´ ATICAS Trabajo Fin de Grado T´ıtulo ´ Arboles inevitables en torneos Realizado por: Esther Berm´udez Carvajal Supervisado por: Desamparados Fern´andez Ternero 10 de Septiembre de 2020 ´ Indice general 1. Preliminares 7 1.1. Nociones b´asicas de grafos . . . . . . . . . . . . . . . . . . . . 7 1.2. Definiciones y resultados previos sobre torneos . . . . . . . . . 9 2. Inevitabilidad de concatenaciones de caminos 19 2.1. Reducci´on a concatenaciones de caminos salientes . . . . . . . 19 2.2. Concatenaciones de caminos salientes . . . . . . . . . . . . . . 25 2.2.1. Concatenaciones de caminos salientes con primeros bloques de longitud al menos dos . . . . . . . . . . . . . . 25 2.2.2. Concatenaciones de caminos salientes con primeros bloques de longitud uno . . . . . . . . . . . . . . . . . . . 28 2.2.3. Casogeneral........................ 29 3. El m´etodo de H¨aggkvist y Thomason 33 4. ´ Arboles con pocas hojas 41 Bibliograf´ıa 43 1 Resumen / Abstract En esta memoria trabajaremos con torneos, centr´andonos en un estudio de los ´arboles inevitables en Torneos. La noci´on de torneo, grafo dirigido completo, es relativamente nueva si la comparamos con otras ´areas de la Teor´ıa de Grafos. Las nociones y resultados que presentaremos nos conducir´an a encontrar el menor n´umero de v´ertices de un torneo donde un ´arbol se encuentra como subgrafo. Consideraremos diferentes tipos de ´arboles, siendo ´estos cada vez menos simples. In this memory we will work with tournaments, focusing on a study of the inevitable trees in Tournaments. The notion of tournament, complete directed graph, is relatively new if we compare it with other areas of Graph Theory. The notions and results that we will present will lead us to find the fewest vertices of a tournament where a tree is found as a subgraph. We will consider different types of trees, these being less and less simple. 3 Introducci´on En 1966 apareci´o un estudio por parte de F. Harary y L. Moser, The theory of round robin tournaments [3], en el cual se estudian los torneos “round robin”. En dichos torneos los jugadores o equipos participan en un juego que no puede terminar en empate y en el que todos los participantes juegan entre s´ı exactamente una vez. As´ı, el t´ermino Torneo se debe al origen de la noci´on. Existe una gran cantidad de fen´omenos emp´ıricos con estructuras asim´etricas y completas, que pueden representarse gr´aficamente como torneos. Podemos verlo en experimentos de comparaci´on pareada, donde, por ejemplo, se quiere saber las preferencias de una persona sobre cierto tema de forma que para cada par de datos indique cu´al prefiere. La estructura de sus preferencias declaradas puede ser representada por un torneo en el que los v´ertices representan los datos y las aristas dirigidas la elecci´on. Tambi´en en estudios sobre dominaci´on en algunas sociedades de animales, de modo que para cada par de individuos, uno domina al otro. En votaci´on por mayor´ıa, el resultado de los votos puede ser representado por un digrafo cuyos v´ertices son grupos pol´ıticos o partidos y cuyas aristas dirigidas indican que partido derrot´o al otro. Los primeros resultados sobre torneos estuvieron motivados por este tipo de aplicaciones, de naturaleza estad´ıstica. En las ´ultimas d´ecadas se ha centrado la atenci´on en la estructura combinatoria de los torneos, dando lugar a un ´area diferenciada dentro de la Teor´ıa de Grafos. En 1965, F. Harary, R.Z. Norman y D. Cartwright presentaron, en una monograf´ıa dedicada a grafos dirigidos [4], un estudio introductorio de los torneos desde el punto de vista de la teor´ıa de grafos, distanci´andose de sus aplicaciones. J.W. Moon reuni´o la mayor´ıa de resultados que exist´ıan sobre torneos hasta 1968 [10]. A lo largo de este art´ıculo, trabajaremos con torneos y una de sus pro5 piedades: la inevitabilidad. Se dice que un digrafo (o grafo dirigido) es ninevitable si todo torneo de orden ncontiene a dicho digrafo como subgrafo. Al principio de este art´ıculo encontraremos un cap´ıtulo de preliminares, d´onde veremos algunos conceptos b´asicos sobre teor´ıa de grafos y torneos para poder introducirnos en el tema del trabajo. En el cap´ıtulo 2 estudiaremos la inevitabilidad de las concatenaciones de caminos (uni´on de caminos disjuntos con un origen com´un), probando primero que podemos restringirnos a concatenaciones de caminos salientes. El objetivo del capitulo 3 es encontrar una cota superior para f(n) por inducci´on, siguiendo el m´etodo de H¨aggkvist y Thomason, donde f(n) el menor entero tal que todo ´arbol orientado es f(n)-inevitable. Para ello definiremos la noci´on de p-coraz´on y lo ilustraremos con ejemplos para facilitar su comprensi´on. Por ´ultimo, en el cap´ıtulo 4 veremos la inevitabilidad de ´arboles con pocas hojas. Esto nos servir´a para demostrar f´acilmente que una cota para f(n) es 38 5n−6, es decir, los ´arboles de orden nson (38 5n−6)-inevitables. 6 Cap´ıtulo 1 Preliminares Este cap´ıtulo consta de dos secciones en las que veremos nociones b´asicas sobre la teor´ıa de grafos y resultados previos sobre torneos. 1.1. Nociones b´asicas de grafos En esta secci´on recordaremos algunas definiciones y resultados b´asicos de Teor´ıa de Grafos que se han extra´ıdo del libro Handbook of Graph Theory [1]. Para ampliar conocimientos, se puede consultar el libro Graph Theory [2]. Definici´on 1.1 Un grafo simple,G= (V, E), consta de un conjunto no vac´ıo de v´ertices V y de un conjunto E de pares no ordenados de elementos distintos de V, a estos pares se les llama aristas. Definici´on 1.2 Un subgrafo de un grafo G= (V, E)es un grafo cuyos conjuntos de v´ertices y aristas son subconjuntos de los de G. Definici´on 1.3 Dado un grafo G, un subgrafo Hse dice maximal verificando una cierta propiedad Psi Hverifica la propiedad Py cualquier subgrafo H0de Gtal que H⊂H0no verifica P. Definici´on 1.4 Un grafo completo es un grafo simple que tiene una arista entre cada par de v´ertices distintos. Denotaremos como Knel grafo completo de n v´ertices. Definici´on 1.5 Se llama camino en un grafo a una secuencia de v´ertices tal que exista una arista entre cada v´ertice y el siguiente. Se dice que dos v´ertices est´an conectados si existe un camino que vaya de uno a otro, de lo contrario estar´an desconectados. La longitud de un camino es el n´umero de aristas o el n´umero de v´ertices menos una unidad. 7 Y por ´ultimo, si tomamos como origen el v´ertice 4, tambi´en se cumple: Hemos visto que para cada par de v´ertices xeyexiste un camino saliente dirigido con origen xy v´ertice final y. Por tanto, este 4-torneo es fuerte. Definici´on 1.34 Las componentes fuertes de un torneo son los subgrafos fuertes maximales. Los siguientes resultados ser´an ´utiles para comprobar si un torneo es o no fuerte. Proposici´on 1.35 Un torneo es fuerte si y solo si cada par de v´ertices est´a contenido en un ciclo. Proposici´on 1.36 La componente fuerte C de un torneo T tal que T−C→ Ces la componente fuerte maximal de T. Ejemplo 1.37 Sea T el siguiente torneo: 14 Si consideramos C={4}, tenemos que T−Ces el subtorneo generado por {1,2,3}: Se tiene que T−C→C, luego C={4}es la componente fuerte maximal de T. Definici´on 1.38 Sea X un subconjunto de v´ertices de T. La secci´on exterior generada por X en T es el conjunto de v´ertices ypara los que existe un camino saliente dirigido (que puede estar constituido por un ´unico v´ertice) desde x∈X. Denotaremos este conjunto por S+(X)y, en particular, por S+(x), si X={x}, y por S+(x, y), si X={x, y}. Escribiremos s+(X) = |S+(X)|. Observaci´on 1.39 Tengamos en cuenta que X⊆S+(X), ya que un solo v´ertice xse puede considerar como un camino con origen xy v´ertice final x. Definici´on 1.40 La secci´on interior generada por X en T, es el conjunto de v´ertices ypara los que existe un camino entrante dirigido desde 15 x∈X. Denotaremos este conjunto por S−(X)y, en particular, por S−(x), si X={x}, y por S−(x, y), si X={x, y}). Escribiremos s−(X) = |S−(X)|. Ejemplo 1.41 Consideremos el siguiente 5-torneo. 1 2 3 4 5 Si X={1}, entonces su secci´on exterior es S+(X) = {1,2,3,5}, ya que existe un camino saliente dirigido con origen 1y v´ertices finales {1,2,3,5} y no lo existe para el v´ertice 4. Tenemos que s+(X) = |S+(X)|= 4. (Figura 1.5) Figura 1.5: Secci´on exterior 16 Su secci´on interior es S−(X) = {1,2,3,4,5}, ya que existe un camino entrante dirigido con origen {1,2,3,4,5}y v´ertice final 1. Tenemos que s−(X) = |S−(X)|= 5. (Figura 1.6) Figura 1.6: Secci´on interior Definici´on 1.42 Un generador externo de un torneo T es un v´ertice x de T tal que S+(x) = V(T). La noci´on dual es la de generador interno. Ejemplo 1.43 En el ejemplo anterior, podemos ver que el v´ertice 1 es un generador interno, ya que S−(x) = V(T). Proposici´on 1.44 ([11]) Cualquier torneo contiene un camino hamiltoniano dirigido, luego tiene un generador externo y tambi´en un generador interno. En la proposici´on anterior, tenemos que el generador externo de un torneo coincide con el origen del camino hamiltoniano dirigido y, el generador interno, con el v´ertice final de dicho camino. A continuaci´on, mostramos varios resultados importantes para el tema de este Trabajo de Fin de Grado. Teorema 1.45 (Teor. 1.1, [6]) Sean Tun torneo de orden n+ 1,Pun camino saliente de orden nyxeydos v´ertices distintos de T. Si s+(x, y)≥ b1(P)+1, entonces xoyes origen de una copia de P en T. 17 Observaci´on 1.46 Cuando decimos que un torneo Tcontiene una copia de un camino P, nos referimos a que Tcontiene un subgrafo dirigido isomorfo aP. En el resto de resultados, abreviaremos “Tcontiene una copia de P”por “Tcontiene a P”. Corolario 1.47 (Cor. 2, [12]) Sean Tun torneo de orden n+ 1 yPun camino de orden n. Al menos dos v´ertices de Tson or´ıgenes de Pen T. En particular, Tcontiene a P. Corolario 1.48 Sean Tun torneo de orden n+ 1,Pun camino saliente de orden ncon b1(P)≥2yxun v´ertice de T. Si d+(x)≥2ys+(x)≥b1(P)+1, entonces xes origen de Pen T. Demostraci´on: Sea yun generador externo del subtorneo T[N+(x)] y z∈N+(x) distinto de y. En T−x,s+(y, z) = s+(x)−1≥b1(P) = b1(∗P)+1, as´ı que, por el Teorema 1.45 , yozes origen de ∗Pen T−x. Por tanto, x es origen de Pen T. Teorema 1.49 Sean Tun torneo de orden n≥8yPun camino de orden n. Entonces Tcontiene a P. Observaci´on 1.50 El resultado anterior es consecuencia del hecho de que todo n-torneo Tcontiene un camino Pde orden nsi y s´olo si el par (T, P) no es una excepci´on de Gr¨umbaum [6, Cor. 4.1], teniendo en cuenta que no hay ninguna excepci´on de Gr¨umbaum con n≥8. 18 Cap´ıtulo 2 Inevitabilidad de concatenaciones de caminos En este cap´ıtulo, estudiaremos la inevitabilidad de los ´arboles m´as simples posibles: las concatenaciones de caminos, que son ´arboles que se obtienen al identificar el origen de varios caminos. En particular, las garras, una clase especial de concatenaciones de caminos donde todos son caminos salientes dirigidos, se ha estudiado en profundidad. En [9], X. Lu, D. Wang y C. K. Wong han probado los siguientes resultados, donde el grado de una garra es el n´umero de caminos que la componen. Teorema 2.1 Toda garra de orden n y grado al menos 19 50nes n-inevitable. Teorema 2.2 Existen garras de orden n y grado 11 23nque no son n-inevitables. El resultado principal de este cap´ıtulo es el Teorema 2.30, que establece que una concatenaci´on de orden n de k caminos es (n+3 2(k2−3k) + 5)- inevitable. Para probarlo, primero veremos que es posible restringirnos a concatenaciones de caminos salientes, que en el caso m´as simple corresponden a garras. 2.1. Reducci´on a concatenaciones de caminos salientes En esta secci´on probaremos una generalizaci´on del siguiente lema: Lema 2.3 (Lema 1.3, [6]) Sean P un camino saliente de orden n1, Q un camino entrante de orden n2, T un torneo de orden al menos n1+n2yxun 19 v´ertice de T. Si xes origen de P y de Q en T, entonces xes origen de la concatenaci´on P∨Qen T. Notaci´on 2.4 Sea Runa concatenaci´on de caminos con origen x. Denotamos por ∗Ral digrafo R−x. Definici´on 2.5 Un camino es casi-ascendente si x1←x2yxi→xi+1 para cualquier 2≤i≤n−1. Lema 2.6 Sean R1una concatenaci´on de orden n1de caminos salientes, R2 una concatenaci´on de orden n2de caminos entrantes y T un torneo de orden al menos n1+n2. Si xes origen de R1y de R2en T, entonces xes origen de R1∨R2en T. Demostraci´on: Sea R1:= Wl i=1 PiyR2:= Wk j=1 Qj. Por dualidad, podemos suponer que d−(x)≥n2. Probaremos por inducci´on en k, el n´umero de caminos de R2, que cualquier origen xde R1en Ttal que d−(x)≥n2es origen de R1∨R2. Si k= 1 entonces R2=Q. Probaremos el resultado por inducci´on en l, el n´umero de caminos de R1.  Si l= 1, por el Lema 2.3 obtenemos el resultado.  Si l > 1, definimos qi:= |N−(x)∩Pi|,q:= |N−(x)∩(T−R1)|y R0 1:= Wl−1 i=1 Pi. ◦Si q+q1+q2+· · · +ql−1≥ |Q|, entonces d− T−∗Pl(x)≥ |Q|. Por tanto, xes origen de R0 1∨Qen T−∗Plpor hip´otesis de inducci´on. As´ı que xes origen de R1∨Q. Podemos suponer, por lo tanto, que ql6= 0. ◦Si b1(Q)≥2, sea Q0un camino entrante dirigido de longitud q+q1+q2+· · ·+ql−1. Claramente, xes origen de Q0en T−∗Pl, porque su grado de entrada (d−(x)) es q+q1+q2+· · · +ql−1. Por hip´otesis de inducci´on, en T−∗Pl,xes origen de R0 1∨Q0. Por tanto, en T−∗R0 1, tenemos d−(x)≥2 (un vecino entrante en ∗Q0y uno en N−(x)∩Pl) y s−(x)≥q+q1+q2+· · · + ql−1+ql≥n2. Por tanto, por el Corolario 1.48, xes origen de Qen T−∗R0 1. Y como xes origen de Pl, por el Lema 2.3, x es origen de Pl∨Q. Por tanto, xes origen de R1∨Qen T. ◦Si b1(Q) = 1, sea Q0un camino casi-ascendente de longitud q+q1+q2+· · ·+ql−1. Por hip´otesis de inducci´on, en T−∗Pl,x es origen de R0∨Q0. Por tanto, en T−∗R0 1, tenemos d−(x)≥2 20 ys+(N−(x)) ≥q+q1+q2+· · · +ql−1+ql−1≥n2−1. As´ı, por el Corolario 1.48, xes origen de Q en T−∗R0 1y, como x es origen de Pl, por el Corolario 1.48, xes origen de Pl∨Q. Luego, xes origen de R1∨Qen T. Si k≥2, sea R0 2:= Wk−1 j=1 Qj. Por el caso anterior, xes origen de R1∨Qk en T. En T−∗Qk,xes origen de R1yd−(x)≥ |R2|−|∗Qk|=|R0 2|. As´ı, por hip´otesis de inducci´on, xes origen de R1∨R0 2en T−∗Qk. Luego, xes origen de R1∨R2en T.  Aplicando este lema, probaremos el siguiente lema, que nos ser´a de gran utilidad. Lema 2.7 Sean R1una concatenaci´on de orden n1de caminos salientes tal que todo torneo de orden f1(n1)contiene a1or´ıgenes de R1yR2una concatenaci´on de orden n2de caminos entrantes tal que todo torneo de orden f2(n2)contiene a2or´ıgenes de R2. Se tiene que, R=R1∨R2es m-inevitable, donde m=max{f1(n1) + f2(n2)−a1−a2+ 1; n1+n2}. En particular, si R1es (n1+l1)-inevitable y R2es (n2+l2)-inevitable con l1+l2≥1, entonces Res (n1+n2+l1+l2−1)-inevitable. Demostraci´on: Consideramos Tun torneo de orden m. Sea O1el conjunto de v´ertices de Tque son or´ıgenes de R1en T. Supongamos, por reducci´on al absurdo, que |O1|< m −f1(n1) + a1y tomamos k=|T−O1| − f(n1) + a1. Sea O2un subconjunto de a1−kv´ertices de O1si k < a1y el conjunto vac´ıo, en otro caso. Observemos que |O2|< a1si k≥1. Ahora en T−(O1−O2) hay al menos a1or´ıgenes de R1. As´ı, uno de ellos no est´a en O2y, por lo tanto, no est´a en O1. Esto contradice la definici´on de O1. As´ı que hay m−f1(n1) + a1or´ıgenes de R1en T. Del mismo modo, hay m−f2(n2)+a2or´ıgenes de R2en T. Si m≥f1(n1)+f2(n2)−a1−a2+1, hay un v´ertice xque es origen de R1y de R2. Por el Lema 2.6, si m≥n1+n2, xes origen de R1∨R2en T. Este lema nos permite limitar nuestro estudio a concatenaciones de caminos salientes. En efecto, si probamos que cada concatenaci´on de orden n1de k1caminos salientes es (n1+l(k1))-inevitable, para cualquier funci´on l, por dualidad tendremos que, toda concatenaci´on de orden n2de k2caminos entrantes es (n2+l(k2))-inevitable. Por el Lema 2.7, la concatenaci´on de orden n de k1caminos salientes y k2caminos entrantes es (n+l(k1)+l(k2))-inevitable. Del Lema 2.7 se deducen directamente los siguientes corolarios: 21 Corolario 2.8 La concatenaci´on de orden n de dos caminos salientes y un camino entrante es (n+ 1)-inevitable. Demostraci´on: Sea R=P1∨P2∨P3con P1yP2dos caminos salientes de orden n1yn2yP3un camino entrante de orden n3. El Corolario 1.47 establece que en cada torneo de orden n3+ 1 hay dos or´ıgenes de P3. Por otra parte, P1∨P2es un camino de orden n1+n2−1 y, por tanto, es (n1+n2)-inevitable por el Corolario 1.47, en otras palabras, hay un origen de P1∨P2en todo torneo de orden n1+n2. Finalmente, del Lema 2.7 se deduce el resultado.  La cota n+ 1 de este lema es la mejor posible: un torneo reducible de orden nen el que la componente fuerte maximal es un 3-ciclo, no contiene la concatenaci´on P1∨P2∨P3, donde P1yP2son caminos salientes de longitud 1 y P3un camino entrante dirigido de longitud n−3. Ejemplo 2.9 Sea Tel siguiente 5-torneo 1 2 3 4 5 T Su componente fuerte maximal es el 3-ciclo definido por los v´ertices C= {1,2,5}ya que T−C−→ C. Consideremos la concatenaci´on P1∨P2∨P3, donde P1yP2son caminos salientes de longitud 1 y P3un camino entrante dirigido de longitud 2. Observamos que los v´ertices 1, 2 y 5 no pueden ser el origen de la concatenaci´on, ya que no hay dos caminos salientes con origen en uno de ellos. Si 22 consideramos el v´ertice 3 como el origen de la concatenaci´on, el ´unico camino entrante que tiene es el que proviene del v´ertice 4. Por tanto, podemos identificar el siguiente v´ertice del camino entrante con el v´ertice 4. Observamos que dicho v´ertice no tiene ning´un camino entrante, por lo que no podemos identificar el siguiente v´ertice, llam´emoslo x, con ninguno. 3 4 x Tampoco podemos considerar el v´ertice 4 como origen de la concatenaci´on, ya que no tiene ning´un camino entrante. Por tanto, T no contiene la concatenaci´on P1∨P2∨P3. Corolario 2.10 Una concatenaci´on de orden n≥14 de dos caminos salientes y dos caminos entrantes es (n+1)-inevitable. Demostraci´on: Sea R=P1∨P2∨Q1∨Q2con P1yP2dos caminos salientes y Q1yQ2dos caminos entrantes. Sea R1=P1∨P2yR2=Q1∨Q2y sean n1el orden de R1yn2el orden de R2. Tenemos n1+n2=n+1. Al ser n≥14 y por dualidad, podemos suponer que n1≥8. Entonces, por el Teorema 1.49, R1 es n1-inevitable, y por el Corolario 1.47, R2es (n2+ 1)-inevitable. Aplicando el Lema 2.7 se deduce el resultado.  La cota n+ 1 de este lema es la mejor posible: un torneo reducible de orden nen el que la componente fuerte maximal es un 3-ciclo, no contiene la concatenaci´on P1∨P2∨Q1∨Q2, donde P1yP2son dos caminos salientes de longitud 1 y Q1yQ2son dos caminos entrantes dirigidos de orden n3y n4, respectivamente, con n3+n4=n−1. Ejemplo 2.11 Consideremos el siguiente 14-torneo 23 Demostraci´on: Sea R1:= Wk1 i=1 PiyR2:= Wk2 i=1 Qi, y n1yn2sus ´ordenes respectivos. Sea Tun torneo de orden n+ 3h(k1) + 2k2−5, T0un subtorneo de Tde orden n2+ 3h(k1) + 2k2−5 y T00 el torneo T−T0. Consideremos los v´ertices xi, 1 ≤i≤h(k1), tal que xies origen de un ´arbol generador casi-adecuado Aien T−[x1,· · · , xi−1]. Aplicando la Proposici´on 2.27, xies origen de un ´arbol casi-adecuado de orden al menos (n2+ 2k2−2) en T0−[Sj6=ixj]. Por tanto, por el Lema 2.22, xies un origen de R2en T0−[Sj6=ixj]. Adem´as, T1=T[V(T00),Sh(k1) i=1 xi] tiene orden n1+h(k)−1. Por tanto, por el Lema 2.25, uno de los xi, digamos x1, es origen de R1en T1. Luego, x1es origen de R en T.  Con la ayuda de los cuatro lemas anteriores, podemos probar el siguiente resultado general para cualquier concatenaci´on de caminos salientes: Teorema 2.29 Una concatenaci´on de orden n de k caminos salientes es (n+ 3h(k−2) −1)-inevitable. Si h(k−2) = 1 2(k2−3k) + 2, este teorema, junto con el Lema 2.7, da lugar al siguiente resultado: Teorema 2.30 Una concatenaci´on de orden n de k≥3caminos es (n+ 3 2(k2−3k)+5)-inevitable. En particular, un ´arbol con tres hojas es (n+5)- inevitable. Ejemplo 2.31 Consideremos el siguiente ´arbol Acon tres hojas, de orden n= 5. a b c d e A Por el teorema anterior, es (n+5)-inevitable y vamos a mostrar que es posible encontrarlo en un 10-torneo concreto. Consideraremos el siguiente torneo T: 30 1 2 3 4 5 6 7 8 9 10 T Tendremos que comprobar que Aest´a contenido como subgrafo en el torneo T. Si identificamos, por ejemplo, el v´ertice 1de Tcon el v´ertice ade A, tendremos que elegir un v´ertice de N+(1) = {2,5,8,9}para identificarlo con el v´ertice bde A. Probaremos a tomar bcomo el v´ertice 2de T. De igual forma, deberemos escoger un v´ertice de N−(2) = {1,3,5,6,8,10}para tomarlo como c, pero el 1ya est´a identificado con a, as´ı que no podremos elegirlo. Escogeremos el v´ertice 3por ejemplo. Por ´ultimo, para identificar d yetendremos que elegir dos v´ertices de N−(3) = {5,7,8,10}. Identificaremos dcon 5yccon 7. Por tanto, nos quedar´a: a= 1, b = 2, c = 3, d = 5, e = 7 Representaremos el ´arbol A, en rojo, contenido como subgrafo del torneo T: 31 b= 2 c= 3 4 d= 5 6 e= 7 8 9 10 T a= 1 32 Cap´ıtulo 3 El m´etodo de H¨aggkvist y Thomason El enfoque de H¨aggkvist y Thomason pretende establecer una cota superior en f(n) por inducci´on. Su m´etodo para encontrar un ´arbol Aen un torneo Tconsiste, en primer lugar, en encontrar el p-coraz´on hp(A) de A en el subtorneo inducido por los v´ertices con grados de salida y de entrada suficientemente grandes. En segundo lugar, por hip´otesis de inducci´on, se encontrar´ıan las componentes de A−hp(A) en el subtorneo correspondiente, estas componentes est´an unidas en Ta las hojas de hp(A) formando A. Definici´on 3.1 Sea A1un sub´arbol de un ´arbol A. Denotamos por A+(A1) (resp. A−(A1)), el bosque uni´on de las componentes del bosque A−A1que est´a unido positivamente (resp. negativamente) a A1, i.e. el conjunto de los sub´arboles maximales A2de A−A1para el cual existe x∈A1ey∈A2tal que xdomina a (resp. es dominado por) yen A. Ejemplo 3.2 Consideremos el ´arbol Arepresentado a continuaci´on: A 1 2 3 4 5 6 7 9 10 11 12 8 33 Si consideramos el sub´arbol A1formado por las aristas (3,2) y(4,2). 3 2 4 A1 Tenemos que A−A1es lo siguiente: A−A1 1 5 6 7 9 10 11 12 8 Sabemos que: A+(A1): bosque uni´on de los A2tales que existe x∈A1ey∈A2tal que x−→ y. A−(A1): bosque uni´on de los A2tales que existe x∈A1ey∈A2tal que y−→ x. Luego, A−(A1)es el bosque formado por la uni´on de los v´ertices 1 y 7, ya que est´an unidos negativamente a A1.A+(A1)es el resto de las componentes de A−A1, ya que est´an unidas positivamente a A1: 1 5 6 7 9 10 11 12 8 A−(A1) A+(A1) 34 Definici´on 3.3 Sea pun entero mayor que dos. El p-coraz´on hp(A)de un ´arbol Ade orden nes el sub´arbol generado por aquellas aristas e∈E(A)para las que cada una de las dos componentes de A−etienen orden al menos n/p. Observaci´on 3.4 Si no existen tales aristas, hp(A)denotar´a el ´unico v´ertice de Acuya eliminaci´on deja componentes de orden menor que n/p. N´otese que hp(A)es conexo, por lo que es un ´arbol. Adem´as, hp(A)tiene a lo sumo p−1 hojas. De hecho, la eliminaci´on en Ade una arista de hp(A)adyacente a una hoja lde hp(A)deja una componente de orden al menos n/p cuya intersecci´on con hp(A)es l. Por tanto, si hp(A)tiene khojas, hp(A)es de orden a lo sumo n−kdn/pe+k. Obs´ervese adem´as, que todas las componentes de A−hp(A) son de orden menor que n/p, esto es, de orden a lo sumo dn/pe − 1. Ejemplos 3.5 1. Consideremos el ´arbol Adel ejemplo anterior: A 1 2 3 4 5 6 7 9 10 11 12 8 Tenemos que Aes un ´arbol de orden n= 12. Si queremos encontrar el 3-coraz´on, debemos considerar las aristas e∈E(A)para las que ambas componentes de A−etengan orden al menos 4. Las aristas que cumplen esta condici´on son (3,2) y (4,2). Luego, el 3-coraz´on de A,h3(A), lo representamos en rojo: 35 A 1 2 3 4 5 6 7 9 10 11 12 8 2. Veamos ahora un ´arbol donde no exista p-coraz´on. Consideremos el siguiente ´arbol A: 1 2 3 4 5 6 7 8 9 10 11 12 A Tenemos que Aes un ´arbol de orden n= 12. Si queremos encontrar el 3-coraz´on, debemos considerar las aristas e∈E(A)para las que ambas componentes de A−etengan orden al menos 4. Observamos que ninguna arista cumple esta condici´on. Luego, el 3-coraz´on de A denotar´a el ´unico v´ertice cuya eliminaci´on deja componentes de orden menor que n/p = 12/3 = 4. Por tanto, el 3-coraz´on ser´a el v´ertice 4. Veamos ahora si existe el 4-coraz´on. Debemos considerar las aristas e∈E(A)para las que ambas componentes de A−etengan orden al menos n/p = 12/4 = 3. Las aristas que cumplen esta condici´on son 36 (4,2) y (4,6). Luego, el 4-coraz´on de A,h4(A), lo representamos en rojo: 1 2 3 4 5 6 7 8 9 10 11 12 A Para calcular el 5-coraz´on, debemos considerar las aristas e∈E(A) para las que ambas componentes de A−etengan orden al menos n/p = 12/5=204, es decir, de orden al menos 3. Por lo que tenemos que el 5-coraz´on coincide con el 4-coraz´on. Calculemos su 6-coraz´on. Para ello, tenemos que considerar las aristas e∈E(A)para las que ambas componentes de A−etengan orden al menos n/p = 12/6 = 2. Las aristas que cumplen esta condici´on son (4,2), (4,5), (4,6), (6,10) y (4,7). Luego, el 6-coraz´on de A,h6(A), lo representamos en rojo: 37 1 2 3 4 5 6 7 8 9 10 11 12 A Observaci´on 3.6 Podemos observar en los ejemplos anteriores que hp(A) tiene a lo sumo p−1hojas. En el primer ejemplo, h3(A)tiene 2hojas. En el segundo, h4(A)yh5(A) tienen 2hojas, y h6(A)tiene 4hojas. Como el p-coraz´on tiene pocas hojas, el objetivo, siguiendo el enfoque de H¨aggkvist y Thomason, es encontrar funciones (peque˜nas) αk(n) tal que todo ´arbol de orden ncon khojas sea αk(n)-inevitable. Para garantizar que los v´ertices del torneo que constituyen el p-coraz´on tengan grados de entrada y de salida grandes, consideramos el siguiente resultado. Proposici´on 3.7 Sea Tun torneo. A lo sumo 2k−1v´ertices de T tienen grado de salida menor que k. Demostraci´on: Sea nel orden de Ty supongamos que s1≤s2≤ · · · ≤ sn−1≤sn es la sucesi´on de los grados de salida de los v´ertices de T. Para cada k≥1, sea ikel mayor ital que si< k, tenemos que probar que ik≤2k−1. Por reducci´on al absurdo, supongamos que ik<2k−1, es decir; que existen al menos 2k v´ertices con grado de salida menor que k, o equivalentemente, con grado de salida menor o igual a k−1. Entonces tenemos que s1+s2+· · · +s2k≤2k(2k−1). 38 Por otra parte, aplicando el Teorema 1.27, tenemos que s1+s2+· · · +s2k≥2k 2=k(2k−1). Uniendo las dos desigualdades llegamos a una contradicci´on. Por tanto, ik≤ 2k−1, como quer´ıamos probar.  Supongamos que, para 2 ≤k≤p, existe una funci´on αk(n) tal que todo ´arbol con khojas es αk(n)-inevitable. Supongamos tambi´en que cualquier ´arbol de orden m<nes α(m)-inevitable. Entonces pretendemos encontrar condiciones para α(n) que garanticen que los ´arboles de orden nsean α(n)- inevitables. Sea Aun ´arbol de orden n,hp(A) su p-coraz´on y kel n´umero de hojas de hp(A). El orden tde hp(A) es a lo sumo n−kdn/pe+k. Sean a+ya−los ´ordenes de A+(hp(A)) y A−(hp(A)). Por dualidad, podemos suponer que a+≤a−. Como a++a−=n−t, tenemos a+≤(n−t)/2 Vamos a demostrar que podemos encontrar Aen un torneo si y solo si encontramos αk(t) v´ertices vtales que d+(v)≥t−1 + a++α(n/p)−n/p (3.1) y d−(v)≥t−1 + a++a−+α(n/p)−n/p. (3.2) En el subtorneo inducido por los αk(t) v´ertices que satisfacen las desigualdades de arriba, podemos encontrar hp(A). Sea A+ 1, A+ 2,· · · , A+ rlas componentes unidas positivamente a hp(A) y a1, a2,· · · , arlos v´ertices de hp(A) que est´an unidos a ellas, respectivamente. Construiremos las componentes A+ jsucesivamente. Queremos encontrar A+ jen el subtorneo inducido por los z∈N+(aj) que no est´an en el ´arbol ya construido: hp(A)∪S1≤l<j A+ l. Como |A+ j|< n/p < n, por hip´otesis de inducci´on, podemos encontrar A+ jen todo torneo de orden α(|A+ j|). Para garantizar la existencia de un sub´arbol A+ j, unido correctamente a hp(A), es suficiente que ajtenga grado de salida al menos t−1+P1≤l<j |A+ l|+α(|A+ j|). Lo que se obtiene de la condici´on (3.1), al ser P1≤l≤r|A+ l|=a+y|A+ j|< n/p. Sea A− 1, A− 2,· · · , A− slas componentes unidas negativamente a hp(A) y b1, b2,· · · , bslos v´ertices de hp(A) que est´an unidos a ellas, respectivamente. Construiremos las componentes A− msucesivamente. Queremos encontrar A− men el subtorneo inducido por los z∈N+(bj) que no est´an en el ´arbol ya construido: hp(A)∪S1≤l≤rA+ l∪S1≤l<m A− l. Como |A− m|< n/p < n, 39