Axiom of choice and chromatic number of the plane

DOI10.1016/S0097-3165(03)00102-XMaRDI QIDQ1406751zbMATH OpenWikidataFDO

Authors S. Shelah, Alexander Soifer

Publication date 7 September 2003

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0097-3165(03)00102-X

zbMATH Keywords

axiom of countable choicechromatic numberLebesgue measurable set

Mathematics Subject Classification ID

Axiom of choice and related propositions (03E25) Coloring of graphs and hypergraphs (05C15)

Review text

Let \(U^2\) be the graph with underlying set \(\mathbb{R}^2\) and with two points adjacent iff their distance is one. It is an old problem to determine the chromatic number of \(U^2\). So far it is known that it can be 4, 5, 6 or 7. Further on it is known that it is at least 5 if monochromatic sets are Lebesgue measurable. The authors investigate the following example: Let \(G\) be the graph with underlying set \(\mathbb{R}\) and the set of edges \(\{(s,t): s- t-\sqrt{2}\in \mathbb{Q}\}\). They show that in ZFC the chromatic number of \(U\) is equal to 2. But assuming the countable axiom of choice and that every set of reals is Lebesgue measurable, the chromatic number of \(U\) cannot be equal to any positive integer \(n\) nor even to \(\aleph_0\).

Recommendations

• Axiom of choice and chromatic number of \(R^n\)
• Graph colorings and the axiom of choice
• The role of the Axiom of Choice in proper and distinguishing colourings
• scientific article; zbMATH DE number 1552837
• On the chromatic number of subsets of the Euclidean plane
• scientific article; zbMATH DE number 2042230
• The chromatic number of the plane: the bounded case
• scientific article; zbMATH DE number 2170328
• Almost-monochromatic sets and the chromatic number of the plane

Cites work

• A model of set-theory in which every set of reals is Lebesgue measurable
• A system of axiomatic set theory. Part III. Infinity and enumerability. Analysis
• scientific article; zbMATH DE number 51916 (Why is no real title available?)
• scientific article; zbMATH DE number 2042230 (Why is no real title available?)
• scientific article; zbMATH DE number 2140325 (Why is no real title available?)
• scientific article; zbMATH DE number 3068973 (Why is no real title available?)
• The axiom of choice
• The realization of distances in measurable subsets covering R^ n.
• Unsolved problems in geometry

Cited in

(20)

• Graph colorings and the axiom of choice
• Axiom of choice and chromatic number of \(R^n\)
• On rainbow isosceles \(n\)-simplexes
• On configurations of solid balls in 3-space: chromatic numbers and knotted cycles
• Same graph, different universe
• Clique numbers of finite unit-quadrance graphs
• Orthogonal colorings of the sphere
• On the chromatic number of an infinitesimal plane layer
• scientific article; zbMATH DE number 2170328 (Why is no real title available?)
• scientific article; zbMATH DE number 2094516 (Why is no real title available?)
• scientific article; zbMATH DE number 2112063 (Why is no real title available?)
• Book review of: Alexander Soifer, The mathematical coloring book. Mathematics of coloring and the colorful life of its creators
• Graph-Coloring and Choice a Note on a Note by Shelah and Soifer
• COMPUTATIONAL GEOMETRY COLUMN 46
• Axiom of choice and chromatic number: Examples on the plane
• Coloring distance graphs on the plane
• Chromatic numbers of Cayley graphs of abelian groups: a matrix method
• Distinguishing colorings, proper colorings, and covering properties without \textsf{AC}
• Brooks' type theorems for coloring parameters of locally finite graphs and Kőnig's Lemma
• On Rado's boundedness conjecture

This page was built for publication: Axiom of choice and chromatic number of the plane

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1406751)