Coloridas variantes a la Teorıa de Ramsey
Amanda Montejano
UMDI Facultad de Ciencias, UNAM Juriquilla
Coloquio del Posgrado Conjunto en Ciencias Matemticas de laUNAM-UMSNH
Morelia, 17 de agosto
1 / 47
1 Teorıa de Ramsey
Resultados clasicos
2 Variantes
teorıa anti-Ramsey
teorıa de suma-cero
y mas...
2 / 47
Un poco de historia
____________________________________________
F. P. Ramsey (1903 - 1930)
l1930
4 / 47
Un poco de historia
____________________________________________
F. P. Ramsey (1903 - 1930)I. Schur (1875 -1941)
B. L. Van ser Waerden (1903 -1996)
l l l l1916 1927 1930 1935
P. Erdös (1913 -1996)
G. Szekeres (1911 -2005)
5 / 47
Un poco de historia
____________________________________________
F. P. Ramsey (1903 - 1930)I. Schur (1875 -1941)
B. L. Van ser Waerden (1903 -1996)
l l l l1916 1927 1930 1935
P. Erdös (1913 -1996)
G. Szekeres (1911 -2005)
6 / 47
Ejemplito
x + y = z es soluble en {1, 2, 3, 4, 5}
¿Sera cierto que tal propiedad se preserva bajo 2-particiones?
8 / 47
Ejemplito
x + y = z es soluble en {1, 2, 3, 4, 5}
¿Sera cierto que tal propiedad se preserva bajo 2-particiones?
9 / 47
Ejemplito
x + y = z es soluble en {1, 2, 3, 4, 5}
¿Sera cierto que tal propiedad se preserva bajo 2-particiones?
10 / 47
Coloraciones
1 2 3 4 5 6 7 8 9 10 11 12 13
Dado un conjunto, X una k-coloracion de X es:
una funcion f : X → {1, 2, ..., k}
una particion X = X1 ∪ X2 ∪ ... ∪ Xk , Xi := f −1(i)
11 / 47
Coloraciones
1 2 3 4 5 6 7 8 9 10 11 12 13
Dado un conjunto, X una k-coloracion de X es:
una funcion f : X → {1, 2, ..., k}
una particion X = X1 ∪ X2 ∪ ... ∪ Xk , Xi := f −1(i)
12 / 47
La teorıa de Ramsey es el estudio
de la preservacion de propiedades
bajo particiones de conjuntos.
La teorıa de Ramsey es el estudio
de la existencia de estructuras
monocromaticas en universos coloreados.
13 / 47
Teorema (Schur 1916)
Para todo entero positivo k existe un mınimo entero positivo S(k) tal quetoda k-coloracion de [n] = {1, 2, ..., n}, con n ≥ S(k), contiene unasolucion monocromatica de x + y = z.
S(2) ≥ 5 k = 4
S(2) = 5, S(3) = 14, S(4) = 45 ¡Unicos valores exactos!
14 / 47
Teorema (Schur 1916)
Para todo entero positivo k existe un mınimo entero positivo S(k) tal quetoda k-coloracion de [n] = {1, 2, ..., n}, con n ≥ S(k), contiene unasolucion monocromatica de x + y = z.
S(2) ≥ 5
k = 4
S(2) = 5, S(3) = 14, S(4) = 45 ¡Unicos valores exactos!
15 / 47
Teorema (Schur 1916)
Para todo entero positivo k existe un mınimo entero positivo S(k) tal quetoda k-coloracion de [n] = {1, 2, ..., n}, con n ≥ S(k), contiene unasolucion monocromatica de x + y = z.
S(2) ≥ 5 k = 4
S(2) = 5, S(3) = 14, S(4) = 45 ¡Unicos valores exactos!
16 / 47
Teorema (Schur 1916)
Para todo entero positivo k existe un mınimo entero positivo S(k) tal quetoda k-coloracion de [n] = {1, 2, ..., n}, con n ≥ S(k), contiene unasolucion monocromatica de x + y = z.
S(2) ≥ 5 k = 4
S(2) = 5, S(3) = 14, S(4) = 45 ¡Unicos valores exactos!
17 / 47
Teorema (Schur 1916)
Para todo entero positivo k existe un mınimo entero positivo S(k) tal quetoda k-coloracion de [n] = {1, 2, ..., n}, con n ≥ S(k), contiene unasolucion monocromatica de x + y = z.
S(2) ≥ 5 k = 4
S(2) = 5, S(3) = 14, S(4) = 45 ¡Unicos valores exactos!
18 / 47
Teorema (Schur 1916)
Para todo entero positivo k existe un mınimo entero positivo S(k) tal quetoda k-coloracion de [n] = {1, 2, ..., n}, con n ≥ S(k), contiene unasolucion monocromatica de x + y = z.
S(2) ≥ 5 k = 4
S(2) = 5, S(3) = 14, S(4) = 45 ¡Unicos valores exactos!
19 / 47
Teorema (van der Waerden, 1927 (version infinita))
Toda coloracion finita de Z+ contiene una progresion aritmeticamonocromatica arbitrariamente larga.
Una progresion aritmetica es un conjunto de enteros de la forma
{a, a + d , a + 2d , ...a + (t − 1)d}
Teorema (van der Waerden, 1927 (version finita))
Para cualesquiera enteros positivos k, t existe un mınimo entero W (k, t)tal que toda k-coloracion de [n] = {1, 2, ..., n}, con n ≥W (k , t), contieneuna AP(t) monocromatica.
20 / 47
Teorema (van der Waerden, 1927 (version infinita))
Toda coloracion finita de Z+ contiene una progresion aritmeticamonocromatica arbitrariamente larga.
Una progresion aritmetica es un conjunto de enteros de la forma
{a, a + d , a + 2d , ...a + (t − 1)d}
Teorema (van der Waerden, 1927 (version finita))
Para cualesquiera enteros positivos k, t existe un mınimo entero W (k, t)tal que toda k-coloracion de [n] = {1, 2, ..., n}, con n ≥W (k , t), contieneuna AP(t) monocromatica.
21 / 47
Teorema (van der Waerden, 1927 (version infinita))
Toda coloracion finita de Z+ contiene una progresion aritmeticamonocromatica arbitrariamente larga.
Una progresion aritmetica es un conjunto de enteros de la forma
{a, a + d , a + 2d , ...a + (t − 1)d}
Teorema (van der Waerden, 1927 (version finita))
Para cualesquiera enteros positivos k, t existe un mınimo entero W (k, t)tal que toda k-coloracion de [n] = {1, 2, ..., n}, con n ≥W (k , t), contieneuna AP(t) monocromatica.
22 / 47
Otros teoremas clasicos que mencionarEl teorema de Rado (1933-36)
Caracteriza las matrices racionales A, tales que el sistema Ax = 0 contiene
una solucion monocromatica en toda k-coloracion de [n].
El teorema de Hales-Jewett (1963)
U = C nt = {x1 x2 ... xn : xi ∈ {0, 1, ...t−1}}
estructura: lıneas combinatorias
El teorema de Ramsey (1930)
U = E (Kn)
estructura: Km
23 / 47
Otros teoremas clasicos que mencionarEl teorema de Rado (1933-36)
Caracteriza las matrices racionales A, tales que el sistema Ax = 0 contiene
una solucion monocromatica en toda k-coloracion de [n].
El teorema de Hales-Jewett (1963)
U = C nt = {x1 x2 ... xn : xi ∈ {0, 1, ...t−1}}
estructura: lıneas combinatorias
El teorema de Ramsey (1930)
U = E (Kn)
estructura: Km
24 / 47
Otros teoremas clasicos que mencionarEl teorema de Rado (1933-36)
Caracteriza las matrices racionales A, tales que el sistema Ax = 0 contiene
una solucion monocromatica en toda k-coloracion de [n].
El teorema de Hales-Jewett (1963)
U = C nt = {x1 x2 ... xn : xi ∈ {0, 1, ...t−1}}
estructura: lıneas combinatorias
El teorema de Ramsey (1930)
U = E (Kn)
estructura: Km
25 / 47
Variantes
f : U → {c1, c2, . . . , ck}⊆ Γ
Teorıa de Ramsey: estructuras monocromaticas.
Teorıa anti-Ramsey: estructuras heterocromaticas.
Teorıa de Ramsey de suma-cero: estructuras de suma-cero.
26 / 47
Variantes
f : U → {c1, c2, . . . , ck}⊆ Γ
Teorıa de Ramsey: estructuras monocromaticas.
Teorıa anti-Ramsey: estructuras heterocromaticas.
Teorıa de Ramsey de suma-cero: estructuras de suma-cero.
27 / 47
Variantes
f : U → {c1, c2, . . . , ck} ⊆ Γ
Teorıa de Ramsey: estructuras monocromaticas.
Teorıa anti-Ramsey: estructuras heterocromaticas.
Teorıa de Ramsey de suma-cero: estructuras de suma-cero.
28 / 47
Teorıa anti-Ramsey
¿Como serıa una version anti-Ramsey del teorema de vdW?
Toerema de van der Waerden para k = t = 3
Si n es suficientemente grande entonces toda 3-coloracion de [n] contieneuna AP(3) monocromatica.
1 n 2n-1
Teorema (Jungic, Radoicic, 2003)
Toda 3-coloracion equipartita de [3n] contiene una AP(3) heterocromatica.
29 / 47
Teorıa anti-Ramsey
¿Como serıa una version anti-Ramsey del teorema de vdW?
Toerema de van der Waerden para k = t = 3
Si n es suficientemente grande entonces toda 3-coloracion de [n] contieneuna AP(3) monocromatica.
1 n 2n-1
Teorema (Jungic, Radoicic, 2003)
Toda 3-coloracion equipartita de [3n] contiene una AP(3) heterocromatica.
30 / 47
Teorıa anti-Ramsey
¿Como serıa una version anti-Ramsey del teorema de vdW?
Toerema de van der Waerden para k = t = 3
Si n es suficientemente grande entonces toda 3-coloracion de [n] contieneuna AP(3) monocromatica.
1 n 2n-1
Teorema (Jungic, Radoicic, 2003)
Toda 3-coloracion equipartita de [3n] contiene una AP(3) heterocromatica.
31 / 47
Ejemplos de resultados de tipo anti-Ramsey (aritmeticos)
Theorem (Alekseev, 1987)
Toda 3-coloracion equipartita de [3n] contiene una solucionheterocromatica de x + y = z.
Theorem (Jungic, Radoicic, 2003)
Toda 3-coloracion equipartita de [3n] contiene una una AP(3)heterocromatica.
Theorem (Fox, Mahdian, Radoicic, 2008)
Toda 4-coloracion equipartita de [4n] contiene una solucionheterocromatica de x + y = z + w.
32 / 47
Analogo anti-Ramsey al teorema de Rado
Teorema (De Loera, La Haye, M, Oliveros, Roldan-Pensado, 2016)
Una mariz racional A es regular heterocromatica si y solo si existe unvector en el ker(A) con entradas enteras positivas, y toda sub-matriz de Aobtenida de borrar dos columnas tiene el mismo rango de A.
A es k-regular heterocromatica, si toda k-coloracion equipartita de[kn] contiene una solucion heterocromatica de Ax = 0.
A is regular heterocromatica si es k-regular heterocromatica para ksuficientemente grande. El mınimo k tal que A es k-regularheterocromatica (si es que existe) se denota por r(A).
33 / 47
¿Que mas podemos hacer?
1 Estimar r(A) para matrices particulares.
2 Mejorar la condicion equipartita.
3 Cambiar el universo de estudio.
34 / 47
Colorear grupos
Oriol Serra
U =G abeliano
estructura: AP(3)
Mario Huicochea
U =Zp
estructura: ax + by + cz = d
Herramienta: Teoremas inversos de la Teorıa Aditiva de Numeros
35 / 47
Colorear con grupos
f : U → {c1, c2, . . . , ck} ⊆ Γ
Γ = Zk (Teorema de Erdos-Ginzburg-Ziv, constante de Daventport)
Γ = Z
{−d , . . . , 0, . . . , d}︷︸︸︷adef
¿Bajo que condiciones f : U → Z contiene una sub-estruc de suma-cero?
abcdefg︸ ︷︷ ︸∑
e∈U f (e) = 0
o |∑
e∈U f (e)| < q
36 / 47
Colorear con grupos
f : U → {c1, c2, . . . , ck} ⊆ Γ
Γ = Zk (Teorema de Erdos-Ginzburg-Ziv, constante de Daventport)
Γ = Z
{−d , . . . , 0, . . . , d}︷︸︸︷adef
¿Bajo que condiciones f : U → Z contiene una sub-estruc de suma-cero?
abcdefg︸ ︷︷ ︸∑
e∈U f (e) = 0
o |∑
e∈U f (e)| < q
37 / 47
Colorear con grupos
f : U → {c1, c2, . . . , ck} ⊆ Γ
Γ = Zk (Teorema de Erdos-Ginzburg-Ziv, constante de Daventport)
Γ = Z
{−d , . . . , 0, . . . , d}︷︸︸︷adef
¿Bajo que condiciones f : U → Z contiene una sub-estruc de suma-cero?
abcdefg︸ ︷︷ ︸∑
e∈U f (e) = 0
o |∑
e∈U f (e)| < q
38 / 47
Colorear con grupos
f : U → {c1, c2, . . . , ck} ⊆ Γ
Γ = Zk (Teorema de Erdos-Ginzburg-Ziv, constante de Daventport)
Γ = Z
{−d , . . . , 0, . . . , d}︷︸︸︷adef
¿Bajo que condiciones f : U → Z contiene una sub-estruc de suma-cero?
abcdefg︸ ︷︷ ︸∑
e∈U f (e) = 0
o |∑
e∈U f (e)| < q39 / 47
Teorıa de Ramsey de suma-cero
Existira un analogo al teorema de van der Waerden para Z-coloraciones?
efg︸︷︷︸{−1, 0, 1} or {−1, 1}
+ − − + + − + − + + − + − − − − + + − + + − + − +−
Given a positive even integer t, it is true that for sufficiently large n, anyzero-sum f : [n]→ {−1, 1} contains a zero-sum AP(t) ?
SI Adriana Hansberg, Yair Caro
40 / 47
Teorıa de Ramsey de suma-cero
Existira un analogo al teorema de van der Waerden para Z-coloraciones?efg︸︷︷︸
{−1, 0, 1} or {−1, 1}
+ − − + + − + − + + − + − − − − + + − + + − + − +−
Given a positive even integer t, it is true that for sufficiently large n, anyzero-sum f : [n]→ {−1, 1} contains a zero-sum AP(t) ?
SI Adriana Hansberg, Yair Caro
41 / 47
Teorıa de Ramsey de suma-cero
Existira un analogo al teorema de van der Waerden para Z-coloraciones?efg︸︷︷︸
{−1, 0, 1} or {−1, 1}
+ − − + + − + − + + − + − − − − + + − + + − + − +−
Given a positive even integer t, it is true that for sufficiently large n, anyzero-sum f : [n]→ {−1, 1} contains a zero-sum AP(t) ?
SI Adriana Hansberg, Yair Caro
42 / 47
Teorıa de Ramsey de suma-cero
Existira un analogo al teorema de van der Waerden para Z-coloraciones?efg︸︷︷︸
{−1, 0, 1} or {−1, 1}
+ − − + + − + − + + − + − − − − + + − + + − + − +−
Given a positive even integer t, it is true that for sufficiently large n, anyzero-sum f : [n]→ {−1, 1} contains a zero-sum AP(t) ?
SI Adriana Hansberg, Yair Caro
43 / 47
Teorıa de Ramsey de suma-cero
Existira un analogo al teorema de van der Waerden para Z-coloraciones?efg︸︷︷︸
{−1, 0, 1} or {−1, 1}
+ − − + + − + − + + − + − − − − + + − + + − + − +−
Given a positive even integer t, it is true that for sufficiently large n, anyzero-sum f : [n]→ {−1, 1} contains a zero-sum AP(t) ?
SI Adriana Hansberg, Yair Caro
44 / 47
Mas variantes... al estilo de la teorıa extremal de graficas
Teorema (Mantel, 1907)
Si G = (V ,E ) satisface |E | > 14 |V |
2 entonces G contiene un triangulo.
Conjetura
If G = (V ,E ) is a k-edge-coloured graph with colouring E = tki=1Ei and|Ei | ≥ 1
4k−2 |V |2 holds for 1 ≤ i ≤ k , then G contains a
non-monochromatic triangle.
45 / 47
Mas variantes... al estilo de la teorıa extremal de graficas
Teorema (Mantel, 1907)
Si G = (V ,E ) satisface |E | > 14 |V |
2 entonces G contiene un triangulo.
Conjetura
If G = (V ,E ) is a k-edge-coloured graph with colouring E = tki=1Ei and|Ei | ≥ 1
4k−2 |V |2 holds for 1 ≤ i ≤ k , then G contains a
non-monochromatic triangle.
46 / 47
Proyecto actual
El teorema de Hales-Jewett (1963)
U = Cnt = {x1 x2 ... xn : xi ∈ {0, 1, ...t − 1}}
47 / 47