Coloração clara

Este artigo é um esboço sobre matemática .

Você pode compartilhar seu conhecimento, melhorando-o ( como? ) De acordo com as recomendações dos projetos correspondentes .

Em matemática , e em particular na teoria dos grafos , coloração justa é a operação de atribuir cores aos vértices de um gráfico não direcionado ( coloração do gráfico ), de modo que:

Em outras palavras, a distribuição dos vértices em cores diferentes deve ser o mais uniforme possível.

A solução óbvia para obter uma cor justa é fazer com que cada vértice tenha uma cor diferente. No entanto, essa solução usa muito mais cores do que o necessário. Na maioria das vezes, procuramos obter uma coloração justa ideal, minimizando o número de cores.

Exemplos

Estrela

O grafo estelar K 1.5 na figura ao lado é um grafo bipartido completo e, portanto, poderia ser colorido apenas com duas cores: uma para o centro e outra para a periferia. No entanto, uma cor se aplicaria apenas a um vértice enquanto a outra se aplicaria a cinco: a distribuição de cores não seria justa.

O menor número de cores em uma coloração clara deste gráfico é 4, conforme mostrado na figura: o vértice central é sempre o único de sua cor, e devemos, portanto, distribuir os cinco vértices restantes em pelo menos três cores diferentes em tais uma forma que nenhuma cor é representada por mais de dois vértices. De maneira mais geral, W. Meyer observa que são necessárias cores para colorir uma estrela K 1, n de maneira justa .

Biclique

Um fenômeno interessante aparece no grafo bipartido completo K n , n , com n ímpar. Este gráfico tem uma coloração justa de duas cores, assumindo uma cor para cada uma das duas partes. No entanto, ele não tem cores claras em n cores, embora se possa intuitivamente esperar que seja "mais fácil" por ter mais cores disponíveis.

Na verdade, qualquer partição justa dessas n cores afeta exatamente 2 vértices por cor. Não podemos colocar esses dois vértices em partes diferentes, pois isso formaria pares de vértices conectados e da mesma cor. Você não pode colocar apenas pares de vértices em cada parte, já que o número de vértices em cada parte é ímpar.

Teorema de Hajnal-Szemerédi

O grau máximo de um gráfico é o valor máximo dos graus de seus vértices.

O teorema de Brooks publicado em 1941 diz que um gráfico de grau máximo Δ Δ pode ser colorido com cores, com duas exceções ( gráficos completos e ciclos ímpares). No entanto, essa coloração geralmente é tudo menos clara.

Paul Erdős conjecturou em 1964 que o gráfico pode ser colorido de forma justa com apenas mais uma cor.

Esta conjectura foi provada por András Hajnal e Endre Szemerédi em 1970 e agora é chamada de teorema Hajnal-Szemerédi  :

Teorema  -  Qualquer gráfico de grau máximo Δ pode ser colorido igualmente com Δ + 1 cores.

Por exemplo, o grafo bipartido K 3, 3 apresentado acima, para o qual Δ = 3, pode ser colorido com 4 cores de forma equitativa.

A prova original de Hajnal e Szemerédi era longa e complicada, mas uma prova mais simples foi fornecida por Kierstead e Kostochka em 2008.

Muito trabalho foi realizado desde a publicação deste teorema, por um lado para torná-lo mais forte em termos do número de cores necessárias e, por outro lado, para generalizá-lo. Uma série de conjecturas permanecem abertas nesta área.

Formulários

Uma justificativa para o interesse em cores claras foi sugerida por W. Meyer em 1973. Diz respeito a questões de planejamento e programação . Nesse contexto, os vértices do gráfico representam um conjunto de tarefas a serem concluídas, e uma aresta conecta duas tarefas que não podem ser realizadas ao mesmo tempo. Uma coloração do gráfico representa uma divisão das tarefas em subconjuntos de tarefas que podem ser realizadas simultaneamente. O número de cores corresponde ao número de etapas de tempo necessárias para completar o todo. Para problemas de balanceamento de carga , é desejável executar um número igual (ou quase igual) de tarefas durante cada etapa. H. Furmańczyk, em um artigo de 2006, menciona uma aplicação particular deste tipo, onde se associa cursos em uma universidade com horários para distribuir os cursos nos diferentes horários de forma equitativa e para evitar pares de horários incompatíveis de aulas ao mesmo tempo.

O teorema de Hajnal-Szemerédi também foi usado para limitar a variância de somas de variáveis ​​aleatórias de dependência limitada. Se cada variável é maximamente dependente de outros Δ, a coloração justa do gráfico de dependência pode ser usada para dividir as variáveis ​​em subconjuntos independentes, dentro dos quais as desigualdades de Chernoff podem ser calculadas , resultando em uma limitação mais global. Estreita na variância do que se a distribuição tinha sido injusto.

Notas e referências

  1. (em) Walter Meyer , '  Fair colouring  " , Amer. Matemática. Monthly , Mathematical Association of America, vol.  80, n o  8,1973, p.  920-922 ( DOI  10.2307 / 2319405 , JSTOR  2319405 )
  2. (em) Paul Erdos , "Problem 9" in Mr. Fieldler, Theory of Graphs and its Applications , Praga, Czech Acad. Sci. Publ.,1964, p.  159
  3. (em) A. Hajnal e E. Szemerédi , "Prova de uma conjectura de P. Erdős" em Combinatorial Theory and Its Applications, II (Proc. Colloq., Balatonfüred, 1969) , North-Holland,1970( Math Reviews  0297607 ) , p.  601-623
  5. (em) Hanna Furmanczyk , '  Fair color of graph products  " , Opuscula Mathematica , vol.  26, n o  1,2006, p.  31–44 ( Resenhas de matemática  2272280 , ler online )
  6. (em) Sriram V. Pemmaraju , "Equitable colorings extend Chernoff Hoeffding-bounds" , em Proc. 12º ACM-SIAM Symp. Algoritmos Discretos (SODA 2001) ,2001( leia online ) , p.  924-925
  7. (em) Svante Janson  (em) e Andrzej Ruciński , "  The infamous upper tail  " , Random Structures & Algorithms , vol.  20, n o  3,2002, p.  317–342 ( DOI  10.1002 / rsa.10031 , Math Reviews  1900611 )
  8. Como é o caso nas suposições do lema local de Lovász .

Veja também

Fonte

Artigos relacionados

links externos