Additional reading

Online papers and books


    Graph Theory

  1. B. Bollobas, Modern Graph Theory, Springer, 1999
  2. R. Diestel, Graph Theory, Springer, 3rd edition, 2005
    Electronic edition , 2005
  3. A. Brandst\"adt, V.B. Le and J.P. Spinrad, Graph classes: A survey, SIAM Monographs in Discrete mathematics and Applications, 1999

    Comment: These three books are our main sources for graph properties.

    Probabilistic Graph Theory

  4. J. Spencer, The strange logic of random graphs, Springer, 2001
  5. N. Alon and J. Spencer, The probabilistic method, 3rd edition, Wiley, 2008
  6. B. Bollobas, Random graphs, Academic Press, 1985


  7. P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009
    Book details , Book download
  8. H. Wilf, generatingfunctionology, A.K. Peters, 3rd edition, 2006
    Book details , Book download 2nd edition hyperlinked.
  9. F. Bergeron, G. Labelle and P. Leroux, Combinatorial species and tree-like structures, Encyclopedia of Mathematics and its applications, Cambridge University Press, 1998.
  10. G. Everest, A. van der Porten, I. Shparlinski and T. Ward, Recurrence Sequences, Mathematical Surveys and Monographs, vol. 104, AMS, 2003

    Papers for projects


  11. K. Compton, 1988 Survey
    Comment: Still best survey on Logics and 0-1 laws.
  12. P. Kolaitis and M. Vardi, 0-1 laws for fragments of Second Order Logic: A survey, 1992
    Comment: A more specific survey than Compton's.

    Monadic Second Order Logic

  13. M. Kaufmann's counter example
    Comment: MSOL has no 0-1 law (a simple proof)
  14. J. Tyszkiewicz, On asymptotic probabilities of Monadic Second Order properties, 1992
    Comment: More counter examples for Monadi Second Order Logic.

    Generalized quantifiers

  15. A. Dawar and E. Graedel, Generalized quantifiers and 0-1 laws,
    Comment: In search of other logics with 0-1 laws.
  16. P. Kolaitis and S. Kopparty, Random graphs and the parity quantifier, 2009
    Comment: A nice limit law for the parity quantifier.

    Pebble games and applications

    Comment: All these papers deal with finding formulas of minimal quantifier rank defining a structure up to isomorphism.

  17. O. Pikhurko, H. Veith and O. Verbitsky, The first order definability of graphs: Upper bounds for quantifier rank, Discrete Applied Mathematics, 2006
  18. O. Pikhurko and O. Verbitsky, Descriptive complexity of finite structures: Saving the quantifier rank, J. Symbolic Logic, 2005
  19. O. Pikhurko, J. Spencer and O. Verbitsky, Succint definitions in the first order theory of graphs, Annals Pure Appl. Logic, 2006
  20. J. Kim, O. Pikhurko, J. Spencer and O. Verbitsky, How complex are random graphs in First Order Logic? Arxiv preprint math/0401247, 2004
  21. O. Pikhurko and O. Verbitsky, Logical Complexity of Graphs: A Survey
    Preprint, March 2010