Математический сборник
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Скоро в журнале
Архив
Импакт-фактор
Правила для авторов
Лицензионный договор
Загрузить рукопись
Историческая справка

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Матем. сб.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Математический сборник, 2020, том 211, номер 7, страницы 60–71
DOI: https://doi.org/10.4213/sm9321
(Mi sm9321)
 

Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)

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

М. Е. Жуковскийab, Н. М. Свешниковc

a Лаборатория продвинутой комбинаторики и сетевых приложений, Московский физико-технический институт (национальный исследовательский университет), г. Долгопрудный, Московская обл.
b Московский центр фундаментальной и прикладной математики
c Физтех-школа прикладной математики и информатики, Московский физико-технический институт (национальный исследовательский университет), г. Долгопрудный, Московская обл.
Список литературы:
Аннотация: Рассматривается случайный граф Эрдёша–Реньи в равномерной модели $G(n,m)$, где $m=m(n)$ – такая последовательность целых неотрицательных чисел, что $m(n)\sim cn^{\alpha}<(2-\varepsilon)n^2$ для некоторых $c>0$, $\alpha\in[0,2]$ и $\varepsilon>0$. Доказано, что $G(n,m)$ подчиняется закону нуля или единицы для языка первого порядка тогда и только тогда, когда либо $\alpha\in\{0,2\}$, либо $\alpha$ иррационально, либо $\alpha\in(0,1)$ и $\alpha$ не принадлежит множеству чисел вида $1-1/\ell$, $\ell\in\mathbb{N}$.
Библиография: 15 названий.
Ключевые слова: закон нуля или единицы, логика первого порядка, равномерная модель случайного графа.
Финансовая поддержка Номер гранта
Российский научный фонд 18-71-00069
Исследование М. Е. Жуковского выполнено за счет гранта Российского научного фонда (проект № 18-71-00069) в Лаборатории продвинутой комбинаторики и сетевых приложений Московского физико-технического института (национального исследовательского университета). Разделы 2.2, 2.3 и 2.5, а также доказательства теорем 4 и 6 выполнены М. Е. Жуковским. Разделы 1, 2.1 и 2.4, а также доказательство теоремы 5 выполнены Н. М. Свешниковым.
Поступила в редакцию: 21.08.2019 и 28.01.2020
Англоязычная версия:
Sbornik: Mathematics, 2020, Volume 211, Issue 7, Pages 956–966
DOI: https://doi.org/10.1070/SM9321
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.179.4
MSC: Primary 05C80, 60F20; Secondary 03C07
Образец цитирования: М. Е. Жуковский, Н. М. Свешников, “Закон нуля или единицы первого порядка для равномерной модели случайного графа”, Матем. сб., 211:7 (2020), 60–71; M. E. Zhukovskii, N. M. Sveshnikov, “First-order zero-one law for the uniform model of the random graph”, Sb. Math., 211:7 (2020), 956–966
Цитирование в формате AMSBIB
\RBibitem{ZhuSve20}
\by М.~Е.~Жуковский, Н.~М.~Свешников
\paper Закон нуля или единицы первого порядка для равномерной модели случайного графа
\jour Матем. сб.
\yr 2020
\vol 211
\issue 7
\pages 60--71
\mathnet{http://mi.mathnet.ru/sm9321}
\crossref{https://doi.org/10.4213/sm9321}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4045698}
\zmath{https://zbmath.org/?q=an:1448.05184}
\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2020SbMat.211..956Z}
\elib{https://elibrary.ru/item.asp?id=45283034}
\transl
\by M.~E.~Zhukovskii, N.~M.~Sveshnikov
\paper First-order zero-one law for~the~uniform~model of the random graph
\jour Sb. Math.
\yr 2020
\vol 211
\issue 7
\pages 956--966
\crossref{https://doi.org/10.1070/SM9321}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000573486400001}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85092051086}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/sm9321
  • https://doi.org/10.4213/sm9321
  • https://www.mathnet.ru/rus/sm/v211/i7/p60
  • Эта публикация цитируется в следующих 2 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Математический сборник Sbornik: Mathematics
    Статистика просмотров:
    Страница аннотации:333
    PDF русской версии:59
    PDF английской версии:31
    Список литературы:33
    Первая страница:17
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024