Combinatória - Combinatorics

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 . Ele está intimamente relacionado a muitas outras áreas da matemática e tem muitas aplicações que vão da lógica à física estatística , da biologia evolutiva à ciência da computação , etc.

O escopo completo da combinatória não é universalmente aceito. Segundo HJ 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:

  • a enumeração (contagem) de estruturas especificadas, às vezes referidas como arranjos ou configurações em um sentido muito geral, associadas a sistemas finitos,
  • a existência de tais estruturas que satisfaçam certos critérios dados,
  • a construção dessas estruturas, talvez de várias maneiras, e
  • otimização : encontrar a "melhor" estrutura ou solução entre várias possibilidades, seja a "maior", a "menor" ou a satisfação de algum outro critério de otimalidade .

Leon Mirsky disse: "combinatória é uma gama de estudos interligados que têm algo em comum, mas divergem amplamente em seus objetivos, seus métodos e o grau de coerência que alcançaram." Uma maneira de definir combinatória é, talvez, descrever suas subdivisões com seus problemas e técnicas. Essa é a abordagem usada a seguir. No entanto, também existem razões puramente históricas para incluir ou não alguns tópicos sob o guarda-chuva combinatória. Embora preocupada 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 .

A Combinatória é bem conhecida pela amplitude dos problemas que enfrenta. Problemas combinatórios surgem em muitas áreas da matemática pura , especialmente em álgebra , teoria da probabilidade , topologia e geometria , bem como em suas muitas áreas de aplicação. Muitas questões combinatórias têm sido historicamente consideradas isoladamente, fornecendo uma solução ad hoc para um problema que surge em algum contexto matemático. No final do século XX, entretanto, métodos teóricos poderosos e gerais foram desenvolvidos, tornando a combinatória um ramo independente da matemática por direito próprio. Uma das partes mais antigas e acessíveis da combinatória é a teoria dos grafos , que por si só tem inúmeras conexões naturais com outras áreas. A combinatória é frequentemente usada 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 .

História

Um exemplo de toque de mudança (com seis sinos), um dos primeiros resultados não triviais na teoria dos gráficos .

Conceitos combinatórios básicos e resultados enumerativos surgiram em todo o mundo antigo . No século 6 aC, o antigo médico indiano Sushruta afirma no Sushruta Samhita que 63 combinações podem ser feitas de 6 sabores diferentes, tomados um de cada vez, dois de cada vez, etc., computando assim todas as 2 6  - 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 se mostrou estar relacionado aos números de Schröder-Hiparco . Anteriormente, no Ostomaquião , Arquimedes (século III aC) pode ter considerado o número de configurações de um quebra-cabeça de ladrilhos , enquanto os 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 fórmulas podem ter sido familiares aos matemáticos indianos já no século 6 EC. 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 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 sobre permutações.

Durante o Renascimento , junto com o resto da matemática e das ciências , a combinatória teve um renascimento. Obras de Pascal , Newton , Jacob Bernoulli e Euler tornaram-se fundamentais no campo emergente. Nos tempos modernos, os trabalhos de JJ 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 teve uma explosão de interesse ao mesmo tempo, especialmente em relação ao 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 a outros campos, que vão da álgebra à probabilidade, da análise funcional à teoria dos números , etc. Essas conexões derrubam os limites entre a combinatória e partes da matemática e da ciência da computação teórica, mas no mesmo tempo levou a uma fragmentação parcial do campo.

Abordagens e subcampos da combinatória

Enumerative combinatorics

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 concentra-se 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 de combinatória enumerativa. A maneira doze vezes fornece uma estrutura unificada para contar 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

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 .

Teoria dos grafos

Os gráficos são objetos fundamentais em combinatória. Considerações de gama teoria gráfico de enumeração (por exemplo, o número de gráficos em n vértices com k bordas) para estruturas existentes (por exemplo, ciclos de Hamilton) a representação algébrica (por exemplo, dado um gráfico G e dois números x e y , faz o Tutte polinomial 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 são considerados assuntos separados. Embora os métodos combinatórios se apliquem a muitos problemas da teoria dos grafos, as duas disciplinas geralmente são usadas para buscar soluções para diferentes tipos de problemas.

Teoria do design

A teoria do projeto é um estudo de projetos combinatórios , que são coleções de subconjuntos com certas propriedades de interseção . Projetos de blocos são projetos combinatórios de um tipo especial. Essa área é uma das partes mais antigas da combinatória, como no problema das colegiais 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 grupos simples finitos . A área tem outras conexões com a teoria da codificação e combinatória geométrica.

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 conjunto de poderes de {x, y, z} ordenado por inclusão .

A teoria da ordem é o estudo de conjuntos parcialmente ordenados , tanto finitos quanto infinitos. Vários exemplos de ordens parciais aparecem na álgebra , geometria, teoria dos números e em toda a combinatória e teoria dos grafos. Classes notáveis ​​e exemplos de ordens parciais incluem reticulados e álgebras booleanas .

Teoria Matroid

A teoria da matroid abstrai parte da geometria . Ele 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 matróide. A teoria da matroid 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 extremal estuda questões extremas em sistemas de conjuntos . Os tipos de questões abordadas neste caso são sobre o maior gráfico 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 ) com exatidão e só se pode dar uma estimativa assintótica .

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

