A Jump to the Bell Number for Hereditary Graph Properties
J. Balogh, B. Bollobas, D. Weinreich

Citation
J. Balogh, B. Bollobas, D. Weinreich. "A Jump to the Bell Number for Hereditary Graph Properties". Journal of Combinatorial Theory B, 95:29-48, 2005.

Abstract
In the last decade and a half it was discovered that even very general graph properties undergo phase transitions: the number of graphs `jumps' at certain places. To be more specific, a hereditary property of graphs is an infinite class P of isomorphism classes of graphs closed under the deletion of vertices. Writing P(n) for the set of graphs in P with vertex set 1, 2, ... , n, and f(n) for the number of graphs in P(n), the question is the behavior of this function f(n). Several such jumps have been proved, and the present paper shows that there is a jump in a hitherto unexpected range: we show that the jump from speeds somewhat below the nth power of n to the penultimate range is in fact clean, and provide a sharp lower bound for hereditary properties in this range. It turns out that the jump is up to the nth Bell number, the number of partitions of a set with n distinguishable elements.

Electronic downloads

(No downloads are available for this publication.)

Citation formats

• HTML

  J. Balogh, B. Bollobas, D. Weinreich. <a
  href="http://chess.eecs.berkeley.edu/pubs/763.html"
  >A Jump to the Bell Number for Hereditary Graph
  Properties</a>, <i>Journal of Combinatorial
  Theory B</i>, 95:29-48,  2005.

• Plain text

  J. Balogh, B. Bollobas, D. Weinreich. "A Jump to the
  Bell Number for Hereditary Graph Properties".
  <i>Journal of Combinatorial Theory B</i>,
  95:29-48,  2005.

• BibTeX

  @article{BaloghBollobasWeinreich05_JumpToBellNumberForHereditaryGraphProperties,
      author = {J. Balogh and B. Bollobas and D. Weinreich},
      title = {A Jump to the Bell Number for Hereditary Graph
                Properties},
      journal = {Journal of Combinatorial Theory B},
      volume = {95},
      pages = {29-48},
      year = {2005},
      abstract = { In the last decade and a half it was discovered
                that even very general graph properties undergo
                phase transitions: the number of graphs `jumps' at
                certain places. To be more specific, a hereditary
                property of graphs is an infinite class P of
                isomorphism classes of graphs closed under the
                deletion of vertices. Writing P(n) for the set of
                graphs in P with vertex set 1, 2, ... , n, and
                f(n) for the number of graphs in P(n), the
                question is the behavior of this function f(n).
                Several such jumps have been proved, and the
                present paper shows that there is a jump in a
                hitherto unexpected range: we show that the jump
                from speeds somewhat below the nth power of n to
                the penultimate range is in fact clean, and
                provide a sharp lower bound for hereditary
                properties in this range. It turns out that the
                jump is up to the nth Bell number, the number of
                partitions of a set with n distinguishable
                elements.},
      URL = {http://chess.eecs.berkeley.edu/pubs/763.html}
  }
  

Posted by Christopher Brooks on 4 Nov 2010.
For additional information, see the Publications FAQ or contact webmaster at chess eecs berkeley edu.