UNIVERSIDAD DE CHILE ´ FACULTAD DE CIENCIAS F´ISICAS Y MATEMATICAS ´ ´ DEPARTAMENTO DE INGENIERIA MATEMATICA

´ MAS ´ VARIANTES ALEATORIAS DE LA SUBSECUENCIA COMUN GRANDE

´ SOTO SAN MART´IN JOSE

2006

UNIVERSIDAD DE CHILE ´ FACULTAD DE CIENCIAS F´ISICAS Y MATEMATICAS ´ ´ DEPARTAMENTO DE INGENIERIA MATEMATICA

´ MAS ´ GRANDE VARIANTES ALEATORIAS DE LA SUBSECUENCIA COMUN

´ SOTO SAN MART´IN JOSE

´ EXAMINADORA COMISION

CALIFICACIONES: ◦

NOTA (n )

PROFESOR GU´IA SR. MARCOS KIWI

:

PROFESOR CO-GU´IA SR. MART´IN MATAMALA

:

PROFESOR INTEGRANTE SR. MARTIN LOEBL

:

NOTA FINAL EXAMEN DE T´ITULO

:

(Letras)

MEMORIA PARA OPTAR AL T´ITULO DE ´ INGENIERO CIVIL MATEMATICO

SANTIAGO - CHILE JULIO - 2006

FIRMA

RESUMEN DE LA MEMORIA PARA OPTAR AL T´ITULO DE ´ INGENIERO CIVIL MATEMATICO ´ SOTO SAN MART´IN POR: JOSE FECHA: 13 DE JULIO DE 2010 PROF. GU´IA: SR. MARCOS KIWI

´ MAS ´ GRANDE VARIANTES ALEATORIAS DE LA SUBSECUENCIA COMUN El problema de la subsecuencia com´ un m´ as grande (LCS por sus siglas en ingl´es: longest common subsequence) es un problema combinatorio que surge naturalmente en distintas aplicaciones pr´ acticas, como b´ usqueda de patrones en mol´eculas de ADN, alineamiento de prote´ınas, comparaci´ on de archivos, etc. El objetivo general de este trabajo de t´ıtulo es estudiar algunos aspectos de la distribuci´ on del largo de la subsecuencia com´ un m´ as grande de varias palabras, cuando sus letras han sido escogidas de manera aleatoria. Se presenta un marco hist´ orico sobre el problema. Se generalizan resultados de Chv´ atal y Sankoff [12] y de Alexander [9] concernientes al comportamiento asint´ otico del largo esperado de la LCS de dos palabras al caso de varias palabras. En particular, se prueba que para toda ley de probabilidad µ sobre un alfabeto fijo, el largo esperado normalizado de la LCS de varias palabras, cuyas letras son escogidas de acuerdo a µ, tiende a una constante y se da una estimaci´ on para la velocidad de convergencia. A continuaci´ on se muestran algunas cotas num´ericas encontradas para esta constante para el caso en el que µ es la distribuci´ on uniforme sobre un alfabeto peque˜ no y se muestra una aplicaci´ on de estas cotas para refutar una conjetura de Steele [8] que data de los ochenta. Se presenta adem´ as un problema m´ as general denominado problema del subhipergrafo mon´ otono m´ as grande y un resultado que relaciona este problema con el problema de la secuencia creciente m´ as larga de varias permutaciones. Este resultado prueba y extiende, al caso de varias palabras, una conjetura de Sankoff y Mainville recientemente demostrada por Kiwi, Loebl y Matouˇsek [7] referente al comportamiento asint´ otico del largo esperado de la LCS de dos palabras cuando el tama˜ no del alfabeto se va a infinito. Finalmente se estudian algunas variantes de este problema y se generalizan los resultados obtenidos a dichas variantes.

iii

Agradecimientos Quiero agradecer a mis padres y hermanos por el apoyo incondicional que me han brindado en todas las metas que he trazado en la vida y en las que vendr´ an y por todo el cari˜ no que me han entregado siempre. Aprovecho de agradecer a Giannina, una persona muy especial para m´ı, no s´ olo por su incuestionable afecto sino tambi´en por su alegr´ıa y comprensi´ on en esta etapa de cambios importantes, tanto en lo personal como en lo profesional. Expreso mi agradecimiento a mi profesor gu´ıa, Sr. Marcos Kiwi, por su apoyo y confianza permanentes, as´ı como por todo su valiosa ayuda en mi desarrollo acad´emico. Menci´on aparte merecen su disposici´ on, consejos y tiempo invertidos durante el desarrollo de esta memoria, los cuales sin lugar a dudas posibilitaron una mejor realizaci´on de la misma. Asimismo agradezco a los profesores integrantes de la comisi´ on por su tiempo e inter´es en la tem´ atica propuesta, y a todos los profesores y acad´emicos que me guiaron durante la realizaci´ on de mis estudios superiores. En estas l´ıneas, no quisiera dejar de mencionar a mis amigos y compa˜ neros, no s´ olo por todos los gratos momentos junto a ellos sino tambi´en por su valioso apoyo y compa˜ n´ıa. Finalmente quiero agradecer a Conicyt via FONDAP en Matematicas Aplicadas y al proyecto Anillo en Redes ACT08 por el financiamiento otorgado.

iv

´Indice general

1. Introducci´ on

1

1.1. Organizaci´ on del trabajo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2. Preliminares

2 4

2.1. Comportamiento asint´ otico del largo esperado de la LCS . . . . . . . . . . . . . . . .

4

2.2. La subsecuencia diagonal m´ as grande. Estimaci´ on de la velocidad de convergencia del largo normalizado de una LCS . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

3. Cotas inferiores para las constantes de Chv´ atal y Sankoff

15

3.1. Una cota inferior simple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

3.2. Una mejor cota inferior . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

3.2.1. Subsecuencia com´ un m´ as larga entre dos palabras en un alfabeto binario . . .

17

3.2.2. Subsecuencia com´ un m´ as larga de varias palabras en un alfabeto binario . . .

19

3.2.3. Encontrando una cota inferior . . . . . . . . . . . . . . . . . . . . . . . . . . .

22

3.2.4. Implementaci´ on y cotas obtenidas . . . . . . . . . . . . . . . . . . . . . . . .

24

3.2.5. Extensiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

3.3. Aplicaci´ on: Conjetura de Steele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

4. Problema del subhipergrafo mon´ otono de tama˜ no m´ aximo 4.1. Subhipergrafo mon´ otono de tama˜ no m´ aximo

v

. . . . . . . . . . . . . . . . . . . . . .

28 29

´INDICE GENERAL

4.2. Aproximaci´ on de la mediana. Teorema Principal . . . . . . . . . . . . . . . . . . . .

31

4.3. Demostraci´ on de las cotas inferiores en el Teorema Principal . . . . . . . . . . . . . .

34

4.4. Demostraci´ on de la cotas superiores en el Teorema Principal . . . . . . . . . . . . . .

40

4.4.1. Notaci´ on y definiciones

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

40

4.4.2. Demostraci´ on para el caso N < tβ . . . . . . . . . . . . . . . . . . . . . . . .

41

4.4.3. Demostraci´ on para el caso N ≥ tβ . . . . . . . . . . . . . . . . . . . . . . . .

42

4.4.4. Demostraci´ on de la cota superior para la esperanza y mediana . . . . . . . .

50

4.5. Resultado para el modelo de d palabras aleatorias

. . . . . . . . . . . . . . . . . . .

52

4.5.1. Problema de la secuencia creciente m´ as larga o problema de Ulam . . . . . .

52

4.5.2. Reducci´ on al problema de Ulam . . . . . . . . . . . . . . . . . . . . . . . . .

53

4.5.3. Aplicaci´ on del Teorema Principal al modelo de d-palabras aleatorias . . . . .

54

4.6. Resultado para el modelo binomial . . . . . . . . . . . . . . . . . . . . . . . . . . . .

60

5. Variantes sim´ etricas del problema de la LCS 5.1. Modelo sim´etrico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

66 66

5.1.1. Reducci´ on al problema de la secuencia creciente m´ as larga de una involuci´ on

69

5.1.2. Resultado para el modelo sim´etrico . . . . . . . . . . . . . . . . . . . . . . . .

70

5.2. Modelo antisim´etrico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

74

vi

Cap´ıtulo 1

Introducci´ on Dadas dos palabras s y t, diremos que s es una subsecuencia de t si la primera puede obtenerse a partir de la segunda borrando cero o m´ as letras sin cambiar la posici´ on relativa de las letras restantes. Dada una lista de d palabras no necesariamente distintas, (si )di=1 , llamaremos subsecuencia com´ un m´ as grande de todos ellas a toda subsecuencia com´ un de largo m´ aximo. El problema de encontrar una subsecuencia com´ un m´ as grande (LCS por sus siglas en ingl´es: longest common subsequence) de un conjunto de palabras es un problema combinatorio que surge cada vez que necesitamos buscar similitudes entre distintos textos. Una motivaci´ on importante a este problema nace del a´rea de la biolog´ıa molecular. Las mol´eculas de ADN pueden ser representadas como palabras en un alfabeto de 4 caracteres: {A, C, G, T } correspondientes a los nucle´ otidos presentes en la mol´ecula y, vistas como palabras, pueden constar de millones de caracteres. Calcular una LCS de varias secuencias de ADN nos da una buena idea de cuan similares son dichas mol´eculas. No s´ olo eso, en muchos casos, por ejemplo en los virus asociados a ciertas enfermedades, ´estas mol´eculas mutan con facilidad y ser´ıa importante conocer cual es el trozo de c´ odigo gen´etico que tienen en com´ un para poder entender como defenderse de nuevas mutaciones. Otro campo de aplicaci´ on importante es la comparaci´ on de archivos. Un ejemplo es el programa “diff” de Unix usado para comparar dos versiones diferentes del mismo archivo. Este programa funciona b´ asicamente considerando las l´ıneas de cada archivo como un car´ acter y luego calcula la LCS de dichos caracteres retornando las l´ıneas que no pertenecen a dicha subsecuencia. Otras aplicaciones en este campo incluyen la detecci´ on de plagio de textos o de c´ odigos fuentes de programas y el uso de control de versiones (CVS) para la creaci´ on de un software. El problema de encontrar una LCS entre una palabra de largo m y otra de largo n puede ser resuelto usando programaci´ on din´ amica en tiempo O(nm). El algoritmo fue originalmente propuesto por Wagner y Fischer [15] en los setenta y mejorado a lo largo de los a˜ nos. Una lista de mejoras a este algoritmo puede encontrarse en [3].

1

Cap´ıtulo 1: Introducci´ on

El caso general de encontrar una LCS de varias palabras de largo n1 , . . . , nd puede ser resuelto usando programaci´ on din´ amica en tiempo O(n1 · · · nd ). Sin embargo, si d no es fijo, el problema resulta ser NP-duro [16]. En esta memoria nos concentraremos en estudiar versiones aleatorias del problema de determinar el largo de una LCS. Principalmente se estudiar´ an algunos aspectos de la distribuci´ on del largo de la subsecuencia com´ un m´ as grande de varias palabras, cuando sus letras han sido escogidas de manera aleatoria dentro de un alfabeto conocido. Un primer paso para de este estudio es conocer como se comporta el largo esperado de la LCS de varias palabras al variar el largo de las mismas. Chv´ atal y Sankoff [1] en los setentas probaron que el largo de una LCS de dos palabras del mismo largo es asint´ oticamente lineal con respecto al largo de las palabras pero no fueron capaces de determinar la constante de proporcionalidad entre ambos largos. Esta constante depende del n´ umero de palabras y del tama˜ no del alfabeto del cual las letras son elegidas. A´ un en el caso m´ as simple de 2 palabras en un alfabeto binario dicha constante, denominado en la literatura como la constante de Chv´ atal y Sankoff, no ha podido ser determinada. Se han realizado muchos esfuerzos (ver [2, 3, 4, 5, 6]) para encontrar buenas cotas num´ericas para dicha constante, teniendo ninguna de ellas una forma cerrada. En los 80, Steele [8] conjetur´ o una relaci´ on algebraica entre la constante de Chv´ atal y Sankoff y su s´ımil para el caso de 3 palabras. Dicha relaci´ on no parece ser acertada y de hecho en los 90, Danˇc´ık [3] hace una demostraci´ on de la falsedad de una generalizaci´ on de esta conjetura, pero nada se ha dicho para el caso original. A principios de esta d´ecada, Kiwi, Loebl y Matouˇsek [7] demostraron una conjetura de Sankoff y Mainville [12] referente al comportamiento del radio cuando el tama˜ no del alfabeto tiende a infinito, relacionando con su demostraci´ on este problema con el problema de la secuencia creciente m´ as larga de una permutaci´ on, tambi´en conocido como problema de Ulam en dos dimensiones.

1.1.

Organizaci´ on del trabajo

El presente trabajo se encuentra dividido de la siguiente manera. En el Cap´ıtulo 2 presentaremos algo de nomenclatura y un marco sobre algunos resultados conocidos para el problema de la subsecuencia com´ un m´ as grande de dos palabras, los cuales extenderemos al caso de varias palabras. Espec´ıficamente, se probar´ a que para toda ley de probabilidad µ sobre un alfabeto fijo, el largo esperado normalizado de la LCS de varias palabras cuyas letras son escogidas de acuerdo a µ tiende a una constante y se dar´ a una estimaci´ on para la velocidad de convergencia. En el Cap´ıtulo 3 se estudiar´ a el m´etodo usado por Lueker [6] para encontrar cotas inferiores para la constante de Chv´ atal y Sankoff y se modificar´ a para ser aplicado al caso de varias palabras. Adem´ as se mostrar´ a una aplicaci´ on de estas cotas para refutar la conjetura de Steele [8]. En el Capitulo 4 se presentar´ a un problema m´ as general denominado problema del subhipergrafo

2

Cap´ıtulo 1: Introducci´ on

mon´ otono m´ as grande y un resultado que relaciona este problema con el problema de la secuencia creciente m´ as larga de varias permutaciones. Este resultado prueba y extiende, al caso de varias palabras, la conjetura de Sankoff y Mainville. Finalmente, en el Cap´ıtulo 5 se estudiar´ an algunas variantes de este problema y se extender´ an los resultados obtenidos a dichas variantes. El lector podr´ a encontrar al principio de cada capitulo una rese˜ na m´ as detallada de los principales resultados que se obtienen en cada uno.

3

Cap´ıtulo 2

Preliminares Decimos que una palabra s es una subsecuencia de una palabra t si la primera puede obtenerse a partir de la segunda borrando cero o m´ as letras sin cambiar la posici´ on relativa de las letras restantes. Dada una lista de d palabras no necesariamente distintas, (si )di=1 , llamamos subsecuencia com´ un m´ as grande de todos ellas a toda subsecuencia com´ un de largo m´ aximo. Adem´ as, en lo que sigue al n´ umero de palabras, d, lo llamaremos dimensi´ on del problema. En este cap´ıtulo estaremos interesados en estudiar el comportamiento del largo de una LCS de d palabras cuando sus letras son elegidas de manera aleatoria de un alfabeto fijo. Espec´ıficamente mostraremos que el largo esperado de dicha subsecuencia, normalizado por el largo de las palabras originales, converge a una constante y daremos una estimaci´ on para la velocidad de convergencia hacia esa constante.

2.1.

Comportamiento asint´ otico del largo esperado de la LCS

Un primer paso para estudiar la distribuci´ on del largo de la subsecuencia com´ un m´ as grande, es conocer el comportamiento del largo esperado de dicha subsecuencia. En lo que sigue, denotaremos (d) por Ln,k (µ) al largo de una LCS de d palabras aleatorias de largo n, donde sus letras son elegidas independientes e id´enticamente distribuidas (i.i.d.) de un alfabeto Σ de tama˜ no k, siguiendo una ley de probabilidad µ. En general, µ ser´ a la distribuci´ on uniforme sobre Σ, y en este caso, para ahorrar (d) notaci´ on, llamaremos Ln,k a la variable aleatoria mencionada anteriormente. Adem´ as, en el caso bidimensional (d = 2), omitiremos el super´ındice d. Chv´ atal y Sankoff [1] iniciaron el estudio del comportamiento asint´ otico en n del largo esperado de una LCS de dos palabras cuyas letras son elegidas de manera uniforme sobre un alfabeto fijo. En nuestra nomenclatura, ellos probaron que:

4

Cap´ıtulo 2: Preliminares

Teorema 2.1. Para todo k ≥ 2, existe una constante γk,2 tal que γk,2 = l´ım

n→∞

ELn,k n

ELn,k

= sup

n

n>0

.

(2.1.1)

Daremos una demostraci´ on de la siguiente extensi´ on del teorema anterior al caso de d palabras elegidas bajo cualquier distribuci´ on de probabilidad µ: Teorema 2.2. Sea k ≥ 2 y Σ un alfabeto de tama˜ no k. Sea µ una distribuci´ on de probabilidad sobre Σ, entonces para todo d ≥ 2, existe γk,d (µ) tal que γk,d (µ) = l´ım

n→∞

EL(d) n,k (µ) n

= sup

N

n∈

EL(d) n,k (µ) n

.

(2.1.2)

En el caso que µ sea la distribuci´ on uniforme, denotaremos al l´ımite anterior simplemente γk,d . La constante γ2,2 es llamada com´ unmente en la literatura constante de Chv´ atal y Sankoff. Por extensi´ on, llamaremos constantes de Chv´ atal y Sankoff a la familia de constante γk,d (µ). El valor exacto de estas constantes, incluso para el caso uniforme, es desconocido. Chv´ atal y Sankoff [1] dieron las primeras cotas para el valor de γk,2 , para k peque˜ no. Para el caso de un alfabeto binario, nuevas cotas y t´ecnicas para encontrarlas fueron creadas posteriormente por Deken [2], Danˇc´ık y Paterson [3, 4], Baeza-Yates, Navarro, Gavald´ a y Scheihing [5] y Lueker [6]. Para demostrar el Teorema 2.2, basta probar que la cantidad decir basta probar el siguiente lema: Lema 2.3 (Superaditividad de

EL(d) n,k (µ) es superaditiva en n, es

EL(d) n,k (µ)). Para todo m, n ∈ N, m, n ≥ 1,

(d) (d) EL(d) n,k (µ) + ELm,k (µ) ≤ ELn+m,k (µ).

Demostraci´ on. Sea Σ un alfabeto fijo de tama˜ no k y µ una ley de probabilidad sobre Σ. Consideremos una secuencia s1 , s2 , . . . , sd de palabras de largo n y una secuencia t1 , t2 , . . . , td de palabras de largo m, cuyas letras son elegidas de acuerdo a µ. Es f´ acil ver que L(s1 , s2 , . . . , sd ) + L(t1 , t2 , . . . , td ) ≤ L(s1 t1 , s2 t2 , . . . , sd td ), pues la concatenaci´ on de cualquier LCS de (s1 , s2 , . . . , sd ) con una LCS de (t1 , t2 , . . . , td ) resulta ser una subsecuencia com´ un de (s1 t1 , s2 t2 , . . . , sd td ). Tomando esperanza, se concluye el resultado. 

2.2.

La subsecuencia diagonal m´ as grande. Estimaci´ on de la velocidad de convergencia del largo normalizado de una LCS

En esta secci´ on definiremos una noci´ on relacionada a la subsecuencia com´ un m´ as grande que (d) nos permitir´ a estimar cuan r´ apido converge ELn,k (µ)/n a γk,d y posteriormente, encontrar algunas cotas inferiores para γk,d . 5

Cap´ıtulo 2: Preliminares

Sean X e Y , dos palabras sobre un alfabeto Σ de largo al menos n. Denotemos X(i) a la subpalabra de los primeros i caracteres de X, (respectivamente Y (j) ser´ a la subpalabra de los primeros j caracteres de Y ). Denotemos por Dn (X, Y ) al largo de la subsecuencia com´ un m´ as larga de todos los pares de prefijos que podemos obtener de X e Y tal que el largo conjunto de dichos prefijos sea n. Es decir: Dn (X, Y ) = m´ ax{L(X(i), Y (j)) | i + j = n}. Siguiendo la nomenclatura usada por Danˇc´ık [3], llamaremos a esta cantidad el largo de la subsecuencia diagonal m´ as grande (DCS por sus siglas en ingl´es, diagonal common subsequence) entre X(n) e Y (n). (Cuando X e Y son palabras de largo n, entonces la denotamos simplemente largo de la DCS entre X e Y ). Adem´ as, denotaremos Dn,k (µ) a la variable aleatoria correspondiente al largo de la subsecuencia diagonal m´ as grande entre dos palabras de largo n cuyas letras son elegidas independientemente de acuerdo a una ley de probabilidad µ. Alexander [9] prob´ o una relaci´ on entre el comportamiento asint´ otico de la LCS de dos palabras aleatorias de largo n y el comportamiento asint´ otico de la DCS de dos palabras aleatorias de largo n. En nuestra notaci´ on, Alexander prob´ o el siguiente resultado: Proposici´ on 2.4. Existe una constante α tal que para todo n ∈ N, √ 2EDn,k (µ) − α n ln n ≤ ELn,k (µ) ≤ ED2n,k (µ). Adem´ as, para todo k positivo, la cantidad δk,2 (µ) = l´ım

n→∞

EDn,k (µ) n

est´ a bien definida, y de hecho δk,2 (µ) = γk,2 (µ)/2. El resultado anterior es importante pues permite, en el momento de estimar el largo esperado de una LCS de dos palabras, omitir la condici´ on de que ambas palabras involucradas tengan largo n. S´ olo basta que la suma de ambos largos sea 2n. Veremos que podemos extender este resultado al caso de d palabras. Para ello definamos primero el an´ alogo al largo de la subsecuencia diagonal m´ as grande en el caso d-dimensional. Sean X1 , . . . , Xd palabras sobre un alfabeto Σ de largo al menos n. Definamos Dn (X1 , X2 , . . . , Xd ), an´ alogamente al caso anterior como sigue: n

Dn (X1 , X2 , . . . , Xd ) = m´ ax L(X1 (i1 ), X2 (i2 ), . . . , Xd (id )) |

d X j=1

o ij = n .

Al igual que en el caso bidimensional, denotamos a esta cantidad la DCS de X1 (n), . . . , Xd (n). (d) Adem´ as, llamaremos Dn,k (µ) a la variable aleatoria correspondiente al largo de la subsecuencia diagonal m´as grande de d palabras de largo n cuyas letras son elegidas independientemente de acuerdo a una ley de probabilidad µ. Probaremos una proposici´ on similar a la probada por Alexander [9]. 6

Cap´ıtulo 2: Preliminares

Proposici´ on 2.5. Existe una constante α tal que para todo n ≥ 2, √ (d) (d) (d) d · EDn,k (µ) − d3/2 α n ln n ≤ ELn,k (µ) ≤ EDnd,k (µ). Adem´ as, para todo k positivo, y d ≥ 2, la cantidad δk,d (µ) = l´ım

n→∞

(d) EDn,k (µ)

n

est´ a bien definida, y de hecho δk,d (µ) = γk,d (µ)/d. Para probar esta proposici´ on, necesitaremos de la siguiente versi´ on de la desigualdad de Azuma [13]. Lema 2.6 (Desigualdad de Azuma). Sean Z1 , . . . , ZN variables aleatorias independientes, con todos los Zk tomando valores en un conjunto Λ. Sea X = f (Z1 , . . . , ZN ), con f : ΛN → R una funci´ on olo en una coordenada, entonces c-Lipschitz, es decir, una funci´ on tal que si z, z 0 ∈ ΛN difieren s´ |f (z) − f (z 0 )| ≤ c. Entonces, la variable X satisface para todo t ≥ 0,

P[X ≥ EX + t] ≤ e−2t /N c , 2 2 P[X ≤ EX − t] ≤ e−2t /N c . 2

2

