RUS  ENG
Полная версия
СЕМИНАРЫ

Математический кружок школы ПМИ МФТИ
12 мая 2017 г. 18:30, г. Долгопрудный, МФТИ, Новый Корпус, 239


Logic and random graphs from minor closed classes

T. Muller


https://www.youtube.com/watch?v=CZYJSr8YNT8

Аннотация: 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.


© МИАН, 2024