Combinatoria

La combinatoria enumerativa es el área más clásica de la combinatoria y se centra en contar el número de ciertos objetos combinatorios. Si bien contar el número de elementos en un conjunto es un problema matemático bastante amplio , muchos de los problemas que surgen en las aplicaciones tienen una descripción combinatoria relativamente simple. Los números de Fibonacci son el ejemplo básico de un problema en combinatoria enumerativa. El método de doce partes proporciona un marco unificado para contar permutaciones , combinaciones y particiones .

La combinatoria analítica se ocupa de la enumeración de estructuras combinatorias utilizando herramientas del análisis complejo y la teoría de la probabilidad . A diferencia de la combinatoria enumerativa, que utiliza fórmulas combinatorias explícitas y funciones generadoras para describir los resultados, la combinatoria analítica tiene como objetivo obtener fórmulas asintóticas .

La teoría de particiones estudia diversos problemas de enumeración y asintóticos relacionados con particiones enteras , y está estrechamente vinculada a las series q , las funciones especiales y los polinomios ortogonales . Originalmente parte de la teoría de números y el análisis , ahora se considera parte de la combinatoria o un campo independiente. Incorpora el enfoque biyectivo y diversas herramientas del análisis y la teoría analítica de números , y tiene conexiones con la mecánica estadística . Las particiones pueden visualizarse gráficamente con diagramas de Young o diagramas de Ferrers . Aparecen en varias ramas de las matemáticas y la física , incluyendo el estudio de los polinomios simétricos y del grupo simétrico , y en la teoría de la representación de grupos en general.

Los grafos son objetos fundamentales en combinatoria. Las consideraciones de la teoría de grafos abarcan desde la enumeración (p. ej., el número de grafos con n vértices y k aristas) hasta las estructuras existentes (p. ej., los ciclos hamiltonianos) y las representaciones algebraicas (p. ej., dado un grafo G y dos números x e y , ¿tiene el polinomio de Tutte T _G ( x , y ) una interpretación combinatoria?). Aunque existen conexiones muy fuertes entre la teoría de grafos y la combinatoria, a veces se las considera disciplinas separadas. ^{[ 21 ]} Si bien los métodos combinatorios se aplican a muchos problemas de la teoría de grafos, ambas disciplinas se utilizan generalmente para buscar soluciones a diferentes tipos de problemas.

La teoría del diseño estudia los diseños combinatorios , que son colecciones de subconjuntos con ciertas propiedades de intersección . Los diseños de bloques son diseños combinatorios de un tipo especial. Esta área es una de las más antiguas de la combinatoria, como en el problema de la colegiala propuesto por Kirkman en 1850. La solución del problema es un caso particular de un sistema de Steiner , que desempeña un papel importante en la clasificación de grupos simples finitos . Esta área también tiene conexiones con la teoría de la codificación y la combinatoria geométrica.

La teoría del diseño combinatorio puede aplicarse al área del diseño de experimentos . Parte de la teoría básica de los diseños combinatorios se originó en el trabajo del estadístico Ronald Fisher sobre el diseño de experimentos biológicos. También se encuentran aplicaciones modernas en una amplia gama de áreas, que incluyen geometría finita , programación de torneos , loterías , química matemática , biología matemática , diseño y análisis de algoritmos , redes , pruebas grupales y criptografía . ^{[ 22 ]}

La geometría finita estudia los sistemas geométricos que poseen un número finito de puntos. Las estructuras análogas a las de las geometrías continuas ( plano euclidiano , espacio proyectivo real , etc.), pero definidas combinatoriamente, son los principales objetos de estudio. Esta área ofrece una rica fuente de ejemplos para la teoría del diseño . No debe confundirse con la geometría discreta ( geometría combinatoria ).

La teoría del orden estudia los conjuntos parcialmente ordenados , tanto finitos como infinitos. Proporciona un marco formal para describir enunciados como «esto es menor que aquello» o «esto precede a aquello». Diversos ejemplos de órdenes parciales aparecen en álgebra , geometría, teoría de números y, en general, en combinatoria y teoría de grafos. Entre las clases y ejemplos más notables de órdenes parciales se incluyen los retículos y las álgebras booleanas .