Demostraci´ on Proposici´ on 2.5. Sea (Xi )di=1 , una secuencia de d palabras de largo n. Notemos que si cambiamos un car´ acter de alguna de las palabras Xi , entonces los valores de L(X1 , . . . , Xd ) y de (d) (d) Dn (X1 , . . . , Xd ) cambian en a lo m´ as 1. Es decir, Ln,k (µ) y Dn,k (µ) son 1-Lipschitz (vistos como funciones de Σdn en R). Es decir, se tienen las hip´ otesis de la desigualdad de Azuma para ambas cantidades. Luego,

P

"

(d) Dn,k (µ)

≤E

(d) Dn,k (µ)

−

Con esto, si denotamos λ = EDn,k (µ) − (d)

r

p

#   nd ln(2) 2(nd ln(2)/2) 1 ≤ exp − = . 2 nd 2

nd ln(2)/2,

h i 1 (d) ≤ P Dn,k (µ) > λ 2 = P [L(X1 (i1 ), . . . , Xd (id )) > λ, para alg´ un (i1 , . . . , id )] X ≤ P [L(X1 (i1 ), . . . , Xd (id )) > λ] . 0 λ,
L X1 [j1 + 1, j1 + jτ (1) ], . . . , Xd [jd + 1, jd + jτ (d) ] > λ, .. . "m−1 # " #! m m−1 m X X X X L X1 jτ l (1) + 1, jτ l (1) , . . . , Xd jτ l (1) + 1, jτ l (1) > λ, l=0

L X1

" d−2 X

l=0

jτ l (1) + 1,

l=0

d−1 X l=0

l=0

#

jτ l (1) , . . . , Xd

" d−2 X l=0

(B0 ) (B1 )

(Bm )

l=0

jτ l (1) + 1,

d−1 X

jτ l (1)

l=0

#!

.. .

> λ.

(Bd−1 )

tienen la misma probabilidad, son independientes (pues dependen de caracteres distintos) y adem´ as, si se cumplen simultaneamente, entonces L(X1 , . . . , Xd ) > dλ. Con esto:



1 2I

d

≤ (P(B0 ))d = P(B0 , B1 , . . . , Bd−1 ) ≤ P(Ln,k (µ) > dλ). (d)

Sin embargo, usando la desigualdad de Azuma obtenemos que: ! r    d d2 n ln(2I) 2d2 n ln(2I)/2 1 (d) (d) P Ln,k (µ) ≥ ELn,k (µ) + ≤ exp − = . 2 dn 2I

8

Cap´ıtulo 2: Preliminares

Como λ = E

(d) Dn,k (µ)

P

−

q

nd ln(2) , 2

se tiene, gracias a las dos desigualdades anteriores, que ! !! r r d2 n ln(2I) nd ln(2) (d) (d) (d) (d) Ln,k (µ) ≥ ELn,k (µ) + ≤ P Ln,k (µ) > d EDn,k (µ) − , 2 2

y luego, r d2 n ln(2I) nd ln(2) (d) > d · EDn,k (µ) − d . E 2 2
 e(n−1) d−1 Usando la desigualdad I = n−1 , y que ln(2) < 1 se concluye que: d−1 ≤ d−1 r r nd ln(2) d2 n(ln(2) + (d − 1) ln(e(n − 1)/(d − 1))) (d) (d) d · EDn,k (µ) − d < ELn,k (µ) + 2 2 r n(1 + (d − 1)(1 + ln(n))) (d) ≤ ELn,k (µ) + d 2 p (d) ≤ ELn,k (µ) + d nd ln(n), (d) Ln,k (µ) +

r

y luego usando que para n ≥ 2, ln(2) ≤ ln(n), s d·E

(d) Dn,k (µ)

Tomando α =

p

− d nd ln(n)



 1 (d) + 1 ≤ ELn,k (µ). 2

3/2, se concluye la primera desigualdad.

La segunda desigualdad se tiene pues para toda secuencia de d palabras X1 , . . . , Xd de largo nd, L(X1 (n), . . . , Xd (n)) ≤ Dnd (X1 , . . . , Xd ). Tomando esperanza se concluye. Demostremos la segunda parte de la proposici´ on. Por lo reci´en probado, para todo n, p (d) EL(d) EDnd,k (µ) EL(d) n,k (µ) nd,k (µ) + α nd ln(nd) ≤ ≤ . n n nd Lo anterior dice que el siguiente l´ımite existe e indica su valor: l´ım

n→∞

Por otro lado,

(d) EDnd,k (µ)

n

= γk,d (µ).

(2.2.1)

(d) EDn,k (µ) es no decreciente en n, luego,

bn/dc · n/d

(d) EDdbn/dc,k (µ)

bn/dc

≤

(d) EDn,k (µ)

n/d

≤

(d) EDddn/de,k (µ) dn/de

dn/de

·

n/d

.

Por (2.2.1), tanto el t´ermino de la izquierda como el de la derecha convergen a γk,d (µ), lo cual concluye la demostraci´ on.  9

Cap´ıtulo 2: Preliminares

Alexander [9] prob´ o adem´ as el siguiente teorema para estimar la velocidad de convergencia de

ELn,k (µ):

