Combinatória

Combinatória é uma área da matemática preocupada principalmente com a contagem, tanto como um meio quanto como um fim na obtenção de resultados, e certas propriedades de estruturas finitas. Está intimamente relacionado com muitas outras áreas da matemática e tem muitas aplicações que vão desde a lógica à física estatística e da biologia evolutiva à ciência da computação.

A análise combinatória é conhecida pela amplitude dos problemas que aborda. Problemas combinatórios surgem em muitas áreas da matemática pura, notavelmente em álgebra, teoria da probabilidade, topologia e geometria, bem como em suas diversas áreas de aplicação. Muitas questões combinatórias têm sido historicamente consideradas isoladamente, dando uma solução ad hoc para um problema que surge em algum contexto matemático. No final do século XX, no entanto, métodos teóricos poderosos e gerais foram desenvolvidos, tornando a combinatória um ramo independente da matemática por si só. Uma das partes mais antigas e acessíveis da combinatória é a teoria dos grafos, que por si só possui inúmeras conexões naturais com outras áreas. A combinatória é usada frequentemente na ciência da computação para obter fórmulas e estimativas na análise de algoritmos.

Um matemático que estuda combinatória é chamado de combinatorialista.

Definição

O escopo completo da combinatória não é universalmente aceito. De acordo com H.J. Ryser, uma definição do assunto é difícil porque atravessa muitas subdivisões matemáticas. Na medida em que uma área pode ser descrita pelos tipos de problemas que aborda, a combinatória está envolvida com:

• o enumeração (contagem) de estruturas especificadas, por vezes referidas como arranjos ou configurações em um sentido muito geral, associadas a sistemas finitos,
• o existência de tais estruturas que satisfazem determinados critérios dados,
• o construção destas estruturas, talvez de muitas maneiras, e
• otimização: encontrar a "melhor" estrutura ou solução entre várias possibilidades, seja a "maior", "pequena" ou satisfazer alguns outros critério de otimização.

Leon Mirsky disse: "combinatória é uma gama de estudos interligados que têm algo em comum e ainda divergem amplamente em seus objetivos, métodos e grau de coerência que atingiram." Uma forma de definir combinatória é, talvez, descrever suas subdivisões com seus problemas e técnicas. Esta é a abordagem que é usada abaixo. No entanto, também existem razões puramente históricas para incluir ou não alguns tópicos sob o guarda-chuva da combinatória. Embora preocupados principalmente com sistemas finitos, algumas questões e técnicas combinatórias podem ser estendidas a um cenário infinito (especificamente, contável), mas discreto.

História

Um exemplo de mudança tocando (com seis sinos), um dos primeiros resultados não triviais na teoria dos grafos.

Conceitos combinatórios básicos e resultados enumerativos apareceram em todo o mundo antigo. No século 6 aC, o antigo médico indiano Sushruta afirma em Sushruta Samhita que 63 combinações podem ser feitas de 6 sabores diferentes, tomados um de cada vez, dois de cada vez, etc., calculando assim todos os 2⁶ − 1 possibilidades. O historiador grego Plutarco discute uma discussão entre Crisipo (século III aC) e Hiparco (século II aC) sobre um problema enumerativo bastante delicado, que mais tarde foi demonstrado estar relacionado aos números de Schröder-Hiparco. Anteriormente, no Ostomachion, Arquimedes (século III aC) pode ter considerado o número de configurações de um quebra-cabeça de azulejos, enquanto interesses combinatórios possivelmente estavam presentes em obras perdidas de Apolônio.

Na Idade Média, a combinatória continuou a ser estudada, em grande parte fora da civilização europeia. O matemático indiano Mahāvīra (c. 850) forneceu fórmulas para o número de permutações e combinações, e essas As fórmulas podem ter sido familiares aos matemáticos indianos já no século VI dC. O filósofo e astrônomo rabino Abraham ibn Ezra (c. 1140) estabeleceu a simetria dos coeficientes binomiais, enquanto uma fórmula fechada foi obtida posteriormente pelo talmudista e matemático Levi ben Gerson (mais conhecido como Gersonides), em 1321. O triângulo aritmético - um diagrama gráfico que mostra as relações entre os coeficientes binomiais - foi apresentado por matemáticos em tratados que datam do século 10 e acabaria por se tornar conhecido como o triângulo de Pascal. Mais tarde, na Inglaterra medieval, a campanologia forneceu exemplos do que hoje é conhecido como ciclos hamiltonianos em certos gráficos de Cayley em permutações.