La teoría de matroides abstrae parte de la geometría . Estudia las propiedades de conjuntos (generalmente finitos) de vectores en un espacio vectorial que no dependen de coeficientes específicos en una relación de dependencia lineal . No solo la estructura, sino también las propiedades enumerativas pertenecen a la teoría de matroides. Esta teoría fue introducida por Hassler Whitney y estudiada como parte de la teoría del orden. Actualmente es un campo de estudio independiente con diversas conexiones con otras ramas de la combinatoria.

La combinatoria extrema estudia el tamaño máximo que puede tener una colección de objetos finitos ( números , grafos , vectores , conjuntos , etc.) si debe satisfacer ciertas restricciones. Gran parte de la combinatoria extrema se centra en clases de sistemas de conjuntos ; esto se conoce como teoría extremal de conjuntos. Por ejemplo, en un conjunto de n elementos, ¿cuál es el mayor número de subconjuntos de k elementos que pueden intersecarse dos a dos? ¿Cuál es el mayor número de subconjuntos que no contienen a ningún otro? Esta última pregunta se responde con el teorema de Sperner , que dio origen a gran parte de la teoría extremal de conjuntos.

Los tipos de preguntas abordadas en este caso se refieren al grafo más grande posible que satisface ciertas propiedades. Por ejemplo, el grafo más grande sin triángulos con 2n vértices es un grafo bipartito completo K _n,n . A menudo es demasiado difícil incluso encontrar la respuesta extremal f ( n ) de forma exacta y solo se puede dar una estimación asintótica .

La teoría de Ramsey es otra rama de la combinatoria extremal. Establece que cualquier configuración suficientemente grande contendrá algún tipo de orden. Es una generalización avanzada del principio del palomar .

En combinatoria probabilística, las preguntas son del siguiente tipo: ¿cuál es la probabilidad de una determinada propiedad para un objeto discreto aleatorio, como un grafo aleatorio ? Por ejemplo, ¿cuál es el número promedio de triángulos en un grafo aleatorio? Los métodos probabilísticos también se utilizan para determinar la existencia de objetos combinatorios con ciertas propiedades prescritas (para las cuales puede ser difícil encontrar ejemplos explícitos) al observar que la probabilidad de seleccionar aleatoriamente un objeto con esas propiedades es mayor que 0. Este enfoque (a menudo denominado método probabilístico ) ha demostrado ser muy eficaz en aplicaciones a la combinatoria extremal y la teoría de grafos. Un área estrechamente relacionada es el estudio de cadenas de Markov finitas , especialmente en objetos combinatorios. Aquí también se utilizan herramientas probabilísticas para estimar el tiempo de mezcla .

A menudo asociada con Paul Erdős , pionero en la materia, la combinatoria probabilística se consideraba tradicionalmente un conjunto de herramientas para estudiar problemas en otras áreas de la combinatoria. Recientemente, esta disciplina se ha consolidado como un campo independiente de la combinatoria.

La combinatoria algebraica es un área de las matemáticas que emplea métodos del álgebra abstracta , en particular la teoría de grupos y la teoría de la representación , en diversos contextos combinatorios y, a la inversa, aplica técnicas combinatorias a problemas algebraicos . La combinatoria algebraica se ha concebido de forma más amplia como un área de las matemáticas donde la interacción entre métodos combinatorios y algebraicos es especialmente fuerte y significativa. Así, los temas combinatorios pueden ser de naturaleza enumerativa o involucrar matroides , politopos , conjuntos parcialmente ordenados o geometrías finitas . En el ámbito algebraico, además de la teoría de grupos y la teoría de la representación, son comunes la teoría de retículos y el álgebra conmutativa .

La combinatoria de palabras se ocupa de los lenguajes formales . Surgió de forma independiente en diversas ramas de las matemáticas, como la teoría de números , la teoría de grupos y la probabilidad . Tiene aplicaciones en la combinatoria enumerativa, el análisis fractal , la informática teórica , la teoría de autómatas y la lingüística . Si bien muchas aplicaciones son recientes, la jerarquía clásica de Chomsky-Schützenberger de clases de gramáticas formales es quizás el resultado más conocido en este campo.

