• 12 мая
  • Долгопрудный, Институтский переулок, 9, МФТИ, Корпус Прикладной Математики, Аудитория 115

Tobias Muller - Logic and random graphs from minor closed classes

Регистрация на событие закрыта

Извините, регистрация закрыта. Возможно, на событие уже зарегистрировалось слишком много человек, либо истек срок регистрации. Подробности Вы можете узнать у организаторов события.

Другие события организатора

Школа Прикладной Математики и Информатики МФТИ
16 дней назад
12 мая, начало в 18:30
Долгопрудный
Институтский переулок, 9, МФТИ, Корпус Прикладной Математики, Аудитория 115

Математический кружок школы прикладной математики и информатики МФТИ

Abstract

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.

Biography of a lecturer

Tobias Muller did his PhD at Oxford University in 2007 under Colin McDiarmid. After that he had temporary positions in Eindhoven, Tel Aviv and Amsterdam before taking up his current position in Utrecht. He works in combinatorics and probability with some emphasis on random graphs.

 

Регистрация

Рекомендуемые события

Организуете события? Обратите внимание на TimePad!

Профессиональная билетная система, статистика продаж 24/7, выгрузка списков участников, встроенные инструменты продвижения, личный кабинет для самостоятельного управления и еще много чего интересного.

Узнать больше