*banner
 

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.

Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright.

©2002-2018 Chess