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

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





Для просмотра файлов Вам могут потребоваться








Семинар отдела дискретной математики МИАН
15 апреля 2014 г. 16:00, г. Москва, МИАН, комн. 511 (ул. Губкина, 8)
 


О законах нуля или единицы для свойств первого порядка случайного графа Эрдеша–Реньи

М. Е. Жуковский

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

Аннотация: В докладе речь пойдет об асимптотике вероятностей свойств первого порядка случайного графа Эрдеша–Реньи $G(n,p)$ (в случайном графе $G(n,p)$ на $n$ вершинах ребра проводятся независимо с вероятностью $p$). Свойствами первого порядка называются свойства, выражаемые формулами, записанными на языке первого порядка (в записи участвуют символы переменных $x,y,x_1,…$ (вершины графа), символы отношений $\sim$ (символ смежности двух вершин) и $=$ (символ совпадения двух вершин), логические связки и кванторы). Например, свойства графа содержать треугольник, быть полным или обладать изолированной вершиной являются свойствами первого порядка. Связность графа не является свойством первого порядка. В 1969 году Глебский, Коган, Легонький и Таланов (а в 1976 году независимо Р. Фагин) доказали, что случайный граф $G(n,p)$ подчиняется закону нуля или единицы. А именно, для любого свойства первого порядка вероятность выполнения этого свойства стремится либо к 0, либо к 1. Если в качестве вероятности $p$ выбрать некоторую функцию $p=p(n)$, то закон может нарушаться. Так, в 1988 году Дж. Спенсер и С. Шелла рассмотрели $p=n^{-\alpha}$, где $\alpha>0$, и обнаружили удивительный эффект: при иррациональных $\alpha$ закон нуля или единицы выполнен, а при рациональных $\alpha\in(0,1]$ – нет. Они получили, кроме того, исчерпывающий результат для рациональных $\alpha\in(1,\infty)$. Дальнейшие исследования в области были связаны с уменьшением множества свойств и рассмотрением всех свойств, выражаемых формулами первого порядка с ограниченной числом $k$ кванторной глубиной (кванторной глубиной формулы называется максимальная длина цепочки вложенных кванторов в этой формуле). Если вероятность выполнения любого свойства из такого множества стремится либо к 0, либо к 1, то говорят, что выполнен $k$-закон нуля или единицы. Для различных $k\in\mathbb{N}$ нами были найдены диапазоны значений $\alpha$, при которых случайный граф $G(n,n^{-\alpha})$ подчиняется $k$-закону нуля или единицы. Были найдены, кроме того, наименьшее и наибольшее в интервале $(0,1)$ значения $\alpha$, при которых нарушается $k$-закон.

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2017