Teorema 2.7. Existe una constante A tal que para todo k, todo µ y n ≥ 1, γk,2 (µ)n ≥ ELn,k (µ) ≥ γk,2 (µ) − A(n log n)1/2 . Extenderemos este teorema al caso de d palabras, para ello necesitaremos probar dos lemas: Lema 2.8. Sean n, m ≥ 0. Luego para toda secuencia de d palabras, (Xi )di=1 , de largo al menos n + m y toda secuencia i1 , . . . , id tal que i1 + · · · + id = n + m,  L(X1 (j1 ), . . . , Xd (jd )) + L(X1 (i1 ), . . . , Xd (id ))) ≤ m´ ax 0≤jl ≤il ,l=1,...,d, j1 +j2 +···+jd =n

 L(X1 [j1 + 1, i1 ], . . . , Xd [jd + 1, id ] + 1 .

Demostraci´ on. Sea M = m1 . . . mN una subsecuencia com´ un de (X1 (i1 ), . . . , Xd (id )) de largo m´ ax(k) (k) (k) N on de cada car´ acter de imo. Denotemos c = (c1 , . . . , cN ) al vector de N que indica la posici´ (1) (d) M como subsecuencia de la palabra k-´esima y denotemos para cada 1 ≤ l ≤ N , el = (cl , . . . , cl ) la posici´on del l-´esimo car´ acter de M en cada palabra. Adem´ as, por conveniencia definamos e0 = (0, . . . , 0) y eN +1 = (i1 + 1, . . . , id + 1). Asignemos adem´ as a cada vector e ∈ Nd , su m´ odulo |e| definido como la suma de las componentes de e. Por ejemplo, si consideramos la LCS M = bbac, marcada con negrita en las siguientes palabras: X1 : X2 : X2 :

b c b

c b a

a b a

b a b

a a c

c a a

c c c

Entonces c1 = (1, 4, 5, 6), c2 = (2, 3, 4, 7) y c3 = (1, 4, 6, 7), y luego e0 = (0, 0, 0), e1 = (1, 2, 1), e2 = (4, 3, 4), e3 = (5, 4, 6), e4 = (6, 7, 7), e5 = (8, 8, 8). Notemos que los (el )0≤l≤N +1 son vectores en Nd que forman una cadena creciente con respecto al orden parcial natural de Nd , donde un vector es menor que otro si la desigualdad se tiene componente a componente. Llamemos ahora T al ´ındice del primer vector de la cadena (el )0≤l≤N +1 tal que |eT | ≥ n, y llamemos e¯ = (¯ e1 , . . . , e¯d ) a alg´ un vector de m´ odulo n menor o igual que eT y mayor o igual que eT −1 (componente a componente). Como |eT −1 | < n dicho vector existe. En el ejemplo anterior, si n fuera 13, entonces T ser´ıa 3 (pues e2 = (4, 2, 4) tiene m´ odulo 11 y e3 = (5, 4, 6) tiene m´odulo 15), y luego podemos definir e¯ como cualquier vector de m´ odulo 13 entre (4, 3, 4) y (5, 4, 6), por ejemplo e¯ = (4, 4, 5). Dividamos cada una de las palabras en dos subpalabras, las subpalabras formadas por los caracteres que est´ an antes de la posici´ on e¯ (incluido) y las subpalabras formadas por los caracteres 10

Cap´ıtulo 2: Preliminares

que est´ an despu´es de e¯ (sin incluir). Con esto, los caracteres asociados a eT −1 est´ an completamente contenidos en el primer bloque de subpalabras, y, para todo l ≥ T + 1, los caracteres asociados a el quedan completamente contenido en el segundo bloque de palabras. Sin embargo, al ser e¯ menor o igual componente a componente que eT , es posible que al hacer la divisi´ on, los caracteres asociados a eT queden separados. En nuestro ejemplo las palabras divididas quedan: X1 X2 X2 :

b c b

c b a

a b a

b a b

a a c

c a a

c c c

y luego uno de los alineamientos (el car´ acter a asociado a e3 = (5, 4, 6)) queda cortado. Con esto, el largo de la LCS del primer bloque, L(X1 (¯ e1 ), . . . , Xd (¯ ed )) resulta ser mayor o igual al numero de aristas de la cadena (exceptuando e0 ) que quedan en el primer bloque, es decir T − 1, y el largo de la LCS del segundo bloque, L(X1 [¯ e1 + 1, i1 ], . . . , Xd [¯ ed + 1, id ]) resulta ser mayor o igual al numero de las aristas de la cadena (exceptuando eN +1 ) que quedan en el segundo bloque, es decir, N − T . Por lo tanto,   m´ ax L(X1 (j1 ), . . . , Xd (jd )) + L(X1 [j1 + 1, i1 ], . . . , Xd [jd + 1, id ] + 1 0≤jl ≤il ,l=1,...,d, j1 +j2 +···+jd =n

≥ L(X1 (¯ e1 ), . . . , Xd (¯ ed ) + L(X1 [¯ e1 + 1, i1 ], . . . , Xd [¯ ed + 1, id ] + 1

≥ T − 1 + N − T + 1 = L(X1 (i1 ), . . . , Xd (id )).



Lema 2.9. Para n ≥ 1 y β > 0 se definen las funciones generatrices   X
gn (β) = ln E exp β[L(X1 (i1 ), . . . , Xd (id )) + 1] . 0≤i1 ,...,id , i1 +i2 +···+id =nd

Para todo β > 0, la secuencia {gn (β) : n ≥ 1} es subaditiva, es decir, gn+m (β) ≤ gn (β) + gm (β). Demostraci´ on. Por el lema anterior y la invarianza bajo traslaci´ on del valor esperado del largo de

11

Cap´ıtulo 2: Preliminares

una LCS, X

E exp (β[L(X1 (i1 ), . . . , Xd (id )) + 1])

0≤i1 ,...,id , i1 +i2 +···+id =d(n+m)

≤

≤

X

E exp β

0≤i1 ,...,id , i1 +i2 +···+id =d(n+m)



m´ ax

0≤jl ≤il ,l=1,...,d, j1 +j2 +···+jd =dn

! + L(X1 [j1 + 1, i1 ], . . . , Xd [jd + 1, id ]) + 2

X

X

X

X



E exp β L(X1 (j1 ), . . . , Xd (jd )) + 1

0≤i1 ,...,id , 0≤jl ≤il ,l=1,...,d, i1 +i2 +···+id =d(n+m) j1 +j2 +···+jd =dn

=

L(X1 (j1 ), . . . , Xd (jd ))

! + L(X1 [j1 + 1, i1 ], . . . , Xd [jd + 1, id ]) + 1

! E exp β L(X1 (j1 ), . . . , Xd (jd )) + 1

0≤i1 ,...,id , 0≤jl ≤il ,l=1,...,d, i1 +i2 +···+id =d(n+m) j1 +j2 +···+jd =dn



! · E exp β L(X1 [1, i1 − j1 ], . . . , Xd [1, id − jd ]) + 1 . 

Haciendo el cambio de variable r1 = i1 − j1 , . . . , rd = id − jd , lo anterior queda igual al producto  ! X E exp β L(X1 (j1 ), . . . , Xd (jd )) + 1 0≤j1 ,...,jd , j1 +j2 +···+jd =dn

·

X

0≤r1 ,...,rd , r1 +r2 +···+rd =dm

! E exp β L(X1 (r1 ), . . . , Xd (rd )) + 1 . 

Tomando logaritmo se concluye.



De los lemas anteriores podemos deducir el siguiente teorema de estimaci´ on de la velocidad de convergencia de ELn,d (µ): Teorema 2.10. Existe una constante A tal que para todo k, todo µ y n ≥ 2d, nγk,d (µ) ≥ ELn,d (µ) ≥ nγk,d (µ) − Ad2 (n log n)1/2 . Demostraci´ on. La primera desigualdad se tiene por superaditividad de ELn,d (µ). Para probar la segunda desigualdad primero acotaremos superior e inferiormente gn (β) y nos aprovecharemos de 12

Cap´ıtulo 2: Preliminares

que esta cantidad es subaditiva. Denotemos S al n´ umero de t´erminos que aparece en la suma corre
spondiente a la definici´ on de gn (·). Es decir, S = |{0 ≤ (i1 , . . . , id ) : i1 + · · · + id = nd}| = nd+d−1 . d
(d) Como todos los t´erminos de la suma son menores o iguales que E exp β[Dnd,k (µ) + 1] ,





(d) (d) E exp β[Dnd,k (µ) + 1] ) ≤ exp(gn (β)) ≤ S E exp β[Dnd,k (µ) + 1] ).

Usando la desigualdad de Jensen vemos que
(d) (d) gn (β) ≥ ln E exp β[Dnd,k (µ) + 1] ) ≥ β E[Dnd,k (µ) + 1]

y luego, por subaditividad de gn (·), se tiene,

EDnd,k (µ) + 1 gn (β) gn (β) ≥ l´ım ≥ l´ım = dδk,d (µ) = γk,d (µ). n n βn βn n (d)

Con lo cual, para todo β y todo n (notar que β puede depender de n), gn (β) ≥ nγk,d (µ). β (d)

on innecesaria, D = Dnd,k (µ), Ahora acotemos superiormente gn (β). Llamemos, para evitar notaci´ y sea ED < λ < n un valor a ser especificado m´ as tarde. Se tiene, h i h i E exp(βD) = E exp(βD)1{D≤λ} + E exp(βD)1{λ≤D≤n}   n Z n βλ βx ≤ e P[D ≤ λ] + −e P[D > x] + βeβx P[D > x]dx λ λ Z n βλ βx =e + βe P[D > x]dx. λ

Usando la desigualdad de Azuma, lo anterior es menor o igual que  −2(x − ED)2 βe exp e + dx nd2 λ   Z n −2[x − (ED + βnd2 /4)]2 βλ 2 =e +β exp + β(ED + βnd /8) dx nd2 λ   Z n −2[x − (ED + βnd2 /4)]2 βλ β(ED+βnd2 /4) ≤ e + βe exp dx. nd2 λ p Tomando λ = ED + βnd2 /4 y usando el cambio de variable z = 2/(nd2 )(x − λ), lo anterior es igual a r   Z n Z
−2[x − λ]2 nd2 ∞ βλ βλ βλ βλ e + βe exp dx ≤ e + βe exp −z 2 dz. 2 nd 2 0 λ βλ

Z

n

βx



13

Cap´ıtulo 2: Preliminares

Es decir, "

E exp(βD) ≤ exp(β ED + β nd /4) 1 + β 2

2

r

# nd2 π . 8

Luego, recordando la primera cota para gn (β) y que ln(1 + z) < z para todo z > 0,  

gn (β) ≤ ln S E exp β[D + 1] = ln Seβ E exp(βD) " #! r 2π nd ≤ ln S exp(β + β ED + β 2 nd2 /4) 1 + β 8 r nd2 π ≤ ln(S) + β + β ED + β 2 nd2 /4 + β . 8
 e(nd+d−1) d Usando la desigualdad S = nd+d−1 ≤ (e(n + 1))d < (nd)2d si n ≥ 2, la Proposi≤ d d ci´ on 2.5, y la cota inferior para gn (β), tenemos: p (d) 3/2 EL(d) α nd ln(nd) + d · EDnd,k (µ) nd,k (µ) ≥ −d ! r p gn (β) ln(S) nd2 π 2 2 ≥ −d α n ln(nd) + d − − 1 − βnd /4 − β β 8 ! r 2π p 2d ln(n) nd − 1 − βnd2 /4 − ≥ −d2 α n ln(nd) + d nγk,d (µ) − β 8 r   p nπ 2 ln(n) = dnγk,d (µ) − d2 α n ln(nd) − d2 + 1/d + βnd/4 + . β 8 p Finalmente como β lo podemos hacer depender de n, definamos β = ln(nd)/(nd) ≥ 0, con lo cual r   p p 1p nπ (d) 2 2 ELnd,k (µ) ≥ dnγk,d(µ) − d α n ln(nd) − d 2 nd ln(nd) + 1/d + nd ln(nd) + 4 8 p 2 ≥ dnγk,d (µ) − d nd ln(nd) (α + 3) . Con esto tenemos la cota buscada para todos los m´ ultiplos  de d mayores o iguales que 2d. Para extender esta cota notemos que para todo n ≥ 2d, n ≥ nd · d ≥ n2 . Con esto, por superaditividad

de

EL(d) en probado, nd,k (µ) y el resultado reci´ EL(d) n,k (µ) = n

EL(d) n,k (µ) n

≥n

EL(d) (µ) b n cd,k dn  d

d

q  n n nd2 (α + 3) d d ln( d d) n ≥ nγk,d (µ) − d d √ ≥ γk,d (µ) − 2(α + 1)d2 n ln n. 14



Cap´ıtulo 3

Cotas inferiores para las constantes de Chv´ atal y Sankoff En este cap´ıtulo mostraremos algunas cotas inferiores para las constantes de Chv´ atal y Sankoff. Daremos primero una cota inferior simple que no depende del n´ umero de palabras, sino expl´ıcitamente de la distribuci´ on µ con la que se eligen los caracteres de las palabras. Luego nos enfocaremos en acotar inferiormente las constantes correspondientes al caso en el que µ es la distribuci´ on uniforme sobre un alfabeto peque˜ no. Las mejores cotas conocida para el caso de 2 palabras elegidas uniformemente sobre un alfabeto binario, es decir, para la constante γ2,2 , fueron obtenidas hace algunos a˜ nos por Lueker [6]. Lueker prob´ o que 0,788071 ≤ γ2,2 ≤ 0,826280. En este cap´ıtulo extenderemos las Ideas y t´ecnicas usadas por Lueker para probar la cota inferior de γ2,2 , para poder encontrar nuevas cotas en el caso de d palabras.

3.1.

Una cota inferior simple

En esta secci´ on mostraremos una cota inferior para las constantes de Chv´ atal y Sankoff, γk,d (µ), que no depende de d. Para ello usaremos la siguiente versi´ on de la desigualdad de Chernoff [13, Remark 2.5]. Lema 3.1 (Desigualdad de Chernoff).PSean X1 , . . . , Xn , variables aleatorias independientes del tipo Bernoulli de par´ ametro p y sea X = ni=1 Xi . Entonces para todo t > 0,   −2t2 P(X ≤ np − t) ≤ exp . n 15

Cap´ıtulo 3: Cotas inferiores para las constantes de Chv´ atal y Sankoff

Para una palabra aleatoria de largo n suficientemente grande, el n´ umero de apariciones de un car´ acter σ fijo en dicha palabra es aproximadamente nµ(σ). Intuitivamente lo anterior quiere decir que si n es suficientemente grande y disponemos de d palabras aleatorias de largo n, la palabra formada por nµ(σ) caracteres ‘σ’ es, con alta probabilidad, una subsecuencia com´ un de todas las palabras. Veremos a continuaci´ on que lo anterior es cierto y que, por lo tanto podemos acotar inferiormente γk,d (µ) por la probabilidad de σ bajo µ para cualquier car´ acter σ del alfabeto. Proposici´ on 3.2. Para todo d ≥ 2, k ≥ 2 y toda distribuci´ on de probabilidad µ sobre un alfabeto Σ de tama˜ no k. γk,d (µ) ≥ m´ ax µ(σ). σ∈Σ

Demostraci´ on. Sea σ ∈ Σ un s´ımbolo del alfabeto. Tomemos S1 , . . . , Sd , palabras aleatorias de largo n sobre Σ elegidas independientemente bajo µ. Definamos Yi como el n´ umero de apariciones as 0 < ε < 1 y p = µ(σ). Por desigualdad de σ en la palabra Si e Y = m´ın {Y1 , . . . , Yd }. Sea adem´ de Markov, y de la definici´ on e independencia de los Yi tenemos que

E(Y ) ≥ np(1 − ε)P(Y ≥ np(1 − ε)) = np(1 − ε)P(∀1 ≤ i ≤ d, Yi ≥ np(1 − ε)) = np(1 − ε) [P(Y1 ≥ np(1 − ε))]d ≥ np(1 − ε) [1 − P(Y1 ≤ np(1 − ε))]d . Notemos ahora que Y1 es suma de las indicatrices asociadas a los eventos consistentes en que el j-´esimo car´ acter de Y1 sea σ. Dichas indicatrices son variables Bernoulli independientes de par´ ametro p. Luego, por el lema anterior, P(Y1 ≤ np − npε) ≤ exp(−2n(pε)2 ). Sigue que: 
 E(Y ) ≥ np(1 − ε) 1 − exp −2n(pε)2 d .   ! 1 1 − 2ε 1/d , se obtiene que: Tomando n suficientemente grande, digamos n ≥ − ln 1 − 2(pε)2 1−ε

E(Y ) ≥ np(1 − ε)



1 − 2ε 1−ε



= np(1 − 2ε).

Notemos ahora que por definici´ on de Y , cada palabra Si tiene al menos Y apariciones de σ, es decir, la palabra σ Y , que corresponde a la palabra de largo Y cuyos caracteres son todos iguales a σ, es una subsecuencia com´ un de S1 , . . . , Sd . Por lo tanto el largo de la subsecuencia com´ un m´as grande entre ellas debe ser mayor que Y . Es decir, L(S1 , . . . , Sd ) ≥ Y . Con esto,

EL(d) n,k (µ) n

=

E(L(S1 , S2 , . . . , Sd )) n

≥

E(Y ) n

≥ p(1 − 2ε) = µ(σ)(1 − 2ε).

Tomando l´ımite en n y luego haciendo tender ε a 0 se deduce que para todo σ, (d)

γn,k (µ) ≥ µ(σ). 16



Cap´ıtulo 3: Cotas inferiores para las constantes de Chv´ atal y Sankoff

Aplicando la proposici´ on anterior al caso de distribuci´ on uniforme se obtiene directamente el siguiente corolario. Corolario 3.3. Para todo d ≥ 2 y k ≥ 2, γk,d ≥

3.2.

1 . k

Una mejor cota inferior

En esta secci´ on aplicaremos la t´ecnica usada por Lueker [6] para encontrar cotas inferiores para el caso bidimensional en un alfabeto binario (con distribuci´ on uniforme) y la extenderemos al caso d-dimensional, lo que nos permitir´ a obtener cotas para γ2,d , para d peque˜ no. En la siguiente subsecci´ on daremos las definiciones usadas por Lueker para el caso de dos palabras.

3.2.1.

Subsecuencia com´ un m´ as larga entre dos palabras en un alfabeto binario

Sean X1 y X2 dos palabras aleatorias de largo n sobre un alfabeto binario cuyas letras son elegidas de manera uniforme. Para s y t, dos palabras fijas en dicho alfabeto, definimos   Wn (s, t) = E m´ ax L (sX1 (i), tX2 (j)) , (3.2.1) i+j=n

donde X(i) representa la subpalabra de los primeros i caracteres de X, y L(a, b) es, como antes, el largo de una subsecuencia com´ un m´ as larga entre a y b. Informalmente Wn (s, t) representa el largo esperado de una LCS entre dos palabras cuyos prefijos son s y t y cuyos sufijos consisten en total de n caracteres aleatorios. La Proposici´ on 2.4 mostrada en el cap´ıtulo anterior, referente a la subsecuencia diagonal m´ as larga, permite concluir que, sin importar s o t, γ2,2 = l´ım

n→∞

1 W2n (s, t). n

(3.2.2)

La idea es aproximar γ2,2 por W2n (s, t). Fijemos, para ello un l ∈ N, l ser´ a el largo de las 2l palabras s y t usadas. Llamemos wn al vector de 2 coordenadas cuyas componentes son todos los valores de Wn (s, t) cuando s y t var´ıan sobre todas las palabras de largo l. En adelante, todos los vectores que usaremos tendr´ an coordenadas indexadas por secuencias de palabras. Para evitar confusiones reservaremos la notaci´ on de par´entesis cuadrados para cuando queramos referirnos a una coordenada de un vector y par´entesis redondos para evaluaci´ on de funciones.

17

Cap´ıtulo 3: Cotas inferiores para las constantes de Chv´ atal y Sankoff

Por ejemplo wn tendr´ a 16 coordenadas si l = 2:    wn [00, 00]  wn [00, 01]         .. wn =  = .     wn [11, 10]   wn [11, 11]

Wn (00, 00) Wn (00, 01) .. .



   .  Wn (11, 10)  Wn (11, 11)

Lueker [6] estableci´ o una cota inferior para cada una de las componentes de wn en funci´ on 1 2 de wn−1 y wn−2 . Para poder ver dicha cota, introduzcamos la siguiente notaci´ on: Si s = s s . . . sl es una palabra de largo l ≥ 2, llamaremos I(s) (por inicio) a la primera letra de s y C(s) (por cola) a la subpalabra que queda al eliminar la primera letra de s, es decir: I(s) = s1 , C(s) = s2 . . . sl , y luego s = I(s)C(s). Con esto podemos encontrar f´ acilmente la siguiente relaci´ on entre wn , wn−1 y wn−2 .  Si I(s) = I(t), entonces:

wn [s, t] ≥ 1 +  Si I(s) 6= I(t), entonces:

wn [s, t] ≥ m´ ax

 1 X 2

1 4

c∈{0,1}

X

wn−2 [C(s)c, C(t)c0 ].

(3.2.3)

(c,c0 )∈{0,1}2

  X 1 wn−1 [C(s)c, t], wn−1 [s, C(t)c] .  2

(3.2.4)

c∈{0,1}

Usando las desigualdades anteriores es f´ acil definir una funci´ on T tal que para todo n ≥ 2 wn ≥ T (wn−1 , wn−2 ),

(3.2.5)

donde la desigualdad es componente a componente. M´ as a´ un, la funci´ on T se puede descomponer en dos funciones m´ as simples: T= y T6= , tales que, si Π= (w) (respectivamente Π6= (w)) es la proyecci´ on sobre las componentes que corresponden a los pares de palabras cuya primera letra coincide (respectivamente no coincide), entonces para todo n ≥ 2: Π= (wn ) ≥ T= (wn−2 ),

Π6= (wn ) ≥ T6= (wn−1 ).

(3.2.6) (3.2.7)

Antes de proceder a la generalizaci´ on a varias palabras, veamos un par de ejemplos. Si queremos calcular wn [001, 011], puesto que los caracteres iniciales coinciden, usaremos la transformaci´ on T= : wn [001, 011] ≥ T= (wn−2 )[001, 011]
1 = 1 + wn−2 [010, 110] + wn−2 [010, 111] + wn−2 [011, 110] + wn−2 [011, 111] . 4 18

Cap´ıtulo 3: Cotas inferiores para las constantes de Chv´ atal y Sankoff

Si queremos, en cambio, calcular wn [001, 111], como los caracteres iniciales difieren, usaremos la transformaci´ on T6= : wn [001, 111] ≥ T6= (wn−1 )[001, 111]  
1
1 = m´ ax wn−1 [010, 111] + wn−1 [011, 111] , wn−1 [001, 110] + wn−1 [001, 111] . 2 2

3.2.2.

Subsecuencia com´ un m´ as larga de varias palabras en un alfabeto binario

Podemos extender las definiciones de la subsecci´ on anterior f´ acilmente a d palabras de la siguiente manera: Sea X = (Xi )di=1 una colecci´ on de d palabras aleatorias de largo n sobre un alfabeto binario y sea S = (si )di=1 una colecci´ on de d palabras fijas en dicho alfabeto. Definimos   (d) m´ ax L (s1 X1 (i1 ), s2 X2 (i2 ), . . . , sd Xd (id )) . (3.2.8) Wn (s1 , . . . , sd ) = E i1 +i2 +...+id =n

Esta cantidad representa el largo esperado de una LCS entre d palabras de prefijos s1 , . . . , sd y sufijos consistentes en un total de n caracteres aleatorios repartidos en las d palabras. La Proposici´ on 2.5 referente a la subsecuencia diagonal m´as larga de varias palabras demostrada en el cap´ıtulo anterior, permite concluir que para toda secuencia de d palabras S = (si )di=1 : 1 (d) W (s1 , . . . , sd ). n→∞ n dn Por claridad, omitiremos en adelante el super´ındice d. γ2,d = l´ım

(3.2.9)

Al igual que en el caso de dos palabras descrito en la secci´ on anterior, fijemos un l ∈ N. Llamemos wn al vector de 2ld coordenadas, cuyas componentes son todos los valores de Wn (s1 , . . . , sd ) cuando on de la s1 , . . . , sd var´ıan sobre todas las secuencias de d palabras de largo l. Siguiendo la notaci´ subsecci´on anterior, definamos wn [s1 , . . . , sd ] = Wn (s1 , . . . , sd ). En el caso de dos palabras encontramos una funci´ on que permit´ıa establecer cotas para un on de los dos vectores wn−1 y wn−2 . Ahora necesitaremos d vectores. vector wn en funci´ Para S = (si )di=1 una secuencia de d palabras llamemos J0 (S) (respectivamente J1 (S)) a los ´ındices j en [d] = {1, . . . , d} tales que I(sj ) = 0 (respectivamente, tales que I(sj ) = 1). Usaremos adem´ as la notaci´ on J0 (S) = [d] \ J0 (S) = J1 (S) y J1 (S) = [d] \ J1 (S) = J0 (S) Es f´ acil ver que si las d palabras comienzan con el mismo car´ acter, es decir |J0 (S)| = d o´ |J1 (S)| = d, entonces 1 X wn [s1 , . . . , sn ] ≥ 1 + d wn−d [C(s1 )c1 , . . . , C(sd )cd ]. (3.2.10) 2 d ~c∈{0,1}

Informalmente, la desigualdad anterior dice que si todas las palabras de S comienzan con el mismo car´ acter, entonces el largo de la subsecuencia com´ un m´ as larga entre ellas (permitiendo 19

Cap´ıtulo 3: Cotas inferiores para las constantes de Chv´ atal y Sankoff

sufijos de n caracteres aleatorios) es al menos 1 (el car´ acter en que coinciden) m´ as el largo de la subsecuencia com´ un m´ as larga entre las palabras obtenidas al eliminar el primer car´ acter y tomar prestado d caracteres (los eliminados) de los n caracteres aleatorios. Si no todas las palabras comienzan con el mismo car´ acter tambi´en podemos encontrar una cota, pero para ello necesitaremos algo de notaci´ on extra. Dados A y B dos conjuntos, definimos AB como el conjunto de todas las funciones de B en A. Para una secuencia de d palabras S = (si )di=1 , y c ∈ {0, 1}J0 (S) una funci´ on a valores en {0, 1} definida en el conjunto de ´ındices i donde la palabra si no comienza con 0, definimos τ0 (S, c) a la traslaci´ on de S que mantiene los 0 iniciales y concatena c, es decir, a la secuencia de d palabras que resulta al cambiar cada palabra de S que no comience por 0 por la palabra que resulta al eliminar su primer car´ acter y concatenar, al final, el car´ acter correspondiente por c. Expl´ıcitamente,
d τ0 (S, c) = τ0 (S, c)i i=1 con τ0 (S, c)i =

(

si , C(si )c(i),

si i ∈ J0 (S), si i ∈ 6 J0 (S).

(3.2.11)

Similarmente, si c ∈ {0, 1}J1 (S) definimos τ1 (S, c) a la traslaci´ on de S que mantiene los 1 iniciales
d y concatena c. Es decir τ1 (S, c) = τ1 (S, c)i i=1 con τ1 (S, c)i =

(

si , C(si )c(i),

si i ∈ J1 (S), si i ∈ 6 J1 (S).

(3.2.12)

Usando la notaci´ on anterior, podemos ver que si S es una secuencia de d palabras tal que no todas comienzan con el mismo car´ acter (es decir, 0 < |J0 (S)| < d y luego 0 < |J1 (S)| < d). Entonces:

wn [S] ≥ m´ ax

 1    |J0 (S)|   2  1      2|J1 (S)|

X

wn−|J0(S)| [τ0 (S, c)],

X

wn−|J1(S)| [τ1 (S, c)].

c∈{0,1}J0 (S)

(3.2.13)

c∈{0,1}J1 (S)

Intuitivamente, el primer t´ermino del m´ aximo anterior representa el largo esperado de la LCS de las palabras que obtendr´ıamos al deshacernos de los caracteres 1 iniciales (buscando con esto que el primer alineamiento sea un 0) y concatenar en aquellas palabras uno de los n caracteres aleatorios. An´ alogamente, el segundo t´ermino representa lo que obtendr´ıamos al buscar que el primer alineamiento sea un 1. Con esto, la desigualdad anterior dice que el largo de la subsecuencia com´ un m´ as grande de las palabras de S (aumentadas con n caracteres aleatorios) es al menos el m´ aximo entre el largo esperado de la LCS de las palabras que obtendr´ıamos al descartar los 1 iniciales y el largo esperado de la LCS de las palabras que obtendr´ıamos al descartar los 0 iniciales.

20

Cap´ıtulo 3: Cotas inferiores para las constantes de Chv´ atal y Sankoff

Para dejar m´ as claro lo anterior, veamos un ejemplo para el caso de d = 4 palabras:  X 1   wn−1 [001, 011, 01c(3), 001],    2 c∈{0,1}{3} wn [001, 011, 101, 001] ≥ m´ ax X 1   wn−3 [01c(1), 11c(2), 101, 01c(4)].    23 {1,2,4} c∈{0,1}

En este ejemplo, s´ olo una palabra, la tercera, no empieza con 0. Luego, el primer t´ermino del m´ aximo resulta ser el promedio entre los valores de wn−1 en las 2 secuencias posibles de palabras que se obtienen de S al borrar el 1 inicial de la tercera palabra y concatenar un car´ acter al final. Por otro lado, las otras tres palabras de S empiezan con 0 (es decir, no empiezan con 1). Luego, el segundo t´ermino del m´ aximo resulta ser el promedio sobre el valor que toma wn−3 en todas las secuencias de palabras que se forman a partir de S al borrar los 0 iniciales y concatenar, en aquellas palabras, un car´ acter al final. Notemos ahora que si usamos los lados derechos de las dos desigualdades descritas para wn en (3.2.10) y (3.2.13) es posible definir una funci´ on T tal que para todo n ≥ d wn ≥ T (wn−1 , wn−2 , . . . , wn−d ),

(3.2.14)

Π0 (wn ) ≥ T0 (wn−d ), Πd (wn ) ≥ Td (wn−d ), ∀r, 0 < r < d Πr (wn ) ≥ Tr (wn−r , wn−d+r ).

(3.2.15)

donde la desigualdad es componente a componente. M´ as a´ un, al igual que en la subsecci´ on 3.2.2, podemos descomponer T , esta vez en d+1 funciones m´ as simples denotadas Tr , tales que, si Πr (w) es la proyecci´ on sobre las componentes que corresponden a las secuencias tales que r de las d palabras comienzan con 0, entonces para todo n ≥ d

Usando los conceptos de traslaci´ on que mantiene un car´ acter que definimos antes, podemos reescribir T de una manera que nos facilitar´ a su programaci´ on y an´ alisis. Para i ∈ {0, 1} definild ld mos la transformaci´ on lineal Ai : (R2 )d 7−→ R2 , que toma d vectores de tama˜ no 2ld , digamos (v1 , v2 , . . . vd ), y devuelve un vector Ai (v1 , v2 , . . . vd ), tal que si S = (si )di=1 es una secuencia de d palabras de tama˜ no l (que representa una de las 2ld secuencias posibles), entonces: X 1 v|Ji (S)| [τi (S, c)]. (3.2.16) Ai (v1 , v2 , . . . , vd )[S] = 2|Ji (S)| J (S) c∈{0,1}

i

Decimos que A0 es la parte glotona de T que mantiene los 0 (y elimina los 1), y que A1 es la parte glotona de T que mantiene los 1 (y elimina los 0). Adem´ as, convengamos como es habitual que la suma sobre un conjunto vac´ıo es 0 (para incluir el caso |Ji (S)| = 0). Con esto, si v1 , v2 , . . . , vd es una secuencia de d vectores de tama˜ no 2ld , entonces de las desigualdades (3.2.10) y (3.2.13) se concluye que podemos definir T en funci´ on de sus partes glotonas como: T (v1 , v2 , . . . , vd ) = b + m´ ax{A0 (v1 , v2 , . . . , vd ), A1 (v1 , v2 , . . . , vd )},

(3.2.17)

donde b es el vector de R que vale 1 en las coordenadas correspondientes a las secuencias de d palabras de largo l que comienzan con el mismo car´ acter (todas con 0 o todas con 1) y 0 en las dem´ as coordenadas. 2ld

21

Cap´ıtulo 3: Cotas inferiores para las constantes de Chv´ atal y Sankoff

3.2.3.

Encontrando una cota inferior

Al principio de la subsecci´ on anterior, vimos que para toda secuencia de palabras s1 , . . . , sd , se tiene γ2,d = l´ımn→∞ n1 wdn [s1 , . . . , sd ]. Un primer intento para encontrar una cota para dicha cantidad podr´ıa basarse en la monotonicidad de la transformaci´ on T reci´en definida. Gracias a ella se puede realizar el siguiente procedimiento: x Lamentablemente en el procedimiento anterior no disponemos de un an´ alisis adecuado para estimar a partir de que valor de n tenemos efectivamente una cota inferior para γ2,d , (la cantidad vdn [s1 , . . . , sd ]/n no es siquiera creciente.) Necesitamos una estrategia distinta. Para esto, usaremos el siguiente resultado, que es una generalizaci´on al caso de d palabras de un resultado obtenido por Lueker [6] para el caso bidimensional: Lema 3.4. Sea T : (R2 )d 7−→ R2 una transformaci´ on que cumple con las siguientes propiedades: ld

ld

1. Monoton´ıa: (v1 , v2 , . . . , vd ) ≤ (w1 , w2 , . . . , wd ) =⇒ T (v1 , v2 , . . . , vd ) ≤ T (w1 , w2 , . . . , wd ).

(3.2.18)

2. Invarianza bajo traslaci´ on: ld ld Si r ∈ R, 1 es el vector de unos en R2 , y ~1 = (1, 1, . . . , 1) es el vector de unos en (R2 )d , ld entonces para todo vector (v1 , v2 , . . . , vd ) ∈ (R2 )d : T ((v1 , v2 , . . . , vd ) + r~1) = T (v1 , v2 , . . . , vd ) + r 1.

(3.2.19)

3. Factibilidad: Existe un tr´ıo (z, r, ε) (que denotaremos tr´ıo factible) con z ∈ R2 , r un real y ε ≥ 0 tal que: T (z + (d − 1)r 1, . . . , z + 2r 1, z + r 1, z) ≥ z + dr 1 − ε1. (3.2.20) ld

Entonces, para toda secuencia (vn )n∈N de vectores de

R2 tales que para todo n ≥ d se satisface: ld

vn ≥ T (vn−1 , vn−2 , . . . , vn−d ).

(3.2.21)

se tiene que existe un vector z0 tal que para todo n ≥ 0, vn ≥ z0 + n(r − ε)1.

(3.2.22)

Demostraci´ on. Sea T una transformaci´ on mon´ otona, invariante bajo traslaci´on y (z, r, ε) un tr´ıo factible para T . Sea vn una secuencia como en la hip´ otesis y α cualquier real suficientemente grande tal que para todo j menor o igual que d − 1 vj + α1 ≥ z + j(r − ε)1.

22

Cap´ıtulo 3: Cotas inferiores para las constantes de Chv´ atal y Sankoff

Por ejemplo si consideramos el vector m´ ax0≤j≤(d−1) (z + j(r − ε)1 − vj ), podemos elegir α como el valor m´ as grande de dicho vector. Con esto z0 = z − α1 cumple (3.2.22) para todo n ≤ (d − 1). Probemos por inducci´ on que esto se extiende a todo n ≥ d. Supongamos que (3.2.22) se cumple hasta n − 1, veamos que se cumple para n. Por hip´ otesis de inducci´ on: (vn−1 , . . . , vn−d ) ≥ (z0 + (n − 1)(r − ε)1, . . . , z0 + (n − j)(r − ε)1, . . . , z0 + (n − d)(r − ε)1) = (z + (d − 1)r 1, . . . , z + (d − j)r 1 + (j − 1)ε1, . . . , z + (d − 1)ε1) + ((n − d)(r − ε) − (d − 1)ε − α) ~1

≥ (z + (d − 1)r 1, . . . , z + (d − j)r 1, . . . , z) + ((n − d)(r − ε) − (d − 1)ε − α) ~1.

Aplicando T a ambos lados de la desigualdad, se obtiene, por monoton´ıa e invarianza bajo traslaci´ on: vn ≥ T (vn−1 , vn−2 , . . . , vn−d ) ≥ T (z + (d − 1)r 1, . . . , z + (d − j)r 1, . . . , z) + ((n − d)(r − ε) − (d − 1)ε − α) 1.

Usando que (z, r, ε) es un tr´ıo factible de T se tiene que vn ≥ z + (dr − ε)1 + ((n − d)(r − ε) − (d − 1)ε − α)1 = z − α1 + n(r − ε)1 = z0 + n(r − ε)1. Lo que concluye la demostraci´ on del lema.



De (3.2.16) y (3.2.17) se concluye f´ acilmente que la transformaci´ on T definida en la subsecci´ on anterior es mon´ otona e invariante bajo traslaci´ on. Luego, si probamos la existencia de un tr´ıo (z, r, ε) factible para T podremos concluir, gracias al lema, que la sucesi´ on de vectores (wn )n∈N satisface wn ≥ z0 + n(r − ε)1 para todo n y luego, gracias a (3.2.9) deducir que: γ2,d ≥ d(r − ε).

(3.2.23)

Sigue que, para encontrar buenas cotas inferiores para γ2,d basta encontrar buenos tr´ıos factibles, en particular alg´ un tr´ıo que tenga r grande y ε lo m´ as peque˜ no posible. Una forma de conseguir esto es modificar un poco la estrategia explicada al principio de esta subsecci´ on. De hecho, al igual que en dicho procedimiento, basta iterar la transformaci´ on T partiendo de d vectores iniciales cualquiera v0 , v1 , . . . , vd−1 calculando vn = T (vn−1 , vn−2 , . . . , vn−d ) para n ≥ d. La transformaci´ on T tiene buenas propiedades y, al menos emp´ıricamente, se ve que los vn definidos como antes son tales que vn /n converge a un vector con todas sus coordenadas iguales. Luego, si se toma un n suficientemente grande, los vectores vn y vn−1 diferir´ an pr´ acticamente en una constante por el vector 1. Es decir, existe una constante r tal que vn − vn−1 ∼ r 1 para todo n 23

Cap´ıtulo 3: Cotas inferiores para las constantes de Chv´ atal y Sankoff

grande. Notemos ahora que T (vn+d−1 , . . . , vn+1 , vn ) = vn+d por definici´ on, luego, de la observaci´ on anterior y la continuidad de T , se tendr´ a que T (vn + (d − 1)r 1, vn + (d − 2)r 1, . . . , vn + r 1, vn ) ∼ vn + dr 1. Sigue que para encontrar un tr´ıo factible podemos tomar un n suficientemente grande, de modo que la diferencia entre vn y vn−1 sea un vector con todas sus coordenadas practicamente iguales, definir z como vn , tomar r como el m´ aximo valor tal que vn − vn−1 ≥ r 1, y luego definir ε lo m´ as peque˜ no posible de modo que el tr´ıo (z, r, ε) resulte factible. Con esto, gracias a (3.2.23), se obtiene una (buena) cota para γ2,d . Es importante recalcar que no necesitamos probar la propiedad de convergencia de vn /n para obtener una cota para γ2,d . S´ olo basta exhibir un buen tr´ıo factible como testigo en virtud del lema anterior.

3.2.4.

Implementaci´ on y cotas obtenidas

A continuaci´ on describiremos el procedimiento usado para obtener un tr´ıo factible (z, r, ε) para umero T y, en conclusi´ on, una cota inferior para γ2,d . Este procedimiento tiene como entradas el n´ de palabras a usar d, el largo de cada palabra, l y una tolerancia δ que regula el momento en el que terminamos el procedimiento: trioFactible(d, l, δ) ld Definir para i = 0, . . . , d − 1, el vector vi como el vector de ceros en R2 . Iterar desde i = d: Definir vi ← T (vi−1 , vi−2 , . . . , vi−d ). Definir ∆ ← vi − vi−1 . M ← m´ axj ∆[j]. m ← m´ınj ∆[j]. Si M − m < δ, salir de la iteraci´ on. Si no, actualizar i ← i + 1. axj W [j]. Definir z ← vi , r ← M , W ← z + dr 1 − T (z + (d − 1)r 1, . . . , z + r 1, z), ε ← m´ Retornar (z, r, ε). cotaInferior(d, l, δ) Definir (z, r, ε) ←trioFactible(d, l, δ) Retornar d(r − ε). Usando la definici´ on de T dada por sus partes glotonas (3.2.17) es sencillo escribir una implementaci´ on del procedimiento anterior en cualquier lenguaje de programaci´ on. Aprovechamos la 0 1 linealidad de A y A para almacenarlas como un conjunto de matrices ralas, lo cual acelera mucho cada iteraci´ on. A medida que aumentamos l, como es de esperarse, la cota va mejorando, sin embargo la memoria usada crece demasiado (recordar que cada vector es de tama˜ no 2ld ). De hecho, un an´ alisis simple de la definici´ on de A0 y A1 permite concluir que s´ olo para almacenar ambas matrices de una manera rala es necesario guardar al menos 2ld 2d = 2(d+1)l valores distintos de 0. Por dicha raz´ on s´ olo es posible realizar este procedimiento para valores peque˜ nos de d y l. 24

Cap´ıtulo 3: Cotas inferiores para las constantes de Chv´ atal y Sankoff

Los resultados obtenidos se muestran en la Tabla 3.1. Valores para d = 2 l Cota para γ2,2 1 0.66666666418314 2 0.72727271808253 3 0.74792242549591 4 0.75857669196192 5 0.76544695856955 6 0.77027385445717 7 0.77397507816660 8 0.77686064534113 9 0.77925933824914

l 1 2 3

Valores para d = 5 Cota para γ2,5 0.615384368494691 0.626505887219029 0.632165355051306

Valores para d = 3 l 1 2 3 4 5 6 7

Cota para γ2,3 0.66666665424904 0.67391302685782 0.68741051941928 0.69295022383657 0.69773770403703 0.70131710654988 0.70447344812276

Valores para d = 6 l Cota para γ2,6 1 0.592592356497814 2 0.610924985301239 3 0.617761437978714

Valores para d = 4

l 1 2 3 4 5

Cota para γ2,4 0.615384595264409 0.643216010100026 0.651309094992399 0.657241281735180 0.661274795991150

Valores para d = 7 l 1 2

Cota para γ2,7 0.592592481860063 0.602493036014458

Tabla 3.1: Cotas inferiores para γ2,d Los resultados se obtuvieron con nuestra implementaci´ on usando δ = 10−8 . Es importante notar que el m´etodo converge r´ apidamente al resultado y de hecho, en ning´ un caso fueron necesarias m´ as de 150 iteraciones. La parte m´ as lenta del algoritmo corresponde al c´ alculo de las matrices ralas.

3.2.5.

Extensiones

Es relativamente simple extender los resultados anteriores a alfabetos de cualquier tama˜ no. Veamos como hacer esto. Sea Σ un alfabeto finito cualquiera. Definamos Wnd (·) y wn de manera an´ aloga al caso de alfabeto binario, con la salvedad que ahora la colecci´ on de palabras aleatorias d ld (Xi )i=1 es tomada sobre Σ y los vectores wn tienen |Σ| coordenadas. Al igual que antes wn estar´ a acotada inferiormente por una funci´ on T de los u ´ ltimos d vectores. La idea es escribir T en funci´ on de sus partes glotonas. La definici´ on ser´ a similar para ello extendamos la definici´ on de traslaciones que mantengan ciertos caracteres (y reemplacen los dem´ as). Para una palabra s sobre Σ de largo l definimos, al igual que antes I(s) como el primer car´ acter de s y C(s) como su cola, es decir, la subpalabra que resulta al eliminar dicho car´ acter. Adem´ as, d para todo σ ∈ Σ y toda secuencia S = (si )i=1 de d palabras de largo l sobre Σ, definimos Jσ (S) como el conjunto de ´ındices j tales que la palabra sj comienza con σ, es decir I(sj ) = σ. Definamos adem´ as Jσ (S) = [d] \ Jσ (S) los ´ındices de las palabras que no comienzan con σ. Para σ ∈ Σ y c ∈ ΣJσ (S) una asignaci´ on definimos la traslaci´ on de S que mantiene los caracteres 25

Cap´ıtulo 3: Cotas inferiores para las constantes de Chv´ atal y Sankoff

iniciales σ y cambia los dem´ as por c como τσ (S.c) = τσ (S, c)i

τσ (S, c)i =

(

si , C(si )c(i),


d

i=1

con:

si i ∈ Jσ (S), si i ∈ 6 Jσ (S).

Con esto, para cada σ ∈ Σ, definimos la transformaci´ on lineal Aσ :



R|Σ|

ld

d

7→

R|Σ| , que ld

toma d vectores de tama˜ no |Σ|ld , digamos (v1 , v2 , . . . vd ), y devuelve Aσ (v1 , v2 , . . . , vd ), tal que si S = (s1 , s2 , . . . , sd ) es una secuencia de d palabras de tama˜ no l (que representa una de las |Σ|ld secuencias posibles), entonces: Aσ (v1 , v2 , . . . , vd )[S] =

X

1

v|Jσ (S)| [τσ (S, c)]. |Σ||Jσ (S)| c∈ΣJσ (S)

Llamamos, haciendo una analog´ıa al caso de dos palabras, parte glotona de T que mantiene σ a la transformaci´ on Aσ . Notemos que esta definici´ on es consistente con la definici´ on de A0 y A1 realizada para el caso de Σ = {0, 1} en la subsecci´ on 3.2.2. Finalmente definamos T como la transformaci´ on que a una secuencia (v1 , v2 , . . . vd ) de d vectores

de

R|Σ| le asocia ld

T (v1 , v2 , . . . vd ) = b + m´ ax B σ (v1 , v2 , . . . vd ), σ∈Σ

con b el vector de R|Σ| que vale 1 en las coordenadas correspondientes a secuencias de d palabras de largo l que comienzan con el mismo car´ acter y 0 en las dem´ as. Con esto, para todo n ≥ d, ld

wn ≥ T (wn−1 , wn−2 , . . . , wn−d ). Sigue que, aplicando una versi´ on del Lema 3.4, se puede obtener una cota inferior para γ|Σ|,d del mismo modo que antes.

3.3.

Aplicaci´ on: Conjetura de Steele

Steele [8] conjetur´ o en 1986 que la constante γ2,3 asociada a la LCS de 3 palabras sobre un alfabeto binario se pod´ıa obtener a partir de la constante γ2,2 asociada a la LCS de s´ olo 2 palabras mediante la siguiente relaci´ on: γ2,3 = (γ2,2 )2 . De hecho, ´el hace una generalizaci´ on de su conjetura, diciendo que γ2,d = (γ2,2 )d−1 . Danˇc´ık [3] lo cita de manera incorrecta, afirmando que la conjetura planteada por Steele es para alfabetos de cualquier tama˜ no. En otras palabras, Danˇc´ık argumenta d−1 que la conjetura de Steele es γk,d = (γk,2 ) para todo k y luego prueba que tal conjetura es falsa al observar que [3]: 1 ≤ l´ım inf k1−1/d γk,d ≤ l´ım sup k1−1/d γk,d ≤ e. (3.3.1) k→∞

k→∞

26

Cap´ıtulo 3: Cotas inferiores para las constantes de Chv´ atal y Sankoff

Sin embargo, esto s´ olo prueba la falsedad de la conjetura extendida, pues los resultados usados son ciertos asint´ oticamente en k. Hasta ahora, no existen referencias a la veracidad o falsedad de la conjetura original de Steele (que se refiere s´ olo a alfabetos binarios). Daremos un argumento simple para probar que la conjetura de Steele general (γ2,d = (γ2,2 )d−1 ) es falsa y que de hecho no es cierta para ning´ un d ≥ 3. Lueker [6] prob´ o las siguientes cotas para γ2,2 : L = 0, 788071 ≤ γ2,2 ≤ 0,826280 = U. Usando la cota inferior simple (Corolario 3.3) mostrada al principio del cap´ıtulo, tenemos que 1/2 ≤ γ2,d para todo d. Luego, si la conjetura de Steele fuera cierta se tendr´ıa que 1/2 ≤ γ2,d = (γ2,2 )d−1 ≤ U d−1 , lo cual es falso para todo d ≥ 1 + ln(1/2)/ ln U ≈ 4,6. Con esto hemos probado que la conjetura general es falsa para todo d ≥ 5. Para ver el caso d = 3 (que es precisamente el caso original de la conjetura de Steele) y el caso d = 4 basta observar los resultados num´ericos obtenidos para las cotas inferiores de γk,d en la Tabla 3.2. d

Cota inferior para γ2,d

3 4 5 6 7

0.7044734481 0.6612747959 0.6321653550 0.6177614379 0.6024930360

U d−1 (Cota superior asumiendo conjetura de Steele) 0.6827386384 0.5641332822 0.4661320484 0.3182463600 0.2629606023

Tabla 3.2: Tabla con las mejores cotas obtenidas para distintos d. U = 0,826280 es la mejor cota superior conocida para γ2,2 .

27

Cap´ıtulo 4

Problema del subhipergrafo mon´ otono de tama˜ no m´ aximo √ Sankoff y Mainville [12] conjeturaron en los ochenta que l´ımk→∞ γk,2 k = 2. Kiwi, Loebl y Matouˇsek [7] probaron recientemente la veracidad de la conjetura anterior relacionando el problema de la subsecuencia com´ un m´ as grande con el problema de Ulam o de la secuencia creciente m´ as grande de una permutaci´ on. Danˇc´ık [3] se˜ nala que una extensi´ on natural a la conjetura de Sankoff y Mainville al caso de 1−1/d = 2. Sin embargo esto no parece acertado pues en el argumento d palabras ser´ıa l´ımk→∞ γk,d k usado para probar la veracidad de la conjetura original, se usa explicitamente que 2 es el valor de la constante c2 correspondiente al problema de la secuencia creciente m´ as larga, tambi´en conocido como problema de Ulam en dos dimensiones. Por lo anterior, es razonable pensar que la buena extensi´ on para la conjetura de Sankoff y Mainville ser´ıa l´ımk→∞ γk,d k1−1/d = cd , donde cd es la constante para el problema de Ulam en d dimensiones. Esto u ´ ltimo ser´ a probado en este cap´ıtulo como corolario del estudio de un nuevo problema que realizaremos en las siguientes secciones. Espec´ıficamente, para el problema de la subsecuencia com´ un m´ as grande, probaremos el siguiente teorema. Teorema 4.1. Para todo d entero positivo y todo ε > 0 existen k0 y A suficientemente grandes tal que para todo k ≥ k0 y todo n ≥ Ak 1−1/d se tiene:

(1 − ε)

cd n 1−1/d k

 (d)  cd n ≤ E Ln,k ≤ (1 + ε) 1−1/d . k

28

Cap´ıtulo 4: Problema del subhipergrafo mon´otono de tama˜ no m´aximo

 (d)  (d) Por otro lado, si Med Ln,k es una mediana de Ln,k , (1 − ε)

cd n 1−1/d k

 (d)  cd n ≤ Med Ln,k ≤ (1 + ε) 1−1/d . k

Adem´ as, existe una constante absoluta C > 0 tal que, para k y n como antes, se tiene la siguiente cota exponencial para la cola de la distribuci´ on, h  cd n i cd n  2 P L(d) ≤ (1 − ε) · ≤ exp −Cε , n,k k1−1/d k1−1/d   h Cε2 cd n i cd n (d) . P Ln,k ≥ (1 + ε) · 1−1/d ≤ 2 exp − · 1 + ε k1−1/d k Corolario 4.2. Para todo d entero positivo, l´ım γk,d k1−1/d = cd .

k→∞

Este resultado se obtendr´ a en este cap´ıtulo como corolario de un teorema m´ as general que (d) abarca no s´ olo estimar el comportamiento de la distribuci´on de Ln,k sino que de varias distribuciones similares.

4.1.

Subhipergrafo mon´ otono de tama˜ no m´ aximo

Replantearemos el problema de la LCS de varias palabras, siguiendo el enfoque usado en [7] para el caso de 2 palabras. En dicho trabajo la noci´ on de subsecuencia com´ un de dos palabras fue analogada a la noci´ on de un cierto tipo de subgrafos (denominados subgrafos planares) de un grafo bipartito cuyos v´ertices representan los caracteres de las palabras. Para el caso general de d palabras, la extensi´ on natural requiere que trabajemos con hipergrafos en vez de grafos. Definici´ on. Dados d conjuntos disjuntos, A1 , A2 , . . . , Ad , diremos que un hipergrafo H = (V, E) es d-partito de clases A1 , A2 , . . . Ad y d-uniforme (o simplemente d-hipergrafo) si se cumplen las siguientes condiciones: d [ 1. V = • Aj . j=1

2. E ⊆ {{v (1) , v (2) , . . . , v (d) } | v (j) ∈ Aj , j = 1, . . . , d}. Sin p´erdida de generalidad, identificaremos E con el subconjunto de A1 ×A2 ×· · ·×Ad que contiene las d-tuplas ordenadas asociadas a las aristas de E. Adem´ as, usaremos la notaci´ on habitual E(H) = E y V (H) = V .

29

Cap´ıtulo 4: Problema del subhipergrafo mon´otono de tama˜ no m´aximo

En general, de aqu´ı en adelante, llamaremos nj = |Aj | al tama˜ no del j-´esimo conjunto y supondremos adem´ as que los elementos de Aj est´ an dotados de un orden total ≤ (supondremos, de hecho, abusando un poco de notaci´ on, que los v´ertices est´ an numerados 1, 2, . . . , nj ). Denotaremos Kn1 ,n2 ,...,nd al d-hipergrafo completo sobre las clases anteriores, es decir al hipergrafo tal que E(Kn1 ,n2 ,...,nd ) = A1 × A2 × · · · × Ad . En el caso que todas las clases tengan el mismo (d) cardinal, digamos n1 = n2 = · · · = nd = n, lo denotaremos simplemente Kn . En A1 × A2 × · · · × Ad consideramos la relaci´ on de orden parcial natural ≤ definida por:     v (1) , v (2) , . . . , v (d) ≤ w(1) , w(2) , . . . , w(d) ⇐⇒ v (j) ≤ w(j) , para todo 1 ≤ j ≤ d. Diremos que un conjunto de aristas de un d-hipergrafo es un emparejamiento mon´ otono si todo par de aristas distintas {e, f } es comparable v´ıa este orden, es decir si e ≤ f o´ f ≤ e. Si un d-hipergrafo H es tal que E(H) es un emparejamiento mon´ otono, diremos simplemente que H es un hipergrafo mon´ otono. Adem´ as, denotaremos L(H) al n´ umero de aristas de un subhipergrafo mon´ otono de H de tama˜ no m´ aximo. Llamamos modelo de d-hipergrafo aleatorio a toda familia de distribuciones D = (D(Kn1 ,...,nd )) on de probabilidad sobre los subhipergrafos de Kn1 ,...,nd donde cada D(Kn1 ,...,nd ) es una distribuci´ que cumple las siguientes propiedades: 1. [Monotonicidad] Si H se distribuye de acuerdo a D(Kn1 ,...,nd ), y H 0 es un subhipergrafo inducido de H tal que V (H 0 ) contiene exactamente n0j v´ertices de la clase Aj , entonces H 0 se distribuye de acuerdo a D(Kn01 ,...,n0d ). 2. [Independencia por bloques] Si H1 y H2 son dos subhipergrafos inducidos de H disjuntos entonces las distribuciones inducidas por H1 y H2 son independientes (y luego, L(H1 ) y L(H2 ) tambi´en lo son). Los modelos de hipergrafo m´ as simples (y en los que enfocaremos nuestra atenci´ on) son los siguientes: 1. Denotemos Σ(Kn1 ,...,nd , k) a la distribuci´ on sobre todos los subhipergrafos de Kn1 ,...,nd obtenidos al asignar a cada uno de sus v´ertices un s´ımbolo de {1, . . . , k} de manera uniforme e independiente y quedarse s´ olo con las aristas cuyos elementos tengan asignado el mismo s´ımbolo. Llamaremos al modelo Σ(·, k), modelo de d palabras aleatorias sobre un alfabeto de tama˜ no k. El nombre de este modelo proviene del hecho que si H es elegido de acuerdo a Σ(Kn1 ,...,nd , k) entonces L(H) es precisamente el largo de la LCS de las d palabras que se pueden “leer” en (d) los s´ımbolos de las clases en que est´ a particionado H, y luego L(Σ(Kn , k)) tiene la misma (d) distribuci´ on que Ln,k .

30

Cap´ıtulo 4: Problema del subhipergrafo mon´otono de tama˜ no m´aximo

2. Sea G(Kn1 ,...,nd , p) la distribuci´ on sobre todos los subhipergrafos de Kn1 ,...,nd donde la probabilidad de que una arista e est´e en el subhipergrafo es p, y estos eventos son independientes. Llamaremos al modelo G(·, p) modelo binomial, de par´ ametro p, de d-hipergrafos. 1

3

3

2

3

1

3

3

1

2

1

1

3

2

3

1

2

1

3

3

1

3

1

2

1

2

A1 A2 A3 Figura 4.1: Representaci´ on esquem´ atica de un subhipergrafo mon´ otono de tama˜ no m´ aximo de H, an representadas por l´ıneas poligonales donde H es elegido de acuerdo a Σ(K10,7,9 , 3). Las aristas est´ que pasan por sus v´ertices. Sobre cada v´ertice se indica el s´ımbolo elegido en la realizaci´ on de H y, en este caso, L(H) = 5. Intuitivamente la monotonicidad es equivalente a que las aristas no se crucen ni compartan v´ertices Finalmente, dado un modelo, llamaremos par´ ametro interno del modelo a cualquier valor que sea constante para todas las distribuciones que participan del modelo. Por ejemplo, k y p (o cualquier funci´ on de ellos) son par´ ametros internos de los modelos Σ(·, k) y G(·, p) respectivamente. En este cap´ıtulo probaremos un teorema que permitir´ a estimar el valor esperado de L(H) as´ı como el valor de sus medianas, cuando H es elegido de acuerdo a alg´ un modelo de hipergrafo aleatorio con ciertas condiciones especiales (en particular, los modelos anteriormente descritos). (d) (d) Usando que L(Σ(Kn , k)) se distribuye como Ln,k , obtendremos como corolario el Teorema 4.1 enunciado al comienzo de este cap´ıtulo.

4.2.

Aproximaci´ on de la mediana. Teorema Principal

En los modelos que estudiaremos, la siguiente desigualdad de Talagrand ser´ a de vital importancia: Lema 4.3 (Desigualdad de Talagrand). Supongamos que Z1 , . . . , ZN son variables aleatorias independientes que toman valores en un cierto conjunto Λ. Sea X = f (Z1 , . . . , ZN ), con f : ΛN → R una funci´ on tal que las siguientes condiciones se cumplen para un cierto l0 y una cierta funci´ on Φ. 1. (f es Lipschitz) Si z, z 0 ∈ ΛN difieren solo en una coordenada, entonces |f (z) − f (z 0 )| ≤ l0 .

2. (Existencia de testigos) Si z ∈ ΛN y r ∈ R tal que f (z) ≥ r, entonces existe un conjunto de ´ındices J ⊆ {1, . . . , N }, |J| ≤ Φ(r)/l2 y un testigo (wj : j ∈ J) tal que para todo y ∈ ΛN con yj = zj cuando j ∈ J, se tiene f (y) ≥ r. 31

Cap´ıtulo 4: Problema del subhipergrafo mon´otono de tama˜ no m´aximo

Sea Med(X) una mediana de X. Entonces, para todo t ≥ 0, se cumplen las siguientes desigualdades:

P[X ≤ Med(X) − t] ≤ 2e−t /4Φ(Med(X)) , 2 P[X ≥ Med(X) + t] ≤ 2e−t /4Φ(Med(X)+t) . 2

Notemos que para el modelo de d palabras aleatorias, el valor de L(H) depende exclusivamente de los s´ımbolos asignados a los v´ertices (que son independientes), y adem´ as si cambiamos uno de los s´ımbolos, entonces el valor de L(H) cambia a lo m´ as en 1. Adem´ as, si L(H) ≥ r, entonces existen dr v´ertices testigos (los extremos de las r aristas) que garantizan que para cualquier asociaci´ on de caracteres que preserve la asociaci´ on correspondiente a los v´ertices testigos, el hipergrafo resultante posee un subhipergrafo mon´ otono de al menos r aristas. Luego por Talagrand, si Med es una mediana de L(H), entonces para todo s ≥ 0,  2  s P[L(H) ≤ (1 − s) Med] ≤ 2 exp − Med , 4d   s2 P[L(H) ≥ (1 + s) Med] ≤ 2 exp − Med . 4d(1 + s) Similarmente, para el modelo binomial, el valor de L(H) depende de la existencia o no de las aristas (que son independientes), con lo cual al igual que antes el valor de L(H) es 1-Lipschitz. Adem´ as, si L(H) ≥ r, entonces existen r aristas testigos que garantizan que L(H) ≥ r, para cualquier hipergrafo H que contenga dichas aristas. luego, si Med es una mediana de L(H), entonces para todo s ≥ 0,  2  s P[L(H) ≤ (1 − s) Med] ≤ 2 exp − Med , 4   s2 P[L(H) ≥ (1 + s) Med] ≤ 2 exp − Med . 4(1 + s) Este tipo de cotas aparecer´ a en todos los modelos que estudiaremos, en virtud de esto, la siguiente definici´ on nos ser´ au ´ til. Definici´ on. Diremos que un modelo D tiene una constante de concentraci´ on h si para toda mediana Med de L(H) se cumple que para todo s ≥ 0,
P[L(H) ≤ (1 − s) Med] ≤ 2 exp −hs2 Med ,   s2 P[L(H) ≥ (1 + s) Med] ≤ 2 exp −h Med . (1 + s) Si podemos estimar una mediana de L(H) para los modelos a estudiar, y logramos probar que la media y la mediana est´ an cerca, entonces gracias a la desigualdad anterior, tendremos una buena cota de concentraci´ on con respecto a la media. Lamentablemente estimar una mediana no es f´ acil 32

Cap´ıtulo 4: Problema del subhipergrafo mon´otono de tama˜ no m´aximo

en este contexto, pero s´ı podremos hacerlo cuando los tama˜ nos nj de las clases, satisfagan ciertas condiciones. En particular, veremos que cuando los tama˜ nos de las clases se encuentran en cierto rango, entonces podremos encontrar una aproximaci´ on de la mediana que resultar´ a ser proporcional al promedio geom´etrico de los tama˜ nos de las clases del hipergrafo. Definici´ on ((c, λ, θ)-mediana). Diremos que un modelo de d-hipergrafo D con par´ ametro interno t admite una (c, λ, θ)-aproximaci´ on de la mediana (o simplemente, una (c, λ, θ)-mediana) si para todo δ > 0 existen constantes a(δ), b(δ) y t0 (δ) suficientemente grandes tales que para todo t ≥ t0 y todo conjunto de valores n1 , . . . , nd de promedio geom´etrico N y suma S, que cumplan N ≥ tλ a,

(Cota inferior en el tama˜ no)

θ

Sb ≤ t .

(Cota superior en el tama˜ no)

se tiene que si Med[L(D(Kn1 ,...,nd ))] es una mediana de L(D(Kn1 ,...,nd )), (1 − δ)

cN cN ≤ Med[L(D(Kn1 ,...,nd , t))] ≤ (1 + δ) λ . λ t t

En otras palabras, si D es un modelo de par´ ametro interno t que admite una (c, λ, θ)-mediana, y adem´ as los valores n1 , . . . , nd de promedio geom´etrico N y suma S son tales que N = Ω(tλ ) y S = O(tθ ), entonces, para t grande, toda mediana de L(D(Kn1 ,...,nd )) estar´ a cerca de cN t−λ . Cabe recalcar que la definici´ on anterior depende expl´ıcitamente del par´ ametro interno t elegido para D. La definici´ on anterior podr´ a parecer en estos momentos algo artificial. Sin embargo, m´ as adelante veremos que no es dif´ıcil obtener aproximaciones para la mediana de este tipo en nuestros modelos. Esto se lograr´ a relacionando el problema de determinar el tama˜ no de un subhipergrafo mon´ otono de tama˜ no m´ aximo con otro problema bastante estudiado en la literatura, el problema de la secuencia creciente m´ as larga. Todo esto se ver´ a en las secciones 4.5 y 4.6. Volvamos a la definici´ on anterior. La importancia de esta noci´ on es que, cuando el modelo a estudiar admite adem´ as una constante de concentraci´ on, nos permitir´ a encontrar una cota de concentraci´ on en torno a la aproximaci´ on de la mediana. Gracias a las propiedades de independencia por bloques y monotonicidad de estos modelos demostraremos adem´ as que podemos extender dicha cota de concentraci´ on a un caso mucho m´ as general: esencialmente reemplazaremos la condici´ on Sb ≤ tθ dada por la definici´ on de (c, λ, θ)mediana por una relaci´ on de “balanceo” de los tama˜ nos nj de las clases del hipergrafo, pidiendo que su suma S no sea demasiado grande con respecto a su promedio geom´etrico N . Adem´ as, en dicho caso, probaremos que la mediana y la media no est´ an muy lejos y luego la cota anterior se convierte adem´ as en una estimaci´ on de la media. El siguiente teorema es el teorema principal de este cap´ıtulo.

33

Cap´ıtulo 4: Problema del subhipergrafo mon´otono de tama˜ no m´aximo

Teorema 4.4 (Teorema Principal). Sea D un modelo de d-hipergrafo con par´ ametro interno t, con constante de concentraci´ on h y que admite una (c, λ, θ)-mediana. Sea tambi´en g : R → R una funci´ on tal que g(t) = O(tη ) para un cierto 0 ≤ η < m´ın {λ/(d − 1), θ − λ} . Para todo ε > 0, existen t0 y A suficientemente grandes tales que si t ≥ t0 y los valores n1 , . . . , nd de promedio geom´etrico N y suma S cumplen: N ≥ tλ A,

(Condici´ on de tama˜ no)

S ≤ g(t)N,

(Condici´ on de balanceo)

se tiene, definiendo M = cN/tλ , (1 − ε)M ≤ E[L(D(Kn1 ,...,nd ))] ≤ (1 + ε)M.

(4.2.1)

Por otro lado, si Med[L(D(Kn1 ,...,nd ))] es una mediana de L(D(Kn1 ,...,nd )), (1 − ε)M ≤ Med[L(D(Kn1 ,...,nd ))] ≤ (1 + ε)M.

(4.2.2)

Adem´ as, existe una constante absoluta K, tal que para t y n1 , . . . , nd como antes, se tiene la siguiente cota exponencial para la cola de la distribuci´ on:
P [L(D(Kn1 ,...,nd )) ≤ (1 − ε)M ] ≤ exp −Khε2 M , (4.2.3)   ε2 M . (4.2.4) P [L(D(Kn1 ,...,nd )) ≥ (1 + ε)M ] ≤ exp −Kh 1+ε

4.3.

Demostraci´ on de las cotas inferiores en el Teorema Principal

En esta secci´ on probaremos las cotas inferiores dadas por el teorema, es decir, probaremos la cota inferior en (4.2.1), (4.2.2) y la desigualdad (4.2.3). Notemos primero que si ε ≥ 1 todas estas cotas son triviales, luego asumiremos en esta parte que 0 < ε < 1. Sea entonces D un modelo de hipergrafo aleatorio como en la hip´ otesis del Teorema η Principal y sean η < m´ın {λ/(d − 1), θ − λ} y g tal que g(t) = O(t ). En particular sabemos que existe una constante g0 > 1 tal que g(t) ≤ g0 tη cuando t es grande. Sea δ suficientemente peque˜ no para que (1 − δ)2 (1 − 2δ) ≥ (1 − ε/2)

(Definici´ on de δ)

y sean a = a(δ), b = b(δ) y t0 = t0 (δ) dados por la definici´ on de (c, λ, θ)-mediana. Consideremos adem´ as A una constante suficientemente grande dependiente s´ olo de δ, ε y los 0 datos del problema y elijamos t0 > t (δ) suficientemente grande de modo que para todo t ≥ t0 , g(t) ≤ g0 tη

y

g0 bAtη ≤ tθ−λ . 34

(4.3.1)

Cap´ıtulo 4: Problema del subhipergrafo mon´otono de tama˜ no m´aximo

Sean ahora t > t0 y n1 , n2 , . . . , nd de promedio geom´etrico N y suma S que satisfagan las condiciones de tama˜ no y balanceo para estas constantes, es decir, tales que: N ≥ Atλ

S ≤ g(t)N ≤ g0 N tη

y

y sea H un hipergrafo elegido de acuerdo a D(Kn1 ,...,nd ). Si los nj satisfacen las cotas de tama˜ no en la definici´ on de (c, λ, θ)-mediana, tendr´ıamos gracias a que el modelo posee una constante de concentraci´ on, una cota de concentraci´ on en torno a cN t−λ que nos servir´ıa para proseguir. Sin embargo, puede que S sea demasiado grande para satisfacer la cota superior en el tama˜ no. Por dicha raz´ on, descompondremos H en subhipergrafos que tengan tama˜ no adecuado. La idea es dividir H en subhipergrafos del mismo tama˜ no, que denotaremos bloques, y de tal forma que, en cierto modo, sean proporcionales a H. La divisi´ on no ser´ a exacta puesto que el n´ umero de v´ertices de cada clase no necesariamente ser´ a divisible por el n´ umero de bloques. Sin embargo podremos suplir este inconveniente haciendo que el bloque final de la divisi´ on m´ as peque˜ no que los dem´ as. no (y probablemente un bloque Sea q = dN/(Atλ )e. Dividiremos H en q bloques del mismo tama˜ adicional m´ as peque˜ no). Para cada 1 ≤ j ≤ d definamos n0j = bnj /qc a ser el largo de la clase j de un bloque y llamemos N 0 al promedio geom´etrico de dichos largos y S 0 a su suma. Definamos con esto para todo 1 ≤ i ≤ q el hipergrafo Hi inducido por los v´ertices: Clase A1 : (i − 1)n01 +1, . . . , in01 . Clase A2 : (i − 1)n02 +1, . . . , in02 . .. .

Clase Ad : (i − 1)n0d +1, . . . , in0d . n01

A1 A2 A3

H1

n02

n03

H2

2n01 2n02

H3

3n02

2n03

3n01

H4

3n03

4n01

n1

4n02 n2

4n03

n3

Figura 4.2: Divisi´ on de un hipergrafo H en q = 4 bloques del mismo tama˜ no. Debido a que las clases de H no son m´ ultiplos de 4 en algunas de ellas sobran v´ertices. Las clases de los 4 bloques H1 , H2 , H3 , H4 tienen largos pr´ acticamente proporcionales a los de las clases correspondientes de H. Con esto, para todo i, Hi se distribuye de acuerdo a D(Kn01 ,...,n0d ). Adem´ as los L(Hi ) al ser disjuntos son independientes entre s´ı. Notemos adem´ as que la uni´ on de todos estos bloques no 35

Cap´ıtulo 4: Problema del subhipergrafo mon´otono de tama˜ no m´aximo

necesariamente cubre todo H. De hecho en la clase j hay nj − qbnj /qc ≥ 0 v´ertices sin usar. No nos preocuparemos de dichos v´ertices pues todo lo que necesitamos de ahora en adelante es que Pq L(H) ≥ i=1 L(Hi ). Por otro lado, por definici´ on

N N 2N ≤q ≤ λ +1≤ . λ At At Atλ

(Estimaci´ on de q)

Necesitaremos del siguiente lema para estimar N 0 , Lema 4.5. Para toda colecci´ on de reales positivos (xj )1≤j≤d ,  d−1 d d d Y Y X (xj − 1) ≥ xj −  xj  . j=1

j=1

j=1

Demostraci´ on. Lo probaremos por inducci´ on en d. Para d = 1 se tiene igualdad, y en general para d ≥ 2 si asumimos que el lema es cierto para todo valor menor que d, se tendr´ a   d d d−1 d−1 d−1 Y Y Y Y Y xj − (xj − 1) = (xd − 1)  xj − (xj − 1) + xj j=1

j=1

j=1



≤ (xd − 1)  

=

d−1 X j=1

d−1 X j=1

j=1

xj 

d−2 

xj 

d−2

j=1



+

 xd − 1 +

d−1 X j=1

d−1 X j=1

d−1

xj  

 d−1 d X xj  ≤  xj  .



j=1

Gracias al lema anterior, a la estimaci´ on de q y a la condici´ on de balanceo,     d−1 1/d 1/d  1/d d  d  d d Y Y Y X nj nj nj  nj   N  = ≥ N0 ≥  −1  ≥ −  q q q q q j=1

j=1

j=1

j=1

 i1/d 1  1h d 2N d−1 d−1 η(d−1) 1/d d−1 d = N − qS ≥ N − λ g0 N t q q At   N 2 d−1 η(d−1)−λ 1/d = 1 − g0 t . q A

Ahora, usando que η(d − 1) < λ e imponiendo A suficientemente grande, se tiene:   N N 2 d−1 1/d N 0 ≥N ≥ 1 − g0 ≥ (1 − δ). (Estimaci´on de N 0 ) q q A q 36

Cap´ıtulo 4: Problema del subhipergrafo mon´otono de tama˜ no m´aximo

Usando la estimaci´ on anterior y la estimaci´ on para q, probaremos que n01 , . . . , n0d cumplen las cotas de tama˜ no dadas por la definici´ on de (c, λ, θ)-mediana. En efecto recordando (4.3.1) e imponiendo A ≥ 2a/(1 − δ), N 1 (1 − δ) ≥ Atλ (1 − δ) ≥ atλ , q 2 λ Sb SbAt ≤ ≤ g0 bAtλ+η ≤ tθ . S 0b ≤ q N N0 ≥

Con esto, si H 0 se distribuye de acuerdo a D(Kn01 ,...,n0d ) y llamamos Med0 a una mediana de L(H 0 ), se tendr´a en virtud de la definici´ on de (c, λ, θ)-mediana, que cN 0 t−λ (1 − δ) ≤ Med0 ≤ cN 0 t−λ (1 + δ). Luego, por desigualdad de Markov y recordando que h es constante de concentraci´ on de D y que N 0 ≥ Atλ (1 − δ)/2,   cN 0 cN 0 0 0 E[L(H )] ≥ (1 − 2δ) λ P L(H ) ≥ (1 − 2δ) λ t t      0 1 − 2δ cN 0 0 ≥ (1 − 2δ) λ 1 − P L(H ) ≤ Med t 1−δ      cN 0 δ 0 0 = (1 − 2δ) λ 1 − P L(H ) ≤ 1 − Med t 1−δ    cN 0 δ2 0 ≥ (1 − 2δ) λ 1 − 2 exp −h Med t (1 − δ)2    cN 0 δ2 cN 0 ≥ (1 − 2δ) λ 1 − 2 exp −h t (1 − δ) tλ    0 cN hδ2 c ≥ (1 − 2δ) λ 1 − 2 exp − A . t 2 Como A lo podemos tomar suficientemente grande,Plo anterior se puede hacer mayor o igual que (1 − 2δ)(1 − δ)cN 0 t−λ . Luego, usando que L(H) ≥ qi=1 L(Hi ), la estimaci´ on de N 0 y la definici´ on de δ,

E[L(H)] ≥ q E[L(H 0 )] ≥ (1 − 2δ)(1 − δ)

qcN 0 cN ≥ (1 − 2δ)(1 − δ)2 λ λ t t

≥ (1 − ε/2)M ≥ (1 − ε)M, lo que concluye la demostraci´ on de la cota inferior para la esperanza dada por (4.2.1). Para probar la cota para la cola inferior (4.2.3) notemos que:   X cN P L(H) ≤ (1 − ε) λ ≤ P [L(Hi ) = si , i = 1 . . . q] . t q

N

(s1 ,...,sq )∈ s1 +···+sq ≤(1−ε)cN t−λ

37

Cap´ıtulo 4: Problema del subhipergrafo mon´otono de tama˜ no m´aximo

Llamemos T al conjunto de ´ındices de la suma anterior y para todo T = (s1 , . . . , sq ) ∈ T , denotemos PT = P [L(Hi ) = si , i = 1 . . . q]. Probaremos que PT es exponencialmente peque˜ na con −λ respecto a cN t . En efecto, como los L(Hi ) son independientes y est´ an id´enticamente distribuidos, PT =

q Y i=1

P[L(Hi ) = si ] ≤

q Y i=1

P[L(H 0 ) ≤ si ].

no adecuado para usar la aproximaci´ on de la mediana. Luego, Recordemos que H 0 tiene tama˜ 0 por definici´ on de (c, λ, θ)-mediana, si llamamos como antes Med a una mediana de L(H 0 ) se tendr´ a que para todos aquellos i tales que si ≤ (1 − δ)cN 0 t−λ ≤ Med0 ≤ (1 + δ)cN 0 t−λ ≤ 2cN 0 t−λ ,     Med0 −si 0 0 0 P[L(H ) ≤ si] = P L(H ) ≤ 1 − Med Med0   (Med0 −si )2 ≤ 2 exp −h Med0   htλ 0 −λ 2 ((1 − δ)cN t − s ) ≤ 2 exp − . i 2cN 0 Luego, para todo 1 ≤ i ≤ q,

  htλ 0 −λ 2 P[L(H ) ≤ si] ≤ 2 exp − m´ ax(0, (1 − δ)cN t − si ) 2cN 0 0

y entonces − ln PT ≥ −

q X i=1

ln P[L(H 0 ) ≤ si ]

≥ −q ln(2) +

q htλ X m´ ax(0, (1 − δ)cN 0 t−λ − si )2 . 2cN 0 i=1

Pero por Cauchy-Schwartz, recordando que N 0 q ≥ N (1 − δ) y la definici´ on de δ, v u q q X u X tq m´ ax(0, (1 − δ)cN 0 t−λ − si )2 ≥ m´ ax(0, (1 − δ)cN 0 t−λ − si ) i=1

i=1

0

≥ (1 − δ)cN qt

−λ

−

q X

si

i=1

≥ (1 − δ)2 cN t−λ − (1 − ε)cN t−λ


≥ cN t−λ (1 − δ)2 (1 − 2δ) − (1 − ε) cN ε ≥ λ. 2t 38

Cap´ıtulo 4: Problema del subhipergrafo mon´otono de tama˜ no m´aximo

Notando que lo anterior es positivo y recordando que N ≥ N 0 q, se tiene, − ln PT ≥ −q ln(2) +

q htλ X m´ ax(0, (1 − δ)cN 0 t−λ − si )2 2cN 0 i=1

c2 N 2 ε2 2cN 0 q 4t2λ hcN ε2 ≥ −q ln(2) + . 8tλ ≥ −q ln(2) +

htλ

·


Con esto, usando la estimaci´ on ab ≤ (ea/b)b ,   n cN cN o P L(H) ≤ (1 − ε) λ ≤ (s1 , . . . , sq ) ∈ Nd | s1 + · · · + sq ≤ (1 − ε) λ · m´ax PT T ∈T t t   −λ b(1 − ε)cN t c ≤ · m´ ax PT T ∈T q   hcN ε2 −λ ≤ exp q ln(e(1 − ε)cN t /q) + q ln 2 − 8tλ     2e(1 − ε)cN t−λ hcN ε2 ≤ exp q ln − . q 8tλ Ahora, recordando que N ≤ qAtλ ≤ 2N e imponiendo A suficientemente grande de modo que 32 ln(2e(1 − ε)cA) ≤ Ahcε2 , se tiene que:     cN 2N hcN ε2 P L(H) ≤ (1 − ε) λ ≤ exp ln (2e(1 − ε)cA) − t Atλ 8tλ   hN cε2 hcN ε2 ≤ exp − 16tλ 8tλ   2 hε cN = exp − . 16tλ Lo que concluye la demostraci´ on de la cota para la cola inferior (4.2.3). Para demostrar la cota inferior para la mediana en (4.2.2) basta recordar que N ≥ Atλ , con lo cual el lado derecho de la u ´ ltima desigualdad es menor o igual a   hcε2 exp − A . 16 Imponiendo A suficientemente grande, lo anterior se puede hacer menor o igual a 1/2. Es decir,   hemos probado que P L(H) ≤ (1 − ε)cN t−λ ≤ 1/2, lo que implica que toda mediana de L(H) es mayor o igual a (1 − ε)cN t−λ .

39

Cap´ıtulo 4: Problema del subhipergrafo mon´otono de tama˜ no m´aximo

Comentarios. 1. En la demostraci´ on que acabamos de concluir encontramos que la la cota para la cola inferior (4.2.3) se satisface para cualquier constante K ≤ 1/16. En realidad, rehaciendo la demostraci´ on con cotas m´ as precisas, e imponiendo δ m´ as peque˜ no y A m´ as grande, podemos hacer que K tome cualquier valor estrictamente menor que 1. 2. La demostraci´ on de las cotas inferiores del Teorema Principal tambi´en puede ser aplicada a otras familias de distribuciones que no sean necesariamente modelos de d-hipergrafo como tal. (d) En particular, la misma demostraci´ on es v´ alida para familias del tipo D = D(Kn ), es decir, para familias de distribuciones restringidas a los hipergrafos tales que todas sus clases tienen el mismo largo. La u ´ nica condici´ on que necesitamos es que estas familias mantengan la propiedad de monotonicidad e independencia por bloques, entendiendo que los u ´ nicos subhipergrafos validos son los que tienen sus clases del mismo largo. La raz´ on por la cual la demostraci´ on sigue funcionando en dicho caso, es que si H es un hipergrafo con todas sus clases del mismo largo, entonces al dividirlo en bloques “proporcionales” al original, los hipergrafos resultantes siguen teniendo sus clases del mismo largo. Este argumento nos servir´ a para poder aplicar esta demostraci´ on a la variante sim´etrica que se estudiar´ a en el Cap´ıtulo 5.

4.4.

Demostraci´ on de la cotas superiores en el Teorema Principal

En esta secci´ on probaremos las cotas superiores dadas por el Teorema Principal, es decir, probaremos la cota superior de (4.2.1), la cota superior de (4.2.2) y la desigualdad (4.2.4). Demostraremos en detalle (4.2.4). La demostraci´ on de esta cota es bastante extensa, por lo cual la hemos dividido en tres partes. En la primera parte definimos algunas variables que nos ser´ an de utilidad y algunas desigualdades que usaremos frecuentemente. Estas definiciones son relativamente t´ecnicas por lo cual se recomienda usar esta secci´ on m´ as que nada como referencia. A continuaci´ on demostraremos las cotas para el caso cuando el promedio geom´etrico de las clases del hipergrafo, N no es muy grande, en particular cuando N = o(tθ−η ). Finalmente trataremos el caso cuando N es grande.

4.4.1.

Notaci´ on y definiciones

Consideremos D un modelo de d-hipergrafo aleatorio con par´ ametro interno t, constante de concentraci´ on h y que admite una (c, λ, θ)-mediana. Sean adem´ as ε > 0, η < m´ın {λ/(d − 1), θ − λ} y g : N → N como en la hip´ otesis del teorema, en particular, sabemos que existe una constante η g0 > 1 tal que g(t) ≤ g0 t cuando t es suficientemente grande.

40

Cap´ıtulo 4: Problema del subhipergrafo mon´otono de tama˜ no m´aximo

Definamos 

ε2 ε δ = m´ın 1, , (1 + ε) 6



0

0

, a = a(δ), b = b(δ), t = t (δ), A = m´ ax



a 8 ln 2 , δ hδc



,

(4.4.1)

on de (c, λ, θ)-mediana. con a(δ), b(δ) y t0 (δ) los valores entregados por la definici´ Elijamos adem´ as dos constantes arbitrarias α y β tales que: λ < α < β < θ − η.

(4.4.2)

La idea detr´ as de la definici´ on de estas constantes es aprovechar el hecho que si ρ1 < ρ2 entonces ρ ρ 1 2 t = o(t ). olo de la dimenDurante la demostraci´ on encontraremos dos constantes K1 y K2 , dependientes s´ si´ on d del problema. Con ellas, podremos elegir t0 mayor que t0 de modo que para todo t ≥ t0 , se tenga g(t) ≤ g0 tη , 1 θ−η 9Atλ < tα < tβ < t (4.4.3) bdg0 y 2αK1 λ tα t < . (4.4.4) δcK2 h ln t Las constantes t0 y el A reci´en definidos ser´ an los que entregar´ a esta parte del teorema. Sean ahora t ≥ t0 y un conjunto de enteros positivos n1 , n2 , . . . , nd , de promedio geom´etrico N y suma S que satisfagan las condiciones de tama˜ no (N ≥ Atλ ) y de balanceo (S ≤ g(t)N ). Sea adem´ as M = cN t−λ y H elegido de acuerdo a D(Kn1 ,...,nd ). Dividiremos la demostraci´ on de la cota para la cola en dos casos de acuerdo a si N es mayor o menor que tβ .

4.4.2.

Demostraci´ on para el caso N < tβ

Si N < tβ podremos probar que H tiene tama˜ no adecuado para aplicar la definici´ on de (c, λ, θ)mediana con lo cual, recordando que D posee una constante de concentraci´ on h, encontraremos una cota exponencial para P (L(H) ≥ (1 + ε)M ). Por las condiciones de tama˜ no y balanceo, la definici´ on de A en (4.4.1) y la desigualdad (4.4.3), 1. N ≥ Atλ ≥ atλ /δ ≥ atλ . 2. Sb ≤ g(t)bN ≤ g0 btη+β ≤ tθ /d ≤ tθ . Lo anterior prueba que n1 , . . . , nd satisfacen las cotas de tama˜ no dadas por la definici´ on de (c, λ, θ)mediana. Luego, si H es elegido de acuerdo a D(Kn1 ,...,nd ), entonces toda mediana de L(H) est´ a

41

Cap´ıtulo 4: Problema del subhipergrafo mon´otono de tama˜ no m´aximo

entre M (1 − δ) y M (1 + δ). Sigue que para Med una mediana de L(H),     (1 + ε)M − Med P (L(H) ≥ (1 + ε)M ) ≤ P L(H) ≥ 1 + Med Med   ((1 + ε)M − Med)2 / Med2 ≤ 2 exp −h Med [(1 + ε)M/ Med]   ((1 + ε)M − Med)2 = 2 exp −h (1 + ε)M   (ε − δ)2 ≤ exp ln 2 − h M . (1 + ε) Recordando la definici´ on de A y que δ ≤ ε/2 < ε/6, lo anterior es menor a:     hε2 hε2 ε2 hnc Ahδc − exp − M ≤ exp M 8 4(1 + ε) (1 + ε) 8tλ 4(1 + ε)   hε2 = exp − M , 8(1 + ε) y luego la cota buscada para la concentraci´ on se tiene tomando K cualquier constante menor o igual a 1/8. Hemos probado as´ı que la cota se tiene cuando N < tβ .

4.4.3.

Demostraci´ on para el caso N ≥ tβ

En esta subsecci´ on, probaremos la cota para el caso N ≥ tβ . En esta ocasi´ on no podremos probar que H tiene un tama˜ no adecuado para aplicar la definici´ on de (c, λ, θ)-mediana y as´ı obtener la cota exponencial buscada. Sin embargo, de manera similar a como lo hicimos para probar las cotas inferiores del Teorema Principal, podremos dividir H en bloques que si tengan esta condici´ on.

Partici´ on en bloques Definamos l = tα , L = g0 tη+α y mmax = d(1 + ε)M e .

(4.4.5)

En lo que sigue acotaremos superiormente la cantidad P (L(H) ≥ mmax ), es decir, la probabilidad de que H posea un subhipergrafo mon´ otono con al menos mmax aristas. Notemos que ning´ un subhipergrafo mon´ otono de H puede tener un n´ umero de aristas mayor que el tama˜ no de alguna de las clases de H. Esto se debe a que cada arista usa un v´ertice de cada clase y en un subhipergrafo mon´ otono las aristas no comparten v´ertices. En consecuencia L(H) debe ser menor que N , el promedio geom´etrico de los largos de las clases y por lo tanto, si mmax

42

Cap´ıtulo 4: Problema del subhipergrafo mon´otono de tama˜ no m´aximo

es mayor que N la probabilidad anterior resulta ser 0. Por esto en lo que sigue asumiremos adem´ as que mmax ≤ N . Sea J un subhipergrafo mon´ otono sobre el mismo conjunto de v´ertices que Kn1 ,...,nd con mmax aristas. Definiremos una partici´ on de E(J) en bloques de aristas consecutivas, de modo que cada bloque no ocupe m´ as de L nodos consecutivos de cada clase de partici´ on y cada bloque no tenga demasiadas aristas. Espec´ıficamente, si llamamos   l mmax smax = (4.4.6) N pediremos que cada bloque de la partici´ on no tenga m´ as de smax aristas. Dadas dos aristas e y ee de J, con e ≤ ee, denotamos [e, ee] al subconjunto de aristas ubicadas entre e y ee, usando el orden natural (coordenada a coordenada) definido anteriormente. Es decir [e, ee] = {f ∈ E(J) | e ≤ f ≤ ee}.

Denotaremos partici´ on en bloques de E(J) al conjunto P(J) = {[ei , eei ] | 1 ≤ i ≤ q}, con   (i) (i) (i) (i) (i) (i) ei = v1 , v2 , . . . vd , eei = ve1 , ve2 , . . . ved , construido de la siguiente forma: 1. e1 es la primera arista de E(J).

a definida, eei es la mayor arista de E(J) que cumple: 2. Una vez que ei est´ a) [ei , eei ] tiene a lo m´ as smax elementos. (i)

(i)

b) vej − vj ≤ L para todo 1 ≤ j ≤ d. (Esto es, con un poco de abuso de notaci´ on, recordando que cada clase de partici´ on de K tiene sus nodos numerados 1, 2, . . . , nj ).

3. Una vez definido eei , si todav´ıa quedan aristas mayores en E(J), tomamos ei+1 como la arista inmediatamente mayor a eei . (1)

A1

(1)

v1

(2)

(2)

v1

A2 A3

(3)

v1

[e1 , ee1 ]

ve2

ve1

(3)

ve1

(1)

(1)

v2

(2)

v2

ve2

(2)

[e2 , ee2 ] (3)

v2

ve2

(3)

ve2

Figura 4.3: Partici´ on en bloques de un hipergrafo H. Cada bloque [ei , eei ] posee a lo m´ as smax aristas y cada clase de un bloque no tiene m´ as de L v´ertices.

43

Cap´ıtulo 4: Problema del subhipergrafo mon´otono de tama˜ no m´aximo

La partici´ on en bloques definida de esta forma, es una partici´ on de E(J) en q bloques consecutivos. Probaremos las siguientes cotas para q: N 3N ≤q≤ . l l

(Estimaci´ on de q)

En efecto:  Cada bloque tiene a lo m´ as smax aristas, luego q ≥ mmax /smax ≥ N/l.  Denotemos bloques cortos al bloque final [eq , eeq ] y a todos aquellos bloques que tengan ex-

actamente smax aristas. Sea B0 ⊆ [q] el conjunto de ´ındices de los bloques cortos. Luego mmax ≥ (|B0 | − 1)smax ≥ (|B0 | − 1)(mmax l/N − 1). Como mmax l/N es suficientemente grande, sigue que |B0 | ≤ 2N/l.

 Denotemos bloques regulares a aquellos bloques que no son cortos y sea B1 = [q] \ B0 . Adem´ as,

llamemos cubrimiento del bloque a todos los nodos contenidos entre la primera arista del bloque (inclusive) y la primera arista del bloque siguiente (sin incluir). Por definici´ on de la partici´ on, si el bloque i-´esimo es regular, entonces se tendr´ a que para Pd (i+1) (i) (i+1) (i) alguna de las clases j, vj − vj ≥ L. Sigue que − vj ) ≥ L. Es decir, el j=1 (vj n´ umero de nodos que cubre el bloque es al menos L. Como todos los nodos son cubiertos por exactamente un bloque, se concluye que |B1 | ≤ S/L ≤ N g0 tη /L = N/l.

 Las observaciones anteriores dicen que q = |B0 | + |B1 | ≤ 3N/l.

Tipos de particiones Sea si el n´ umero de aristas de E(J) en el bloque i. Definimos el tipo de la partici´ on T = T (M ) a la 3q-tupla T = (e1 , ee1 , s1 , . . . , eq , eeq , sq ).

Sea adem´ as T el conjunto de todos los posibles tipos de particiones de un subhipergrafo mon´ otono de K con mmax aristas. Lema 4.6. Para alguna constante K1 que s´ olo depende de d,   N |T | ≤ exp K1 ln l . l Demostraci´ on. Notemos que las aristas ei se determinan completamente al indicar sus v´ertices. Luego el n´ umero de formas de elegir e1 , . . . , eq es a lo m´ as el n´ umero de elegir q elementos en cada
Qd ni uno de las clases de partici´ on de los nodos, es decir i=1 q . Similarmente, el n´ umero de formas de elegir ee1 , . . . , eeq est´ a acotado por la misma cantidad. 44

Cap´ıtulo 4: Problema del subhipergrafo mon´otono de tama˜ no m´aximo

Por otro lado, el n´ umero de elecciones para los si es menor que el n´ umero de particiones de mmax en q sumandos positivos. Como asumimos al principio de la subsecci´ o n que mmax ≤ N , se tiene que

N a la cantidad anterior es menor que q . Usando la estimaci´ on b ≤ (ea/b)b se obtiene que, para un q fijo, el n´ umero de tipos est´ a acotado por: !   Y d   2 ni N ≤ (eN/q)q q q i=1

d Y (eni /q)q i=1

!2

q

= (eN/q)

d Y

eni /q

i=1

!2q

= (eN/q)q+2qd .

Usando las estimaciones obtenidas para q se obtiene que:

|T | ≤

b3N/lc

X

q=dN/le

(eN/q)q(1+2d) ≤ 3

N l



eN (N/l)

(1+2d)3N/l

=3

N (el)(1+2d)3N/l , l

y luego: ln |T | ≤ ln



3N l



+ (1 + 2d)3

N N N (1 + ln(l)) ≤ (2 + 2d)3 (1 + ln(l)) ≤ (1 + d)12 ln l. l l l



Probabilidad de un subhipergrafo mon´ otono con un tipo de partici´ on de bloques A continuaci´ on veremos que para cada tipo fijo T la probabilidad de que un hipergrafo elegido seg´ un D(Kn1 ,...,nd ) contenga un subhipergrafo mon´ otono del tipo T con mmax aristas es exponencialmente peque˜ na con respecto a M . Lema 4.7. Para cada tipo T ∈ T , la probabilidad PT de que un hipergrafo elegido seg´ un D(Kn1 ,...,nd ) contenga un subhipergrafo mon´ otono J con mmax aristas, tal que T (J) = T cumple,   ε2 PT ≤ exp −K2 h M , (1 + ε) para alguna constante absoluta, K2 > 0. Demostraci´ on. Sea T = (e1 , ee1, s1 , . . . , eq , eeq , sq ) un tipo de partici´ on y, como antes, para todo i, (i) (i) (i) (i) (i) (i) llamemos ei = v1 , v2 , . . . vd y eei = ve1 , ve2 , . . . ved . Sea H elegido de acuerdo a D(Kn1 ,...,nd ), y sea Hi el subhipergrafo inducido por los v´ertices entre ei y eei , es decir por los v´ertices (i)

(i)

(i)

(i)

(i)

(i)

(i)

(i)

(i)

v1 , v1 +1, . . . , ve1 , v2 , v2 +1, . . . , ve2 , .. . vd , vd +1, . . . , ved . 45

Cap´ıtulo 4: Problema del subhipergrafo mon´otono de tama˜ no m´aximo

  (i) (i) (i) Notemos que Hi se distribuye de acuerdo a D Kn(i) ,n(i) ,...,n(i) , donde nj = vej − vj + 1 son los 1

2

d

largos en cada clase de partici´ on. Adem´ as. si existe un subhipergrafo J de H tal que T (J) = T , entonces se debe tener que L(Hi ) ≥ si para todo i = 1, . . . , q. Como los eventos L(Hi ) ≥ si son independientes para distintos i (recordar que D es un modelo independiente por bloques), se tiene que: PT ≤

q Y i=1

h  

P L D Kn(i) ,n(i) ,...,n(i) 1

2

d



i ≥ si .

Q  (i) 1/d d Denotemos por Ni = n al promedio geom´etrico de los largos de las clases de Hi y j=1 j Pd (i) nos de las clases de Hi cumplen las cotas por Si = j=1 nj a su suma. Si para cada i, los tama˜ de tama˜ no en la definici´ on de (c, λ, θ)-mediana, entonces todas las probabilidades anteriores ser´ an peque˜ nas. (i)

(i)

(i)

Por construcci´ on de los bloques: n1 , n2 , . . . , nd ≤ L. Luego Si b ≤ dbL = g0 dbtη+α < tθ . Sin embargo, la cota inferior en el tama˜ no, Ni ≥ atλ , puede fallar por lo cual artificialmente aumentaremos el tama˜ no de los bloques donde esta condici´ on falle. Espec´ıficamente, definamos para todo i: (i)

(i)

(i)

(i)

(i)

(i)

n ¯ 1 = m´ ax(δn1 Atλ /N, n1 ), n ¯ 2 = m´ ax(δn2 Atλ /N, n2 ), .. . n ¯ d = m´ ax(δnd Atλ /N, nd ). Q  (i) 1/d d Como es costumbre, llamemos N i = n ¯ al promedio geom´etrico de los nuevos largos j=1 j Pd (i) de las clases y S i = j=1 n ¯ j a su suma.

Notemos que si aumentamos los tama˜ nos de las clases de partici´ on de un hipergrafo, por monotonicidad, la probabilidad de que posea un emparejamiento mon´ otono de si aristas aumenta. Luego PT ≤

q Y i=1

q h    i Y h    i P L D Kn(1) ,n(2) ,...,n(d) ≥ si ≤ P L D Kn¯ (1) ,¯n(2) ,...,¯n(d) ≥ si . i

i

i

i=1

i

i

i

Veamos que los nuevos largos s´ı cumplen las cotas de tama˜ no buscadas. En efecto, recordando la desigualdad (4.4.3), podemos ver que para todo j, δnj Atλ /N ≤ δnj tα /N ≤ δStα /N ≤ δg(t)tα ≤ δg0 tα+η = δL ≤ L. 46

Cap´ıtulo 4: Problema del subhipergrafo mon´otono de tama˜ no m´aximo

(i)

(i)

Luego, como los nj tambi´en son menores que L se concluye que los n ¯ j son menores que L y con θ esto, al igual que antes de agrandar los bloques, S i b ≤ t . Por otro lado, recordando que A ≥ a/δ, Ni =

Y d

(i)

n ¯j

j=1

1/d

≥

 d 1/d δAtλ Y nj = δAtλ ≥ atλ . N j=1

Sigue que los nuevo tama˜ nos cumplen las cotas dadas por la definici´ on de (c, λ, θ)-mediana. Sea ahora Medi una mediana de L(D(Kn¯ 1 ,¯n2 ,...,¯nd ), t)). Por definici´ on de (c, λ, θ)-mediana, i

i

i

(1 − δ)cN i t−λ ≤ Medi ≤ (1 + δ)cN i t−λ . on Luego, para los i tales que si ≥ (1 + δ)cN¯i t−α ≥ Medi , usando que h es constante de concentraci´ para el modelo, se tendr´ a ! 

2 h    i si Medi − 1  P L D Kn¯ (1) ,¯n(2) ,...,¯n(d) ≥ si ≤ 2 exp −h Medi i i i si Medi   (si − Medi )2 = 2 exp −h si   (si − (1 + δ)cN i t−λ )2 ≤ 2 exp −h . si Luego para todo i, recordando que si , el n´ umero de aristas del bloque i es a lo m´ as smax ,   h    i m´ ax(0, si − (1 + δ)cN i t−λ )2 P L D Kn¯ (1) ,¯n(2) ,...,¯n(d) ≥ si ≤ 2 exp −h si i i i   m´ ax(0, si − (1 + δ)cN i t−λ )2 ≤ 2 exp −h . smax Con esto: − ln PT ≥ − ln =−

q X i=1

q Y i=1

ln

h    i P L D Kn¯ (1) ,¯n(2) ,...,¯n(d) ≥ si i

i

i

!

 h    i P L D Kn¯ (1) ,¯n(2) ,...,¯n(d) ≥ si

≥ −q ln(2) +

i

q h X

smax

i=1

i

i

m´ ax(0, si − (1 + δ)cN i t−λ )2 .

Acotemos inferiormente la suma del lado derecho de la u ´ ltima expresi´ on obtenida. Para ello usaremos la siguiente desigualdad de H¨ older generalizada: 47

Cap´ıtulo 4: Problema del subhipergrafo mon´otono de tama˜ no m´aximo

Lema 4.8 (Desigualdad de H¨ older generalizada). Para toda colecci´ on de n´ umeros positivos xi,j , 1 ≤ i ≤ q, 1 ≤ j ≤ d,  d q Y q d d X X Y   xi,j ≤ xdi,j . i=1 j=1

j=1 i=1

  (i) 1/d Usando la desigualdad anterior, para la colecci´ on xi,j = n ¯j , se tiene que q X

Ni =

i=1

q Y d X

i=1 j=1



≤

xi,j ≤ 

q  d X Y

j=1 i=1

≤

d  Y



q d X Y

j=1 i=1

(i) n ¯j 

1/d  (i) n + δnj Atλ /N  j

nj + δqnj Atλ /N

j=1

1/d

1/d



=

d Y

j=1



  1/d nj  1 + δqAtλ /N .

Recordando las cotas obtenidas para q y la desigualdad (4.4.3), se concluye que: q X i=1

N i ≤ N (1 + 3δAtλ−α ) ≤ N (1 + δ/3) ≤ N (1 + δ).

Usando la desigualdad anterior, la desigualdad de Cauchy-Schwartz y recordando que la suma de los si es exactamente mmax = d(1 + ε)M e, se tiene: v u q q   u X
2 X tq −λ m´ ax 0, si − (1 + δ)cN i t ≥ m´ ax 0, si − (1 + δ)cN i t−λ i=1

i=1

≥ mmax − (1 + δ)ct

−λ

q X

Ni

i=1 2

≥ M (1 + ε) − M (1 + δ) .

Veamos que el lado derecho es positivo, para eso recordemos que por definici´ on δ ≤ ε/6 . Con esto, (1 + ε) − (1 + δ)2 = ε − 2δ − δ2 ≥ ε − 3δ ≥ ε/2. Es decir:

v u q u X
2 εM tq m´ ax 0, si − (1 + δ)cN i t−λ ≥ . 2 i=1

48

Cap´ıtulo 4: Problema del subhipergrafo mon´otono de tama˜ no m´aximo

Lo anterior implica que: − ln PT ≥ −q ln(2) + ≥ −q ln(2) +

q h X

smax

i=1

2  m´ ax 0, si − (1 + δ)cN i t−λ

ε2 M 2 . smax q 4 h

·

Adem´ as, por definici´ on, smax ≤ (1 + ε)

lM . N

Luego: − ln PT ≥ −q ln(2) +

hN ε2 M . 4q(1 + ε)l

Finalmente, recordando que q ≤ 3N/l, y que l ≥ 9Atλ , se concluye que: N ln(2) hε2 M + 3Atλ 12(1 + ε)   2 cN hε ln(2) − . = λ t 12(1 + ε) 3Ac

− ln PT ≥ −

Dado que A ≥ 8 ln(2)/(hcδ) y δ ≤ ε2 /(1 + ε),

  cN hε2 hδ − ln PT ≥ λ − t 12(1 + ε) 24 ε2 hM ≥ , (1 + ε) 24

con lo cual la constante K2 buscada en el Lema 4.7 resulta ser positiva y mayor o igual que 1/24. 

Demostraci´ on de la cota para la cola superior para el caso N ≥ tβ Demostraci´ on de (4.2.4). Tenemos que

P [L(D(Kn1 ,n2 ,...,nd )) ≥ mmax ] ≤

49

X

T ∈T

PT ≤ |T | m´ ax PT . t∈T

Cap´ıtulo 4: Problema del subhipergrafo mon´otono de tama˜ no m´aximo

De los Lemas 4.6 y 4.7, la desigualdad (4.4.4) y la definici´ on de δ,   N ε2 M P [L(D(Kn1 ,n2 ,...,nd ), t)) ≥ mmax ] ≤ exp K1 ln l − K2 h l (1 + ε)   ln t ε2 = exp K1 αN α − K2 h M t (1 + ε)   δK2 h cN ε2 ≤ exp M − K2 h 2 tλ (1 + ε)   K2 hε2 ≤ exp − M . 2(1 + ε) Recordando que K2 era una constante absoluta (1/24), se tiene que cualquier constante K menor o igual a 1/24 sirve para la cota de concentraci´ on dada por (4.2.4). 

4.4.4.

Demostraci´ on de la cota superior para la esperanza y mediana en el Teorema Principal.

Ahora probaremos las cotas superiores de (4.2.1) y (4.2.2). Para la demostraci´ on de la cota superior de la esperanza, observemos primero que en la demostraci´ on anterior, para d y η fijos, A y t0 dependen solamente de δ y que para todo ε ≥ 2, δ = δ(ε) = 1 (Ver (4.4.1)). Sean ahora ε0 > 0, d, η y g como antes y K la constante entregada por la desigualdad (4.2.4) que acabamos de demostrar. Sea adem´ as, δ0 = δ(ε0 /2) como en (4.4.1) y A0 una constante suficientemente grande como para que   KhcA0 ε20 ε0 8 ≤ ε0 . exp − ≤ y (Elecci´on de A0 ) 2 4(1 + ε0 /2) 12 c A20 Kh e = m´ t0 = m´ ax{t0 (δ0 ), t0 (2)}. Definamos A ax{A(δ0 ), A(1), A0 } y e

Sean ahora t ≥ e t0 y valores n1 , . . . , nd de promedio geom´etrico N y suma S que satisfagan las e reci´en definidas, es decir, tales que: condiciones de tama˜ no y balanceo para estas constantes e t0 y A eλ N ≥ At

y

Sb ≤ g(t)N.

e garantiza que la desigualdad (4.2.4) es v´ La elecci´on de te0 y A alida tanto para ε = ε0 /2 como para todo ε ≥ 2. Sea H elegido de acuerdo a D(Kn1 ,...,nd ) y M = cN t−λ . Notemos primero que:

E[L(H)] = E[L(H)1[0,(1+ε0 /2)M ] (L(H))] + E[L(H)1[(1+ε0 /2)M,3M ] (L(H))] + E[L(H)1[3M,∞] (L(H))].

50

Cap´ıtulo 4: Problema del subhipergrafo mon´otono de tama˜ no m´aximo

Acotemos cada t´ermino por separado. El primero queda:

E[L(H)1[0,(1+ε0 /2)M ] (L(H))] ≤ (1 + ε0 /2)M. El segundo queda gracias a la desigualdad (4.2.4),

E[L(H)1[(1+ε0 /2)M,3M ] (L(H))] ≤ 3M P[L(H) > (1 + ε0 /2)M ] 

 Khε20 /4 cN ≤ 3M exp − · (1 + ε0 /2) tλ   M ε0 Khε20 /4 ≤ 3M exp − cA0 ≤ . (1 + ε0 /2) 4

Notando que para ε > 2, ε2 /(1 + ε) ≥ ε/2, se tiene que Z ∞ E[L(H)1[3M,∞] (L(H))] ≤ P[L(H) > (1 + ε)M ] dε 2   Z ∞ Khε2 exp − ≤ M dε (1 + ε) 2   Z ∞ Khε exp − ≤ M dε 2 2 2M 2M M ε0 2 exp(−M Kh) ≤ 2 ≤ 2 2 ≤ . = M Kh M Kh 4 c A0 Kh En resumen,

E[L(H)] ≤ (1 + ε0 /2)M + M ε0 /4 + M ε0 /4 = (1 + ε0 )M. Lo que completa la demostraci´ on de la cota superior para la esperanza. Para ver la cota superior para la Mediana, sea ε > 0 y sean A y t0 las constantes asociadas a este ε en la demostraci´ on de la cota para la cola superior (4.2.4). Si definamos   (1 + ε) ln(2) 0 A = m´ ax A, , Khcε2 entonces para todo t ≥ t0 y todo n1 , . . . , nd , de promedio geom´etrico N y suma S que satisfagan las condiciones de tama˜ no y balanceo para esta nueva constante A0 reci´en definida, es decir, tales que: N ≥ A0 tλ se tendr´a:

y



Sb ≤ g(t)N,

ε2 cN P[L(H) ≥ (1 + ε)M ] ≤ exp −Kh · λ 1+ε t





ε2 ≤ exp −Kh cA0 1+ε



≤ 1/2,

lo que implica que toda mediana de L(H) es menor o igual que (1 + ε/2)M . Esto concluye la demostraci´ on de la cota superior para la mediana, lo cual finaliza la demostraci´ on del Teorema Principal. 51

Cap´ıtulo 4: Problema del subhipergrafo mon´otono de tama˜ no m´aximo

Comentarios. En la demostraci´ on anterior se prob´ o que la cota para la cola superior (4.2.4) se satisface para cualquier constante K ≤ 1/48. Sin embargo, al igual que en la demostraci´ on para la cola inferior, si se rehace la demostraci´ on con cotas m´ as precisas, se puede hacer que K tome cualquier valor estrictamente menor que 1.

4.5.

Resultado para el modelo de d palabras aleatorias

En esta secci´ on probaremos que el modelo de d-palabras aleatorias admite una (c, λ, θ)-mediana, lo cual, gracias al Teorema Principal nos permitir´ a obtener estimaciones para la media y la mediana del tama˜ no del subhipergrafo mon´ otono m´ as grande para este modelo. Probaremos en particular que la constante c en la definici´ on de (c, λ, θ)-mediana para este modelo corresponde exactamente a la constante de Ulam para el problema de la secuencia creciente m´ as larga en d-dimensiones, denotada generalmente como cd .

4.5.1.

Problema de la secuencia creciente m´ as larga o problema de Ulam

Dada una permutaci´ on π ∈ Sn , llamamos secuencia creciente de largo L a toda secuencia 1 ≤ i1 < i2 < · · · < iL ≤ n tal que π(i1 ) < π(i2 ) < · · · < π(iL ). Ulam [18] en 1961, fue al parecer el primero en proponer la siguiente pregunta: ¿Cuan r´ apido crece el largo esperado de la secuencia creciente m´ as larga de una permutaci´ on en Sn con respecto a n? Por dicha raz´ on, el problema de determinar el comportamiento de dicho largo tambi´en es conocido en la literatura como el problema de Ulam. Denotemos LIS(n) a la variable aleatoria correspondiente al largo de la secuencia creciente m´ as larga de una permutaci´ on escogida de manera uniforme en Sn . Usamos esta notaci´on por las siglas en ingl´es del problema Longest Increasing Sequence. Ulam [18] dio un an´ alisis preliminar para determinar el comportamiento de esta variable. Usando simulaciones de Monte Carlo, Ulam not´ o √ que el valor esperado de LIS(n), a medida que n crece se aproxima a 2 n. Hammersley [19] en 1972, √ dio una demostraci´ on rigurosa de la convergencia en probabilidad de LIS(n)/ n a una constante, conjeturando que dicho valor es 2. Cinco a˜ nos m´ as tarde, trabajos de Logan y Shepp [20] y de Vershik y Kerov [21] permitieron demostrar la veracidad de dicha conjetura. Reescribamos el problema anterior de una manera que nos ser´ a m´ as u ´ til para nuestros prop´ ositos. Sea π ∈ Sn una permutaci´ on y sea X = X(π) el conjunto X(π) = {(i, π(i)) | 1 ≤ i ≤ n}. Con esto, toda secuencia creciente de π puede verse como una cadena (subconjunto totalmente ordenado) de X usando como orden el orden natural en N2 (es decir: (a, b) ≤ (c, d) ⇐⇒ a ≤ c ∧ b ≤ d). Usando la interpretaci´ on anterior, podemos extender este concepto a m´ as dimensiones (el caso original, corresponde a 2 dimensiones). Para d un entero positivo, y n ∈ N, consideremos d − 1 permutaciones, π1 , . . . , πd−1 ∈ Sn . Sea adem´ as X el conjunto {(i, π1 (i), . . . , πd−1 (i)) | 1 ≤ i ≤ n}. 52

Cap´ıtulo 4: Problema del subhipergrafo mon´otono de tama˜ no m´aximo

Llamaremos secuencia creciente de largo L de las permutaciones π1 , . . . , πd−1 a toda cadena de largo L en (X, ≤), donde (a1 , . . . , ad ) ≤ (b1 , . . . , bd ) ⇐⇒ ai ≤ bi para todo i. An´ alogamente al caso 2-dimensional, llamemos LISd (n) a la variable aleatoria correspondiente al largo de la secuencia creciente m´ as larga de d − 1 permutaciones π1 , . . . , πd−1 elegidas de manera uniforme e independientemente en Sn . El problema de Ulam d-dimensional corresponde entonces a estudiar la distribuci´ on de la variable LISd (n). El problema anterior puede ser visto tambi´en como un problema geom´etrico de la siguiente manera. Sean d y n enteros positivos fijos. Consideremos ~x(1), ~x(2), . . . , ~x(n) a ser n puntos elegidos de manera independiente y uniforme en el cubo unitario d-dimensional [0, 1]d . En este espacio definimos el orden parcial natural ≤ como: ~y ≤ ~z ⇐⇒ yi ≤ zi para todo 1 ≤ i ≤ d. Denotamos Hd (n) al largo de la cadena m´ as larga que podemos formar en este orden parcial. Se puede probar on. que Hd (n) y LISd (n) siguen la misma distribuci´ Bollobas y Winkler [11] probaron en 1992 que para todo d existe una constante cd tal que √ √ Hd (n)/ d n (y luego LISd (n)/ d n) tiende a cd en esperanza y en probabilidad cuando n → ∞. Los valores para dichas constantes, denotadas constantes de Ulam, no se conocen salvo por las dos primeras: c1 = 1 y c2 = 2, pero se sabe [11] que para todo d, cd < e y que l´ımd→∞ cd = e.

4.5.2.

Reducci´ on al problema de Ulam

Volvamos a nuestro problema. Sea H un hipergrafo elegido de acuerdo al modelo de d-palabras aleatorias Σ(Kn1 ,n2 ,...,nd , k), y sea H 0 el subhipergrafo de H obtenido al remover todas las aristas incidentes en nodos de grado 2 o mayor. Denotemos E y E 0 a E(H) y E(H 0 ) respectivamente. Para estimar una mediana de L(H) ser´ a necesario m´ as adelante estimar L(H 0 ). Notemos, sin embargo, 0 que L(H ) es precisamente el largo de la cadena m´ as larga que podemos formar en E 0 usando el as larga orden natural de aristas. En otras palabras, L(H 0 ) es el largo de la secuencia creciente m´ de d − 1 permutaciones en {1, 2, . . . , |E 0 |}. La observaci´ on anterior nos permitir´ a utilizar los resultados existentes para el problema de Ulam en el an´ alisis de nuestro problema. En particular, el siguiente teorema de Bollobas y Brightwell [10] de concentraci´ on de la secuencia creciente m´ as larga d-dimensional nos ser´ a de utilidad. Teorema 4.9. Para cada entero d ≥ 2, existe una constante Dd tal que, para m suficientemente grande, ! λDd m1/2d log m 2 P | LISd (m) − E LISd (m)| > ≤ 80λ2 e−λ log log m para todo λ con 2 < λ < m1/2d / log log m. No usaremos directamente el teorema, sino que demostraremos y usaremos el siguiente corolario: Corolario 4.10. Para todo entero d ≥ 2 y todo t > 0 y α > 0, existe un m0 (t, α, d) suficientemente 53

Cap´ıtulo 4: Problema del subhipergrafo mon´otono de tama˜ no m´aximo

grande tal que si m ≥ m0 , entonces   P | LISd (m) − cd m1/d | > tcd m1/d ≤ α.

con cd la constante para el problema de Ulam d-dimensional.

Demostraci´ on. Sean d, t y α como en la hip´ otesis y sea Dd la constante dada por el Teorema 4.9. √ De la definici´ on de la constante de Ulam [11], sabemos que l´ımn→∞ E LISd (m)/ d m = cd . Luego, podemos elegir un m0 = m0 (t, α, d) suficientemente grande tal que para todo m ≥ m0 las siguientes condiciones se cumplan: 1. |E LISd (m) − cd m1/d | < tcd m1/d /2. def

2. λ = λ(m) =

tcd m1/2d log log m m1/2d · ≤ . 2Dd log m log log m

2

3. 80λ2 e−λ ≤ α 4. El Teorema 4.9 es v´ alido para m. Estas condiciones se puede obtener pues (log log m)2 = o(log m) y l´ımm→∞ λ(m) = ∞. Sigue que, para todo m > m0 .   P | LISd (m) − cd m1/d | > tcd m1/d   ≤ P | LISd (m) − E LISd (m)| + |E LISd (m) − cd m1/d | > tcd m1/d ! tcd m1/d ≤ P | LISd (m) − E LISd (m)| > 2 ! λDd m1/2d log m = P | LISd (m) − E LISd (m)| > log log m 2

≤ 80λ2 e−λ ≤ α.

4.5.3.



Aplicaci´ on del Teorema Principal al modelo de d-palabras aleatorias

Como ya se dijo al principio de la secci´ on, demostraremos que el modelo de d-palabras aleatorias admite una (c, λ, θ)-mediana. Para ello necesitaremos un par de lemas que nos permitir´ an estimar L(H). Lema 4.11 (Desigualdad de Chebyshev P para indicatrices). Sean X1 , . . . , Xm variables aleatorias P que s´ olo toman valores 0 y 1 y sea X = m X su suma. Sea adem´ a s ∆ = m i=1 (i,j):i6=j E[Xi Xj ]. Para todo t ≥ 0, 1 P[|X − E[X]| ≥ t] ≤ 2 (E[X](1 − E[X]) + ∆) t 54

Cap´ıtulo 4: Problema del subhipergrafo mon´otono de tama˜ no m´aximo

Demostraci´ on. Por desigualdad de Chebyshev, Var[X] = E[X 2 ] − E[X]2 =

m m X X i=1 j=1

P[|X − E[X]| ≥ t] ≤ Var[X]/t2 . Adem´as,

E[Xi Xj ] − E[X]2 = ∆ +

m X i=1

E[Xi2 ] − E[X]2 .

Como los Xi son tales que Xi2 = Xi , lo anterior es igual a ∆ + E[X] − E[X]2 , con lo que se concluye la demostraci´ on.  Lema 4.12. Si n1 , . . . , nd son los largos de las clases de H, y llamamos S = 1/d Q d n a su promedio geom´etrico, entonces: N= i=1 i

Pd

i=1 ni

a su suma y

Nd . kd−1     N d k − 1 S−d Nd S 0 E[|E |] = d−1 ≥ d−1 1 − . k k k k N dS E[|E \ E 0 |] ≤ d . k

E[|E|] =

(4.5.1) (4.5.2) (4.5.3)

Adem´ as, para todo η > 0, 1 1 P[|E 0 − E[|E 0 |]| ≥ ηE[|E 0 |]] ≤ 2 + 2 0 η E[|E |] η



k−1 k−2

2d−1

!

−1 .

(4.5.4)

Demostraci´ on. Sea K = Kn1 ,...,nd , y para cada arista e ∈ E(K), llamemos Xe e Ye a las indicatrices de los eventos e ∈ E y e ∈ E 0 respectivamente. Con esto, X X |E| = Xe y |E 0 | = Ye . e∈E(K)

e∈E(K)

Adem´ as,  d 1 1 E[Xe ] = k = d−1 . k k  d     1 1 S−d 1 k − 1 S−d E[Ye ] = k 1− = d−1 . k k k k Notando que |E(K)| =

Qd

i=1 ni

= N d se concluye (4.5.1) y la primera igualdad en (4.5.2).

Por otro lado, usando una desigualdad de Bernoulli, Nd E[|E |] = d−1 k 0



1 1− k

S−d

Nd ≥ d−1 k

55



S−d 1− k



Nd ≥ d−1 k



S 1− k



Cap´ıtulo 4: Problema del subhipergrafo mon´otono de tama˜ no m´aximo

y luego

E[|E \ E 0 |] = E[|E|] − E[|E 0 |] ≤

N dS . kd

Esto concluye (4.5.2) y (4.5.3). Para la u ´ ltima parte del lema, sean e y f dos aristas distintas de E(K). Tenemos dos casos: Caso 1. Si e ∩ f 6= ∅, entonces e y f no pueden aparecer juntas en E 0 , por lo tanto Caso 2. Si e ∩ f = ∅ entonces

E(Ye Yf ) = P(e ∈ E , f ∈ E ) = 0

0

k X  2d  X 1 i=1 j6=i

k

2 1− k

E(Ye Yf ) = 0.

S−2d

k(k − 1)(k − 2)S−2d (k − 1)2S−2d kS−1 (k − 2)S−2d = · kS k2S−2 (k − 1)2S−2d−1  S−1  2d−1 k(k − 2) k−1 = E(Ye )E(Yf ) · · . (k − 1)2 k−2 =

Notando que k(k − 2) ≤ (k − 1)2 para todo k, lo anterior es menor o igual que:   k − 1 2d−1 E(Ye )E(Yf ) · . k−2 Del an´ alisis anterior se deduce que : def

∆=

X

(e,f ):e6=f

E(Ye Yf ) ≤ |(e, f ) : e ∩ f = ∅| ·



E[|E 0 |] Nd

2 

k−1 k−2

2d−1

≤ E[|E |]

0 2



k−1 k−2

2d−1

.

Aplicando la desigualdad de Chebyshev para indicatrices (Lema 4.11) a las variables Ye y llamando Y = |E 0 |, se obtiene:

P(|Y − E(Y )| ≥ ηE(Y )) ≤

1 (η E(Y ))2

E(Y ) + ∆ − E(Y )2

1 1 ≤ 2 + 2 η E(Y ) η



k−1 k−2

2d−1




!

−1 .



Gracias a los lemas reci´en probados podemos mostrar la siguiente estimaci´ on para la mediana de L(H) cuando H es elegido de acuerdo a Σ(Kn1 ,n2 ,...,nd , k). Proposici´ on 4.13. Sea δ > 0, d ≥ 2, y un conjunto n1 , n2 , . . . , nd de enteros positivos de suma
1/d Pd Qd S = etrico N = . Definamos M = cd N/k1−1/d con cd la i=1 ni y promedio geom´ i=1 ni constante de Ulam d-dimensional. Existen constantes C = C(δ) y K = K(δ) suficientemente grandes tal que: 56

Cap´ıtulo 4: Problema del subhipergrafo mon´otono de tama˜ no m´aximo

1. Si k ≥ K, N ≥ Ck 1−1/d , 12S d ≤ δcd kd−1+1/d y S ≤ k/2, entonces toda mediana de la variable L(Σ(Kn1 ,...,nd , k)) es menor que (1 + δ)M . 2. Si k ≥ K, n ≥ Ck 1−1/d y S ≤ δk/2, entonces toda mediana de L(Σ(Kn1 ,...,nd , k)) es mayor que (1 − δ)M . Demostraci´ on. Sea H un hipergrafo elegido de acuerdo a Σ(Kn1 ,...,nd , k) y asumamos las hip´ otesis de la proposici´ on. Probar la proposici´ on es equivalente a mostrar que

P[L(H) ≥ (1 + δ)M ] ≤ 1/2.

(4.5.5)

P[L(H) ≤ (1 − δ)M ] ≤ 1/2.

(4.5.6)

y que

Probemos (4.5.5), para ello notemos primero que L(H) ≤ L(H 0 ) + |E \ E 0 |. Con esto:   P [L(H) ≥ (1 + δ)M ] ≤ P L(H 0 ) + |E \ E 0 | ≥ (1 + δ)M   ≤ P L(H 0 ) + |E \ E 0 | ≥ (1 + δ)M, |E \ E 0 | ≥ M δ/2   + P L(H 0 ) + |E \ E 0 | ≥ (1 + δ)M, |E \ E 0 | < M δ/2     ≤ P |E \ E 0 | ≥ M δ/2 + P L(H 0 ) ≥ (1 + δ/2)M h i   ≤ P |E \ E 0 | ≥ M δ/2 + P |E 0 | ≥ (1 + δ/2)M d /cdd h i + P L(H 0 ) ≥ (1 + δ/2)M, |E 0 | < (1 + δ/2)M d /cdd .

Acotaremos los tres t´erminos de la derecha uno a uno. El primer t´ermino lo acotaremos usando la desigualdad de Markov, la desigualdad N < S y el Lema 4.12 como sigue:   Mδ 2 2k1−1/d N d S 2SN d−1 2S d 1 0 P |E \ E | ≥ ≤ E(|E \ E 0 |) ≤ · d = ≤ ≤ . 2 Mδ δcd n k 6 δcd kd−1+1/d δcd kd−1+1/d El segundo t´ermino lo acotamos usando el Lema 4.12, obteniendo: h i   P |E 0 | ≥ (1 + δ/2)M d /cdd ≤ P |E 0 | ≥ (1 + δ/2)E[|E 0 |] !   4 4 k − 1 2d−1 ≤ 2 + −1 . δ E[|E 0 |] δ2 k−2 Recordando que S ≤ k/2 e imponiendo K = K(δ) suficientemente grande lo anterior se puede hacer menor que: 4k d−1 4 8k d−1 1 8 1 2 + (48δ ) ≤ + ≤ 2 d+ . 2 d 2 2 d δ N (1 − S/k) δ δ N 12 δ C 12

Tomando C d ≥ 96/δ2 , lo anterior es menor o igual que 1/6. 57

Cap´ıtulo 4: Problema del subhipergrafo mon´otono de tama˜ no m´aximo

Para el tercer t´ermino, consideremos m = b(1+ δ/2)M d /cdd c. Usando la desigualdad de Bernoulli (1 + x)a ≤ 1 + ax para x ≥ −1 y 0 < a < 1, se tiene: h i P L(H 0 ) ≥ (1 + δ/2)M, |E 0 | < (1 + δ/2)M d /cdd ≤ P [LISd (m) ≥ (1 + δ/2)M ] " # (1 + δ/2)cd m1/d ≤ P LISd (m) ≥ (1 + δ/2)1/d   1 + δ/2 1/d ≤ P LISd (m) ≥ cd m 1 + δ/2d     (d − 1)δ 1/d . ≤ P LISd (m) ≥ 1 + cd m 2d + δ Necesitamos que N sea suficientemente grande para poder aplicar el Corolario 4.10. Espec´ıficamente si llamamos t = (d − 1)δ/(2d + δ) e imponemos C d ≥ m0 + 1, con m0 = m0 (t, 1/6, d) como en el corolario 4.10, se tendr´ a que: m = b(1 + δ/2)M d /cdd c = b(1 + δ/2)N d /kd−1 c ≥ bC d c ≥ m0 y luego, usando la conclusi´ on de dicho corolario, h i P L(H 0 ) ≥ (1 + δ/2)M, |E 0 | < (1 + δ/2)M d /cdd ≤ 1/6.

En resumen,

P[L(H) ≥ (1 + δ)M ] ≤

1 1 1 1 + + = , 6 6 6 2

que es lo que quer´ıamos probar. Probemos ahora (4.5.6). Para ello notemos primero que si δ ≥ 1, el resultado se tiene pues toda mediana de L(H) es positiva. Luego asumamos en esta parte que δ < 1. Como L(H 0 ) ≤ L(H), se tiene que h i P [L(H) ≤ (1 − δ)M ] ≤ P L(H 0 ) ≤ (1 − δ)M, |E 0 | ≤ (1 − δ)M d /cdd h i + P L(H 0 ) ≤ (1 − δ)M, |E 0 | > (1 − δ)M d /cdd h i ≤ P |E 0 | ≤ (1 − δ)M d /cdd h i + P L(H 0 ) ≤ (1 − δ)M, |E 0 | > (1 − δ)M d /cdd .

Al igual que antes, acotamos los t´erminos por separado. El primer t´ermino lo acotamos de manera similar al segundo t´ermino para el caso anterior, obteniendo:   h i h i 1−δ 0 d d 0 d d−1 0 0 P |E | ≤ (1 − δ)M /cd = P |E | ≤ (1 − δ)N /k ≤ P |E | ≤ E[|E |] 1 − S/k       1−δ δ 0 0 0 0 ≤ P |E | ≤ E[|E |] ≤ P |E | ≤ 1 − E[|E |] 1 − δ/2 2 !   4 4 k − 1 2d−1 ≤ 2 + −1 . δ E[|E 0 |] δ2 k−2 58

Cap´ıtulo 4: Problema del subhipergrafo mon´otono de tama˜ no m´aximo

Recordando que S ≤ δk/2 < k/2 y que podemos tomar K = K(δ) suficientemente grande lo anterior se puede hacer menor que: 4kd−1 8k d−1 1 4 2 + (32δ ) ≤ + . δ2 N d (1 − S/k) δ2 δ2 N d 8

Tomando C d ≥ 64/δ2 , lo anterior es menor que 1/4.

Para el segundo t´ermino, tomemos m = d(1 − δ)M d /cdd e. Usando una desigualdad de Bernoulli, h i P L(H 0 ) ≤ (1 − δ)M, |E 0 | > (1 − δ)M d /cdd ≤ P [LISd (m) ≤ (1 − δ)M ] h i = P LISd (m) ≤ (1 − δ)1−1/d cd m1/d h i ≤ P LISd (m) ≤ (1 − (1 − 1/d)δ)cd m1/d . Ahora necesitamos que m sea suficientemente grande para poder aplicar el Corolario 4.10. Es
1/d pec´ıficamente si llamamos t = (1 − 1/d)δ e imponemos C ≥ m0 /(1 − δ) con m0 = m0 (t, 1/4, d) como en el corolario 4.10, se tendr´ a que: m ≥ (1 − δ)M d /cdd = (1 − δ)N d /kd−1 ≥ (1 − δ)C d ≥ m0 .

Y luego, usando la conclusi´ on de dicho corolario, h i P L(H 0 ) ≤ (1 − δ)M, |E 0 | > (1 − δ)M d /cdd ≤ 1/4.

Resumiendo:

P[L(H) ≤ (1 − δ)M ] ≤

1 1 1 + = , 4 4 2

lo que concluye la demostraci´ on.



Gracias a la proposici´ on anterior tenemos el siguiente corolario: Corolario 4.14. El modelo Σ de d-palabras aleatorias de par´ ametro interno k admite una (c, λ, θ)mediana, con (c, λ, θ) = (cd , 1 − 1/d, 1 − 1/d + 1/d2 ),

donde cd la constante para el problema de Ulam d-dimensional.

as adelante, y Demostraci´ on. Sean n1 , . . . , nd con promedio geom´etrico N y suma S a especificar m´ sea H elegido de acuerdo a Σ(Kn1 ,...,nd , k). Sean adem´ as M = cN/k λ = cd N/k1−1/d , δ > 0, C(δ) y K(δ) como en la proposici´ on anterior. Definamos a(δ) = C(δ), b(δ) = (12/(δcd ))1/d y k 0 (δ) > K(δ) suficientemente grande de modo 2 que para todo k > k 0 (δ), k1−1/d+1/d < m´ın{δ/2, 1/2}b(δ)k. Con esto, si k > k 0 (δ), y se satisfacen las 2 cotas de tama˜ no para estas constantes, es decir, N ≥ a(δ)k 1−1/d y Sb(δ) ≤ k 1−1/d+1/d , se tendr´ an todas las hip´ otesis de la proposici´ on anterior. Con esto toda mediana de L(H) estar´ a entre (1 − δ)M y (1 + δ)M .  59

Cap´ıtulo 4: Problema del subhipergrafo mon´otono de tama˜ no m´aximo

Gracias a este u ´ ltimo corolario podemos aplicar el Teorema Principal al modelo de d palabras aleatorias, recordando que en este caso h = 1/(4d) es constante de concentraci´ on para el modelo. Teorema 4.15 (Teorema de estimaci´ on para el modelo de d-palabras aleatorias). Sean ε > 0 y g : N → R una funci´ on tal que g(k) = O(k η ) para un cierto 0 ≤ η < 1/d2 . Existen k0 y A suficientemente grandes tales que si k ≥ k0 y los valores n1 , . . . , nd de promedio geom´etrico N y suma S cumplen N ≥ k1−1/d A,

(Condici´ on de tama˜ no)

S ≤ g(k)N,

(Condici´ on de balanceo)

se tiene, definiendo M = cd N/k1−1/d , con cd la constante de Ulam d-dimensional, (1 − ε)M ≤ E[L(Σ(Kn1 ,...,nd , k))] ≤ (1 + ε)M.

(4.5.7)

Por otro lado, si Med[L(Σ(Kn1 ,...,nd , k))] es una mediana de L(Σ(Kn1 ,...,nd , k)), (1 − ε)M ≤ Med[L(Σ(Kn1 ,...,nd , k))] ≤ (1 + ε)M. Adem´ as, existe una constante absoluta C > 0 tal que para k y n1 , . . . , nd como antes:   C 2 P [L(Σ(Kn1 ,...,nd , k)) ≤ (1 − ε)M ] ≤ exp − ε M , d   C ε2 P [L(Σ(Kn1 ,...,nd , k)) ≥ (1 + ε)M ] ≤ exp − M . d 1+ε

4.6.

(4.5.8)

(4.5.9) (4.5.10)

Resultado para el modelo binomial

En esta secci´ on veremos que, al igual que el modelo anterior, el modelo binomial admite una (c, λ, θ)-mediana y luego podemos aplicar el Teorema Principal en este modelo. Consideremos en lo que sigue H elegido de acuerdo al modelo binomial G(Kn1 ,...,nd , p), y H 0 el subhipergrafo de H obtenido al remover todas las aristas incidentes en nodos de grado 2 o mayor. Denotemos E y E 0 a E(H) y E(H 0 ). Usando el mismo m´etodo de la secci´ on anterior, encontraremos una estimaci´ on de la mediana de L(G(Kn1 ,...,nd , p). Para ello, necesitaremos los siguientes lemas: Pd Lema 4.16. Para todo conjunto de n´ umeros positivos n1 , . . . , nd , si definimos S = j=1 nj , Q 1/d Q d d d e= e d ≤ S d−1 . N= yN entonces N d − N j=1 nj j=1 (nj − 1) Demostraci´ on. Aplicaci´ on directa del Lema 4.5



60

Cap´ıtulo 4: Problema del subhipergrafo mon´otono de tama˜ no m´aximo

Lema 4.17. Si S =

Pd

j=1 nj , N =

Q d

j=1 nj

E[|E|] = N d p,

1/d

E[|E 0 |] = N d p(1 − p)N

 d e = Qd (nj − 1) entonces: yN j=1

(4.6.1)

d −N ed

(4.6.2)

E[|E \ E 0 |] ≤ N d S d−1 p2 .

≥ N d p(1 − S d−1 p),

(4.6.3)

Adem´ as, para todo η > 0,

P[|E 0 | − E[|E 0 |]| ≥ ηE[|E 0 |]] ≤

η2

1 . E[|E 0 |]

(4.6.4)

Demostraci´ on. Sea K = Kn1 ,...,nk , y para cada arista e ∈ E(K), llamemos Xe e Ye a las indicatrices de los eventos e ∈ E y e ∈ E 0 respectivamente. Con esto, X X |E| = Xe y |E 0 | = Ye . e∈E(K)

e∈E(K)

Adem´ as, para todo e, se tiene que E[Xe ] = p y E[Ye ] = p(1 − p)N se concluyen (4.6.1) y la primera igualdad en (4.6.2).

d −N ed

. Notando que |E(K)| = N d

Por otro lado, usando una desigualdad de Bernoulli y el lema anterior,

E[|E 0 |] = N d p(1 − p)N

d −N ed

Luego,

e d )p) ≥ N d p(1 − S d−1 p). ≥ N d p(1 − (N d − N

E[|E \ E 0 |] = E[|E|] − E[|E 0 |] ≤ N d S d−1 p2 , lo que concluye (4.6.2) y (4.6.3).

Para la u ´ ltima parte del lema, sean e y f dos aristas distintas de E(K). Tenemos dos casos: Caso 1. Si e ∩ f 6= ∅, entonces e y f no pueden aparecer ambas en E 0 , por lo tanto

E(Ye Yf ) = 0.

Caso 2. Si e ∩ f = ∅ entonces Ye e Yf son independientes y luego,   E[|E 0 |] 2 2 E(Ye Yf ) = E[Yf ]E[Ye ] = E[Ye ] = . Nd Del an´ alisis anterior, def

∆=

X

(e,f ):e6=f

E(Ye Yf ) = |(e, f ) : e ∩ f = ∅| ·



E[|E 0 |] Nd

2

≤ E[|E 0 |]2 .

Aplicando la desigualdad de Chebyshev para indicatrices (Lema 4.11) a las variables Ye y llamando Y = |E 0 |, se obtiene:

P(|Y − E(Y )| ≥ ηE(Y )) ≤

1 1 (E(Y )(1 − E(Y )) + ∆) ≤ 2 . 2 (η E(Y )) η E(Y ) 61



Cap´ıtulo 4: Problema del subhipergrafo mon´otono de tama˜ no m´aximo

Al igual que en el caso del modelo de d-palabras aleatorias, L(H 0 ) corresponde al largo de la secuencia creciente m´ as larga de d − 1 permutaciones en {1, 2, . . . , |E 0 |} y luego podemos usar el Corolario 4.10 para estimar dicha cantidad. Gracias a esto, podemos demostrar la siguiente cota para la mediana. Proposici´ on 4.18. Sean δ > 0, d ≥ 2 y un conjunto n1 , n2 , . . . , nd de enteros positivos de suma Q 1/d Pd d S = i=1 ni , y promedio geom´etrico N = n . Definamos M = cd N p1/d con cd la coni=1 i stante de Ulam d-dimensional. Existe una constante C = C(δ) suficientemente grande tal que: 1. Si N p1/d ≥ C, 12S 2d−2 p2−1/d ≤ δcd y S d−1 p ≤ 1/2, entonces toda mediana de L(H) es menor que (1 + δ)M . 2. Si N p1/d ≥ C y S d−1 p ≤ δ/2, entonces toda mediana de L(H) es mayor que (1 − δ)M . Demostraci´ on. La demostraci´ on de esta proposici´ on es muy similar a la de la Proposici´ on 4.13. Al igual que entonces, probar la proposici´ on es equivalente a mostrar que

P[L(H) ≥ (1 + δ)M )] ≤ 1/2

(4.6.5)

P[L(H) ≤ (1 − δ)M )] ≤ 1/2.

