Geodesic
On axiomatizability of hereditary classes of graphs and matroids
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 13 (2016), pp. 137-147 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

In the paper, hereditary classes of graphs and matroids are studied by means of the model theory. The problems of first-order axiomatizability of some classes of graphs and matroids are considered. The criterion of axiomatizability of monotone hereditary classes of graphs defined by forbidden noninduced subgraphs is proved. Necessary and sufficient conditions of universal and finite axiomatizability of the monotone hereditary classes of graphs are obtained. It is proved that the class of matroids of fixed rank k is finitely axiomatizabile, as well as two hereditary classes of matroids of bounded rank — the class of matroids of rank not exeeding $k$ and the class of partition matroids of rank not exeeding $k$. It is also shown that the hereditary class of matroids of finite rank is nonaxiomatizable.
Keywords: axiomatizability, graph, matroid, hereditary class. 
@article{SEMR_2016_13_a4,
     author = {A. V. Iliev},
     title = {On axiomatizability of hereditary classes of graphs and matroids},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {137--147},
     year = {2016},
     volume = {13},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2016_13_a4/}
}
TY  - JOUR
AU  - A. V. Iliev
TI  - On axiomatizability of hereditary classes of graphs and matroids
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2016
SP  - 137
EP  - 147
VL  - 13
UR  - http://geodesic.mathdoc.fr/item/SEMR_2016_13_a4/
LA  - ru
ID  - SEMR_2016_13_a4
ER  - 
%0 Journal Article
%A A. V. Iliev
%T On axiomatizability of hereditary classes of graphs and matroids
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2016
%P 137-147
%V 13
%U http://geodesic.mathdoc.fr/item/SEMR_2016_13_a4/
%G ru
%F SEMR_2016_13_a4
A. V. Iliev. On axiomatizability of hereditary classes of graphs and matroids. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 13 (2016), pp. 137-147. http://geodesic.mathdoc.fr/item/SEMR_2016_13_a4/

[1] M. Aigner, Combinatorial Theory, Mir, M., 1982 (in Russian) | MR

[2] X. Caicedo, “Finitely axiomatizable quasivarieties of graphs”, Algebra Universalis, 34:2 (1995), 314–321 | DOI | MR | Zbl

[3] R. Diestel, Graph theory, Izdatelstvo Instituta matematiki, Novosibirsk, 2002 (in Russian)

[4] Yu. L. Ershov, Problems of decidability and constructive models, Nauka, M., 1980 (in Russian) | MR

[5] Yu. L. Ershov, I. A. Lavrov, A. D. Taimanov, M. A. Taitslin, “Elementary theories”, Uspekhi Mat. Nauk, 20:4(124) (1965), 37–108 (in Russian) | MR | Zbl

[6] Yu. L. Ershov, E. A. Palyutin, Mathematical Logic, Nauka, M., 1987 (in Russian) | MR | Zbl

[7] Journal of Applied and Industrial Mathematics, 57 (2014), 245–255 | DOI | MR | Zbl

[8] H. Whitney, “On the abstract properties of linear dependence”, American Journal of Mathematics, 57 (1935), 509–533 | DOI | MR