рус eng
«THE BULLETIN OF IRKUTSK STATE UNIVERSITY». SERIES «MATHEMATICS»
«IZVESTIYA IRKUTSKOGO GOSUDARSTVENNOGO UNIVERSITETA». SERIYA «MATEMATIKA»
ISSN 1997-7670 (Print)
ISSN 2541-8785 (Online)

List of issues > Series «Mathematics». 2024. Vol 50

A Note on Pseudofinite Acyclic Graphs

Author(s)
Nurlan D. Markhabatov1,2, Yerzhan R. Baissalov1

1L. N. Gumilyov Eurasian National University, Astana, Kazakhstan

2Kazakh-British Technical University, Alma-Ata, Kazakhstan

Abstract
Acyclic graphs approximated by finite acyclic graphs are considered. It is proved that any countably categorical acyclic graph is smoothly approximable. An example of pseudofinite acyclic graph theory is given, which has an even, odd, and infinite number of rays.
About the Authors

Nurlan D. Markhabatov D., Cand. Sci. (Phys.–Math.), Lecturer-Researcher, L. N. Gumilyov Eurasian National University, Astana, 010000, Kazakhstan, Researcher, Kazakh-British Technical University, Alma-Ata, Kazakhstan, markhabatov@gmail.com

Erzhan R. Baissalov , Cand. Sci. (Phys.–Math.), Associate Professor, L. N. Gumilyov Eurasian National University, Astana, 010000, Kazakhstan, baisal59@gmail.com

For citation

Markhabatov N. D., Baissalov Ye. R. A Note on Pseudofinite Acyclic Graphs. The Bulletin of Irkutsk State University. Series Mathematics, 2024, vol. 50, pp. 116–124.

https://doi.org/10.26516/1997-7670.2024.50.116

Keywords
approximation of theory, tree, acyclic graph, pseudofinite theory, smoothly approximated structure, pseudofinite graph
UDC
510.67, 519.17
MSC
03C50,05C25
DOI
https://doi.org/10.26516/1997-7670.2024.50.116
References
  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.

Full text (english)