# 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.
• Current version: 2020-07-05_3 (35p)
Bib entry
@article{Sh:986,
author = {Haber, Simcha 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}
}