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

Изучается асимптотическое поведение вероятностей свойств первого порядка для случайных равномерных гиперграфов. В 1990 г. Дж. Спенсер ввел понятие спектра для свойств графов и доказал, что существует свойство первого порядка с бесконечным спектром. В статье дается определение спектра для свойств равномерных гиперграфов и устанавливается почти точная оценка минимальной кванторной глубины формулы первого порядка с бесконечным спектром.

Ключевые слова

Источник финансирования

Работа выполнена за счет гранта Российского научного фонда (проект № 16-11-10014)

Получено

12.10.2018

Дата публикации

12.10.2018

Кол-во символов

452

Цитировать Скачать pdf Для скачивания PDF необходимо авторизоваться

ГОСТ	Попова С. Н. Бесконечные спектры свойств первого порядка случайных гиперграфов // Проблемы передачи информации – 2018. – Tом 54. – Выпуск 3 C. 92-101 [Электронный ресурс]. URL: http://ras.jes.su/ppi/s207987840000570-6-1 (дата обращения: 04.05.2024). DOI: 10.31857/S055529230001328-4
MLA	Popova, S. "Infinite Spectra of First-Order Properties for Random Hypergraphs." Problemy peredachi informatsii 54.3 (2018):92-101. DOI: 10.31857/S055529230001328-4
APA	Popova S. (2018). Infinite Spectra of First-Order Properties for Random Hypergraphs. Problemy peredachi informatsii 54(3), pp.92-101 DOI: 10.31857/S055529230001328-4

Размещенный ниже текст является ознакомительной версией и может не соответствовать печатной.

всего просмотров: 1053

Оценка читателей: голосов 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. Жуковский М.Е. Расширение k-закона нуля или единицы // ДАН. 2014. Т. 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. Жуковский М.Е., Райгородский А.М. Случайные графы: модели и предельные характеристики // УМН. 2015. Т. 70. № 1 (421). С. 35–88.

7. Жуковский М.Е. Спектры формул первого порядка малой кванторной глубины // УМН. 2015. Т. 70. № 6 (426). С. 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. Ванцян А.Г. Эволюция случайных однородных гиперграфов // Вероятностные задачи дискретной математики. М: МИЭМ, 1987. С. 126–131.

13. Spencer J.H. Threshold Functions for Extension Statements // J. Combin. Theory Ser. A. 1990. V. 53. № 2. P. 286–305.

14. Алон Н., Спенсер Дж. Вероятностный метод. М.: БИНОМ, 2007.

15. Жуковский М.Е. Оценка количества максимальных расширений в случайном графе // Дискрет. матем. 2012. Т. 24. № 1. С. 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.