13
$\begingroup$

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}
}
Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ you can get a second page here: mendeley.com/research/on-cliques-in-graphs/# :) $\endgroup$
    – Suresh Venkat
    Sep 27, 2011 at 22:50
  • 1
    $\begingroup$ Argh! Curse you! $\endgroup$
    – Josephine Moeller
    Sep 27, 2011 at 23:06
  • 9
    $\begingroup$ Take the complete graph on $2n$ nodes and remove a perfect matching; there are $2^n$ maximal cliques. $\endgroup$
    – Jukka Suomela
    Sep 27, 2011 at 23:06
  • 12
    $\begingroup$ 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. $\endgroup$
    – David Eppstein
    Sep 27, 2011 at 23:34
  • 3
    $\begingroup$ answers please, not comments. $\endgroup$
    – Suresh Venkat
    Sep 28, 2011 at 3:38

4 Answers 4

Reset to default
19
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you very much for taking the time to write out a very detailed answer. $\endgroup$
    – Josephine Moeller
    Sep 28, 2011 at 5:27
  • 1
    $\begingroup$ @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) $\endgroup$
    – user844541
    Mar 3, 2014 at 9:24
7
$\begingroup$

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

Improve this answer
$\endgroup$
7
$\begingroup$

Here is a copy of the 1965 paper by Moon and Moser: http://users.monash.edu.au/~davidwo/MoonMoser65.pdf

Note that the result was actually first proved in 1960 by Miller and Muller: http://users.monash.edu.au/~davidwo/MillerMuller-NumberMaximalCliques.pdf

Improve this answer
$\endgroup$
6
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Möller asked for Moon and Moser, you answered Miller and Muller, and a piece from Mathematical Monthly. What's going on? $\endgroup$
    – Pål GD
    Jul 25, 2017 at 16:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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