|
СЕМИНАРЫ |
|
Logic and random graphs from minor closed classes T. Muller |
|||
Аннотация: 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. |