Durante o Renascimento, juntamente com o resto da matemática e das ciências, a combinatória desfrutou de um renascimento. As obras de Pascal, Newton, Jacob Bernoulli e Euler tornaram-se fundamentais no campo emergente. Nos tempos modernos, as obras de J.J. Sylvester (final do século 19) e Percy MacMahon (início do século 20) ajudaram a estabelecer as bases para a combinatória enumerativa e algébrica. A teoria dos grafos também desfrutou de um aumento de interesse ao mesmo tempo, especialmente em conexão com o problema das quatro cores.

Na segunda metade do século 20, a combinatória teve um rápido crescimento, o que levou ao estabelecimento de dezenas de novos periódicos e conferências sobre o assunto. Em parte, o crescimento foi estimulado por novas conexões e aplicações em outros campos, variando da álgebra à probabilidade, da análise funcional à teoria dos números, etc. ao mesmo tempo levou a uma fragmentação parcial do campo.

Abordagens e subáreas da combinatória

Combinatória enumerativa

Cinco árvores binárias em três vértices, um exemplo de números catalães.

A combinatória enumerativa é a área mais clássica da combinatória e se concentra na contagem do número de certos objetos combinatórios. Embora contar o número de elementos em um conjunto seja um problema matemático bastante amplo, muitos dos problemas que surgem nas aplicações têm uma descrição combinatória relativamente simples. Os números de Fibonacci são o exemplo básico de um problema em combinatória enumerativa. A forma doze vezes fornece uma estrutura unificada para a contagem de permutações, combinações e partições.

Combinatória analítica

A combinatória analítica diz respeito à enumeração de estruturas combinatórias usando ferramentas de análise complexa e teoria da probabilidade. Em contraste com a combinatória enumerativa, que usa fórmulas combinatórias explícitas e funções geradoras para descrever os resultados, a combinatória analítica visa obter fórmulas assintóticas.

Teoria da partição

Uma partição de avião.

A teoria da partição estuda vários problemas de enumeração e assintóticos relacionados a partições inteiras e está intimamente relacionada a séries q, funções especiais e polinômios ortogonais. Originalmente uma parte da teoria e análise dos números, agora é considerada uma parte da combinatória ou um campo independente. Ele incorpora a abordagem bijetiva e várias ferramentas em análise e teoria analítica dos números e tem conexões com a mecânica estatística. As partições podem ser visualizadas graficamente com diagramas de Young ou diagramas de Ferrers. Eles ocorrem em vários ramos da matemática e da física, incluindo o estudo de polinômios simétricos e do grupo simétrico e na teoria de representação de grupo em geral.

Teoria dos gráficos

Petersen grafo.

Gráficos são objetos fundamentais em combinatória. As considerações da teoria dos grafos variam de enumeração (por exemplo, o número de gráficos em n vértices com k arestas) a estruturas existentes (por exemplo, ciclos hamiltonianos) a representações algébricas (por exemplo, dado um gráfico G e dois números x e y, faz o polinômio de Tutte T _G(x,y) tem uma interpretação combinatória?). Embora existam conexões muito fortes entre a teoria dos grafos e a combinatória, às vezes elas são consideradas disciplinas separadas. Embora os métodos combinatórios se apliquem a muitos problemas da teoria dos grafos, as duas disciplinas são geralmente usadas para buscar soluções para diferentes tipos de problemas.

Teoria do design

A teoria do design é um estudo de designs combinatórios, que são coleções de subconjuntos com certas propriedades de interseção. Projetos de bloco são projetos combinatórios de um tipo especial. Esta área é uma das partes mais antigas da combinatória, como no problema da colegial de Kirkman proposto em 1850. A solução do problema é um caso especial de um sistema de Steiner, cujos sistemas desempenham um papel importante na classificação de finitos grupos simples. A área tem mais conexões com a teoria de codificação e combinatória geométrica.

A teoria do design combinatório pode ser aplicada à área de design de experimentos. Parte da teoria básica dos projetos combinatórios se originou no trabalho do estatístico Ronald Fisher sobre o projeto de experimentos biológicos. Aplicações modernas também são encontradas em uma ampla gama de áreas, incluindo geometria finita, programação de torneios, loterias, química matemática, biologia matemática, projeto e análise de algoritmos, rede, teste de grupo e criptografia.

Geometria finita

A geometria finita é o estudo de sistemas geométricos com apenas um número finito de pontos. Estruturas análogas às encontradas em geometrias contínuas (plano euclidiano, espaço projetivo real, etc.) mas definidas combinatorialmente são os principais itens estudados. Esta área fornece uma rica fonte de exemplos para a teoria do design. Não deve ser confundido com geometria discreta (geometria combinatória).