(4.6.6)

y que

Para probar (4.6.5), notemos primero que L(H) ≤ L(H 0 ) + |E \ E 0 |. Con esto:   P [L(H) ≥ (1 + δ)M ] ≤ P L(H 0 ) + |E \ E 0 | ≥ (1 + δ)M   = P L(H 0 ) + |E \ E 0 | ≥ (1 + δ)M, |E \ E 0 | ≥ M δ/2   + P L(H 0 ) + |E \ E 0 | ≥ (1 + δ)M, |E \ E 0 | < M δ/2     ≤ P |E \ E 0 | ≥ M δ/2 + P L(H 0 ) ≥ (1 + δ/2)M h i   ≤ P |E \ E 0 | ≥ M δ/2 + P |E 0 | ≥ (1 + δ/2)M d /cdd h i + P L(H 0 ) ≥ (1 + δ/2)M, |E 0 | < (1 + δ/2)M d /cdd .

Acotaremos los tres t´erminos de la derecha uno a uno. El primer t´ermino lo acotamos usando la desigualdad de Markov, la desigualdad N < S y el Lema 4.12 como sigue:   Mδ 2 2p2 S d−1 N d 0 P |E \ E | ≥ ≤ E(|E \ E 0 |) ≤ 2 Mδ δcd N p1/d =

