Existential monadic second order convergence law fails on sparse random graphs

被引：1

作者：

Egorova, Alena ^{[1
]}

Zhukovskii, Maksim ^{[1
]}

机构：

[1] Moscow Inst Phys & Technol, Lab Adv Combinator & Network Applicat, Dolgoprudnyi, Russia

来源：

EUROPEAN JOURNAL OF COMBINATORICS | 2020年 / 83卷

基金：

俄罗斯科学基金会;

关键词：

PROBABILITIES; MODELS;

D O I：

10.1016/j.ejc.2019.103017

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

In the paper, we prove that existential monadic second order convergence law fails for the binomial random graph G(n, n(-alpha)) for every alpha is an element of (0, 1). (C) 2019 Elsevier Ltd. All rights reserved.

引用

页数：19

共 18 条

[1]

Alon Noga, 2004, The probabilistic method

[2]

[Anonymous], 2001, RANDOM GRAPHS

[3] PROBABILITIES ON FINITE MODELS [J].

FAGIN, R .

JOURNAL OF SYMBOLIC LOGIC, 1976, 41 (01) :50-58

[4] ON THE INDEPENDENCE NUMBER OF RANDOM GRAPHS [J].

FRIEZE, AM .

DISCRETE MATHEMATICS, 1990, 81 (02) :171-175

[5]

Glebskii Yu. V., 1969, Cybernetics, V5, P142, DOI 10.1007/BF01071084

[6]

Janson S., 2000, WIL INT S D

[7] ON RANDOM MODELS OF FINITE POWER AND MONADIC LOGIC [J].

KAUFMANN, M ;

SHELAH, S .

DISCRETE MATHEMATICS, 1985, 54 (03) :285-293

[8]

Kaufmann M., 1987, 32 CLI

[9] The 0-1 law fails for monadic existential second-order logic on undirected graphs [J].

Le Bars, JM .

INFORMATION PROCESSING LETTERS, 2001, 77 (01) :43-48

[10]

Libkin Leonid, 2004, AN EATCS SERIES

← 1 2 →