All
 
|
 
 


Infinite Spectra of First-Order Properties for Random Hypergraphs
 
PIIS055529230001328-4-1
DOI10.31857/S055529230001328-4
Publication type Article
Status Published
Authors
S. Popova 
Affiliation:
Journal nameProblemy peredachi informatsii
EditionVolume 54 Issue 3
Pages92-101
Abstract

                  

Keywords
Received12.10.2018
Publication date12.10.2018
Number of characters452
Cite   Download pdf To download PDF you should sign in
Размещенный ниже текст является ознакомительной версией и может не соответствовать печатной

views: 1051

Readers community rating: votes 0 

1. Shelah S., Spencer J.H. Zero-One Laws for Sparse Random Graphs // J. Amer. Math. Soc. 1988. V. 1. № 1. P. 97–115.
2. Zhukovskii M.E. Zero-One k-Law // Discrete Math. 2012. V. 312. № 10. P. 1670–1688.
3. Zhukovskij M.E. Rasshirenie k-zakona nulya ili edinitsy // DAN. 2014. T. 454. № 1. P. 23–26.
4. Spencer J.H. Infinite Spectra in the First Order Theory of Graphs // Combinatorica. 1990. V. 10. № 1. P. 95–102.
5. Spencer J.H. The Strange Logic of Random Graphs. Berlin: Springer-Verlag, 2001.
6. Zhukovskij M.E., Rajgorodskij A.M. Sluchajnye grafy: modeli i predel'nye kharakteristiki // UMN. 2015. T. 70. № 1 (421). S. 35–88.
7. Zhukovskij M.E. Spektry formul pervogo poryadka maloj kvantornoj glubiny // UMN. 2015. T. 70. № 6 (426). S. 209–210.
8. Matushkin A. Zero-One Law for Random Uniform Hypergraphs // arXiv:1607.07654 [math.PR], 2016.
9. Ebbinghaus H.D., Flum J. Finite Model Theory. Berlin: Springer, 1999.
10. Verbitsky O., Zhukovskii M. On the First-Order Complexity of Induced Subgraph Isomorphism // 26th EACSL Annual Conf. on Computer Science Logic (CSL’2017). August 20–24, 2017. Stockholm, Sweden. Leibniz Int. Proc. Inform. (LIPIcs). V. 82. Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2017. Article № 40. P. 40:1–40:16.
11. Matushkin A.D., Zhukovskii M.E. First Order Sentences about Random Graphs: Small Number of Alternations // Discrete Appl. Math. 2018. V. 236. P. 329–346.
12. Vantsyan A.G. Ehvolyutsiya sluchajnykh odnorodnykh gipergrafov // Veroyatnostnye zadachi diskretnoj matematiki. M: MIEhM, 1987. S. 126–131.
13. Spencer J.H. Threshold Functions for Extension Statements // J. Combin. Theory Ser. A. 1990. V. 53. № 2. P. 286–305.
14. Alon N., Spenser Dzh. Veroyatnostnyj metod. M.: BINOM, 2007.
15. Zhukovskij M.E. Otsenka kolichestva maksimal'nykh rasshirenij v sluchajnom grafe // Diskret. matem. 2012. T. 24. № 1. S. 79–107.
16. Ehrenfeucht A. An Application of Games to the Completeness Problem for Formalized Theories // Fund. Math. 1960/1961. V. 49. P. 121–149.
17. Janson S., Łuczak T., Ruciński A. Random Graphs. New York: Wiley, 2000.
18. Janson S. New Versions of Suen’s Correlation Inequality // Random Structures Algorithms. 1998. V. 13. № 3–4. P. 467–483.

Система Orphus

Loading...
Up