Регистрация / Вход
Прислать материал

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

Сведения об участнике
ФИО
Матушкин Александр Дмитриевич
Вуз
Федеральное государственное автономное образовательное учреждение высшего профессионального образования "Московский физико-технический институт (государственный университет)"
Тезисы (информация о проекте)
Область наук
Математика. Механика
Раздел области наук
Математика
Тема
Закон нуля или единицы для случайный однородных гиперграфов
Резюме
In this work limit probabilities of first-order properties of the random $s$-uniform hypergraph in the binomial model $G^{s}(n,p)$ are studied. We give a complete discription of all positive $\alpha$ such that $G^{s}(n,n^{-\alpha})$ obeys Zero-One Law. Moreover, for any rational $\rho\geq 1/(s-1)$ we prove the existence of a strictly balanced $s$-uniform hypergraph with the density $\rho$.
Ключевые слова
случайные гиперграфы; закон нуля или единицы
Цели и задачи
Исследовать предельные вероятности свойств первого порядка в биномиальной модели случайного однородного гиперграфа $G^{s}(n,p)$
Введение

In this work limit probabilities of first-order properties of the random $s$-uniform hypergraph in the binomial model $G^{s}(n,p)$ are studied. We give a complete discription of all positive $\alpha$ such that $G^{s}(n,n^{-\alpha})$ obeys Zero-One Law. Moreover, for any rational $\rho\geq 1/(s-1)$ we prove the existence of a strictly balanced $s$-uniform hypergraph with the density $\rho$.

Методы и материалы

Строго сбалансированные гиперграфы, теорема Боллобаша, универсальные расширения, игра Эренфойхта

Описание и обсуждение результатов

In 1988 J. Spencer and S. Shelah gave the complete description of all $\alpha>0$, such that the random graph $G(n,n^{-\alpha})$ obeys Zero-One Law. 

\begin{theorem} [J. Spencer, S. Shelah]
\label{zero_one_graphs}
Let $p(n)=n^{-\alpha}$, $\alpha>0$. 
\begin{itemize}
\item[(1)] If $\alpha\in\mathbb{Q}\cap(0,1]$ or $\alpha=\frac{k+1}{k}$, $k\in\mathbb{N}$, then $G(n,p(n))$ does not obey Zero-One Law.
\item[(2)] If $\alpha\notin\mathbb{Q}\cap(0,1]$, then $G(n,p(n))$ obeys Zero-One Law.
\item[(3)] If $\alpha>1$, $\alpha\neq\frac{k+1}{k}$, then $G(n,p(n))$ obeys Zero-One Law.
\end{itemize}
\end{theorem}

In this paper, we generalize (1) and (2) of Theorem~\ref{zero_one_graphs} to the case of $s$-hypergraphs. In the proof of the generalization of (1) we exploit the following theorem (that is also proved in this paper): densities of strictly balanced $s$-hypergraphs occupy full spectrum $[1/(s-1),\infty)\cap\mathbb{Q}$. In the proof of the generalizationa of (2) we use Duplicator's look-ahead strategy, that was proposed by Spencer.

Используемые источники
S. Shelah, J.H. Spencer, \emph{Zero-one laws for sparse random graphs}, J. Amer. Math. Soc., \textbf{1}: 97--115, 1988.

J.H. Spencer, \emph{The Strange Logic of Random Graphs}, Number 22 in Algorithms and Combinatorics, Springer-Verlag, Berlin, 2001.

N. Alon and J.H. Spencer, \emph{The Probabilistic Method}, Wiley-Interscience, New York, 2000.
Information about the project
Surname Name
Matushkin Alexander
Project title
Zero-One Law for random uniform hypergraphs
Summary of the project
In this work limit probabilities of first-order properties of the random $s$-uniform hypergraph in the binomial model $G^{s}(n,p)$ are studied. We give a complete discription of all positive $\alpha$ such that $G^{s}(n,n^{-\alpha})$ obeys Zero-One Law. Moreover, for any rational $\rho\geq 1/(s-1)$ we prove the existence of a strictly balanced $s$-uniform hypergraph with the density $\rho$.
Keywords
random hypergraphs; Zero-One Law