Far Eastern Mathematical Journal

To content of the issue

Connection between Buchstaber invariants and generalized chromatic numbers

A. A. Aizenberg

2011, issue 2, P. 113–139

Abstract

Let $K$ be a combinatorial simplicial complex. The work is devoted to $s(K)$ and $s_{\mathbb{R}}(K)$ – complex and real Buchstaber numbers which are combinatorial invariants of a simplicial complex $K$. The main tool in the study of these invariants is the notion of characteristic function, which can be regarded as an analogue of proper coloring in the graph theory. This analogy allows to prove estimations connecting Buchstaber numbers and chromatic number. It is shown in the work that real and complex Buchstaber numbers are not equal on the class of simplicial complexes. Also we provide an example of simplicial complexes $K$ and $L$ such that $s(K?L) \ne s(K)+s(L)$. The similarity between real Buchstaber number and chromatic number led to the notion of characteristic polynomial of simplicial complex. This polynomial takes values equal to the number of characteristic functions and possesses properties similar to those of a chromatic polynomial of a graph. \noindent The main results of the paper were reported on the section talk at the International conference “Toric Topology and Automorphic Functions” (September, 5–10th, 2011, Khabarovsk, Russia).

Keywords: simplicial complex, Buchstaber invariant, characteristic function, linearly independent coloring, chromatic number, chromatic polynomial, binary matroid

Download the article (PDF-file)

References

[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] V. M. Bukhshtaber, T. E. Panov, “Deistviia torov, kombinatornaia topologiia i gomologicheskaia algebra”, UMN, 55:5 (2000), 3–106. [3] V. M. Bukhshtaber, T. E. Panov, Toricheskie deistviia v topologii i kombinatorike, MTsNMO, Moskva, 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] N. Iu. Erokhovets, “Invariant Bukhshtabera prostykh mnogogrannikov”, UMN, 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] I. V. Izmest'ev, “Trekhmernye mnogoobraziia, opredeliaemye raskraskoi granei prostogo mnogogrannika”, Matematicheskie zametki, 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.

To content of the issue