Аннотация:
A classical result of Glebskii et al. 1969 and indepently Fagin 1976 states that in the Erdos-Renyi model with edge-probability p=1/2 every graph property that can be expressed as a sentence in first order logic holds with probability tending to either zero or one.
A class of graphs is minor closed, if it is closed under the operations of removing edges and of "contracting" edges. (An example of a minor closed class of graphs is the class of all graphs that have a crossing-free drawing
on some fixed surface S.)
I will discuss a recent work, joint with P. Heinig, M. Noy and A.Taraz, on analogues of the classical result of Glebskii et al./Fagin for random graphs from a minor closed class (i.e. we sample a graph uniformly at random from all graphs on n vertices from some minor closed class).
The proofs build on the major progress that was made in recent years in the study of these random graph models.