Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-11T03:02:52.238Z Has data issue: false hasContentIssue false
  • English
  • Français

GRAPHS ON EUCLIDEAN SPACES DEFINED USING TRANSCENDENTAL DISTANCES

Part of: Set theory Real and complex geometry

Published online by Cambridge University Press:  14 June 2011

Péter Komjáth  and
James Schmerl
Péter Komjáth
Affiliation:
Department of Computer Science, Eötvös University, PO Box 120, Budapest, 1518, Hungary (email: kope@cs.elte.hu)
James Schmerl
Affiliation:
Department of Mathematics, University of Connecticut, Storrs, CT 06269-3009, U.S.A. (email: james.schmerl@uconn.edu)

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Given a set D of positive real numbers, let Xn(D) denote the graph with ℝn as the vertex set such that two points are joined if their distance is in D. Bukh conjectured in [Measurable sets with excluded distances. Geom. Funct. Anal.18 (2008), 668–697] that if D is algebraically independent, then Chr(Xn(D)), the chromatic number of Xn(D), is finite. Here we prove that Chr(Xn(D)) is countable and that, if n=2 , even the coloring number is countable. Furthermore, we prove that Chr (Y )is countable, where Y is the following graph on ℂn: let 𝔽 be a countable subfield of ℂ and let D⊆ℂ be algebraically independent over 𝔽; join a,b∈ℂn if there is some p(x,y)∈𝔽[x,y]such that p(x,x)is identically zero and p(a,b)≠0is algebraic over some d∈𝔽∪D.

MSC classification

Secondary: 03E05: Other combinatorial set theory 51M05: Euclidean geometries (general) and generalizations

Information

Type
Research Article
Information
Mathematika , Volume 58 , Issue 1 , January 2012 , pp. 1 - 9
Copyright
Copyright © University College London 2012

References

[1]Bukh, B., Measurable sets with excluded distances. Geom. Funct. Anal. 18 (2008), 668–697.CrossRefGoogle Scholar
[2]Erdős, P., Problems and results in chromatic number theory. In Proof Techniques in Graph Theory (ed. Harary, F.), Academic Press (New York, 1969), 47–55.Google Scholar
[3]Erdős, P. and Hajnal, A., On chromatic number of graphs and set systems. Acta Math. Acad. Sci. Hungar. 17 (1966), 61–99.CrossRefGoogle Scholar
[4]Erdős, P. and Komjáth, P., Countable decompositions of ℝ2 and ℝ3. Discrete Comput. Geom. 5 (1990), 325–331.CrossRefGoogle Scholar
[5]Jacobson, N., Basic Algebra II, W. H. Freeman and Company (New York, 1989).Google Scholar
[6]Komjáth, P., A decomposition theorem for ℝn. Proc. Amer. Math. Soc. 120 (1994), 921–924.Google Scholar
[7]Komjáth, P., The list-chromatic number of infinite graphs defined on Euclidean spaces. Discrete Comput. Geom. 45 (2011), 497–502.CrossRefGoogle Scholar
[8]Komjáth, P. and Totik, V., Problems and Theorems in Classical Set Theory, Springer (New York, 2006).Google Scholar
[9]Schmerl, J. H., Countable partitions of Euclidean space. Math. Proc. Cambridge Philos. Soc. 120 (1996), 7–12.CrossRefGoogle Scholar