2p2−1/d S d−1 N d−1 2p2−1/d S 2d−2 1 ≤ ≤ . δcd δcd 6

62

Cap´ıtulo 4: Problema del subhipergrafo mon´otono de tama˜ no m´aximo

El segundo t´ermino lo acotamos usando el Lema 4.12 y la desigualdad de Bernoulli (1 + x)a ≥ 1 + ax para x ≥ −1 y a > 1, obteniendo: h i   P |E 0 | ≥ (1 + δ/2)M d /cdd ≤ P |E 0 | ≥ (1 + δ/2)E[|E 0 |] ≤

δ2

4 4 8 ≤ 2 d ≤ 2 d . 0 d−1 E(|E |) δ N p(1 − S p) δ N p

Tomando C d ≥ 48/δ2 , lo anterior es menor o igual que 1/6.

Para el tercer t´ermino, consideremos m = b(1+ δ/2)M d /cdd c, de modo que usando la desigualdad de Bernoulli (1 + x)a ≤ 1 + ax para x ≥ −1 y 0 < a < 1, se tiene: h i P L(H 0 ) ≥ (1 + δ/2)M, |E 0 | < (1 + δ/2)M d /cdd ≤ P [LISd (m) ≥ (1 + δ/2)M ] " # (1 + δ/2)cd m1/d ≤ P LISd (m) ≥ (1 + δ/2)1/d   1 + δ/2 1/d ≤ P LISd (m) ≥ cd m 1 + δ/(2d)     (d − 1)δ 1/d = P LISd (m) ≥ 1 + cd m . 2d + δ Necesitamos que m sea suficientemente grande para poder aplicar el Corolario 4.10. Espec´ıficamente si llamamos t = (d − 1)δ/(2d + δ) e imponemos C d ≥ m0 + 1 con m0 = m0 (t, 1/6, d) como en el Corolario 4.10, se tendr´ a que: m = b(1 + δ/2)M d /cdd c = b(1 + δ/2)N d pc ≥ bC d c ≥ m0 . Y luego, usando la conclusi´ on de dicho corolario, h i P L(H 0 ) ≥ (1 + δ/2)M, |E 0 | < (1 + δ/2)M d /cdd ≤ 1/6.

