O número de panelinhas em um gráfico: o resultado de Moon e Moser 1965

10

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!)n

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}
}
Josephine Moeller
fonte
11
você pode obter uma segunda página aqui: mendeley.com/research/on-cliques-in-graphs/# :)
Suresh Venkat
Argh! Maldito seja!
Josephine Moeller
8
Pegue o gráfico completo em nós e remova uma correspondência perfeita; existem cliques máximas. 2n2n
Jukka Suomela
12
O limite inferior apertado real é removendo um conjunto de triângulos disjuntos em vez de uma combinação perfeita. Dá cliques em vez de , um pouco mais. 3n/32n/2
David Eppstein
3
respostas por favor, não comentários.
precisa saber é o seguinte

Respostas:

17

nn>1 13n/343(n-4)/323(n-2)/3n

K2K3K3

vGGGvvGv

David Eppstein
fonte
Muito obrigado por escrever uma resposta muito detalhada.
Josephine Moeller
11
@ David Eppstein, você tem um resultado semelhante para o limite do número máximo de k-plexs (onde k-plex é semelhante a um clique, exceto pelo fato de que qualquer nó pode ser desconectado de no máximo k outros nós)
user844541
6

As respostas que foram dadas até agora são ótimas. Eu pensei em adicionar algumas referências.

  • O teorema de Moon-Moser foi provado independentemente por Miller e Muller [1960] em um relatório técnico.
  • Wood [2011] e Vatter [2011] fornecem provas mais simples do Teorema, usando basicamente a abordagem descrita por David.

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.

Serge Gaspers
fonte
11
Möller pediu Moon e Moser, você respondeu Miller e Muller, e um artigo da Mathematics Monthly. O que está acontecendo?
GD