Семинары
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Календарь
Поиск
Регистрация семинара

RSS
Ближайшие семинары




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


Logic and random graphs from minor closed classes

T. Muller

Количество просмотров:
Эта страница:196
Youtube Live:



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