Resumiendo,

P[L(H) ≥ (1 + δ)M ] ≤

1 1 1 1 + + = , 6 6 6 2

que es lo que quer´ıamos probar. Probemos ahora (4.6.6). Para ello notemos primero que si δ ≥ 1, el resultado se tiene pues toda mediana de L(H) es positiva. Luego asumamos en esta parte que δ < 1. Como L(H 0 ) ≤ L(H),

h

P [L(H) ≤ (1 − δ)M ] = P L(H 0 ) ≤ (1 − δ)M, |E 0 | ≤ (1 − δ)M d /cdd

i

h i + P L(H 0 ) ≤ (1 − δ)M, |E 0 | > (1 − δ)M d /cdd h i ≤ P |E 0 | ≤ (1 − δ)M d /cdd h i + P L(H 0 ) ≤ (1 − δ)M, |E 0 | > (1 − δ)M d /cdd . 63

Cap´ıtulo 4: Problema del subhipergrafo mon´otono de tama˜ no m´aximo

Al igual que antes, acotamos los t´erminos por separado. El primer t´ermino lo acotamos de manera similar al segundo t´ermino para el caso anterior, obteniendo:   i h i h (1 − δ) 0 d d 0 d 0 0 P |E | ≤ (1 − δ)M /cd = P |E | ≤ (1 − δ)N p ≤ P |E | ≤ E[|E |] (1 − S d−1 p)     1−δ 0 0 ≤ P |E | ≤ E[|E |] ≤ P |E 0 | ≤ (1 − δ/2)E[|E 0 |] 1 − δ/2 4 8 ≤ 2 ≤ 2 d . 0 δ E[|E |] δ N p Tomando C d ≥ 32/δ2 , lo anterior es menor que 1/4. li,

