Doctorado
  1. Comprendiendo el Álgebra  1.1. Teoría de grupos  1.1.1. Propiedades básicas de los grupos  1.1.2. Subgrupos  1.1.3. Cosets y el teorema de Lagrange  1.1.4. Subgrupos normales  1.1.5. Grupo cociente  1.1.6. Homomorfismos de grupos  1.1.7. Teorema de Sylow  1.1.8. Introducción a los grupos libres  1.1.9. ¿Qué son las actividades grupales?  1.1.10. Grupos simples y resolubles  1.2. Teoría de anillos  1.2.1. Anillos e ideales  1.2.2. Introducción a los homomorfismos de anillos  1.2.3. Anillos polinomiales  1.2.4. Dominios Ideales Principales  1.2.5. Dominios de factorización única  1.2.6. Anillos noetherianos  1.2.7. Anillos de Artiniano  1.3. Teoría de campos  1.3.1. Extensiones de campos  1.3.2. División de áreas  1.3.3. Teoría de Galois  1.3.4. Cierre algebraico en teoría de campos  1.3.5. Campos finitos  1.3.6. Extensión trascendental  1.4. Teoría de módulos  1.4.1. Módulos sobre anillos  1.4.2. Módulos libres  1.4.3. Morfismo de módulos  1.4.4. Módulos simples y semisimples  1.4.5. Módulos proyectivos  1.4.6. Módulos inyectivos  1.5. Álgebra lineal  1.5.1. Espacio vectorial  1.5.2. Transformaciones lineales  1.5.3. Comprendiendo Valores Propios y Vectores Propios  1.5.4. Forma canónica  1.5.5. Espacio de producto interior  1.5.6. Teorema Espectral  1.5.7. Descomposición en valores singulares
  2. Entendiendo el Análisis Matemático  2.1. Análisis real  2.1.1. Números reales y completitud  2.1.2. Introducción a las secuencias y series  2.1.3. Continuidad en el análisis real  2.1.4. Diferenciación en el análisis real  2.1.5. Integración de Riemann  2.1.6. Introducción a los espacios métricos  2.1.7. Medida de Lebesgue  2.2. Análisis complejo  2.2.1. Números complejos  2.2.2. Funciones analíticas  2.2.3. Integración de contornos  2.2.4. Teorema de Cauchy  2.2.5. Teorema del residuo  2.2.6. Mapeo conforme  2.3. Análisis funcional  2.3.1. Comprender ubicaciones estándar  2.3.2. Introducción a los espacios de Banach  2.3.3. Espacios de Hilbert  2.3.4. Operadores lineales  2.3.5. Teoría espectral  2.3.6. Operadores compactos  2.4. Teoría de la medida  2.4.1. Álgebra sigma  2.4.2. Medidas e integrales en la teoría de la medida  2.4.3. Integración de Lebesgue  2.4.4. Teorema de convergencia  2.4.5. Teorema de Fubini  2.5. Análisis Armónico  2.5.1. Serie de Fourier  2.5.2. Transformada de Fourier  2.5.3. Teoría de la distribución  2.5.4. Wavelets
  3. Topología  3.1. Topología general  3.1.1. Conjuntos abiertos y cerrados  3.1.2. Continuidad  3.1.3. Introducción a la compacidad  3.1.4. Conectividad en topología general  3.1.5. Topología métrica  3.2. Topología algebraica  3.2.1. Grupo fundamental  3.2.2. Teoría de la homotopía  3.2.3. Teoría de la homología  3.2.4. Cohomología  3.2.5. Secuencia exacta  3.3. Topología diferencial  3.3.1. Variedades suaves  3.3.2. Espacio tangente  3.3.3. Campos vectoriales  3.3.4. Comprensión de las Formas Diferenciales
  4. Geometría  4.1. Geometría diferencial  4.1.1. Curvas y superficies en geometría diferencial  4.1.2. Geometría Riemanniana  4.1.3. Comprendiendo las geodésicas en la geometría diferencial  4.1.4. Curvatura  4.2. Geometría algebraica  4.2.1. Variedades afines y proyectivas  4.2.2. Planes  4.2.3. Separadores e intersecciones  4.2.4. Cohomología en geometría algebraica  4.3. Geometría Computacional  4.3.1. Introducción a las cubiertas convexas en geometría computacional  4.3.2. Triangulación  4.3.3. Diagrama de Voronoi  4.3.4. Algoritmos Geométricos
  5. Teoría de números  5.1. Teoría de números elemental  5.1.1. Divisibilidad en la teoría de números elemental  5.1.2. Congruencia en teoría de números elemental  5.1.3. Aritmética modular  5.2. Teoría analítica de números  5.2.1. Teorema de los números primos  5.2.2. Series de Dirichlet  5.2.3. Zeta y funciones L  5.3. Teoría de números algebraicos  5.3.1. Campos numéricos  5.3.2. Introducción a ideales en teoría de números algebraicos  5.3.3. Grupos de clases en teoría de números algebraicos  5.3.4. Representación de Galois
  6. Compañerismo  6.1. Combinatoria computacional  6.1.1. Función generadora  6.1.2. Relación de recurrencia  6.1.3. Ppermutaion y combinaciones  6.2. Teoría de grafos  6.2.1. Isomorfismo de grafos  6.2.2. Planicidad en teoría de grafos  6.2.3. Coloración de grafos  6.3. Combinatoria extrema  6.3.1. Teoría de Ramsey  6.3.2. Métodos probabilísticos en combinatoria extrema  6.4. Combinatoria algebraica  6.4.1. Métodos de matrices en combinatoria algebraica  6.4.2. Teoría de la representación
  7. Argumentos y fundamentos  7.1. Teoría de conjuntos  7.1.1. Axiomas de Zermelo-Fraenkel  7.1.2. Ordinales y cardinales  7.2. Introducción a la teoría de modelos  7.2.1. Estructuras y teorías en la teoría de modelos  7.2.2. Teorema de compacidad  7.3. Teoría de la demostración  7.3.1. Sistemas formales  7.3.2. Consistencia y completitud
  8. Probabilidad y Estadística  8.1. Teoría de la probabilidad  8.1.1. Variables aleatorias  8.1.2. Expectativa y variación  8.1.3. Teorema central del límite  8.2. Procesos estocásticos  8.2.1. Cadenas de Markov  8.2.2. Movimiento Browniano  8.3. Inferencia estadística  8.3.1. Pruebas de hipótesis  8.3.2. Análisis de regresión
  9. Matemáticas aplicadas  9.1. Análisis numérico en matemáticas aplicadas  9.1.1. Métodos iterativos  9.1.2. Interpolación  9.1.3. Análisis de errores  9.2. Ecuaciones diferenciales parciales  9.2.1. Ecuación elíptica  9.2.2. Ecuación parabólica  9.2.3. Ecuaciones hiperbólicas  9.3. Sistemas dinámicos  9.3.1. Teoría del caos  9.3.2. Análisis de estabilidad en sistemas dinámicos

