RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Сиб. электрон. матем. изв.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Сиб. электрон. матем. изв., 2016, том 13, страницы 137–147 (Mi semr662)  

Математическая логика, алгебра и теория чисел

Об аксиоматизируемости наследственных классов графов и матроидов

А. В. Ильев

Sobolev Institute of Mathematics, Pevtsova str., 13, 644043, Omsk, Russia

Аннотация: 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.

Ключевые слова: axiomatizability, graph, matroid, hereditary class.

DOI: https://doi.org/10.17377/semi.2016.13.012

Полный текст: PDF файл (166 kB)
Список литературы: PDF файл   HTML файл

Реферативные базы данных:

Тип публикации: Статья
УДК: 510.67, 519.17
MSC: 03C48, 05B35, 05C63
Поступила 21 декабря 2015 г., опубликована 11 марта 2016 г.

Образец цитирования: А. В. Ильев, “Об аксиоматизируемости наследственных классов графов и матроидов”, Сиб. электрон. матем. изв., 13 (2016), 137–147

Цитирование в формате AMSBIB
\RBibitem{Ile16}
\by А.~В.~Ильев
\paper Об аксиоматизируемости наследственных классов графов и~матроидов
\jour Сиб. электрон. матем. изв.
\yr 2016
\vol 13
\pages 137--147
\mathnet{http://mi.mathnet.ru/semr662}
\crossref{https://doi.org/10.17377/semi.2016.13.012}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/semr662
  • http://mi.mathnet.ru/rus/semr/v13/p137

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Просмотров:
    Эта страница:113
    Полный текст:36
    Литература:51
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020