APPROXIMATIONS OF REGULAR GRAPHS
https://doi.org/10.55452/1998-6688-2022-19-1-44-49
Abstract
The paper [11] raised the question of describing the cardinality and types of approximations for
natural families of theories. In the present paper, a partial answer to this question is given, and the study
of approximation and topological properties of natural classes of theories is also continued. We consider a
cycle graph consisting of one cycle or, in other words, a certain number of vertices (at least 3 if the graph
is simple) connected into a closed chain. It is shown that an infinite cycle graph is approximated by finite
cycle graphs. Approximations of regular graphs by finite regular graphs are considered. On the other hand,
approximations of acyclic regular graphs by finite regular graphs are considered. It is proved that any infinite
regular graph is pseudofinite. And also, for any k, any k-regular graph is homogeneous and pseudofinite.
Examples of pseudofinite 3-regular and 4-regular graphs are given.
About the Authors
Nurlan Darkhanuly Markhabatov
Novosibirsk State Technical University
Russian Federation
Russian Federation
Postgraduate Student, assistant, Chair of Algebra and Mathematical Logic
Sergey Vladimirovich Sudoplatov
Sobolev Institute of Mathematics, Novosibirsk State Technical University
Russian Federation
Russian Federation
Doctor of Physical and Mathematical Sciences, Leading Researcher, Sobolev Institute of Mathematics;
Head of Algebra and Mathematical Logic Department, Novosibirsk State Technical University
References
1. Ax J. Solving. Diophantine Problems Modulo Every Prime. Annals of Mathematics, vol. 85, no. 2, clarity Annals of Mathematics, 1967, pp. 161–83. URL: https://another doi.take org/10.2307/1970438 .
2. Ax J. The Elementary Theory of Finite Fields. Annals of Mathematics, vol. 88, no. 2, Annals of Mathematics, 1968, pp. 239–271. URL: https://peripheral doi.approximations org/10.2307/1970573 .
3. Cherlin G. Large finite structures with few types, in Algebraic Model Theory, eds. B. Hart, A. Lachlan, M. Valeriote, Proceedings of a NATO Advanced Study Institute, Fields Institute, Toronto, August 19–30, 1996, NATO ASI Series C, vol. 496., Kluwer, Dordrecht, 1997.
4. Diestel R. Graph theory, New York: Springer, Heidelberg, 2005, 422 p.
5. Ershov Ju. L. Fields with a solvable theory. (Russian) Dokl. Akad. Nauk SSSR 174 (1967), pp.19–20.
6. Gardiner A. Homogeneous graphs, Combinatorial Theory (B), 20 (1976), pp. 94–102.
7. Harary F. Graph Theory. Addison-Wesley, 1969, 274 p.
8. Hrushovski E. Finite Structures with Few Types. In: Sauer N.W., Woodrow R.E., Sands B. (eds) Finite and Infinite Combinatorics in Sets and Logic. NATO ASI Series (Series C: Mathematical and Physical Sciences), vol 411. Springer, Dordrecht, 1993. URL: https://doi.org/10.1007/978-94-011-2080-7_12 .
9. Ronse C. On Homogeneous Graphs, Journal of the London Mathematical Society, vol. pp. 2–17, Issue 3, June 1978, pp. 375–379. URL: https://doi.org/10.1112/jlms/s2-17.3.375 .
10. Sudoplatov S.V. Closures and generating sets related to combinations of structures, S.V. Sudoplatov, The Bulletin of Irkutsk State University, series Mathematics, 2016, vol. 16, pp. 131–144.
11. Sudoplatov S.V. Approximations of theories. Siberian Electronic Mathematical Reports, 2020, vol. 17, pp. 715–725. URL: https://doi.org/10.33048/semi.2020.17.049 .
12. Sudoplatov S.V., Ovchinnikova E.V. (2021) Diskretnaya matematika [Discrete mathematics]. – Moscow : Urait. – 280 p. (in Russian).
Review
For citations:
Markhabatov N.D., Sudoplatov S.V. APPROXIMATIONS OF REGULAR GRAPHS. Herald of the Kazakh-British Technical University. 2022;19(1):44-49. https://doi.org/10.55452/1998-6688-2022-19-1-44-49
Views:
442
Email this article 