Random graphs and Lindstr\"{o}m quantifiers for natural graph properties
by Haber and Shelah. [HbSh:986]
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.
Back to the list of publications