Число кликов на графике: результат Луны и Мозера 1965 года

10

Я ищу полный текст результата клики Луны и Мозера 1965 г. О кликах в графах (существуют графы с числом максимальных клик, экспоненциальным по ). Платежная система моего университета не имеет доступа к конкретному журналу. (На самом деле, предварительный просмотр предоставляет первые несколько предложений доказательства, но затем оставляет меня без остатка!)n

Меня заинтересовал этот результат, связанный с направлением исследований, которое я проводил, но направление изменилось незначительно, поэтому, по общему признанию, мой интерес теперь чисто академический интерес.

Мой вопрос:

Есть ли где-нибудь ссылка на полный текст статьи, ИЛИ другой документ, который рисует доказательство, ИЛИ, если эскиз доказательства достаточно короткий, чтобы воспроизвести его здесь, кто-нибудь знает это? Также меня интересует класс графов с экспоненциальным числом кликов.

Я добавил BibTeX для справки:

@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}
}
Жозефина Меллер
источник
1
Вы можете получить вторую страницу здесь: mendeley.com/research/on-cliques-in-graphs/# :)
Суреш Венкат
Argh! Проклинаю тебя!
Жозефина Меллер
8
Возьмите полный граф на узлах и удалите идеальное соответствие; есть 2 n максимальных кликов. 2n2n
Юкка Суомела
12
Фактическая жесткая нижняя граница заключается в удалении набора непересекающихся треугольников вместо идеального соответствия. Это дает клика, а не 2 н / 2 , немного больше. 3n/32n/2
Дэвид Эппштейн
3
Ответы пожалуйста, а не комментарии.
Суреш Венкат

Ответы:

17

nn>13n/343(n4)/323(n2)/3n

K2K3K3

vGGGvvGv

Дэвид Эппштейн
источник
Большое спасибо, что нашли время написать очень подробный ответ.
Жозефина Меллер
1
@ Дэвид Эппштейн, у вас есть аналогичный результат для ограничения числа максимальных k-сплетений (где k-plex похож на клику, за исключением того факта, что любой узел может быть отключен не более чем от k других узлов)
user844541
6

Ответы, которые были даны до сих пор, великолепны. Я думал, что добавлю несколько ссылок.

  • Теорема Луны-Мозера была независимо доказана Миллером и Мюллером [1960] в техническом отчете.
  • Вуд [2011] и Ваттер [2011] дают более простые доказательства теоремы, используя в основном подход, изложенный Дэвидом.

Миллер, RE и Мюллер, DE 1960. Проблема максимально согласованных подмножеств. Отчет об исследованиях IBM RC-240, Исследовательский центр им. Дж. Уотсона, Йорктаун-Хайтс, Нью-Йорк.

Vatter, V. 2011. Максимальные независимые множества и разделяющие покрытия . Американский математический ежемесячник 118, 418-423.

Вуд, Д.Р. 2011. О количестве максимальных независимых множеств в графе . CoRR abs / 1104.1243.

Серж Гасперс
источник
1
Мёллер попросил Луну и Мозера, вы ответили Миллеру и Мюллеру, а также часть из «Математического месяца». В чем дело?
Пол GD