Geodesic
Zero-one laws for random graphs with vertices in a Boolean cube
Matematičeskie trudy, Tome 19 (2016) no. 1, pp. 106-177.

Voir la notice de l'article provenant de la source Math-Net.Ru

We study the limit probabilities of first-order properties for random graphs with vertices in a Boolean cube. We find sufficient conditions for a sequence of random graphs to obey the zero-one law for first-order formulas of bounded quantifier depth. We also find conditions implying a weakened version of the zero-one law. 
@article{MT_2016_19_1_a4,
     author = {S. N. Popova},
     title = {Zero-one laws for random graphs with vertices in a {Boolean} cube},
     journal = {Matemati\v{c}eskie trudy},
     pages = {106--177},
     publisher = {mathdoc},
     volume = {19},
     number = {1},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MT_2016_19_1_a4/}
}
TY  - JOUR
AU  - S. N. Popova
TI  - Zero-one laws for random graphs with vertices in a Boolean cube
JO  - Matematičeskie trudy
PY  - 2016
SP  - 106
EP  - 177
VL  - 19
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MT_2016_19_1_a4/
LA  - ru
ID  - MT_2016_19_1_a4
ER  - 
%0 Journal Article
%A S. N. Popova
%T Zero-one laws for random graphs with vertices in a Boolean cube
%J Matematičeskie trudy
%D 2016
%P 106-177
%V 19
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MT_2016_19_1_a4/
%G ru
%F MT_2016_19_1_a4
S. N. Popova. Zero-one laws for random graphs with vertices in a Boolean cube. Matematičeskie trudy, Tome 19 (2016) no. 1, pp. 106-177. http://geodesic.mathdoc.fr/item/MT_2016_19_1_a4/

[1] Alon N., Spenser Dzh., Veroyatnostnyi metod, BINOM, M., 2007

[2] Vereschagin N. K., Shen A., Yazyki i ischisleniya, MTsNMO, M., 2000

[3] Glebskii Yu. V., Kogan D. I., Liogonkii M. I., Talanov V. A., “Ob'em i dolya vypolnimosti formul uzkogo ischisleniya predikatov”, Kibernetika, 1969, no. 2, 17–26 | MR

[4] Gorskaya E. S., Mitricheva I. M., Protasov V. Yu., Raigorodskii A. M., “Otsenka khromaticheskikh chisel evklidova prostranstva metodami vypukloi minimizatsii”, Matem. sb., 200:6 (2009), 3–22 | DOI | MR | Zbl

[5] Demëkhin E. E., Raigorodskii A. M., Rubanov O. I., “Distantsionnye grafy, imeyuschie bolshoe khromaticheskoe chislo i ne soderzhaschie klik ili tsiklov zadannogo razmera”, Matem. sb., 204:4 (2013), 49–78 | DOI | MR | Zbl

[6] Zhukovskii M. E., “Oslablennye zakony «nulya ili edinitsy» dlya sluchainykh distantsionnykh grafov”, Dokl. RAN, 430:3 (2010), 314–317 | MR | Zbl

[7] Zhukovskii M. E., “Oslablennyi zakon nulya ili edinitsy dlya sluchainykh distantsionnykh grafov”, TVP, 55:2 (2010), 344–349 | DOI | MR

[8] Zhukovskii M. E., “O posledovatelnosti sluchainykh distantsionnykh grafov, podchinyayuscheisya zakonu nulya ili edinitsy”, Probl. peredachi inf., 47:3 (2011), 39–58 | MR

[9] Zhukovskii M. E., “Oslablennyi zakon nulya ili edinitsy dlya posledovatelnostei sluchainykh distantsionnykh grafov”, Matem. sb., 203:7 (2012), 95–128 | DOI | MR | Zbl

[10] Mak-Vilyams F. Dzh., Sloen N. Dzh. A., Teoriya kodov, ispravlyayuschikh oshibki, Radio i cvyaz, M., 1979

[11] Popova S. N., “Zakon nulya ili edinitsy dlya sluchainykh distantsionnykh grafov s vershinami v $\{-1,0,1\}^n$”, Probl. peredachi inf., 50:1 (2014), 64–86 | MR | Zbl

[12] Raigorodskii A. M., “Problema Borsuka i khromaticheskie chisla nekotorykh metricheskikh prostranstv”, UMN, 56:1 (2001), 107–146 | DOI | MR | Zbl

[13] Raigorodskii A. M., “Problema Borsuka dlya tselochislennykh mnogogrannikov”, Matem. sb., 193:10 (2002), 139–160 | DOI | MR | Zbl

[14] Raigorodskii A. M., “Zadachi Borsuka i Khadvigera i sistemy vektorov s zapretami na skalyarnye proizvedeniya”, UMN, 57:3 (2002), 159–160 | DOI | MR | Zbl

[15] Raigorodskii A. M., “Problema Erdesha–Khadvigera i khromaticheskie chisla konechnykh geometricheskikh grafov”, Matem. sb., 196:1 (2005), 123–156 | DOI | MR | Zbl

[16] Raigorodskii A. M., “Problemy Borsuka i Gryunbauma dlya reshetchatykh mnogogrannikov”, Izv. RAN. Ser. matem., 69:3 (2005), 81–108 | DOI | MR | Zbl

[17] Raigorodskii A. M., Shitova I. M., “O khromaticheskikh chislakh veschestvennykh i ratsionalnykh prostranstv s veschestvennymi ili ratsionalnymi zapreschennymi rasstoyaniyami”, Matem. sb., 199:4 (2008), 107–142 | DOI | MR | Zbl

[18] Raigorodskii A. M., Modeli sluchainykh grafov, MTsNMO, M., 2011

[19] Brenner J., Cummings L., “The Hadamard maximum determinant problem”, Amer. Math. Monthly, 79:6 (1972), 626–630 | DOI | MR | Zbl

[20] Fagin R., “Probabilities in finite models”, J. Symbolic Logic, 41:1 (1976), 50–58 | DOI | MR | Zbl

[21] Shelah S., Spencer J. H., “Zero-One laws for sparse random graphs”, J. Amer. Math. Soc., 1:1 (1988), 97–115 | DOI | MR | Zbl