Doctorado → Compañerismo ↓


Combinatoria extrema


La combinatoria extrema es un área fascinante de las matemáticas que se centra en el estudio de propiedades extremas (máximas o mínimas) de estructuras discretas. Estas estructuras pueden incluir gráficos, hipergrafos, conjuntos, secuencias y otros objetos combinatorios. Las preguntas centrales de la combinatoria extrema a menudo giran en torno a determinar el tamaño máximo o mínimo de una colección que satisface determinadas condiciones. Esto puede implicar determinar el gráfico más grande con ciertas propiedades o el conjunto más pequeño que satisface condiciones específicas.

Conceptos básicos y definiciones

Para profundizar en la combinatoria extrema, primero debemos comprender algunos conceptos básicos y definiciones que forman la base de este campo.

Grafos y subgrafos

Un grafo es una colección de vértices (o nodos) y las aristas que conectan pares de vértices. Un subgrafo es un subconjunto de los vértices del grafo, más todas las aristas que los conectan.

Hipergrafos

Un hipergrafo generaliza el concepto de grafo al tener aristas que pueden conectar más de dos vértices. Estas aristas, a menudo llamadas hiperaristas, pueden contener cualquier cantidad de vértices.

Conjuntos y secuencias

En combinatoria, conjuntos son colecciones de objetos o números distintos, mientras que secuencias son colecciones ordenadas de objetos o números. Los conjuntos y las secuencias se utilizan comúnmente para estudiar diferentes problemas, como la intersección máxima o secuencias superpuestas.

Teoremas principales en combinatoria extrema

Varios teoremas principales sustentan la combinatoria extrema. Estos teoremas a menudo proporcionan insights o límites sobre las propiedades máximas o mínimas de estructuras combinatorias.

Teorema de Turán

Uno de los resultados más famosos en la teoría de grafos extrema es el teorema de Turán. Este teorema proporciona un límite en el número de aristas en un grafo que carece de un subgrafo completo de cierto tamaño.

