Lower bounds on coloring numbers from hardness hypotheses in pcf theory

Shelah, Saharon

doi:10.1090/proc/13163

Lower bounds on coloring numbers from hardness hypotheses in pcf theory
HTML articles powered by AMS MathViewer

by Saharon Shelah PDF

Proc. Amer. Math. Soc. 144 (2016), 5371-5383 Request permission

Abstract:

We prove that the statement “for every infinite cardinal $\kappa$, every graph with list-chromatic number $\kappa$ has coloring number at most $\beth _\omega (\kappa )$” proved by Kojman (2014) using the RGCH theorem implies the WRGCH theorem, which is a weaker relative of the RGCH, via a short forcing argument.

Similarly, a better upper bound than $\beth _\omega (\kappa )$ in this statement implies stronger (consistent) forms of the WRGCH theorem, the consistency of whose negations is wide open.

Thus, the optimality of Kojman’s upper bound is a purely cardinal arithmetic problem, and, as discussed below, is hard to decide.

References

Noga Alon, Degrees and choice numbers, Random Structures Algorithms 16 (2000), no. 4, 364–368. MR 1761581, DOI 10.1002/1098-2418(200007)16:4<364::AID-RSA5>3.3.CO;2-S
P. Erdős and A. Hajnal, On chromatic number of graphs and set-systems, Acta Math. Acad. Sci. Hungar. 17 (1966), 61–99. MR 193025, DOI 10.1007/BF02020444
Paul Erdős, Arthur L. Rubin, and Herbert Taylor, Choosability in graphs, Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing (Humboldt State Univ., Arcata, Calif., 1979) Congress. Numer., XXVI, Utilitas Math., Winnipeg, Man., 1980, pp. 125–157. MR 593902
M. Gitik, Short Extenders Forcing II., preprint. http://www.math.tau.ac.il/$\sim$gitik/somepapers.html
Moti Gitik and Saharon Shelah, Applications of pcf for mild large cardinals to elementary embeddings, Ann. Pure Appl. Logic 164 (2013), no. 9, 855–865. MR 3056300, DOI 10.1016/j.apal.2013.03.002
Péter Komjáth, The list-chromatic number of infinite graphs, Israel J. Math. 196 (2013), no. 1, 67–94. MR 3096584, DOI 10.1007/s11856-012-0145-6
Menachem Kojman, Shelah’s revised GCH theorem and a question by Alon on infinite graphs colorings, Israel J. Math. 201 (2014), no. 2, 585–592. MR 3265296, DOI 10.1007/s11856-014-0035-1
Shmuel Lifsches and Saharon Shelah, Random graphs in the monadic theory of order, Arch. Math. Logic 38 (1999), no. 4-5, 273–312. Logic Colloquium ’95 (Haifa). MR 1697962, DOI 10.1007/s001530050129
Saharon Shelah, A compactness theorem for singular cardinals, free algebras, Whitehead problem and transversals, Israel J. Math. 21 (1975), no. 4, 319–349. MR 389579, DOI 10.1007/BF02757993
S. Shelah, Compactness in singular cardinals revisited, 266 in Shelah-s list, preprint. arxiv:math.LO/1401.3175
Saharon Shelah, More on cardinal arithmetic, Arch. Math. Logic 32 (1993), no. 6, 399–428. MR 1245523, DOI 10.1007/BF01270465
Saharon Shelah, Advances in cardinal arithmetic, Finite and infinite combinatorics in sets and logic (Banff, AB, 1991) NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., vol. 411, Kluwer Acad. Publ., Dordrecht, 1993, pp. 355–383. MR 1261217
Saharon Shelah, The generalized continuum hypothesis revisited, Israel J. Math. 116 (2000), 285–321. MR 1759410, DOI 10.1007/BF02773223
Shmuel Lifsches and Saharon Shelah, Random graphs in the monadic theory of order, Arch. Math. Logic 38 (1999), no. 4-5, 273–312. Logic Colloquium ’95 (Haifa). MR 1697962, DOI 10.1007/s001530050129
Saharon Shelah, Was Sierpiński right? IV, J. Symbolic Logic 65 (2000), no. 3, 1031–1054. MR 1791363, DOI 10.2307/2586687
Saharon Shelah, Anti-homogeneous partitions of a topological space, Sci. Math. Jpn. 59 (2004), no. 2, 203–255. Special issue on set theory and algebraic model theory. MR 2062196
Saharon Shelah, Two cardinals models with gap one revisited, MLQ Math. Log. Q. 51 (2005), no. 5, 437–447. MR 2163755, DOI 10.1002/malq.200410036
Saharon Shelah, Pcf and abelian groups, Forum Math. 25 (2013), no. 5, 967–1038. MR 3100959, DOI 10.1515/forum-2013-0119
S. Shelah, Forcing axioms for $\lambda$-complete $\mu ^+$-c.c., 1036 in Shelah-s list; preprint.