Combinatoria - Combinatorics

La combinatoria es un área de las matemáticas que se ocupa principalmente de contar, como medio y como fin 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 , desde la biología evolutiva hasta la informática , etc.

El alcance total de la combinatoria no está aceptado universalmente. Según HJ Ryser , una definición del tema es difícil porque atraviesa muchas subdivisiones matemáticas. En la medida en que un área puede describirse por los tipos de problemas que aborda, la combinatoria está involucrada con:

  • la enumeración (recuento) 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, quizás de muchas maneras, y
  • optimización : encontrar la "mejor" estructura o solución entre varias posibilidades, ya sea la "más grande", la "más pequeña" o la satisfacción de algún otro criterio de optimización .

Leon Mirsky ha dicho: "La 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, 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 refieren principalmente a sistemas finitos, algunas preguntas y técnicas combinatorias pueden extenderse a un escenario infinito (específicamente, contable ) pero discreto .

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 muchas áreas de aplicación. Muchas preguntas combinatorias históricamente se han considerado de forma aislada, dando una solución ad hoc a un problema que surge en algún contexto matemático. A finales del siglo XX, sin embargo, se desarrollaron métodos teóricos generales y poderosos, que convirtieron 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 combinatoria .

Historia

Un ejemplo de cambio de timbre (con seis campanas), uno de los primeros resultados no triviales en la teoría de grafos .

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 sabores diferentes, tomados uno a la vez, dos a la vez, etc., calculando así las 2 6  - 1 posibilidades. El historiador griego Plutarco analiza una discusión entre Crisipo (siglo III a. C.) e Hiparco (siglo II a. C.) de un problema enumerativo bastante delicado, que más tarde se demostró que estaba relacionado con los números de Schröder-Hiparco . 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 , se continuó estudiando la combinatoria, 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 fórmulas pueden haber sido familiares para los matemáticos indios ya en el siglo VI EC. El filósofo y astrónomo rabino Abraham ibn Ezra (c. 1140) estableció la simetría de los coeficientes binomiales , mientras que el talmudista y matemático Levi ben Gerson (mejor conocido como Gersonides), en 1321, obtuvo una fórmula cerrada. 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 , 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 gozó 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 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 XX, la combinatoria 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 del álgebra a la probabilidad, del análisis funcional a la teoría de números , etc. Estas conexiones eliminan los límites entre la combinatoria y partes de las matemáticas y la informática teórica, pero en el Al mismo tiempo, condujo a una fragmentación parcial del campo.

Enfoques y subcampos de la combinatoria

Combinatoria enumerativa

Cinco árboles binarios en tres vértices , un ejemplo de números catalanes .

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 de combinatoria enumerativa. La forma de doce 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 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 particiones estudia varios problemas de enumeración y asintóticos relacionados con particiones enteras y está estrechamente relacionada con series q , funciones especiales y 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 en el análisis y la teoría analítica de números y tiene conexiones con la mecánica estadística .

Teoría de grafos

Los gráficos son objetos fundamentales en combinatoria. Consideraciones de la gama de la teoría de grafos de enumeración (por ejemplo, el número de gráficos en n vértices con k bordes) a las estructuras existentes (por ejemplo, ciclos de Hamilton) a representaciones algebraicas (por ejemplo, dada una gráfica G y dos números x y y , que hace el Tutte polinomio T G ( x , y ) ¿tiene 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 se utilizan generalmente 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 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 finitos simples . El área tiene más conexiones con la teoría de la 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 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 geometría discreta ( geometría combinatoria ).

Teoría del orden

Diagrama de Hasse del conjunto de potencias de {x, y, z} ordenado por inclusión .

La teoría de órdenes 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 los ejemplos de órdenes parciales incluyen celosías y álgebras booleanas .

Teoría matroide

La teoría matroide 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 sólo la estructura, sino también las propiedades enumerativas pertenecen a la teoría matroide. La teoría matroide 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 cuestiones extremas sobre sistemas de conjuntos . Los tipos de preguntas que se abordan en este caso se refieren al gráfico más grande posible que satisfaga determinadas propiedades. Por ejemplo, el gráfico sin triángulos más grande 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. Afirma que cualquier configuración suficientemente grande contendrá algún tipo de orden. Es una generalización avanzada del principio de 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 una gráfica aleatoria? 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), simplemente observando que la probabilidad de seleccionar aleatoriamente un objeto con esas propiedades es mayor que 0. Este enfoque ( a menudo referido como el método probabilístico ) demostrado ser muy eficaces en las aplicaciones a la combinatoria extremales 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 mezcla .

A menudo asociado con Paul Erdős , quien hizo el trabajo pionero sobre el tema, la combinatoria probabilística se veía tradicionalmente como un conjunto de herramientas para estudiar problemas en otras partes de la combinatoria. Sin embargo, con el crecimiento de aplicaciones para analizar algoritmos en ciencias de la computación , 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 para convertirse en un campo independiente de combinatoria.

Combinatoria algebraica

Diagrama joven de una partición (5,4,1).

La combinatoria algebraica es un área de las matemáticas que emplea métodos de álgebra abstracta , en particular la teoría de grupos y la teoría de la representación , en varios contextos combinatorios y, a la inversa, aplica técnicas combinatorias a problemas de álgebra . La combinatoria algebraica está expandiendo 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

Construcción de una palabra infinita Thue-Morse .

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

Un icosaedro .

La combinatoria geométrica está relacionada 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 también juegan un papel importante, por ejemplo, el teorema de Cauchy sobre la rigidez de los politopos convexos. Politopos especiales también se consideran, como permutohedra , associahedra y politopos Birkhoff . La geometría combinatoria es un nombre antiguo para la geometría discreta.

Combinatoria topológica

Partiendo un collar con dos cortes.

Los análogos combinatorios de conceptos y métodos en topología se utilizan para estudiar el color de los gráficos , la división justa , las particiones , los conjuntos parcialmente ordenados , los árboles de decisión , los problemas de collar y la teoría de Morse discreta . 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 con 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 sistemas dinámicos .

Combinatoria infinita

La combinatoria infinita, o teoría combinatoria de conjuntos, es una extensión de 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 existen muchas analogías entre contar y medir .

Campos relacionados

Las esferas de besos están conectadas tanto con la teoría de la codificación como con la geometría discreta .

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 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. 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í los sistemas dinámicos se pueden definir en objetos combinatorios. Consulte, por ejemplo, sistema dinámico de gráficos .

Combinatoria y física

Hay interacciones cada vez mayores 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.

Ver también

Notas

Referencias

enlaces externos