Teorema de Turán: Para un grafo con n vértices que no contiene un subgrafo completo con r + 1 vértices, el número máximo de aristas es:

T_r(n) = left(1 - frac{1}{r} right) frac{n^2}{2}

Esto implica que si desea un grafo que no incluya el grafo completo en r + 1 vértices, entonces el número de aristas está limitado por la fórmula anterior.

Por ejemplo, si n = 5 y r = 2, entonces el número máximo de aristas en un grafo libre de triángulos es:

T_2(5) = left(1 - frac{1}{2} right) frac{5^2}{2} = frac{1}{2} cdot frac{25}{2} = 6.25

Por lo tanto, un grafo libre de triángulos con 5 vértices puede tener como máximo 6 aristas.

Teorema de Erdős–Stone

El teorema de Erdős–Stone generaliza el teorema de Turán y es una piedra angular de la teoría de grafos extrema, determinando el número extremo para cualquier grafo con número cromático mayor que 2.

Teorema de Erdős-Stone: Si un grafo G no tiene un subgrafo completo K_{r+1}, entonces el número máximo de aristas es aproximadamente:

ex(n, K_{r+1}) = left(1 - frac{1}{r} + o(1) right) frac{n^2}{2}
A B C

El SVG anterior representa un triángulo.

Teoría extrema de conjuntos

La teoría extrema de conjuntos generalmente trata sobre preguntas sobre familias de conjuntos. El famoso teorema de Erdős-Ko-Rado es uno de los resultados más profundos en esta área.

Teorema de Erdős–Ko–Rado

Este teorema proporciona un límite superior en el tamaño de una familia de conjuntos, si todos los conjuntos se intersectan al menos en un número fijo de elementos.

Teorema de Erdős-Ko-Rado: Supongamos que k ≤ n/2 y F es una familia de subconjuntos de k elementos de {1, 2, ..., n}. Si cada dos conjuntos en F se intersectan entre sí, entonces |F| ≤ C(n-1, k-1). Este límite se alcanza cuando F consiste en todos los conjuntos de k elementos que contienen un elemento fijo.

Para n = 5 y k = 2, la familia de conjuntos { {1,2}, {2,3}, {3,4}, {4,5}, {5,1} } alcanza un límite cuando todos los pares de vértices se intersectan.

Aplicaciones y problemas

La combinatoria extrema tiene aplicaciones en varios campos, incluyendo la ciencia de la computación, la teoría de la información y la teoría de diseño. Es útil para resolver problemas que implican maximizar o minimizar algunas cantidades bajo restricciones dadas.

Problema 1: Maximizar un grafo libre de triángulos

Si un grafo tiene n vértices, ¿cuál es el número máximo de aristas que puede tener sin formar ningún triángulo?

Según el teorema de Turán, la respuesta es:

T_2(n) = left(1 - frac{1}{2} right) frac{n^2}{2} = frac{n^2}{4}

Problema 2: Familia más grande de conjuntos disjuntos

Supongamos que tienes subconjuntos de un conjunto de tamaño n, y quieres la familia más grande de subconjuntos de tal manera que no existan dos subconjuntos disjuntos por pares. La solución a este problema la da el teorema de Erdős-Ko-Rado.

Si los subconjuntos son conjuntos de k elementos, entonces la familia más grande se obtiene cuando cada conjunto tiene al menos un elemento común, y el tamaño es como máximo:

C(n-1, k-1)

Problema 3: Conjetura de Conway sobre los thrackle

Un thrackle es un grafo en el plano en el que cada par de aristas se cruza exactamente una vez. La conjetura de Conway sobre los thrackle afirma que el número máximo de aristas en un thrackle es igual al número de sus vértices.

Aunque este problema no ha sido resuelto, ilustra las preguntas intrigantes planteadas por la combinatoria extrema.

Conclusión

La combinatoria extrema es un campo robusto y vibrante que plantea y resuelve preguntas fundamentales sobre cómo se maximizan y minimizan configuraciones dentro de estructuras prescritas. Proporciona importantes insights no solo en matemáticas puras, sino también en campos computacionales donde estos principios se aplican para resolver problemas del mundo real. Con su rica historia de resultados e investigación en curso, la combinatoria extrema sigue siendo una área importante de investigación matemática.


Doctorado → 6.3


U
username
0%
completado en Doctorado

← Anterior (6.2.3)
Coloración de grafos
Siguiente (6.3.1) →
Teoría de Ramsey

Comentarios 



Combinatoria extrema

https://www.buddymath.com/phd/6.3?bmal=es