Abstract
We prove that the acyclic complex \(\mathrm{Acy }(T)\) of any trisectionable tournament \(T\) is homotopy equivalent to a wedge of spheres, and show that there exists a fix number \(0<\epsilon <1\) such that if \(T\) is a trisectionable tournament and \(d\) is the highest dimension of a sphere occurring in such a decomposition for \(\mathrm{Acy }(T)\), then the (acyclic) chromatic number of \(T\) satisfies \(\chi (T)\leqslant c(d+1)^{\frac{1}{\epsilon }-1}-1\) for some \(1.62<c\leqslant 2\), and by way of an example, we verify that the provided upper bound is tight.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Attali, D., Lieutier, A., Salinas, D.: Efficient data structure for representing and simplifying simplicial complexes in high dimensions. Int. J. Comput. Geom. 22, 279–303 (2012)
Berger, E., Choromanski, K., Chudnovsky, M., Fox, J., Loebl, M., Scott, A., Seymour, P., Thomass, S.: Tournaments and colouring. J. Comb. Theory Ser. B 103, 1–20 (2013)
Biyikoglu, T., Civan, Y.: Four-cycled graphs with topological applications. Ann. Comb. 16, 37–56 (2012)
Burzio, M., Demaria, D.C.: On simply disconnected tournaments. Ars Comb. 24, 149–161 (1987)
Burzio, M., Demaria, D.C.: Characterization of tournaments by coned 3-cycles. Acta Univ. Carol. Math. Phys. 28, 25–30 (1987)
Demaria, D.C., Kiihl, J.C.S.: On the complete digraphs which are simply disconnected. Publ. Math. 35, 517–525 (1991)
Ehrenborg, R., Hetyei, G.: The topology of the independence complex. Eur. J. Comb. 27, 906–923 (2006)
Hoppe, H.: Progressive meshes. Proc. 23rd Annual Conf. Computer Graphics and Interactive Techniques, pp. 99–108. ACM, New York (1996)
Marietti, M., Testa, D.: Cores of simplicial complex. Discrete Comput. Geom. 40, 444–468 (2008)
Matoušek, J.: Using the Borsuk–Ulam theorem. Lectures on Topological Methods in Combinatorics and Geometry. University text, Springer, Heidelberg (2003)
Odlyzko, A.M., Wilf, H.S.: Functional iteration and the Josephus problem. Glasgow Math. 33, 235–240 (1991)
Sloane, N.J.A.: The on-line encyclopedia of integer sequences. https://oeis.org
Acknowledgments
I would like to thank Professor Yusuf Civan for his invaluable comments and generous encouragement and also the referee for useful suggestions and comments that improved the presentation of this work.
Author information
Authors and Affiliations
Corresponding author
Additional information
The author is supported by TÜBİTAK, Grant No: 111T704.
Rights and permissions
About this article
Cite this article
Deniz, Z. Topology of acyclic complexes of tournaments and coloring. AAECC 26, 213–226 (2015). https://doi.org/10.1007/s00200-014-0245-0
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00200-014-0245-0