|
This article is cited in 2 scientific papers (total in 2 papers)
Mathematical logic, algebra and number theory
On axiomatizability of hereditary classes of graphs and matroids
A. V. Iliev Sobolev Institute of Mathematics, Pevtsova str., 13, 644043, Omsk, Russia
Abstract:
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.
Received December 21, 2015, published March 11, 2016
Citation:
A. V. Iliev, “On axiomatizability of hereditary classes of graphs and matroids”, Sib. Èlektron. Mat. Izv., 13 (2016), 137–147
Linking options:
https://www.mathnet.ru/eng/semr662 https://www.mathnet.ru/eng/semr/v13/p137
|
Statistics & downloads: |
Abstract page: | 201 | Full-text PDF : | 61 | References: | 69 |
|