Коллоквиум ФКН: Логика случайного графа: от законов нуля или единицы до приложений. Докладчик: Максим Жуковский, МФТИ

С 1960 года, после выхода основоположной статьи Эрдеша и Реньи, огромное количество работ было посвящено изучению свойств случайного графа. Значительная часть этих работ посвящена свойствам графов, описываемым на языке первого порядка и монадическом языке второго порядка. К таким свойствам можно отнести, например, свойство содержать треугольник, свойство содержать изолированную вершину и свойство связности.
В 2001 году свет увидела книга Дж. Спенсера "Strange logic of random graphs", содержащая обзор известных к тому моменту результатов о вероятностях свойств первого порядка случайного графа. Классический результат в этой области носит название закона нуля или единицы, который утверждает, что вероятность любого свойства первого порядка стремится либо к нулю, либо к единице. Разумеется, с 2001 года наука не стояла на месте — были получены новые результаты, касающиеся не только свойств первого порядка, но и монадических свойств. Более того, эти результаты нашли свое применение в задачах оценивания описательной сложности графовых свойств, решение которых, в свою очередь, позволяет находить новые алгоритмы проверки этих свойств. 

Афиша коллоквиума

Место и время:

25 апреля, 18.10 - 19.30.
Кочновский проезд 3, ауд. 205.

Заказать пропуск на проход в зданиеможно на computerscience@hse.ru