Teoria da ordem

diagrama de Hasse do powerset de {x,y,z} ordenado pela inclusão.

A teoria da ordem é o estudo de conjuntos parcialmente ordenados, tanto finitos quanto infinitos. Ele fornece uma estrutura formal para descrever declarações como "isso é menor que isso" ou "isso precede aquilo". Vários exemplos de ordens parciais aparecem em álgebra, geometria, teoria dos números e em combinatória e teoria dos grafos. Classes notáveis e exemplos de ordens parciais incluem treliças e álgebras booleanas.

Teoria dos Matróides

A teoria Matróide abstrai parte da geometria. Estuda as propriedades de conjuntos (geralmente, conjuntos finitos) de vetores em um espaço vetorial que não dependem dos coeficientes particulares em uma relação de dependência linear. Não apenas a estrutura, mas também as propriedades enumerativas pertencem à teoria dos matróides. A teoria Matróide foi introduzida por Hassler Whitney e estudada como parte da teoria da ordem. Agora é um campo de estudo independente com várias conexões com outras partes da combinatória.

Combinatória extrema

A combinatória extrema estuda quão grande ou quão pequena uma coleção de objetos finitos (números, gráficos, vetores, conjuntos, etc.) pode ser, se tiver que satisfazer certas restrições. Grande parte da combinatória extrema diz respeito a classes de sistemas de conjuntos; isso é chamado de teoria dos conjuntos extremais. Por exemplo, em um conjunto de elementos n, qual é o maior número de subconjuntos de elementos k que podem se cruzar em pares? Qual é o maior número de subconjuntos dos quais nenhum contém nenhum outro? A última questão é respondida pelo teorema de Sperner, que deu origem a grande parte da teoria dos conjuntos extremais.

Os tipos de questões abordadas neste caso são sobre o maior grafo possível que satisfaça certas propriedades. Por exemplo, o maior grafo livre de triângulos em 2n vértices é um grafo bipartido completo K_n,n. Freqüentemente, é muito difícil até mesmo encontrar a resposta extrema f(n) exatamente e pode-se apenas fornecer uma estimativa assintótica.

A teoria de Ramsey é outra parte da combinatória extrema. Ele afirma que qualquer configuração suficientemente grande conterá algum tipo de ordem. É uma generalização avançada do princípio da casa dos pombos.

Combinatória probabilística

Caminhada auto-evitante em um gráfico de grade quadrado.

Na combinatória probabilística, as questões são do seguinte tipo: qual é a probabilidade de uma determinada propriedade para um objeto aleatório discreto, como um grafo aleatório? Por exemplo, qual é o número médio de triângulos em um grafo aleatório? Métodos probabilísticos também são usados para determinar a existência de objetos combinatórios com certas propriedades prescritas (para as quais exemplos explícitos podem ser difíceis de encontrar) observando que a probabilidade de selecionar aleatoriamente um objeto com essas propriedades é maior que 0. Esta abordagem (muitas vezes chamada como o método probabilístico) provou ser altamente eficaz em aplicações de combinatória extrema e teoria dos grafos. Uma área intimamente relacionada é o estudo de cadeias de Markov finitas, especialmente em objetos combinatórios. Aqui, novamente, ferramentas probabilísticas são usadas para estimar o tempo de mistura.

Muitas vezes associada a Paul Erdős, que fez o trabalho pioneiro sobre o assunto, a combinatória probabilística era tradicionalmente vista como um conjunto de ferramentas para estudar problemas em outras partes da combinatória. A área cresceu recentemente para se tornar um campo independente de combinatória.

Combinatória algébrica

Diagrama jovem de uma partição (5,4,1).

A combinatória algébrica é uma área da matemática que emprega métodos de álgebra abstrata, notadamente a teoria dos grupos e a teoria das representações, em vários contextos combinatórios e, inversamente, aplica técnicas combinatórias a problemas de álgebra. A combinatória algébrica passou a ser vista de forma mais ampla como uma área da matemática onde a interação dos métodos combinatórios e algébricos é particularmente forte e significativa. Assim, os tópicos combinatórios podem ser de natureza enumerativa ou envolver matróides, politopos, conjuntos parcialmente ordenados ou geometrias finitas. Do lado algébrico, além da teoria dos grupos e das representações, são comuns a teoria dos retículos e a álgebra comutativa.

Combinatória em palavras

Construção de uma palavra infinita Thue-Morse.

