Combinatoria
Definición
Combinatoria es un área de las matemáticas principalmente relacionada con el conteo, como un medio y un fin en la obtención de 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 a la física estadística, desde la biología evolutiva a la informática, etc.
Para comprender completamente el alcance de la combinatoria se requiere una gran cantidad de amplificación adicional, cuyos detalles no se acuerdan universalmente. Según HJ Ryser, una definición del tema es difícil porque cruza tantas subdivisiones matemáticas. En la medida en que un área se puede describir por los tipos de problemas que aborda, la combinatoria está involucrada con
- la enumeración (conteo) de estructuras específicas, a veces denominadas disposiciones o configuraciones en un sentido muy general, asociadas con sistemas finitos,
- la existencia de tales estructuras que satisfacen ciertos criterios dados,
- la construcción de estas estructuras, tal vez de muchas maneras, y
- optimización , encontrando la "mejor" estructura o solución entre varias posibilidades, ya sea la "más grande", la "más pequeña" o que satisfaga algún otro criterio de optimalidad.
Leon Mirsky ha dicho: "combinatoria es una gama de estudios vinculados 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, tal vez, describir sus subdivisiones con sus problemas y técnicas. Este es el enfoque que se utiliza a continuación. Sin embargo, también hay razones puramente históricas para incluir o no algunos temas bajo el paraguas combinatorio. Aunque se ocupa principalmente de sistemas finitos, algunas preguntas y técnicas combinatorias se pueden extender a un entorno infinito (específicamente contable) pero discreto.
Combinatoria es bien conocido por la amplitud de los problemas que aborda. Los problemas combinatorios surgen en muchas áreas de las matemáticas puras, especialmente en el álgebra, la teoría de la probabilidad, la topología y la geometría, así como en sus muchas áreas de aplicación. Muchas preguntas combinatorias se han considerado históricamente de forma aislada, dando un ad hoc solución a un problema que surge en un contexto matemático. Sin embargo, a fines 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. Combinatorics se utiliza con frecuencia en ciencias de la computación para obtener fórmulas y estimaciones en el análisis de algoritmos.
Un matemático que estudia combinatoria se llama combinatoria .
Historia
Los conceptos combinatorios básicos y los resultados enumerativos aparecieron en todo el mundo antiguo. En el siglo VI AEC, el médico indio Sushruta afirma en Sushruta Samhita que se pueden hacer 63 combinaciones de 6 sabores diferentes, tomadas de a una por vez, de dos en dos, etc., calculando así las 2 - 1 posibilidades. Greekhistorian Plutarch discute una discusión entre Crisipo (siglo III aC) e Hiparco (siglo II aC) de un problema enumerativo bastante delicado, que más tarde se demostró que estaba relacionado con los números de Schröder-Hipparchus. En la Ostomachion , Arquímedes (siglo III aC) considera un rompecabezas de mosaico.
En la Edad Media, la combinatoria continuó siendo estudiada, en gran medida 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 fórmulas pueden haber sido familiares para los matemáticos indios ya en el siglo sexto CE. El filósofo y astrónomo Rabino Abraham ibn Ezra (hacia 1140) estableció la simetría de los coeficientes binomiales, mientras que el talmudista y matemático Levi ben Gerson (más conocido como Gersonides) obtuvo una fórmula cerrada en 1321. El triángulo aritmético el diagrama gráfico que muestra las relaciones entre los coeficientes binomiales- fue presentado por los 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,
Durante el Renacimiento, junto con el resto de las matemáticas y las ciencias, los combinatorios disfrutaron de un renacimiento. Las obras de Pascal, Newton, Jacob Bernoulli y Euler se volvieron fundamentales en el campo emergente. En los tiempos modernos, las obras de JJ 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 una explosión de interés al mismo tiempo, especialmente en relación con el problema de los cuatro colores.
En la segunda mitad del siglo 20, combinatorics disfrutó de un rápido crecimiento, lo que llevó al establecimiento de decenas de nuevas revistas y conferencias en el tema. En parte, el crecimiento fue estimulado por nuevas conexiones y aplicaciones a otros campos, que van desde álgebra a probabilidad, desde análisis funcional a teoría de números, etc. Estas conexiones arrojan los límites entre la combinatoria y partes de las matemáticas y la informática teórica, pero a la mismo tiempo llevó a una fragmentación parcial del campo.
Enfoques y subcampos de combinatoria
Combinatoria enumerativa
La combinatoria enumerativa es el área más clásica de 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 la combinatoria enumerativa. La forma doce veces proporciona un marco unificado para contar permutaciones, combinaciones y particiones.
Combinatoria analítica
La combinatoria analítica se refiere a la enumeración de estructuras combinatorias que utilizan 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 busca obtener fórmulas asintóticas.
Teoría de partición
La teoría de partición estudia diversas enumeraciones y problemas asintóticos relacionados con particiones enteras, y está estrechamente relacionada con la serie q, las funciones especiales y los polinomios ortogonales. Originalmente una parte de la teoría de números y el análisis, ahora se considera una parte de la combinatoria o un campo independiente. Incorpora el enfoque biyectivo y varias herramientas en análisis y teoría de números analíticos, y tiene conexiones con la mecánica estadística.
Teoría de grafos
Los gráficos son objetos básicos en combinatoria. Las preguntas van desde el recuento (por ejemplo, el número de gráficos en n vértices con k bordes) a estructural (por ejemplo, qué gráficos contienen ciclos de Hamilton) a preguntas algebraicas (por ejemplo, dado un gráfico G y dos números x e y , el Tutte polinomial T G ( x , y) tienen una interpretación combinatoria?). Aunque existen conexiones muy sólidas entre la teoría de grafos y la combinatoria, estas dos se consideran a veces como temas separados. Esto se debe al hecho de que, aunque los métodos combinatorios se aplican a muchos problemas de teoría de grafos, generalmente se utilizan para buscar soluciones a problemas diferentes. .
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 combinatoria, como en el problema de colegiala de Kirkman propuesto en 1850. La solución del problema es un caso especial de un sistema Steiner, cuyos sistemas juegan un papel importante en la clasificación de grupos simples finitos. El área tiene conexiones adicionales con la teoría de codificación y la combinatoria geométrica.
Geometría finita
La geometría finita es el estudio de sistemas geométricos que tienen solo un número finito de puntos. Las estructuras análogas a las encontradas en 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 pedido
La teoría del orden es el estudio de conjuntos parcialmente ordenados, tanto finitos como infinitos. Varios ejemplos de órdenes parciales aparecen en álgebra, geometría, teoría de números y en combinatoria y teoría de grafos. Las clases notables y ejemplos de órdenes parciales incluyen celosías y álgebras de Boole.
Teoría de Matroid
La teoría de Matroid abstrae parte de la geometría. Estudia las propiedades de los 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 Matroid fue introducida por Hassler Whitney y estudiada como parte de la teoría del orden. Ahora es un campo de estudio independiente con una serie de conexiones con otras partes de la combinatoria.
Combinatoria extrema
La combinatoria extrema estudia las preguntas extremas sobre los sistemas establecidos. Los tipos de preguntas abordadas en este caso se refieren al gráfico más grande posible que satisface ciertas propiedades. Por ejemplo, el gráfico más grande sin triángulos en 2n vértices es un gráfico bipartito completo K n, 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 la combinatoria probabilística, las preguntas son del siguiente tipo: ¿cuál es la probabilidad de una determinada propiedad para un objeto discreto al azar, 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 los ejemplos explícitos pueden ser difíciles de encontrar), simplemente al observar que la probabilidad de seleccionar aleatoriamente un objeto con esas propiedades es mayor que 0. Este enfoque ( a menudo conocido como el método probabilístico) demostró ser altamente efectivo en aplicaciones a combinatoria extrema y teoría de grafos. Un área estrechamente relacionada es el estudio de cadenas finitas de Markov, especialmente en objetos combinatorios. Aquí nuevamente se usan herramientas probabilísticas para estimar el tiempo de mezcla.
A menudo asociado con Paul Erdős, quien hizo el trabajo pionero sobre 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 el análisis de algoritmos en ciencias de la computación, así como también la probabilidad clásica, la teoría de números probabilística y aditiva, el área creció recientemente para 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 la representación, en diversos contextos combinatorios y, a la inversa, aplica técnicas combinatorias a los problemas del álgebra. La combinatoria algebraica expande continuamente su alcance, tanto en temas como en técnicas, y puede verse como el área de las matemáticas donde la interacción de los métodos combinatorios y algebraicos es particularmente fuerte y significativa.
Combinatoria en palabras
Combinatorics en palabras trata con 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 para 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 Chomsky-Schützenberger de clases de gramáticas formales es quizás el resultado más conocido en el campo.
Combinatoria geométrica
La combinatoria geométrica se relaciona con la geometría convexa y discreta, en particular la combinatoria poliédrica. Pregunta, por ejemplo, cuántas caras de cada dimensión puede tener un politopo convexo. Las propiedades métricas de los politopos desempeñan un papel importante también, por ejemplo, el teorema de Cauchy sobre la rigidez de los politopos convexos. También se consideran politopos especiales, como permutohedra, associahedra y politopes de Birkhoff. Deberíamos notar que la geometría combinatoria es un nombre antiguo para la geometría discreta.
Combinatoria topológica
Los análogos combinatorios de conceptos y métodos en topología se usan para estudiar el coloreado gráfico, la división justa, las particiones, los conjuntos parcialmente ordenados, los árboles de decisión, los problemas de collar y la teoría Morse discreta. No se debe confundir 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 teoría de números, combinatoria, teoría ergódica y análisis armónico. Se trata de estimaciones combinatorias asociadas con operaciones aritméticas (suma, resta, multiplicación y división). La teoría del número aditivo (a veces también llamada combinatoria aditiva) se refiere al caso especial cuando solo se trata de 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 en combinatoria a conjuntos infinitos. Es 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.
Gian-Carlo Rota usó el nombre de 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 ve como 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 codificación
La teoría de codificación comenzó como una parte de la teoría del diseño con construcciones combinatorias tempranas de códigos de corrección de errores. La idea principal del tema es diseñar métodos eficientes y confiables 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 una parte de la combinatoria, con resultados tempranos en politopes convexos y números de besos. Con la aparición de aplicaciones de geometría discreta a la geometría computacional, estos dos campos se fusionaron parcialmente y se convirtieron en un campo de estudio separado. Siguen existiendo muchas conexiones con la combinatoria geométrica y topológica, que a su vez pueden considerarse como una consecuencia de la geometría discreta inicial.
Combinatorics y sistemas dinámicos
Los aspectos combinatorios de los sistemas dinámicos es otro campo emergente. Aquí los sistemas dinámicos se pueden definir en objetos combinatorios. Ver por ejemplo el sistema dinámico de gráficos.
Combinatoria y física
Hay interacciones crecientes entre la combinatoria y la física, particularmente 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áticos y de Tutte por el otro.