×

Colorful polytopes and graphs. (English) Zbl 1275.05019

Summary: The paper investigates connections between abstract polytopes and properly edge colored graphs. Given any finite \(n\)-edge-colored \(n\)-regular graph \(\mathcal{G}\), we associate to \(G\) a simple abstract polytope \(\mathcal{P}_{\mathcal{G}}\) of rank \(n\), the colorful polytope of \(G\), with 1-skeleton isomorphic to \(G\). We investigate the interplay between the geometric, combinatorial, or algebraic properties of the polytope \(\mathcal{P}_{\mathcal{G}}\) and the combinatorial or algebraic structure of the underlying graph \(G\), focussing in particular on aspects of symmetry. Several such families of colorful polytopes are studied including examples derived from a Cayley graph, in particular the graphicahedra, as well as the flagadjacency polytopes and related monodromy polytopes associated with a given abstract polytope. The duals of certain families of colorful polytopes have been important in the topological study of colored triangulations and crystallization of manifolds.

MSC:

05C15 Coloring of graphs and hypergraphs
51M20 Polyhedra and polytopes; regular figures, division of spaces
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] G. Araujo-Pardo, M. Del Río-Francos, M. López-Dudet, D. Oliveros and E. Schulte, The graphicahedron, European Journal of Combinatorics 31 (2010), 1868–1879. · Zbl 1222.05093 · doi:10.1016/j.ejc.2010.03.004
[2] R. Blind and P. Mani, On puzzles and polytope isomorphism, Aequationes Mathematicae 34 (1987), 287–297. · Zbl 0634.52005 · doi:10.1007/BF01830678
[3] J. Bracho and L. Montejano, The combinatorics of colored triangulations of manifolds, Geometriae Dedicata 22 (1987), 303–328. · Zbl 0631.57017 · doi:10.1007/BF00147939
[4] G. Chartrand and L. Lesniak, Graphs and Digraphs, third edition, Chapman and Hall, London, 1996. · Zbl 0890.05001
[5] H. S. M. Coxeter, Regular Polytopes, third edition, Dover, New York, 1973.
[6] L. Danzer and E. Schulte, Reguläre Inzidenzkomplexe, I, Geomtriae Dedicata 13 (1982), 295–308. · Zbl 0505.51019
[7] M. Del Río-Francos, I. Hubard, D. Oliveros and E. Schulte, Symmetric graphicahedra, submitted. · Zbl 1264.51014
[8] J. P. Doignon and C. Huybrechts, Permutographs and the permutahedron, manuscript, 2000.
[9] P. Erdos and R. J. Wilson, On the chromatic index of almost all graphs, Journal of Combinatorial Theory. Series B 23 (1977), 255–257. · Zbl 0378.05032 · doi:10.1016/0095-8956(77)90039-9
[10] M. E. Fernandes and D. Leemans, Polytopes of high rank for the symmetric groups, Advances in Mathematics 228 (2011), 3207–3222. · Zbl 1252.51011 · doi:10.1016/j.aim.2011.08.006
[11] M. Ferri, C. Gagliardi and L. Graselli, A graph-theoretical representation of PL-manifolds – a survey on crystallizations, Aequationes Mathematicae 31 (1986), 121–141. · Zbl 0623.57012 · doi:10.1007/BF02188181
[12] A. Gardiner and C. E. Praeger, A geometrical approach to imprimitive graphs, Proceedings of the London Mathematical Society 71 (1995), 524–546. · Zbl 0837.05068 · doi:10.1112/plms/s3-71.3.524
[13] B. Grünbaum, Regularity of graphs, complexes and designs, in Problèmes combinatoires et théorie des graphes, Colloques Internationaux du Centre National de la Recherche Scientifique, Vol. 260, Centre National de la Recherche Scientifique, Paris, 1977, pp. 191–197.
[14] G.-Th. Guilbaud and P. Rosenstiehl, Analyse algébrique d’un scrutin, Mathématiques et Sciences Humaines 4 (1963), 9–33.
[15] M. I. Hartley, All polytopes are quotients, and isomorphic polytopes are quotients by conjugate subgroups, Discrete & Computational Geometry 21 (1999), 289–298. · Zbl 0927.52017 · doi:10.1007/PL00009422
[16] I. Hubard, A. Orbanic and A. I. Weiss, Monodromy groups and self-invariance, Canadian Journal of Mathematics 61 (2009), 1300–1324. · Zbl 1204.51023 · doi:10.4153/CJM-2009-061-5
[17] R. Jajcay, The structure of automorphism groups of Cayley graphs and maps, Journal of Algebraic Combinatorics 12 (2000), 73–84. · Zbl 1043.05061 · doi:10.1023/A:1008763602097
[18] G. Kalai, A simple way to tell a simple polytope form its graph, Journal of Combinatorial Theory. Series A, 49 (1988), 381–383. · Zbl 0673.05087 · doi:10.1016/0097-3165(88)90064-7
[19] W. Kühnel, Triangulations of manifolds with few vertices, in Advances in Differential Geometry and Topology, World Sci. Publ., Teaneck, NJ, 1990, pp. 59–114.
[20] S. Lins and A. Mandel, Graph-encoded 3-manifolds, Discrete Mathematics 57 (1985), 261–284. · Zbl 0585.57009 · doi:10.1016/0012-365X(85)90179-7
[21] P. McMullen and E. Schulte, Abstract Regular Polytopes, Cambridge University Press, Cambridge, 2002. · Zbl 1039.52011
[22] B. Monson and A. Ivić Weiss, Medial layer graphs of equivelar 4-polytopes, European Journal of Combinatorics 28 (2007), 43–60. · Zbl 1110.52016 · doi:10.1016/j.ejc.2005.10.001
[23] B. Monson and A. Ivić Weiss, Cayley graphs and symmetric 4-polytopes, Ars Mathematica Contemporanea 1 (2008), 185–205. · Zbl 1162.05027
[24] B. Monson, T. Pisanski, E. Schulte and A.I. Weiss, Semisymmetric graphs from polytopes, Journal of Combinatorial Theory. Series A 114 (2007), 421–435. · Zbl 1117.05051 · doi:10.1016/j.jcta.2006.06.007
[25] A. Orbanic, D. Pellicer and A. I. Weiss, Map operation and k-orbit maps, Journal of Combinatorial Theory. Series A 117 (2010), 411–429. · Zbl 1197.51005 · doi:10.1016/j.jcta.2009.09.001
[26] M. Pezzana, Sulla struttura topologica delle varità compatte, Atti del Seminario Matematico e Fisico dell’ Universitá di Modena 23 (1974), 269–277.
[27] T. Pisanski, E. Schulte and A. I. Weiss, On the size of equifacetted semi-regular polytopes, Glasnik Matematički, to appear. · Zbl 1266.51032
[28] P. H. Schoute, Analytic treatment of the polytopes regulary derived from the regular polytopes, Verhandelingen der Koninklijke Akademie van Wetwenschappen te Amsterdam 11, No. 3, Johannes Müller, Amsterdam, 1911, 87 pp.
[29] E. Schulte, Reguläre Inzidenzkomplexe, II, Geometriae Dedicata 14 (1983), 33–56.
[30] A. Vince, Combinatorial maps, Journal of Combinatorial Theory. Series B 34 (1983), 1–21. · Zbl 0505.05054 · doi:10.1016/0095-8956(83)90002-3
[31] A. Vince, Regular combinatorial maps, Journal of Combinatorial Theory. Series B 35 (1983), 256–277. · Zbl 0524.05033 · doi:10.1016/0095-8956(83)90053-9
[32] V. G. Vizing, On and estimate of the chromatic class of a p-graph, Akademiya Nauk SSSR. Sibirskoe Otdelenie. Institut Matematiki. Diskretnyĭ Analiz. Sbornik Trudov 3 (1964), 25–30.
[33] V. G. Vizing, Critical graphs with a given chromatic class, Akademiya Nauk SSSR. Sibirskoe Otdelenie. Institut Matematiki. Diskretnyĭ Analiz. Sbornik Trudov 5 (1965), 9–17.
[34] G. Ziegler, Lectures on Polytopes, Springer-Verlag, New York, 1994. · Zbl 0890.60029
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.