Review lecture in frameworks of the workshop CCEGN-2017

Friday, 12 May 2017 Moscow Institute of Physics and Technology

Logic and random graphs from minor closed classes

A classical result of Glebskii et al. 1969 and independetly 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.