Hostname: page-component-78c5997874-t5tsf Total loading time: 0 Render date: 2024-11-12T20:14:24.009Z Has data issue: false hasContentIssue false
  • English
  • Français

GRAPHS ON EUCLIDEAN SPACES DEFINED USING TRANSCENDENTAL DISTANCES

Part of: Real and complex geometry Set theory

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: [email protected])
James Schmerl
Affiliation:
Department of Mathematics, University of Connecticut, Storrs, CT 06269-3009, U.S.A. (email: [email protected])
Get access

Abstract

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)≠0 is algebraic over some d∈𝔽∪D.

MSC classification

Secondary: 03E05: Other combinatorial set theory 51M05: Euclidean geometries (general) and generalizations
Type
Research Article
Information
Mathematika , Volume 58 , Issue 1 , January 2012 , pp. 1 - 9
Copyright
Copyright © University College London 2012

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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