Liczba klików na wykresie: wynik Księżyca i Mosera 1965

10

Szukam pełnego tekstu wyniku kliknięcia Księżyca i Mosera z 1965 r. O klikach na wykresach (istnieją wykresy z liczbą maksymalnych wykładniczych klik w ). Zapora mojego uniwersytetu nie ma dostępu do konkretnego czasopisma. (W rzeczywistości podgląd zawiera kilka pierwszych zdań dowodu, ale potem pozostawia mnie bez reszty!) $n$

Byłem zainteresowany tym wynikiem związanym z kierunkiem badań, którym podążałem, ale kierunek ten nieznacznie się zmienił, więc moje zainteresowanie jest teraz czysto akademicką ciekawością.

Moje pytanie brzmi:

Czy jest gdzieś link do pełnego tekstu artykułu LUB inny papier, który szkicuje dowód LUB LUB, jeśli szkic jest wystarczająco krótki, aby go odtworzyć tutaj, czy ktoś to wie? Interesuje mnie również klasa grafów z wykładniczą liczbą klików.

Dodałem BibTeX w celach informacyjnych:

@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
źródło

1

możesz dostać drugą stronę tutaj: mendeley.com/research/on-cliques-in-graphs/# :)

— Suresh Venkat

Argh! Przeklnij cię!

— Josephine Moeller

8

Zrób pełny wykres na węzłach i usuń idealne dopasowanie; istnieją maksymalne kliky.

2 n

$2n$

2^{n}

$2^n$

— Jukka Suomela

12

Rzeczywista ścisła dolna granica polega na usunięciu zestawu rozłącznych trójkątów zamiast idealnego dopasowania. Daje kliknięć zamiast , nieco więcej.

3^{n / 3}

$3^{n/3}$

2^{n / 2}

$2^{n/2}$

— David Eppstein,

3

proszę odpowiedzi, a nie komentarze.

— Suresh Venkat

17

Nie mam pod ręką kopii Moon & Moser, ale: maksymalna liczba wyraźnych maksymalnych klików na wykresie węzłowym (przy ) wynosi , lub , zgodnie z wartością mod 3. Myślę, że trochę łatwiej jest zobaczyć to w uzupełniającej się formie liczenia maksimum niezależne zestawy. $n$ $n>1$ $3^{n/3}$ $4\cdot 3^{(n-4)/3}$ $2\cdot 3^{(n-2)/3}$ $n$

Dolna granica wynosi co tak naprawdę prośbą o, i jest najczęściej podane już w komentarzach powyżej: tworzą wykres z Unii rozłącznych kopii i , używając tyle kopii jak to możliwe. Każdy maksymalny niezależny zestaw ma dokładnie jeden węzeł z każdego z tych pełnych wykresów podrzędnych, z których wynika formuła. $K_2$ $K_3$ $K_3$

Wydaje mi się, że górna granica dowodu Księżyca i Mosera polegała na przekształceniu wykresu w formę dolnej granicy (lub formę komplementarną dla maksymalnych klików), na każdym kroku nie zmniejszając liczby niezależnych zbiorów lub klik. Ale istnieje inny sposób udowodnienia tego, który prowadzi do algorytmów cofania optymalnych w najgorszym przypadku, umożliwiających wyświetlanie wszystkich klików lub niezależnych zestawów (patrz np. Mój artykuł arXiv: cs / 0011009 ), który tutaj naszkicuję tylko dlatego, że szczegóły są trochę nudne. Jeśli na danym wykresie znajduje się wierzchołek stopnia trzeciego lub więcej , wówczas każdy maksymalny niezależny zbiór jest albo maksymalnym niezależnym zbiorem w albo zawiera $v$ $G$ $G$ $G\setminus v$ $v$ i jest maksymalnym niezależnym zestawem wykresu utworzonego z przez usunięcie i wszystkich jego sąsiadów. Przez indukcję (wprowadzenie wzoru na liczbę niezależnych zestawów na tych dwóch mniejszych wykresach, z niektórymi modami analizy przypadków 3) następuje granica. Z drugiej strony, jeśli nie istnieje wierzchołek wysokiego stopnia, wówczas wykres jest rozłącznym połączeniem ścieżek i cykli, w którym można bezpośrednio obliczyć liczbę niezależnych zbiorów. $G$ $v$

— David Eppstein
źródło

Dziękuję bardzo za poświęcenie czasu na napisanie bardzo szczegółowej odpowiedzi.

— Josephine Moeller

1

@David Eppstein, czy masz podobny wynik dla ograniczenia maksymalnej liczby k-pleksów (gdzie k-plex jest podobny do kliki, z wyjątkiem tego, że dowolny węzeł można odłączyć co najwyżej k innych węzłów)

— user844541

7

Możesz także poszukać twierdzenia Moon-Moser w książce Fomin-Kratsch Exact Al Algorytmy

— wirować
źródło

6

Odpowiedzi, które zostały podane do tej pory, są świetne. Myślałem, że dodam kilka referencji.

Twierdzenie Księżyca-Mosera zostało niezależnie udowodnione przez Millera i Mullera [1960] w raporcie technicznym.
Wood [2011] i Vatter [2011] podają prostsze dowody twierdzenia, stosując zasadniczo podejście nakreślone przez Davida.

Miller, RE i Muller, DE 1960. Problem maksymalnych spójnych podzbiorów. Raport badawczy IBM RC-240, JT Watson Research Center, Yorktown Heights, NY.

Vatter, V. 2011. Maksymalne niezależne zestawy i pokrywy rozdzielające . American Mathematical Monthly 118, 418-423.

Wood, DR 2011. O liczbie maksymalnych niezależnych zestawów na wykresie . CoRR abs / 1104.1243.

— Serge Gaspers
źródło

1

Möller poprosił o Moon i Mosera, odpowiedziałeś Millerowi i Mullerowi, a także kawałek z Mathematical Monthly. Co się dzieje?

— Pål GD

4

Oto kopia artykułu z 1965 r. Autorstwa Moon and Moser: http://users.monash.edu.au/~davidwo/MoonMoser65.pdf

Zauważ, że wynik został po raz pierwszy udowodniony w 1960 roku przez Millera i Mullera: http://users.monash.edu.au/~davidwo/MillerMuller-NumberMaximalCliques.pdf

— użytkownik26635
źródło