Combinatória probabilística

Na combinatória probabilística, as questões são do seguinte tipo: qual é a probabilidade de uma determinada propriedade para um objeto discreto aleatório, como um gráfico aleatório ? Por exemplo, qual é o número médio de triângulos em um gráfico 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 os quais exemplos explícitos podem ser difíceis de encontrar), simplesmente observando que a probabilidade de selecionar aleatoriamente um objeto com essas propriedades é maior que 0. Esta abordagem ( frequentemente referido como o método probabilístico ) provou ser altamente eficaz em aplicações de combinatória extrema e teoria de 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 .

Freqüentemente associada a Paul Erdős , que fez o trabalho pioneiro no assunto, a combinatória probabilística era tradicionalmente vista como um conjunto de ferramentas para estudar problemas em outras partes da combinatória. No entanto, com o crescimento de aplicativos para analisar algoritmos em ciência da computação , bem como probabilidade clássica, teoria dos números aditivos e teoria dos números probabilísticos , a área cresceu recentemente para se tornar um campo independente da combinatória.

Combinatória algébrica

Diagrama de 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 da representação , em vários contextos combinatórios e, inversamente, aplica técnicas combinatórias a problemas de álgebra . A combinatória algébrica está continuamente expandindo seu escopo, tanto em tópicos quanto em técnicas, e pode ser vista como a área da matemática onde a interação de métodos combinatórios e algébricos é particularmente forte e significativa.

Combinatória de palavras

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

Combinatorics on words lida com linguagens formais . Ele surgiu de forma independente em vários ramos da matemática, incluindo a teoria dos números , teoria dos grupos e probabilidade . Ele tem aplicações para combinatória enumerativa, análise fractal , ciência da computação teórica , teoria de autômatos e linguística . Embora muitas aplicações sejam novas, a clássica hierarquia de classes de gramáticas formais de Chomsky – Schützenberger é talvez o resultado mais conhecido na área.

Combinatória geométrica

Um icosaedro .

A combinatória geométrica está relacionada à geometria convexa e discreta , em particular à combinatória poliédrica . 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 exemplo, o teorema de Cauchy sobre a rigidez dos politopos convexos. Polopos especiais também são considerados, como permutohedra , associahedra e politopos de Birkhoff . Geometria combinatória é um nome antiquado para geometria discreta.

Combinação topológica

Dividindo um colar com dois cortes.

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

Aritmética combinatória

A combinatória aritmética surgiu da interação entre a teoria dos números , a combinatória, a teoria ergódica e a 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 dos números aditivos (à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 na aritmética combinatória é a teoria ergódica dos sistemas dinâmicos .

Combinação infinita

A combinatória infinita, ou teoria dos conjuntos combinatórios, é uma extensão das idéias da combinatória a conjuntos infinitos. É uma parte da teoria dos conjuntos , uma área da lógica matemática , mas usa ferramentas e ideias da teoria dos conjuntos e combinatória extrema.

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

Otimização combinatória

Otimização combinatória é o estudo da otimização em objetos discretos e combinatórios. Começou como parte da teoria combinatória e dos grafos, mas agora é vista como um ramo da matemática aplicada e da ciência da computação, relacionada à pesquisa operacional , teoria de 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 de beijo . Com o surgimento de aplicações de geometria discreta para geometria computacional , esses dois campos se fundiram parcialmente e se tornaram um campo de estudo separado. Restam muitas conexões com combinatórias geométricas e topológicas, que podem ser vistas como conseqüências da geometria discreta inicial.

Sistemas combinatórios e dinâmicos

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

Combinatória e física

Existem interações crescentes 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.

Veja também

Notas

Referências

links externos