Estou procurando o texto completo do resultado da camarilha de Moon and Moser de 1965, On Cliques in Graphs (existem gráficos com um número máximo de cliques exponenciais em ). O paywall da minha universidade não tem acesso ao diário específico. (De fato, a visualização fornece as primeiras frases da prova, mas depois me deixa sem o resto!)
Eu estava interessado neste resultado relacionado a uma direção de pesquisa que eu estava seguindo, mas a direção mudou um pouco, então é certo que meu interesse agora é uma curiosidade puramente acadêmica.
Minha pergunta é:
Existe um link para o texto completo do artigo em algum lugar OU outro artigo que esboça a prova OU se um esboço de prova é curto o suficiente para reproduzir aqui, alguém o conhece? Além disso, estou interessado na classe de gráficos com um número exponencial de panelinhas.
Eu adicionei o BibTeX para referência:
@article {springerlink:10.1007/BF02760024,
author = {Moon, J. and Moser, L.},
affiliation = {University of Alberta Edmonton Canada},
title = {On cliques in graphs},
journal = {Israel Journal of Mathematics},
publisher = {Hebrew University Magnes Press},
issn = {0021-2172},
keyword = {Computer Science},
pages = {23-28},
volume = {3},
issue = {1},
url = {http://dx.doi.org/10.1007/BF02760024},
note = {10.1007/BF02760024},
year = {1965}
}
fonte
Respostas:
fonte
Você também pode procurar o teorema de Moon-Moser no livro Algoritmos Exatos de Fomin-Kratsch
fonte
As respostas que foram dadas até agora são ótimas. Eu pensei em adicionar algumas referências.
Miller, RE e Muller, DE 1960. Um problema de subconjuntos máximos consistentes. Relatório de Pesquisa IBM RC-240, Centro de Pesquisa JT Watson, Yorktown Heights, NY.
Vatter, V. 2011. Máximo de conjuntos independentes e tampas de separação . American Mathematics Monthly 118, 418-423.
Wood, DR 2011. Sobre o número máximo de conjuntos independentes em um gráfico . CRR abs / 1104.1243.
fonte
Aqui está uma cópia do artigo de 1965 de Moon e Moser: http://users.monash.edu.au/~davidwo/MoonMoser65.pdf
Observe que o resultado foi realmente provado pela primeira vez em 1960 por Miller e Muller: http://users.monash.edu.au/~davidwo/MillerMuller-NumberMaximalCliques.pdf
fonte