Para el segundo t´ermino, tomemos m = d(1−δ)M d /cdd e, luego usando la desigualdad de Bernoulh

i

P L(H 0 ) ≤ (1 − δ)M, |E 0 | > (1 − δ)M d /cdd ≤ P [LISd (m) ≤ M (1 − δ)]

h i = P LISd (m) ≤ (1 − δ)1−1/d cd m1/d h i ≤ P LISd (m) ≤ (1 − (1 − 1/d)δ)cd m1/d .

Ahora necesitamos que m sea suficientemente grande para poder aplicar el Corolario 4.10. Espec´ıficamente si llamamos t = (1 − 1/d)δ e imponemos C > (m0 /(1 − δ))1/d con m0 = m0 (t, 1/4, d) como en el corolario 4.10, se tendr´ a que: m ≥ (1 − δ)M d /cdd = (1 − δ)N d p ≥ (1 − δ)C d ≥ m0 . Y luego, usando la conclusi´ on de dicho corolario, h i P L(H 0 ) ≤ (1 − δ)M, |E 0 | > (1 − δ)M d /cdd ≤ 1/4.

Resumiendo:

P[L(H) ≤ (1 − δ)M ] ≤

1 1 1 + = . 4 4 2

Esto concluye la demostraci´ on.



Gracias a la proposici´ on anterior tenemos el siguiente corolario, Corolario 4.19. Si definimos t = 1/p, entonces el modelo G(Kn1 ,...,nd , p), de parametro interno t admite una (c, λ, θ)-mediana con   1 2d − 1 (c, λ, θ) = cd , , . d 2d(d − 1) Demostraci´ on. Sean n1 , . . . , nd con promedio geom´etrico N y suma S a especificar m´ as adelante, y sea H elegido de acuerdo a G(Kn1 ,...,nd , p). Sean adem´ as M = cN/tλ = cd N p1/d , δ > 0 y C(δ) como en la proposici´ on anterior. 64

