Sh:986

• Haber, S., & Shelah, S. Random graphs and Lindström quantifiers for natural graph properties. Preprint. arXiv: 1510.06574
• Abstract:
  We study zero-one laws for random graphs. We focus on the following question that was asked by many: Given a graph property P, is there a language of graphs able to express P while obeying the zero-one law? Our results show that there is a (regular) language able to express connectivity and k-colorability for any constant k and still obey the zero-one law. On the other hand we show that in any (semiregular) language strong enough to express Hamiltonicity one can interpret arithmetic and thus the zero-one law fails miserably. This answers a question of Blass and Harary.
• Version 2021-12-04_2 (26p)

@article{Sh:986,
 author = {Haber, Simi and Shelah, Saharon},
 title = {{Random graphs and Lindstr\"{o}m quantifiers for natural graph properties}},
 note = {\href{https://arxiv.org/abs/1510.06574}{arXiv: 1510.06574}},
 arxiv_number = {1510.06574}
}