La combinatoria geométrica está relacionada con la geometría convexa y discreta . Se pregunta, por ejemplo, cuántas caras de cada dimensión puede tener un politopo convexo . Las propiedades métricas de los politopos también desempeñan un papel importante, como el teorema de Cauchy sobre la rigidez de los politopos convexos. Asimismo, se consideran politopos especiales, como los permutoedros , los asociahedros y los politopos de Birkhoff . Geometría combinatoria es un nombre histórico para la geometría discreta.

Incluye varias subáreas como la combinatoria poliédrica (el estudio de las caras de los poliedros convexos ), la geometría convexa (el estudio de los conjuntos convexos , en particular la combinatoria de sus intersecciones) y la geometría discreta , que a su vez tiene muchas aplicaciones en la geometría computacional . El estudio de los politopos regulares , los sólidos arquimedianos y los números de contacto también forma parte de la combinatoria geométrica. Asimismo, se consideran politopos especiales, como el permutoedro , el asociaedro y el politopo de Birkhoff .

Se utilizan análogos combinatorios de conceptos y métodos de topología para estudiar la coloración de grafos , la división equitativa , las particiones , los conjuntos parcialmente ordenados , los árboles de decisión , los problemas del collar y la teoría discreta de Morse . No debe confundirse con la topología combinatoria , que es una denominación antigua para la topología algebraica .

La combinatoria aritmética surgió de la interacción entre la teoría de números , la combinatoria, la teoría ergódica y el análisis armónico . Se centra en las estimaciones combinatorias asociadas a las operaciones aritméticas (suma, resta, multiplicación y división). La teoría aditiva de números (a veces también llamada combinatoria aditiva) se refiere al caso especial en el que solo intervienen las operaciones de suma y resta. Una técnica importante en la combinatoria aritmética es la teoría ergódica de sistemas dinámicos .

La combinatoria infinita, o teoría combinatoria de conjuntos, es una extensión de las ideas de la combinatoria a los conjuntos infinitos. Forma parte de la teoría de conjuntos , un área de la lógica matemática , pero utiliza herramientas e ideas tanto de la teoría de conjuntos como de la combinatoria extremal. Algunos de los temas estudiados incluyen grafos y árboles continuos , extensiones del teorema de Ramsey y el axioma de Martin . Los desarrollos recientes se refieren a la combinatoria del continuo ^{[ 23 ]} y a la combinatoria sobre sucesores de cardinales singulares ^{[ 24 ] .}

Gian-Carlo Rota utilizó el nombre de combinatoria continua ^{[ 25 ]} para describir la probabilidad geométrica , ya que existen muchas analogías entre el conteo y la medición .

La optimización combinatoria es el estudio de la optimización en objetos discretos y combinatorios. Comenzó como parte de la combinatoria y la teoría de grafos, pero ahora se considera una rama de las matemáticas aplicadas y la informática, relacionada con la investigación operativa , la teoría de algoritmos y la teoría de la complejidad computacional .

La teoría de la codificación surgió como parte de la teoría del diseño, con las primeras construcciones combinatorias de códigos correctores de errores . La idea principal de esta disciplina es diseñar métodos eficientes y fiables de transmisión de datos. Actualmente, constituye un amplio campo de estudio, parte de la teoría de la información .

La geometría discreta (también llamada geometría combinatoria) tuvo sus inicios como parte de la combinatoria, con resultados tempranos sobre politopos convexos y números de contacto . Con la aparición de aplicaciones de la geometría discreta a la geometría computacional , estos dos campos se fusionaron parcialmente y se convirtieron en un campo de estudio independiente. Aún existen muchas conexiones con la combinatoria geométrica y topológica, que a su vez pueden considerarse derivaciones de la geometría discreta inicial.

Los aspectos combinatorios de los sistemas dinámicos constituyen otro campo emergente. En este ámbito, los sistemas dinámicos pueden definirse sobre objetos combinatorios. Véase, por ejemplo, el sistema dinámico de grafos .

Existe una creciente interacción entre la combinatoria y la física , en particular la física estadística . Algunos ejemplos incluyen una solución exacta del modelo de Ising y una conexión entre el modelo de Potts , por un lado, y los polinomios cromáticos y de Tutte , por otro.