Combinatoria
Combinatoria es un área de las matemáticas que se ocupa principalmente del conteo, tanto como medio como para obtener resultados, y ciertas propiedades de las estructuras finitas. Está estrechamente relacionado con muchas otras áreas de las matemáticas y tiene muchas aplicaciones que van desde la lógica hasta la física estadística y desde la biología evolutiva hasta la informática.
La combinatoria es bien conocida por la amplitud de los problemas que aborda. Los problemas combinatorios surgen en muchas áreas de las matemáticas puras, especialmente en álgebra, teoría de la probabilidad, topología y geometría, así como en sus múltiples áreas de aplicación. Históricamente, muchas cuestiones combinatorias se han considerado de forma aislada, dando una solución ad hoc a un problema que surge en algún contexto matemático. Sin embargo, a finales del siglo XX se desarrollaron métodos teóricos poderosos y generales, convirtiendo a la combinatoria en una rama independiente de las matemáticas por derecho propio. Una de las partes más antiguas y accesibles de la combinatoria es la teoría de grafos, que por sí misma tiene numerosas conexiones naturales con otras áreas. La combinatoria se utiliza con frecuencia en informática para obtener fórmulas y estimaciones en el análisis de algoritmos.
Un matemático que estudia combinatoria se llama combinatorialista.
Definición
El alcance completo de la combinatoria no está universalmente aceptado. Según H.J. Ryser, una definición del tema es difícil porque cruza tantas subdivisiones matemáticas. En la medida en que un área puede describirse por los tipos de problemas que aborda, la combinatoria se ocupa de:
- el enumeración (contando) de estructuras especificadas, a veces referidas como arreglos o configuraciones en un sentido muy general, asociadas con sistemas finitos,
- el existencia de tales estructuras que satisfagan ciertos criterios dados,
- el construcción de estas estructuras, tal vez de muchas maneras, y
- optimización: encontrar la estructura o solución "mejor" entre varias posibilidades, ya sea la "más grande", "smallest" o satisfacer a otros criterio de optimización.
Leon Mirsky ha dicho: "la combinatoria es una gama de estudios interrelacionados que tienen algo en común y, sin embargo, difieren ampliamente en sus objetivos, sus métodos y el grado de coherencia que han alcanzado." Una forma de definir la combinatoria es, quizás, describir sus subdivisiones con sus problemas y técnicas. Este es el enfoque que se utiliza a continuación. Sin embargo, también existen razones puramente históricas para incluir o no algunos temas bajo el paraguas de la combinatoria. Aunque se trata principalmente de sistemas finitos, algunas preguntas y técnicas combinatorias se pueden extender a un entorno infinito (específicamente contable) pero discreto.
Historia
Los conceptos combinatorios básicos y los resultados enumerativos aparecieron en todo el mundo antiguo. En el siglo VI a. C., el antiguo médico indio Sushruta afirma en Sushruta Samhita que se pueden hacer 63 combinaciones de 6 gustos diferentes, tomados uno a la vez, dos a la vez, etc., calculando así los 26 − 1 posibilidades. El historiador griego Plutarco analiza una discusión entre Crisipo (siglo III a. C.) e Hiparco (siglo II a. C.) sobre un problema enumerativo bastante delicado, que luego se demostró que estaba relacionado con los números de Schröder-Hipparchus. Anteriormente, en el Ostomachion, Arquímedes (siglo III a. C.) pudo haber considerado el número de configuraciones de un rompecabezas de mosaico, mientras que los intereses combinatorios posiblemente estaban presentes en las obras perdidas de Apolonio.
En la Edad Media, la combinatoria siguió estudiándose, en gran parte fuera de la civilización europea. El matemático indio Mahāvīra (c. 850) proporcionó fórmulas para el número de permutaciones y combinaciones, y estas Las fórmulas pueden haber sido familiares para los matemáticos indios ya en el siglo VI d.C. El filósofo y astrónomo rabino Abraham ibn Ezra (c. 1140) estableció la simetría de los coeficientes binomiales, mientras que una fórmula cerrada fue obtenida posteriormente por el talmudista y matemático Levi ben Gerson (más conocido como Gersonides), en 1321. El triángulo aritmético, un diagrama gráfico que muestra las relaciones entre los coeficientes binomiales, fue presentado por matemáticos en tratados que datan del siglo X y eventualmente se conocería como el triángulo de Pascal. Más tarde, en la Inglaterra medieval, la campanología proporcionó ejemplos de lo que ahora se conoce como ciclos hamiltonianos en ciertos gráficos de Cayley sobre permutaciones.
Durante el Renacimiento, junto con el resto de las matemáticas y las ciencias, la combinatoria disfrutó de un renacimiento. Las obras de Pascal, Newton, Jacob Bernoulli y Euler se convirtieron en fundamentales en el campo emergente. En los tiempos modernos, las obras de J.J. Sylvester (finales del siglo XIX) y Percy MacMahon (principios del siglo XX) ayudaron a sentar las bases de la combinatoria enumerativa y algebraica. La teoría de grafos también disfrutó de un aumento de interés al mismo tiempo, especialmente en relación con el problema de los cuatro colores.
En la segunda mitad del siglo XX, la combinatoria disfrutó de un rápido crecimiento, lo que llevó al establecimiento de docenas de nuevas revistas y conferencias sobre el tema. En parte, el crecimiento fue impulsado por nuevas conexiones y aplicaciones a otros campos, desde el álgebra hasta la probabilidad, desde el análisis funcional hasta la teoría de números, etc. Estas conexiones traspasaron los límites entre la combinatoria y partes de las matemáticas y la informática teórica, pero al mismo tiempo condujo a una fragmentación parcial del campo.
Enfoques y subcampos de la combinatoria
Combinatoria enumerativa
La combinatoria enumerativa es el área más clásica de la combinatoria y se concentra en contar el número de ciertos objetos combinatorios. Aunque 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. La vía doce proporciona un marco unificado para contar permutaciones, combinaciones y particiones.
Combinatoria analítica
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.
Teoría de la partición
La teoría de la partición estudia varios problemas asintóticos y de enumeración relacionados con las particiones enteras y está estrechamente relacionada con las series q, las funciones especiales y los polinomios ortogonales. Originalmente parte de la teoría y el análisis de números, ahora se considera parte de la combinatoria o un campo independiente. Incorpora el enfoque biyectivo y varias herramientas de análisis y teoría analítica de números y tiene conexiones con la mecánica estadística. Las particiones se pueden visualizar gráficamente con diagramas de Young o diagramas de Ferrers. Ocurren en varias ramas de las matemáticas y la física, incluido el estudio de polinomios simétricos y del grupo simétrico y en la teoría de representación de grupos en general.
Teoría de grafos
Los gráficos son objetos fundamentales en combinatoria. Las consideraciones de la teoría de grafos van desde la enumeración (p. ej., el número de gráficos en n vértices con k aristas) hasta estructuras existentes (p. ej., ciclos hamiltonianos) y representaciones algebraicas (p. ej., dada una gráfica G y dos números x y y, ¿el polinomio de Tutte T G(x,y) tienen una interpretación combinatoria?). Aunque existen conexiones muy fuertes entre la teoría de grafos y la combinatoria, a veces se las considera materias separadas. Si bien los métodos combinatorios se aplican a muchos problemas de teoría de grafos, las dos disciplinas generalmente se usan para buscar soluciones a diferentes tipos de problemas.
Teoría del diseño
La teoría del diseño es un estudio de 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 partes más antiguas de la combinatoria, como en el problema de la colegiala de Kirkman propuesto en 1850. La solución del problema es un caso especial de un sistema de Steiner, cuyos sistemas juegan un papel importante en la clasificación de finitos. grupos simples. El área tiene más conexiones con la teoría de la codificación y la combinatoria geométrica.
La teoría del diseño combinatorio se puede aplicar al área de 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. Las aplicaciones modernas también se encuentran 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.
Geometría finita
La geometría finita es el estudio de los sistemas geométricos que tienen solo un número finito de puntos. Estructuras análogas a las que se encuentran en las geometrías continuas (plano euclidiano, espacio proyectivo real, etc.) pero definidas combinatoriamente son los principales elementos estudiados. Esta área proporciona una rica fuente de ejemplos para la teoría del diseño. No debe confundirse con la geometría discreta (geometría combinatoria).
Teoría del orden
La teoría del orden es el estudio de conjuntos parcialmente ordenados, tanto finitos como infinitos. Proporciona un marco formal para describir afirmaciones como "esto es menos que eso" o "esto precede a aquello". Varios ejemplos de órdenes parciales aparecen en álgebra, geometría, teoría de números y en combinatoria y teoría de grafos. Clases notables y ejemplos de órdenes parciales incluyen celosías y álgebras booleanas.
Teoría de las matroides
La teoría de las matroides abstrae parte de la geometría. Estudia las propiedades de conjuntos (generalmente, conjuntos finitos) de vectores en un espacio vectorial que no dependen de los coeficientes particulares en una relación de dependencia lineal. No solo la estructura sino también las propiedades enumerativas pertenecen a la teoría matroide. La teoría de matroides fue introducida por Hassler Whitney y estudiada como parte de la teoría del orden. Ahora es un campo de estudio independiente con varias conexiones con otras partes de la combinatoria.
Combinatoria extrema
La combinatoria extrema estudia cuán grande o pequeña puede ser una colección de objetos finitos (números, gráficos, vectores, conjuntos, etc.), si tiene que satisfacer ciertas restricciones. Gran parte de la combinatoria extrema se refiere a clases de sistemas de conjuntos; esto se llama teoría de conjuntos extremos. Por ejemplo, en un conjunto de elementos n, ¿cuál es el mayor número de subconjuntos de elementos k que pueden cruzarse entre sí por parejas? ¿Cuál es el mayor número de subconjuntos de los cuales ninguno contiene otro? La última pregunta se responde con el teorema de Sperner, que dio origen a gran parte de la teoría de conjuntos extremos.
Los tipos de preguntas abordadas en este caso son sobre el gráfico más grande posible que satisfaga ciertas propiedades. Por ejemplo, el gráfico sin triángulos más grande en 2n vértices es un gráfico bipartito completo Kn,n. A menudo es demasiado difícil incluso encontrar la respuesta extrema f(n) exactamente y solo se puede dar una estimación asintótica.
La teoría de Ramsey es otra parte de la combinatoria extrema. Establece que cualquier configuración suficientemente grande contendrá algún tipo de orden. Es una generalización avanzada del principio del casillero.
Combinatoria probabilística
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 gráfico aleatorio? Por ejemplo, ¿cuál es el número promedio de triángulos en un gráfico aleatorio? Los métodos probabilísticos también se usan para determinar la existencia de objetos combinatorios con ciertas propiedades prescritas (para los cuales puede ser difícil encontrar ejemplos explícitos) al observar que la probabilidad de seleccionar al azar un objeto con esas propiedades es mayor que 0. Este enfoque (a menudo denominado como el método probabilístico) demostró ser muy eficaz en aplicaciones a la combinatoria extrema y la teoría de grafos. Un área estrechamente relacionada es el estudio de cadenas de Markov finitas, especialmente en objetos combinatorios. Aquí nuevamente se utilizan herramientas probabilísticas para estimar el tiempo de mezclado.
A menudo asociado con Paul Erdős, quien realizó el trabajo pionero en el tema, la combinatoria probabilística se consideraba tradicionalmente como un conjunto de herramientas para estudiar problemas en otras partes de la combinatoria. Sin embargo, con el crecimiento de las aplicaciones para analizar algoritmos en informática, así como la probabilidad clásica, la teoría de números aditivos y la teoría de números probabilísticos, el área creció recientemente hasta convertirse en un campo independiente de combinatoria.
Combinatoria algebraica
La combinatoria algebraica es un área de las matemáticas que emplea métodos de álgebra abstracta, especialmente la teoría de grupos y la teoría de representación, en varios contextos combinatorios y, a la inversa, aplica técnicas combinatorias a problemas de álgebra. La combinatoria algebraica ha llegado a verse más ampliamente como un área de las matemáticas donde la interacción de los métodos combinatorios y algebraicos es particularmente fuerte y significativa. Por lo tanto, los temas combinatorios pueden ser de naturaleza enumerativa o involucrar matroides, politopos, conjuntos parcialmente ordenados o geometrías finitas. En el lado algebraico, además de la teoría de grupos y representación, son comunes la teoría de celosías y el álgebra conmutativa.
Combinatoria en palabras
La combinatoria de palabras se ocupa de los lenguajes formales. Surgió de forma independiente dentro de varias ramas de las matemáticas, incluida la teoría de números, la teoría de grupos y la probabilidad. Tiene aplicaciones en combinatoria enumerativa, análisis fractal, informática teórica, teoría de autómatas y lingüística. Si bien muchas aplicaciones son nuevas, la jerarquía clásica de clases de gramáticas formales de Chomsky-Schützenberger es quizás el resultado más conocido en el campo.
Combinatoria geométrica
La combinatoria geométrica está relacionada con la geometría convexa y discreta. Pregunta, por ejemplo, cuántas caras de cada dimensión puede tener un politopo convexo. Las propiedades métricas de los politopos también juegan un papel importante, p. el teorema de Cauchy sobre la rigidez de los politopos convexos. También se consideran politopos especiales, como los permutoedros, los asociaedros y los politopos de Birkhoff. La geometría combinatoria es un nombre histórico para la geometría discreta.
Incluye una serie de 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. a la geometría computacional. El estudio de politopos regulares, sólidos de Arquímedes y números que se besan también forma parte de la combinatoria geométrica. También se consideran politopos especiales, como el permutoedro, el asociaedro y el politopo de Birkhoff.
Combinatoria topológica
Los análogos combinatorios de conceptos y métodos en topología se utilizan para estudiar la coloración de gráficos, la división justa, las particiones, los conjuntos parcialmente ordenados, los árboles de decisión, los problemas de collares y la teoría discreta de Morse. No debe confundirse con la topología combinatoria, que es un nombre más antiguo para la topología algebraica.
Combinatoria aritmética
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 trata de estimaciones combinatorias asociadas a operaciones aritméticas (suma, resta, multiplicación y división). La teoría de números aditivos (a veces también llamada combinatoria aditiva) se refiere al caso especial cuando solo están involucradas las operaciones de suma y resta. Una técnica importante en la combinatoria aritmética es la teoría ergódica de los sistemas dinámicos.
Combinatoria infinita
La combinatoria infinita, o teoría de conjuntos combinatoria, es una extensión de las ideas de la combinatoria a conjuntos infinitos. Es una 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 extrema. Algunas de las cosas estudiadas incluyen gráficos y árboles continuos, extensiones del teorema de Ramsey y el axioma de Martin. Los desarrollos recientes se refieren a la combinatoria del continuo y la combinatoria en sucesores de cardenales singulares.
Gian-Carlo Rota usó el nombre combinatoria continua para describir la probabilidad geométrica, ya que hay muchas analogías entre contar y medir.
Campos relacionados
Optimización combinatoria
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 de operaciones, la teoría de algoritmos y la teoría de la complejidad computacional.
Teoría de la codificación
La teoría de la codificación comenzó como parte de la teoría del diseño con las primeras construcciones combinatorias de códigos de corrección de errores. La idea principal de la asignatura es diseñar métodos eficientes y fiables de transmisión de datos. Ahora es un gran campo de estudio, parte de la teoría de la información.
Geometría discreta y computacional
La geometría discreta (también llamada geometría combinatoria) también comenzó como parte de la combinatoria, con resultados tempranos en politopos convexos y números que se besan. Con el surgimiento de las 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 separado. Quedan muchas conexiones con la combinatoria geométrica y topológica, que en sí mismas pueden verse como consecuencia de la geometría discreta temprana.
Combinatoria y sistemas dinámicos
Los aspectos combinatorios de los sistemas dinámicos es otro campo emergente. Aquí se pueden definir sistemas dinámicos sobre objetos combinatorios. Ver por ejemplo sistema dinámico gráfico.
Combinatoria y física
Cada vez hay más interacciones entre la combinatoria y la física, en particular la física estadística. Los 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ático y de Tutte, por el otro.