Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

I'm looking for the full text of the Moon and Moser 1965 clique result On Cliques in Graphs (there exist graphs with a number of maximal cliques exponential in $n$). My university's paywall doesn't have access to the particular journal. (In fact, the preview provides the first few sentences of the proof, but then leaves me without the rest!)

I was interested in this result related to a research direction I was pursuing, but the direction has changed slightly, so admittedly my interest is now purely academic curiosity.

My question is:

Is there a link to the full text of the paper somewhere OR another paper that sketches the proof OR if a proof sketch is short enough to reproduce here, does anyone know it? Also, I'm interested in the class of graphs with an exponential number of cliques.

I added the BibTeX for reference:

@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}
}
share|improve this question
    
you can get a second page here: mendeley.com/research/on-cliques-in-graphs/# :) –  Suresh Venkat Sep 27 '11 at 22:50
    
Argh! Curse you! –  John Moeller Sep 27 '11 at 23:06
6  
Take the complete graph on $2n$ nodes and remove a perfect matching; there are $2^n$ maximal cliques. –  Jukka Suomela Sep 27 '11 at 23:06
9  
The actual tight lower bound is by removing a set of disjoint triangles instead of a perfect matching. It gives $3^{n/3}$ cliques rather than $2^{n/2}$, slightly more. –  David Eppstein Sep 27 '11 at 23:34
3  
answers please, not comments. –  Suresh Venkat Sep 28 '11 at 3:38
show 2 more comments

3 Answers

up vote 12 down vote accepted

I don't have a copy of Moon & Moser at hand, but: the maximum number of distinct maximal cliques in an $n$-node graph (with $n>1$) is $3^{n/3}$, $4\cdot 3^{(n-4)/3}$, or $2\cdot 3^{(n-2)/3}$, according to the value of $n$ mod 3. I think it's a little easier to see this in the complementary form of counting maximal independent sets.

The lower bound is what you're really asking for, and is mostly given already in the comments above: form a graph from the disjoint union of copies of $K_2$ and $K_3$, using as many copies of $K_3$ as possible. Each maximal independent set has exactly one node from each of these complete subgraphs from which the formula follows.

I seem to recall that the upper bound proof of Moon and Moser involved transforming a graph into the lower bound form (or the complementary form for maximal cliques), at each step not decreasing the number of independent sets or cliques. But there's a different way of proving it that leads to worst-case-optimal backtracking algorithms for listing all the cliques or independent sets (see e.g. my paper arXiv:cs/0011009), which I'll only sketch here because the details are a bit tedious. If there's a vertex $v$ of degree three or more in the given graph $G$, then each maximal independent set of $G$ is either a maximal independent set in $G\setminus v$ or it includes $v$ and is a maximal independent set of the graph formed from $G$ by removing $v$ and all of its neighbors. By induction (plugging in the formula for the number of independent sets in these two smaller graphs, with some case analysis mod 3) the bound follows. On the other hand, if no high degree vertex exists then the graph is a disjoint union of paths and cycles, in which one can calculate the number of independent sets directly.

share|improve this answer
    
Thank you very much for taking the time to write out a very detailed answer. –  John Moeller Sep 28 '11 at 5:27
    
@David Eppstein do you have a similar result for the bound on the number of maximal k-plexs (where k-plex is similar to a clique except from the fact the any node can be disconnected from at most k other nodes) –  user844541 Mar 3 at 9:24
add comment

You can also look for Moon-Moser theorem in Fomin-Kratsch Exact Algorithms book

share|improve this answer
add comment

The answers that have been given so far are great. I thought I'd add some references.

  • The Moon-Moser theorem was independently proved by Miller and Muller [1960] in a technical report.
  • Wood [2011] and Vatter [2011] give simpler proofs of the Theorem, using basically the approach outlined by David.

Miller, R. E. and Muller, D. E. 1960. A problem of maximum consistent subsets. IBM Research Report RC-240, J. T. Watson Research Center, Yorktown Heights, NY.

Vatter, V. 2011. Maximal independent sets and separating covers. American Mathematical Monthly 118, 418-423.

Wood, D. R. 2011. On the number of maximal independent sets in a graph. CoRR abs/1104.1243.

share|improve this answer
    
These are great, thanks very much. –  John Moeller Sep 29 '11 at 19:23
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.