рус eng
«ИЗВЕСТИЯ ИРКУТСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА». СЕРИЯ «МАТЕМАТИКА»
«IZVESTIYA IRKUTSKOGO GOSUDARSTVENNOGO UNIVERSITETA». SERIYA «MATEMATIKA»
«THE BULLETIN OF IRKUTSK STATE UNIVERSITY». SERIES «MATHEMATICS»
ISSN 1997-7670 (Print)
ISSN 2541-8785 (Online)

Список выпусков > Серия «Математика». 2024. Том 50

Заметка о псевдоконечных ациклических графах

Автор(ы)
Н. Д. Мархабатов1,2, Е. Р. Байсалов1

1Евразийский национальный университет им. Л. Н. Гумилева, Астана, Казахстан

2Казахстанско-Британский технический университет, Алма-Ата, Казахстан

Аннотация
Рассматриваются ациклические графы, аппроксимируемые конечными ациклическими графами. Доказано, что любой счетно категоричный ациклический граф гладко аппроксимируем. Приведен пример псевдоконечной ациклической теории графов, имеющей четное, нечетное и бесконечное число лучей.
Об авторах

Мархабатов Нурлан Дарханулы, канд. физ.-мат. наук, преподаватель-исследователь, Евразийский национальный университет им. Л. Н. Гумилева, Астана, 010000, Казахстан; научный сотрудник, Казахстанско-Британский технический университет, Алма-Ата, Казахстан, markhabatov@gmail.com

Байсалов Ержан Рахметтоллаевич, канд. физ.-мат. наук, доц., Евразийский национальный университет им. Л. Н. Гумилева, Астана, 010000, Казахстан, baisal59@gmail.com

Ссылка для цитирования
Markhabatov N. D., Baisalov Ye. R. A Note on Pseudofinite Acyclic Graphs // Известия Иркутского государственного университета. Серия Математика. 2024. Т. 50. C. 116–124. https://doi.org/10.26516/1997-7670.2024.50.116
Ключевые слова
аппроксимация теории, дерево, ациклический граф, псевдоконечная теория, гладко аппроксимируемая структура, псевдоконечный граф
УДК
510.67, 519.17
MSC
03C50,05C25
DOI
https://doi.org/10.26516/1997-7670.2024.50.116
Литература
  1. Garcia D., Robles M. Pseudofiniteness and measurability of the everywhere infinite forest. arXiv:2309.00991, 2023. https://doi.org/10.48550/arXiv.2309.00991
  2. Grinberg D. An introduction to graph theory. arXiv:2308.04512, 2023. https://doi.org/10.48550/arXiv.2308.04512
  3. Herre Heinrich, Mekler Allan, Smith Kenneth. Superstable graphs. Fundamenta Mathematicae, 1983, vol. 118 no. 2, pp. 75–79.
  4. Ivanov A. The structure of superflat graphs. Fundamenta Mathematicae, 1993, vol. 143, no. 2, pp. 107–117.
  5. Kantor W.M., Liebeck M.W., Macpherson H.D. ℵ0-categorical structures smoothly approximated by finite substructures. Proc. London Math. Soc., 1989, vol. 59, pp. 439–463. https://doi.org/10.1112/plms/s3-59.3.439
  6. Malyshev S. B. Kinds of Pregeometries of Acyclic Theories. The Bulletin of Irkutsk State University. Series Mathematics, 2023, vol. 46, pp. 110–120. https://doi.org/10.26516/1997-7670.2023.46.110
  7. Marker D. Model Theory: An Introduction. Graduate Texts in Mathematics, vol. 271. New York, Berlin and Heidelberg, Springer Verlag Publ., 2002, 342 p.
  8. Markhabatov N. D. Approximations of Acyclic Graphs. The Bulletin of Irkutsk StateUniversity. Series Mathematics, 2022, vol. 40, pp. 104–111. https://doi.org/10.26516/1997-7670.2022.40.104
  9. Markhabatov N. D., Sudoplatov S. V., Approximations of Regular Graphs, Herald of the Kazakh-British Technical University, 2022, vol.19, no. 1, pp. 44–49 https://doi.org/10.55452/1998-6688-2022-19-1-44-49
  10. Myasnikov, A.G., Remeslennikov, V.N. Generic Theories as a Method for Approximating Elementary Theories. Algebra and Logic, 2015, vol. 53, pp. 512–519 https://doi.org/10.1007/S10469-015-9314-0
  11. Nurtazin A.T. Graphs and Models with finite chains, Siberian Electronic Mathematical Reports, 2007, vol. 4, pp. 238–248
  12. Ovchinnikova E.V., Shishmarev Yu.E., (1988). Countably categorical graphs, Ninth All-Union Conference on Mathematical Logic. Leningrad, September 27-29, dedicated to the 85th anniversary of Corresponding Member of the USSR Academy of Sciences A.A. Markov, p.120
  13. Podewski, Klaus-Peter, and Ziegler, Martin. Stable graphs. Fundamenta Mathematicae, 1978, vol. 100, no. 2, pp. 101–107.
  14. Sudoplatov S. V. Approximations of theories. Siberian Electronic Mathematical Reports, 2020, vol.17, pp. 715–725
  15. Tao T. Expanding polynomials over finite fields of large characteristic, and a regularity lemma for definable sets. Contributions to Discrete Mathematics, 2014, vol. 10, no. 1, pp. 22–98.
  16. Valizadeh A.N., Pourmahdian M. Pseudofiniteness in Hrushovski Constructions. Notre Dame J. Formal Log., 2020, vol. 61, pp. 1–10. https://doi.org/10.1215/00294527-2019-0038
  17. Valizadeh A.N., Pourmahdian M. Strict Superstablity and Decidability of Certain Generic Graphs. Bull. Iran. Math. Soc., 2019, vol. 45, pp. 1839–1854. https://doi.org/10.1007/s41980-019-00234-2
  18. Woodrow R.E. Theories with a finite number of countable models and a small language. Ph. D. Thesis. Simon Fraser University, 1976, 99 p.

Полная версия (english)