Законы нуля или единицы для случайных графов

Speaker: 
Максим Жуковский (Яндекс)
Date: 
Monday, November 24, 2014 - 18:00
Place: 
ПОМИ, аудитория 106
Abstract: 

В докладе речь пойдет об асимпотическом поведении свойств первого порядка случайного графа Эрдеша-Реньи G(n,p). В 1988 году Дж. Спенсер и С. Шела доказали, что если p=n^{-a}, a - положительное иррациональное число, то для любого свойства первого порядка с вероятностью, стремящейся к 1, случайный граф либо обладает этим свойством, либо нет (иными словами, выполнен закон нуля или единицы). Если же a из интервала (0,1) - рациональное число, то закон нуля или единицы не выполнен. Позже мной было доказано, что для любого свойства первого порядка с ограниченной числом k кванторной глубиной выполнен закон нуля или единицы, если a принадлежит интервалам (0,1/(k-2)) и (1-1/(2^{k}-2),1). На концах этих интервалов закон нуля или единицы не выполнен.

В 1990 году Дж. Спенсер доказал, что существует свойство первого порядка L и бесконечно много таких рациональных чисел a из интервала (0,1), что вероятность того, что случайный граф G(n,n^{-a}) обладает свойством L, не стремится ни к 0, ни к 1 (множество S(L) таких рациональных чисел a называется спектром формулы L). В докладе буде рассказано о недавней совместной работе с Дж. Спенсером, в которой нам удалось получить новые результаты о распределении точек в спектре.