Combinatória em palavras lida com linguagens formais. Surgiu independentemente dentro de vários ramos da matemática, incluindo teoria dos números, teoria dos grupos e probabilidade. Tem aplicações em combinatória enumerativa, análise fractal, ciência da computação teórica, teoria de autômatos e lingüística. Embora muitas aplicações sejam novas, a hierarquia clássica de classes de gramáticas formais de Chomsky-Schützenberger é talvez o resultado mais conhecido no campo.

Combinatória geométrica

Um icosaedro.

A combinatória geométrica está relacionada com a geometria convexa e discreta. Ele pergunta, por exemplo, quantas faces de cada dimensão um politopo convexo pode ter. As propriedades métricas dos politopos também desempenham um papel importante, por ex. o teorema de Cauchy sobre a rigidez de politopos convexos. Também são considerados politopos especiais, como permutoedros, associahedras e politopos de Birkhoff. Geometria combinatória é um nome histórico para geometria discreta.

Inclui várias subáreas como a combinatória poliédrica (estudo das faces dos poliedros convexos), a geometria convexa (o estudo dos conjuntos convexos, em particular a combinatória das suas interseções) e a geometria discreta, que por sua vez tem muitas aplicações à geometria computacional. O estudo de polítopos regulares, sólidos arquimedianos e números que se beijam também faz parte da combinatória geométrica. Politopos especiais também são considerados, como o permutohedron, associahedron e o politopo de Birkhoff.

Combinatória topológica

Dividir um colar com dois cortes.

Análogos combinatórios de conceitos e métodos em topologia são usados para estudar coloração de grafos, divisão justa, partições, conjuntos parcialmente ordenados, árvores de decisão, problemas de colar e teoria discreta de Morse. Não deve ser confundida com topologia combinatória, que é um nome antigo para topologia algébrica.

Combinatória aritmética

A combinatória aritmética surgiu da interação entre a teoria dos números, combinatória, teoria ergódica e análise harmônica. Trata-se de estimativas combinatórias associadas a operações aritméticas (adição, subtração, multiplicação e divisão). A teoria aditiva dos números (às vezes também chamada de combinatória aditiva) refere-se ao caso especial em que apenas as operações de adição e subtração estão envolvidas. Uma técnica importante em combinatória aritmética é a teoria ergódica de sistemas dinâmicos.

Combinatória infinita

A combinatória infinita, ou teoria combinatória dos conjuntos, é uma extensão das ideias da combinatória para conjuntos infinitos. É uma parte da teoria dos conjuntos, uma área da lógica matemática, mas usa ferramentas e ideias tanto da teoria dos conjuntos quanto da combinatória extrema. Algumas das coisas estudadas incluem gráficos e árvores contínuas, extensões do teorema de Ramsey e o axioma de Martin. Desenvolvimentos recentes dizem respeito à combinatória do continuum e combinatória sobre sucessores de cardinais singulares.

Gian-Carlo Rota usou o nome combinatória contínua para descrever a probabilidade geométrica, uma vez que existem muitas analogias entre contar e medir.

Campos relacionados

As esferas beijantes estão ligadas à teoria da codificação e à geometria discreta.

Otimização combinatória

Otimização combinatória é o estudo da otimização em objetos discretos e combinatórios. Começou como parte da combinatória e da teoria dos grafos, mas agora é vista como um ramo da matemática aplicada e da ciência da computação, relacionada à pesquisa operacional, teoria dos algoritmos e teoria da complexidade computacional.

Teoria da codificação

A teoria da codificação começou como parte da teoria do design com as primeiras construções combinatórias de códigos de correção de erros. A ideia principal do assunto é projetar métodos eficientes e confiáveis de transmissão de dados. Agora é um grande campo de estudo, parte da teoria da informação.

Geometria discreta e computacional

A geometria discreta (também chamada de geometria combinatória) também começou como parte da combinatória, com resultados iniciais em politopos convexos e números que se beijam. Com o surgimento de aplicações de geometria discreta à geometria computacional, esses dois campos se fundiram parcialmente e se tornaram um campo de estudo separado. Restam muitas conexões com combinatória geométrica e topológica, que podem ser vistas como conseqüências da geometria discreta inicial.

Combinatória e sistemas dinâmicos

Aspectos combinatórios de sistemas dinâmicos é outro campo emergente. Aqui sistemas dinâmicos podem ser definidos em objetos combinatórios. Veja por exemplo sistema dinâmico gráfico.

Combinatória e física

Existem interações cada vez maiores entre a combinatória e a física, particularmente a física estatística. Os exemplos incluem uma solução exata do modelo de Ising e uma conexão entre o modelo de Potts, por um lado, e os polinômios cromáticos e de Tutte, por outro lado.