×

Deciding the chromatic numbers of algebraic hypergraphs. (English) Zbl 1385.05034

Summary: For each infinite cardinal \(\kappa\), the set of algebraic hypergraphs having chromatic number no larger than \(\kappa\) is decidable.

MSC:

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

References:

[1] BaumgartnerJ. E., Canonical partition relations, this Journal, 40 (1975), pp. 541-554. · Zbl 0325.04006
[2] BochnakJ., CosteM., and RoyM.-F., Real Algebraic Geometry, Ergebnisse der Mathematik und ihrer Grenzgebiete (3), vol. 36, Springer-Verlag, Berlin, 1998. · Zbl 0633.14016
[3] BasuS., PollackR., and RoyM.-F., Algorithms in Real Algebraic Geometry, second ed., Algorithms and Computation in Mathematics, vol. 10, Springer-Verlag, Berlin, 2006. · Zbl 1102.14041
[4] CederJ., Finite subsets and countable decompositions of Euclidean spaces. Revue Roumaine de Mathématiques Pures et Appliquées, vol. 14 (1969), pp. 1247-1251. · Zbl 0188.27604
[5] DaviesR. O., Partitioning the plane into denumberably many sets without repeated distances. Proceedings of the Cambridge Philosophical Society, vol. 72 (1972), pp. 179-183.10.1017/S0305004100046983 · Zbl 0321.04005
[6] ErdősP. and KomjáthP., Countable decompositions of R^2 and R^3. Discrete & Computational Geometry, vol. 5 (1990), pp. 325-331.10.1007/BF02187793 · Zbl 0723.52005
[7] FoxJ., An infinite color analogue of Rado’s theorem. Journal of Combinatorial Theory, Series A, vol. 114 (2007), pp. 1456-1469.10.1016/j.jcta.2007.02.005 · Zbl 1127.05102
[8] KomjáthP., Tetrahedron free decomposition of R^3. Bulletin of the London Mathematical Society, vol. 23 (1991), pp. 116-120.10.1112/blms/23.2.116 · Zbl 0759.05001
[9] KunenK., Partitioning Euclidean space. Mathematical Proceedings of the Cambridge Philosophical Society, vol. 102 (1987), pp. 379-383.10.1017/S0305004100067426S0305004100067426 · Zbl 0657.51009
[10] SchmerlJ. H., Partitioning Euclidean space. Discrete & Computational Geometry, vol. 10 (1993), pp. 101-106.10.1007/BF02573966 · Zbl 0782.51003
[11] SchmerlJ. H., Triangle-free partitions of Euclidean space. Bulletin of the London Mathematical Society, vol. 26 (1994), pp. 483-486.10.1112/blms/26.5.483 · Zbl 0827.51016
[12] SchmerlJ. H., Countable partitions of Euclidean space. Mathematical Proceedings of the Cambridge Philosophical Society, vol. 120 (1996), pp. 7-12.10.1017/S0305004100074612 · Zbl 0887.51013
[13] SchmerlJ. H., Avoidable algebraic subsets of Euclidean space. Transactions of the American Mathematical Society, vol. 352 (2000), pp. 2479-2489.10.1090/S0002-9947-99-02331-4 · Zbl 0948.03045
[14] SchmerlJ. H., Chromatic numbers of algebraic hypergraphs. Combinatorica (2016), pp. 1-16.
[15] van den DriesL, Algebraic theories with definable Skolem functions, this Journal, vol. 49 (1984), pp. 625-629. · Zbl 0596.03032
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.