Logo Studenta
Gratis
179 pág.
Análise combinatória matemática

Vista previa | Página 21 de 30

gozaba de notable buen humor. En 1930, a la edad de
veintisiete años, sufrió un ataque de ictericia y fue llevado al Hospital en
Londres para una operación de emergencia. Murió luego de la operación.
8.4. Teoŕıa de Ramsey 109
Ahora, sean q1, . . . , qt enteros tales que qi ≥ r, para cada
i ∈ {1, . . . , t}. Si existe algún subconjunto B ⊆ S con qi
elementos, de forma tal que todos los subconjuntos de B con
r elementos pertenecen a Ai (esto es, tiene la misma col-
oración), entonces decimos que B es (qi, Ai)-monocromático.
El teorema de Ramsey establece lo siguiente:
Teorema 50 (Ramsey, 1930) Para cualesquiera q1, . . . ,
qt enteros mayores o iguales que r, existe un mı́nimo en-
tero positivo n(q1, . . . , qt; r) con la propiedad que, si n ≥
n(q1, . . . , qt; r), entonces S contiene un subconjunto B de
qi elementos que es (qi, Ai)-monocromático, para algún i ∈
{1, 2, . . . , t}.
La demostración no la veremos en esta obra, aunque co-
mentamos que en la misma el caso interesante ocurre cuando
t = 2 y la prueba utiliza argumentos del Principio del Palo-
mar y el Principio de Inducción Matemática. Por otra parte,
puede observarse que cuando r = 1 el teorema de Ramsey se
reduce al Principio del Palomar.
Una versión simplificada del teorema de Ramsey ocurre
cuando tomamos q1 = q2 = · · · = qt = q. En este caso, el
teorema establece lo siguiente:
Sea S un conjunto con n elementos, con n su-
ficientemente grande. Supongamos que los sub-
conjuntos de S con r elementos son particionados
en t componentes o coloraciones, de manera arbi-
traria. Entonces, existe un subconjunto de S con
q elementos tal que todos sus subconjuntos con r
elementos tienen la misma coloración.
Como ejemplo de aplicación, consideremos n puntos en el
espacio tridimensional, situados en cualquier posición. Cada
pareja de puntos define un segmento recto entre ellos. De
manera general, procedemos a colorear cada uno de estos
110 Caṕıtulo 8. Otros tópicos de la teoŕıa de combinatoria
segmentos, usando únicamente los colores rojo y azul. En-
tonces, si n es suficientemente grande, digamos n ≥ n(q, q; 2),
podemos garantizar la existencia de un subconjunto B con
q puntos de los n puntos originales, de forma tal que to-
dos los segmentos asociados a los q puntos de B tengan la
misma coloración. De manera análoga se puede plantear el
problema asociado con los números Rk anteriormente men-
cionados: Rk = n(k, k; 2).
Los números n(q1, . . . , qt; r) del teorema de Ramsey son
los famosos e inaccesibles números de Ramsey , los cuales
tienen un significado combinatorio profundo. Se conoce ape-
nas lo siguiente acerca de tales números:
(a) Cuando r = 1, tendremos:
n(q1, . . . , qt; 1) = q1 + · · ·+ qt − t+ 1.
(b) Cuando t = 2, tendremos:
n(q1, r; r) = q1
n(r, q2; r) = q2
n(q1, q2; r) ≤ n(p1, p2; r − 1) + 1,
donde p1 = n(q1 − 1, q2; r) y p2 = n(q1, q2 − 1; r).
Desafortunadamente la desigualdad por recurrencia ante-
rior es bastante burda en casi todos los casos. Todo lo que se
conoce sobre los valores concretos de los números de Ramsey,
para r = 2 y t = 2, es lo siguiente:
n(q1, q2; 2) q1 = 3 4 5
q2 = 3 6 9 14
4 9 18
5 14
Finalmente, se menciona que también es muy poco lo
que se conoce acerca de los números de Ramsey para r = 2 y
t = 3: lo más profundo que se sabe es que n(3, 3, 3; 2) = 17.
8.5. Grupos de permutaciones 111
8.5 Grupos de permutaciones
Una permutación de grado n es una biyección
ϕ =
(
1 2 · · · n
k1 k2 · · · kn
)
del conjunto X = {1, 2, . . . , n} en śı mismo. Las permuta-
ciones de grado n, con la operación de la composición de
aplicaciones, forman un grupo Sn, llamado grupo simétrico
de grado n.
El estudio de los subgrupos normales de Sn tiene mucha
importancia dentro de la combinatoria. Se estudian los cic-
los de una permutación, las órbitas de un subgrupo de per-
mutación, la paridad de una permutación, el grupo alternante
An de las permutaciones pares y finalmente se arriba a un re-
sultado importante de la teoŕıa de grupos, que establece que
si n > 4, los únicos subgrupos normales del grupo alternante
An son An y {e}.
También se estudia el famoso teorema de Pólya, que per-
mite contar el número de esquemas relativos a grupos de
permutaciones de objetos. Este teorema se ubica en el sigu-
iente contexto: sea G un grupo de permutaciones (subgrupo
de An) y sea φ una aplicación de X en
A = {a1, a2, . . . , am}.
Dentro de este contexto, los elementos de A son llamados col-
ores y φ es una coloración: cada objeto i es “coloreado” con
el color φ(i). Dos coloraciones φ1 y φ2 pertenecen al mismo
esquema si existe una permutación g ∈ G tal que φ1 g = φ2.
Esto define sobre X una relación de equivalencia. El prob-
lema que se plantea es contar el número de clases de equiva-
lencia —o esquemas— de esta relación. Pólya demostró que
el número de esquemas es P (G;m,m, . . . ,m), donde m es el
112 Caṕıtulo 8. Otros tópicos de la teoŕıa de combinatoria
número de colores de A y
P (G;x1, x2, . . . , xn) =
1
|G|
∑
g∈G
x
λ1(g)
1 x
λ2(g)
2 · · ·x
λn(g)
n
es el polinomio ćıclico de G, concepto que está fuera del al-
cance de este estudio (los exponentes λi(g) denotan el número
de ciclos de g de tamaño i).
8.6 Algunos problemas abiertos
en combinatoria
Presentamos en esta sección algunos problemas abiertos de la
teoŕıa de combinatoria, seleccionados de entre una gran can-
tidad de problemas abiertos existentes. El objetivo de esta
sección es ilustrar lo dif́ıcil que pueden resultar las demostra-
ciones de algunos problemas de aspecto aparentemente in-
ocente, en el campo de la teoŕıa de la combinatoria.
8.6.1 Dos problemas de Paul Erdös
En 1981 Paul Erdös2, uno de los más importantes matemáticos
del siglo XX en el campo de la teoŕıa de la combinatoria,
publicó el art́ıculo “On the Combinatorial Problems which I
would most like to see solved”, en el cual expone alrededor
de 50 problemas abiertos en combinatoria y ofrece, para al-
gunos de ellos, recompensas económicas a quien encuentre
soluciones a los mismos.
2Paul Erdös (1913–1996) Matemático húngaro nacido en Budapest,
considerado uno de los más proĺıficos de la historia de las matemáticas,
con alrededor de 1.500 art́ıculos publicados en revistas internacionales
a lo largo de su vida, la mayoŕıa (casi el 70%) en coautoŕıa con más de
470 colaboradores diferentes. Su primer art́ıculo apareció cuando teńıa
19 años, lo que significa que Erdös publicó en promedio dos art́ıculos
mensuales durante sus 64 años de actividad creadora constante. Este
ritmo frenético no disminuyó con la edad. Murió en Varsovia cuando
8.6. Algunos problemas abiertos en combinatoria 113
La mayoŕıa de estos problemas son muy dif́ıciles de ex-
plicar, pues requieren conocimientos avanzados en el campo.
Sin embargo, algunos pocos son de fácil enunciado, entre los
cuales están los siguientes dos problemas:
1. Sea |Ak| = n, para 1 ≤ k ≤ n y suponga que |Ai∩Aj | ≤
1, para 1 ≤ i < j ≤ n. Demostrar que se puede colorear
los elementos de
⋃n
k=1Ak con n colores, de manera que
cada conjunto Ak, 1 ≤ k ≤ n, contenga elementos de
todos los colores.
Comenta el propio Erdös: “Faber, Lovász y yo hicimos
esta aparentemente inocente conjetura en una fiesta en
Boulder, Colorado, en Setiembre de 1972. Lentamente
comprendimos su gran dificultad. Ofrezco ahora 500
dólares por una prueba o un contraejemplo (no hace
mucho tiempo ofrećıa tan solo 50 dólares; el incremento
es debido no a la inflación sino al hecho que ahora
asist́ıa a un congreso de combinatoria, en la cual ya hab́ıa presentado
dos conferencias. En su último año de vida hab́ıa publicado 25 art́ıculos
y otra docena más estaban en trámite de publicación. Escribió también
varios libros y fue también un proĺıfico autor de reseñas matemáticas:
¡solamente el Mathematical Reviews contiene más de 700 reseñas con su
firma!
Proveniente de una familia jud́ıa, Erdös nació y vivió sus primeros
años rodeado de tragedias familiares,
Página1...171819202122232425...30