×

Coloring \(d\)-embeddable \(k\)-uniform hypergraphs. (English) Zbl 1306.05060

Summary: This paper extends the scenario of the four color theorem in the following way. Let \(\mathcal H_{d,k}\) be the set of all \(k\)-uniform hypergraphs that can be (linearly) embedded into \(\mathbb R^d\). We investigate lower and upper bounds on the maximum (weak) chromatic number of hypergraphs in \(\mathcal H_{d,k}\). For example, we can prove that for \(d\geq 3\) there are hypergraphs in \(\mathcal H_{2d-3,d}\) on \(n\) vertices whose chromatic number is \(\Omega (\log n/\log\log n)\), whereas the chromatic number for \(n\)-vertex hypergraphs in \(\mathcal H_{d,d}\) is bounded by \(\mathcal O(n^{(d-2)/(d-1)})\) for \(d\geq 3\).

MSC:

05C15 Coloring of graphs and hypergraphs
05C65 Hypergraphs
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Appel, K., Haken, W.: Every planar map is four colorable. Part I: discharging. Ill. J. Math. 213, 429-490 (1977) · Zbl 0387.05009
[2] Appel, K., Haken, W., Koch, J.: Every planar map is four colorable. Part II: reducibility. Ill. J. Math. 213, 491-567 (1977) · Zbl 0387.05010
[3] Bokowski, J., Guedes de Oliveira, A.: On the generation of oriented matroids. Discrete Comput. Geom. 24, 197-208 (2000) · Zbl 0969.52008 · doi:10.1007/s004540010027
[4] Brehm, U.: A nonpolyhedral triangulated Möbius strip. Proc. Am. Math. Soc. 89(3), 519-522 (1983) · Zbl 0526.57013
[5] Bryant, J.L.: Approximating embeddings of polyhedra in codimension three. Trans. Am. Math. Soc. 170, 85-95 (1972) · Zbl 0259.57007 · doi:10.1090/S0002-9947-1972-0307245-7
[6] Carathéodory, C.: Über den Variabilitätsbereich der Koeffizienten von Potenzreihen die gegebene Werte nicht annehmen. Math. Ann. 64, 95-115 (1907) · JFM 38.0448.01 · doi:10.1007/BF01449883
[7] Carathéodory, C.: Über den Variabilitätsbereich der Fourierschen Konstanten von positiven harmonischen Funktionen. Rendiconti del Circolo Matematico di Palermo 32, 193-217 (1911) · JFM 42.0429.01 · doi:10.1007/BF03014795
[8] Dey, T.K., Pach, J.: Extremal problems for geometric hypergraphs. Discrete Comput. Geom. 19, 473-484 (1998) · Zbl 0902.05054 · doi:10.1007/PL00009365
[9] Erdős, P., Lovász, L.: Problems and results on 3-chromatic hypergraphs and some related questions. In: Infinite and Finite Sets (to Paul Erdős on his 60th birthday), vol. II., pp. 609-627. North-Holland, Amsterdam (1975) · Zbl 0315.05117
[10] Flores, A.: Über die Existenz \[n\] n-dimensionale Komplexe, die nicht in den \[{\mathbb{R}}_{2n}\] R2n topologisch einbettbar sind. Ergebnisse eines Mathematischen Kolloquiums 5, 17-24 (1933) · Zbl 0007.36803
[11] Flores, A.: Über \[n\] n-dimensionale Komplexe, die im \[{\mathbb{R}}_{2n+1}\] R2n+1 absolut selbstverschlungen sind. Ergebnisse eines Mathematischen Kolloquiums 6, 4-7 (1934)
[12] Fáry, I.: On straight-line representation of planar graphs. Acta Scientiarum Mathematicarum Szeged 11, 229-233 (1948) · Zbl 0030.17902
[13] Gale, D.: Neighborly and cyclic polytopes. In: Convexity: Proceedings of the Seventh Symposium in Pure Mathematics of the American Mathematical Society, pp. 225-232 (1963) · Zbl 0137.41801
[14] Graham, R., Grötschel, M., Lovász, L. (eds.), Handbook of Combinatorics, vol. 1. North-Holland, Amsterdam (1995) · Zbl 0833.05001
[15] Grünbaum, B.: Higher-dimensional analogs of the four-color problem and some inequalities for simplicial complexes. J. Comb. Theory 8(2), 147-153 (1970) · Zbl 0199.27204 · doi:10.1016/S0021-9800(70)80071-0
[16] Gundert, A.: On the Complexity of Embeddable Simplicial Complexes. Diplomarbeit. Freie Universität Berlin (2009). http://www.inf.ethz.ch/personal/gunderta/files/Diplomarbeit.pdf · Zbl 0155.51201
[17] Heawood, J.C.: Map-colour theorem. Q. J. Pure Appl. Math. 24, 332-338 (1890) · JFM 22.0562.02
[18] Kalai, G.: Algebraic shifting. Adv. Stud. Pure Math. 33, 121-163 (2002) · Zbl 1034.57021
[19] Matoušek, J., Tancer, M., Wagner, U.: Hardness of embedding simplicial complexes in \[{\mathbb{R}}^d\] Rd. J. Eur. Math. Soc. 13, 259-295 (2011) · Zbl 1208.68130 · doi:10.4171/JEMS/252
[20] Menger, K.: Dimensionstheorie. Teubner, Leipzig (1928) · doi:10.1007/978-3-663-16056-4
[21] Motzkin, T.S.: Comonotone curves and polyhedra, Abstract 111. Bull. Am. Math. Soc. 63, 35 (1957) · doi:10.1090/S0002-9904-1957-10103-7
[22] Nöbeling, G.: Über eine \[n\] n-dimensionale Universalmenge im \[{\mathbb{R}}_{2n+1}\] R2n+1. Math. Ann. 104(1), 71-80 (1931) · JFM 56.0506.02 · doi:10.1007/BF01457921
[23] Renegar, J.: On the computational complexity and geometry of the first-order theory of the reals. I, II, III. J. Symb. Comput. 13(3), 255-299, 301-327, 329-352 (1992) · Zbl 0763.68042
[24] Ringel, G., Youngs, J.W.T.: Solution of the Heawood map-coloring problem. Proc. Natl. Acad. Sci. USA 60(2), 438-445 (1968) · Zbl 0155.51201 · doi:10.1073/pnas.60.2.438
[25] Rourke, C.P., Sanderson, B.J.: Introduction to Piecewise-Linear Topology. Ergebnisse der Mathematik und ihrer Grenzgebiete, vol. 69. Springer, Berlin (1972) · Zbl 0254.57010
[26] Sarkaria, K.S.: Heawood inequalities. J. Comb. Theory Ser. A 46(1), 50-78 (1987) · Zbl 0628.05029 · doi:10.1016/0097-3165(87)90076-8
[27] Schild, G.: Some minimal nonembeddable complexes. Topol. Appl. 53(2), 177-185 (1993) · Zbl 0817.57022 · doi:10.1016/0166-8641(93)90135-Z
[28] Schlegel, V.: Theorie der homogen zusammengesetzten Raumgebilde. Nova Acta Leopold. 44, 4 (1883) · JFM 15.0463.01
[29] Shephard, G.C.: A theorem on cyclic polytopes. Israel J. Math. 6(4), 368-372 (1968) · Zbl 0174.25403 · doi:10.1007/BF02771216
[30] Spencer, J.: Asymptotic lower bounds for Ramsey functions. Discrete Math. 20, 69-76 (1977) · Zbl 0375.05033 · doi:10.1016/0012-365X(77)90044-9
[31] Van Kampen, E.R.: Komplexe in euklidischen Räumen. Abh. Math. Semin. Univ. Hamburg 9(1), 72-78, corrections ibidem, pp. 152-153 (1933) · JFM 58.0615.02
[32] White, A.T.: Graphs of Groups on Surfaces: Interactions and Models. Mathematics Studies, vol. 188. North-Holland, Amsterdam (2001) · Zbl 1054.05001
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.