рус 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». 2022. Vol 40

Approximations of Acyclic Graphs

Author(s)
Nurlan D. Markhabatov

Novosibirsk State Technical University, Novosibirsk, Russian Federation

Abstract
In this paper, approximations of acyclic graphs are studied. It is proved that any theory of an acyclic graph (tree) of finite diameter is pseudofinite with respect to acyclic graphs (trees), that is, any such theory is approximated by theories of finite structures (acyclic graphs, trees). It is also proved that an acyclic graph of infinite diameter with infinite number of rays is pseudofinite.
About the Authors
Nurlan D. Markhabatov, Postgraduate, Assistant, Novosibirsk State Technical University, Novosibirsk, 630073, Russian Federation, markhabatov@gmail.com
For citation
Markhabatov N. D. Approximations of Acyclic Graphs. The Bulletin of Irkutsk State University. Series Mathematics, 2022, vol. 40, pp. 104–111. https://doi.org/10.26516/1997-7670.2022.40.104
Keywords
approximation of theory, tree, acyclic graph, pseudofinite theory
UDC
510.67
MSC
03C30, 03C15, 03C50, 54A05
DOI
https://doi.org/10.26516/1997-7670.2022.40.104
References

1. Ax J. The elementary theory of finite fields. Ann. Math., 1968, vol. 88, no. 2, pp. 239–271.

2. Diestel R. Graph theory. New York, Springer, Heidelberg, 2005. 422 p.

3. Harary F. Graph Theory. Addison-Wesley, 1969. 274 p.

4. Kulpeshov B.Sh., Sudoplatov S.V. Ranks and approximations for families of ordered theories. Algebra and Model Theory 12. Collection of papers. Eds. Pinus A.G., Poroshenko E.N., Sudoplatov S.V.. Novosibirsk, NSTU Publ.,2019, pp. 32–40.

5. Markhabatov N.D. Pseudofiniteness of locally free algebras. Algebra and Model Theory 12, Collection of papers. Eds. Pinus A.G., Poroshenko E.N., Sudoplatov S.V.. Novosibirsk, NSTU Publ., 2019, pp. 41–46.

6. Markhabatov N.D. Ranks for Families of Permutation Theories. The Bulletin of Irkutsk State University. Series Mathematics, 2019, vol. 28, pp. 85–94. https://doi.org/10.26516/1997-7670.2019.28.85

7. Sudoplatov S.V. Approximations of theories. Siberian Electronic Mathematical Reports, 2020, vol. 17, pp. 715-725. https://doi.org/10.33048/semi.2020.17.049

8. Sudoplatov S.V., Ovchinnikova E.V. Diskretnaya matematika [Discrete mathematics]. Moscow, Urait Publ., 2022, 280 p. (in Russian)


Full text (english)