Дальневосточный математический журнал

К содержанию выпуска


Связь инвариантов Бухштабера и обобщённых хроматических чисел


А. А. Айзенберг

2011, выпуск 2, С. 113–139


Аннотация
Пусть $K$ — комбинаторный симплициальный комплекс. В работе исследуются $s(K)$ и $s_{\mathbb{R}}(K)$ — комплексное и вещественное числа Бухштабера, являющиеся комбинаторными инвариантами комплекса $K$. При изучении этих чисел важную роль играет понятие характеристической функции, которое можно рассматривать как аналог правильной раскраски в теории графов. Эта аналогия позволяет доказать оценки, связывающие числа Бухштабера с хроматическим числом. Показано, что вещественное и комплексное числа Бухштабера являются различными инвариантами на классе симплициальных комплексов. Также приведен пример симплициальных комплексов $K$ и $L$ таких, что $s(K?L) \ne s(K)+s(L)$. Сходство вещественного числа Бухштабера и хроматического числа позволило определить характеристический многочлен симплициального комплекса. Этот многочлен принимает значения, равные количеству вещественных характеристических функций и обладает свойствами, аналогичными свойствам классического хроматического многочлена графа.
\noindent Основные результаты статьи доложены на секционном докладе Международной конференции «Торическая топология и автоморфные функции» (5–10 сентября 2011 г., г. Хабаровск, Россия).

Ключевые слова: симплициальный комплекс, инвариант Бухштабера, характеристическая функция, линейно-независимая раскраска, хроматическое число, хроматический многочлен, бинарный матроид

Полный текст статьи (файл PDF)

Библиографический список

[1] G. D. Birkhoff, “A determinant formula for the number of ways of coloring a map”, Ann. of Math. (2), 14 (1912), 42–46.
[2] В. М. Бухштабер, Т. Е. Панов, “Действия торов, комбинаторная топология и гомологическая алгебра”, УМН, 55:5 (2000), 3–106.
[3] В. М. Бухштабер, Т. Е. Панов, Торические действия в топологии и комбинаторике, МЦНМО, Москва, 2004.
[4] M. Davis, T. Januszkievicz, “Convex polytopes, Coxeter orbifolds and torus actions”, Duke Math. J., 62:2 (1991), 417–451.
[5] F. M. Dong, K. M. Koh, K. L. Teo, Chromatic polynomials and chromaticity of graphs, World Scientific Publishing Company, 2005.
[6] Н. Ю. Ероховец, “Инвариант Бухштабера простых многогранников”, УМН, 63:5, № 383 (2008), 187–188.
7] Yukiko Fukukawa and Mikiya Masuda, Buchstaber invariants of skeleta of a simplex, arXiv: 0908.3448.
[8] The GAP Group, GAP – Groups, Algorithms, and Programming, Version 4.4.12, http://www.gap-system.org, 2008.
[9] И. В. Изместьев, “Трехмерные многообразия, определяемые раскраской граней простого многогранника”, Математические заметки, 69:3 (2001), 375–382.
[10] Wilberd van der Kallen, “Homology stability for linear groups”, Inventiones Mathematicae, 60:3 (1980).
[11] J.P.S. Kung, A source book in matroid theory, Birkhauser, 1986.
[12] Hisashi Nakayama and Yasuzo Nishimura, “The orientability of small covers and coloring simple polytopes”, Osaka J. Math., 42:1 (2005), 243–256.
[13] G. Reisner, “Cohen-Macaulay quotients of polynomial rings”, Advances in Math., 21:1 (1976), 30–49.
[14] G.-C. Rota, “On the foundations of combinatorial theory I. Theory of Mobius Functions”, Probability Theory and Related Fields, 2:4 (1964).
[15] F. Effenberger and J. Spreer, simpcomp – a GAP toolkit for simplicial complexes, Version 1.3.3, http://www.igt.uni-stuttgart.de/LstDiffgeo/simpcomp, 2010.
[16] H. Whitney, “A logical expansion in mathematics”, Bull. Amer. Math. Soc., 38 (1932), 572–579.

К содержанию выпуска