Cap´ıtulo 4: Problema del subhipergrafo mon´otono de tama˜ no m´aximo

Definamos ahora a(δ) = C(δ), b(δ) = (12/(δcd ))1/(2d−2) y t0 (δ) suficientemente grande de modo que para todo t > t0 (δ), t1−1/(2d) < m´ın{δ/2, 1/2}tb(δ)d−1 . Con esto, si t > t0 (δ), n ≥ a(δ)t1/d y Sb(δ) ≤ t(2d−1)/(2d(d−1)) , se tendr´ an todas las hip´ otesis de la proposici´ on anterior y luego, toda mediana de L(H) estar´ a entre (1 − δ)M y (1 + δ)M .  An´ alogamente al modelo anterior y recordando que h = 1/4 es constante de concentraci´ on para el modelo binomial, tenemos el siguiente resultado: Teorema 4.20 (Teorema de estimaci´ on para el modelo binomial). Sea ε > 0 y g : R → R una η funci´ on tal que g(t) = O(t ) para un cierto 0 ≤ η < 1/(2d(d−1)). Existen p0 suficientemente peque˜ no y A suficientemente grande tales que si p ≤ p0 y los valores n1 , . . . , nd de promedio geom´etrico N y suma S cumplen N p1/d ≥ A.

(Condici´ on de tama˜ no)

S ≤ g(1/p)N.

(Condici´ on de balanceo)

se tiene, definiendo M = cd N p1/d con cd la constante de Ulam d-dimensional, (1 − ε)M ≤ E[L(G(Kn1 ,...,nd , p))] ≤ (1 + ε)M.

(4.6.7)

Por otro lado, si Med[L(G(Kn1 ,...,nd , p))] es una mediana de L(G(Kn1 ,...,nd , p)), (1 − ε)M ≤ Med[L(G(Kn1 ,...,nd , p))] ≤ (1 + ε)M. Adem´ as, existe una constante C > 0 absoluta tal que para p y n1 , . . . , nd como antes:
P [L(G(Kn1 ,...,nd , p) ≤ (1 − ε)M ] ≤ exp −Cε2 M ,   ε2 P [L(G(Kn1 ,...,nd , p) ≥ (1 + ε)M ] ≤ exp −C M . 1+ε

65

(4.6.8)

(4.6.9) (4.6.10)

Cap´ıtulo 5

Variantes sim´ etricas del problema de la LCS En este cap´ıtulo describiremos dos variantes del problema del subhipergrafo mon´ otono m´ as grande estudiado en el cap´ıtulo anterior, un modelo que denominaremos modelo sim´etrico y otro que llamaremos modelo antisim´etrico. En ambas variantes consideraremos que d, el n´ umero de clases de partici´ on del hipergrafo a considerar, es 2, es decir, nos restringiremos al caso de grafos bipartitos. En ambos modelos el espacio muestral de grafos ya no ser´ a, como lo era en el caso general, el conjunto de todos los subgrafos de un grafo bipartito completo sino que ser´ a el conjunto de todos los subgrafos que presentan alg´ un tipo de simetr´ıa en sus conjuntos de arcos. Veremos que restringirnos a estos casos sim´etricos no cambia el comportamiento asint´ otico del largo de su subgrafo mon´ otono m´ as grande. De hecho, probaremos que el teorema de estimaci´ on que presenta el modelo binomial de 2-hipergrafo se mantiene sin cambios para estos nuevos modelos.

5.1.

Modelo sim´ etrico

Consideremos la misma notaci´ on usada en el problema del subhipergrafo mon´ otono m´as grande, pero restringi´endolo al caso de dos palabras, esta vez de igual tama˜ no. Sean A y B dos conjuntos disjuntos de tama˜ no n. Asumiremos, al igual que en el cap´ıtulo anterior, que los elementos de ambos conjuntos est´ an numerados de 1 a n y que G es un grafo bipartito con clases de partici´ on A y B, donde identificamos E(G) con el subconjunto de A × B que contiene los pares ordenados asociados a las aristas de G. Adem´ as, usaremos la notaci´ on habitual Kn,n para denotar al grafo bipartito completo de clases de partici´ on A y B. Denotemos S(Kn,n , p) a la distribuci´ on sobre todos los subgrafos de Kn,n donde para todo x < y,

66

Cap´ıtulo 5: Variantes sim´etricas del problema de la LCS

el evento {(x, y), (y, x)} ⊆ E(G), con G una realizaci´ on, tiene probabilidad p, y todos estos eventos son independientes. De la definici´ on anterior, cada vez que el arco (x, y) est´ a en una realizaci´ on, su sim´etrico (y, x) tambi´en lo est´ a. Por esta raz´ on llamaremos a esta distribuci´ on, distribuci´ on sim´etrica bipartita de par´ ametro p. Nos ser´ a de utilidad definir otra distribuci´ on relacionada con la anterior. Para ello, sea ahora el grafo bipartito con clases de partici´ on A y B, donde s´ olo los arcos (x, y) con x < y est´ an ∗ , p) a la distribuci´ ∗ presentes y denotemos O(Kn,n on sobre todos los subgrafos de Kn,n donde la probabilidad de que un arco (x, y), con x < y, est´e en el subgrafo es p y todos los eventos son independientes. Llamamos a esta distribuci´ on, distribuci´ on orientada bipartita de par´ ametro p. ∗ Kn,n

A

1

2

3

4

5

6

7

8

9

10

11

12

G

Eje horizontal

B

A

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

O B

Figura 5.1: Arriba se muestra una representaci´ on de un grafo G elegido de acuerdo a la distribuci´ on sim´etrica bipartita S(K12,12 , p). Intuitivamente un grafo es sim´etrico si su representaci´on gr´ afica resulta ser sim´etrica con respecto a un eje horizontal imaginario ubicado entre ambas clases de partici´ on. Al quedarnos solo con las aristas del tipo (x, y) con x < y obtenemos un grafo que se dis∗ tribuye de acuerdo al modelo orientado bipartito O(K12,12 , p). Dicho grafo se encuentra representado en la zona inferior de la imagen. Al igual que en el cap´ıtulo anterior, para G un subgrafo de Kn,n , denotaremos L(G) al largo de su subgrafo mon´ otono m´ as grande. Tenemos el siguiente lema que relaciona las distribuciones sim´etrica y orientada: ∗ , p)) tiene la misma distribuci´ Lema 5.1. L(O(Kn,n on que L(S(Kn,n , p)). ∗ , p) podemos asoDemostraci´ on. Notemos que para todo grafo O elegido de acuerdo a O(Kn,n ciar de manera u ´ nica un grafo G con el mismo conjunto de v´ertices y con conjunto de aristas E(G) = {(x, y) : (x, y) ∈ E(O) o´ (y, x) ∈ E(O)}, dicho grafo G es un subgrafo sim´etrico de Kn,n y ∗ , p). su probabilidad bajo S(Kn,n , p) es exactamente la misma que la probabilidad de O bajo O(Kn,n

Por otro lado si M es un subgrafo mon´ otono de G, entonces existe otro subgrafo mon´ otono de O (y luego de G), digamos N , del mismo n´ umero de aristas tal que todas las aristas son del tipo x < y. En efecto basta definir E(N ) como {(m´ın(x, y), m´ ax(x, y)) | (x, y) ∈ E(M )}. 67

Cap´ıtulo 5: Variantes sim´etricas del problema de la LCS

Notemos que como G es sim´etrico, si (x, y) ∈ E(M ) entonces ((m´ın(x, y), m´ ax(x, y)) ∈ E(G). Luego, N es efectivamente un subgrafo de G. Por otro lado, como M es mon´ otono, si (x, y) est´ a en E(M ) entonces (y, x) no puede estarlo, luego N tiene el mismo n´ umero de aristas que M . Finalmente es f´ acil notar que si (x, y) y (z, w) son dos aristas de M (y luego, no se cruzan ni comparten v´ertices), entonces (m´ın(x, y), m´ ax(x, y)) y (m´ın(z, w), m´ ax(z, w)) tampoco se cruzan ni comparten v´ertices, con esto N es mon´ otono. 

A

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

G B

A

O B

Figura 5.2: Ejemplo ilustrativo del Lema 5.1. El grafo sim´etrico G indicado arriba es el asociado al grafo mon´ otono O indicado abajo. Las aristas de G indicadas en negrita representan el conjunto de aristas de M , un subgrafo mon´ otono. Las aristas de O indicadas en negrita corresponden a N , el subgrafo mon´ otono derecho asociado a M en el Lema 5.1.

Una observaci´ on importante que se obtiene de la demostraci´ on anterior es que podemos restringir el estudio de los subgrafos mon´ otonos de grafos sim´etricos, al caso de subgrafos sim´etricos orientados, es decir, grafos cuyas aristas son todas del tipo (x, y) con x < y. Queremos obtener un teorema de estimaci´ on para el largo del subgrafo mon´ otono de largo m´ aximo de un grafo sim´etrico. Para ello usaremos el mismo argumento del cap´ıtulo anterior. Comenzamos observando que el modelo sim´etrico posee una constante de concentraci´on para el largo del subgrafo mon´ otono m´ as grande. Para ello, basta ver que si tenemos un grafo sim´etrico G y lo modificamos agregando o quitando un par de aristas {(u, v), (v, u)} entonces el valor de L(G) cambia en a lo m´ as 1. Adem´ as si sabemos que L(G) ≥ r entonces podemos mostrar r pares de aristas testigos (las aristas que forman el subgrafo planar junto con sus sim´etricas) que garantizan que cualquier configuraci´ on de pares de aristas que contengan dicho grupo de aristas testigos, dar´ an a lugar un subgrafo planar de tama˜ no al menos r. Con esto, gracias a la desigualdad de Talagrand, se prueba que el modelo sim´etrico tiene una constante de concentraci´ on h = 1/4, es decir, si Med es

68

Cap´ıtulo 5: Variantes sim´etricas del problema de la LCS

una mediana de L(S(Kn,n , p)), 

 s2 , P [L(S(Kn,n , p) > Med(1 + s)] ≤ 2 exp − 4(1 + s)   s2 P [L(S(Kn,n , p) < Med(1 − s)] ≤ 2 exp − . 4 Med Luego, al igual que antes, para conseguir una cota de concentraci´ on y esperanza, encontraremos una mediana ajustada para este modelo.

5.1.1.

Reducci´ on al problema de la secuencia creciente m´ as larga de una involuci´ on

Sea G un grafo elegido de acuerdo a S(Kn,n ; p) y sea G0 el grafo obtenido a partir de G eliminando los arcos incidentes en v´ertices de grado 2 o m´ as. Denotemos E(G) y E(G0 ) por E y E 0 respectivamente. Notemos que el grafo G0 resultante sigue siendo sim´etrico, en el sentido que si (a, b) ∈ E 0 , entonces (b, a) ∈ E 0 . Llamemos 2m al n´ umero de v´ertices de la clase de partici´on A que 0 tiene grado de incidencia 1 en el grafo G (esta cantidad debe ser par, pues el grafo es sim´etrico). An´ alogamente B posee 2m v´ertices con grado de incidencia 1 en G0 . Si nos quedamos s´ olo con dichos v´ertices (pues el resto tiene grado 0 en G0 ), podemos ver los 0 arcos de G como una involuci´ on (permutaci´ on autoinversa) de [2m] sin puntos fijos. De hecho, como la distribuci´ on de G es invariante bajo permutaciones de los nodos, la distribuci´ on de G0 tambi´en lo es, y luego la involuci´ on resultante es arbitraria y uniformemente elegida dentro de todas las involuciones de [2m] sin puntos fijos. Definamos I2m como la distribuci´ on uniforme sobre todas las involuciones de [2m] sin puntos fijos y denotemos L(I2m ) al largo de su secuencia creciente m´ as larga. Notemos que L(I2m ) se 0 distribuye como L(G ) en este caso. Es sabido [17], que el largo√ esperado de una involuci´ on aleatoria de [2m] sin puntos fijos se comporta asint´ oticamente como 2 2m y de hecho, disponemos de un teorema de concentraci´ on para L(I2m ) de Kiwi [14, Teorema 5] (Esta es una versi´ on mas d´ebil de su resultado pero es todo cuanto necesitaremos): √ Teorema 5.2. Para m suficientemente grande y todo 0 ≤ s ≤ 2 2m, h i √ 2 3/2 P |L(I2m ) − E(L(I2m ))| ≥ s + 32(2m)1/4 ≤ 4e−s /16e 2m . No usaremos directamente el teorema sino que usaremos el siguiente corolario: Corolario 5.3. Para todo entero 0 ≤ t ≤ 1 y todo α > 0 existe un m0 = m0 (t, α) suficientemente grande tal que, para todo m ≥ m0 , h √ √ i P |L(I2m ) − 2 2m| ≥ 2t 2m ≤ α. 69

Cap´ıtulo 5: Variantes sim´etricas del problema de la LCS

Demostraci´ on. Sean 0 ≤ t ≤ 1 y α > 0. Elijamos m0 = m0 (t, α) suficientemente grande tal que, para todo m > m0 las siguientes condiciones se cumplan: √ √ 1. |E(L(I2m )) − 2 2m| + 32(2m)1/4 ≤ t 2m. 2

2. 4e−t

√ 2m/16e3/2

< α.

3. El Teorema anterior se cumple para m. Con esto se tiene que:   h √ √ i √ √ P |L(I2m ) − 2 2m| ≥ 2t 2m ≤ P |L(I2m ) − E(L(I2m ))| ≥ 2t 2m − |E(L(I2m )) − 2 2m| h i √ ≤ P |L(I2m ) − E(L(I2m ))| ≥ t 2m + 32(2m)1/4 2

≤ 4e−t

5.1.2.

√

2m/16e3/2

≤α



Resultado para el modelo sim´ etrico

Probaremos el siguiente lema que nos permitir´ a, al igual que como lo hicimos en el capitulo anterior para los modelo de d-palabras y binomial, encontrar una aproximaci´ on de la mediana. Lema 5.4. Se satisface que

E[|E|] = pn(n − 1), E[|E 0 |] = pn(n − 1)(1 − p)2n−4 ,

E[|E \ E |] ≤ 2p n(n − 1)(n − 2). 0

2

(5.1.1) (5.1.2) (5.1.3)

Adem´ as, para todo η > 0,

P[|E − E[|E|]| ≥ ηE[|E|]] ≤

η2

2 . E[|E|]

(5.1.4)

Demostraci´ on. Para cada i 6= j sea Xij la indicatriz del evento (i, j) ∈ E y sea Yij la indicatriz del evento (i, j) ∈ E 0 . Con esto, para todo i 6= j, E[Xij ] = p, E[Yij ] = E[Xij ]

Y

(1 − E[Xkj ])(1 − E[Xik ]) = p(1 − p)2n−4 .

k6∈{i,j}

P P Notando que |E| = (i,j):i6=j Xij y |E 0 | = (i,j):i6=j Yij y que en ambas sumas el n´ umero de sumandos es n(n − 1), se concluyen las desigualdades (5.1.1) y (5.1.2). Por otro lado, usando una desigualdad de Bernoulli,

E[|E \ E 0 |] = E[|E|] − E[|E 0 |] = pn(n − 1)[1 − (1 − p)2n−4 ] ≤ pn(n − 1)(2n − 4)p, 70

Cap´ıtulo 5: Variantes sim´etricas del problema de la LCS

lo que prueba la desigualdad (5.1.3). Para la u ´ ltima parte del lema, notemos que |E| tambi´en puede escribirse como 2 las variables Xij son variables independientes, se tiene def

∆=

X

E(Xij Xkl ) =

(i,j),(k,l):i