Hostname: page-component-745bb68f8f-lrblm Total loading time: 0 Render date: 2025-02-07T01:12:08.079Z Has data issue: false hasContentIssue false
  • English
  • Français

Space Crossing Numbers

Published online by Cambridge University Press:  16 March 2012

BORIS BUKH  and
ALFREDO HUBARD
BORIS BUKH
Affiliation:
DPMMS, Centre for Mathematical Sciences, University of Cambridge, Cambridge CB3 0WA, UK and Churchill College, Cambridge CB3 0DS, UK (e-mail: B.Bukh@dpmms.cam.ac.uk)
ALFREDO HUBARD
Affiliation:
Courant Institute of Mathematical Sciences, New York University, NY 10012-1185, USA (e-mail: hubard@cims.nyu.edu)
Rights & Permissions [Opens in a new window]

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.

We define a variant of the crossing number for an embedding of a graph G into ℝ3, and prove a lower bound on it which almost implies the classical crossing lemma. We also give sharp bounds on the rectilinear space crossing numbers of pseudo-random graphs.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 21 , Issue 3 , May 2012 , pp. 358 - 373
Copyright
Copyright © Cambridge University Press 2012

References

[1]Agarwal, P. K. and Matoušek, J. (1992) On range searching with semialgebraic sets. In Mathematical Foundations of Computer Science: Prague 1992, Vol. 629 of Lecture Notes in Computer Science, Springer, pp. 1–13.Google Scholar
[2]Ajtai, M., Chvátal, V., Newborn, M. M. and Szemerédi, E. (1982) Crossing-free subgraphs. In Theory and Practice of Combinatorics, Vol. 60 of North-Holland Math. Stud., North-Holland, pp. 9–12.Google Scholar
[3]Bárány, I. and Valtr, P. (1998) A positive fraction Erdős–Szekeres theorem. Discrete Comput. Geom. 19 335–342.CrossRefGoogle Scholar
[4]Basu, S., Pollack, R. and Roy, M.-F. (2006) Algorithms in Real Algebraic Geometry, Vol. 10 of Algorithms and Computation in Mathematics, second edition, Springer. perso.univ-rennes1.fr/marie-francoise.roy/bpr-ed2-posted2.htmlCrossRefGoogle Scholar
[5]Bienstock, D. and Dean, N. (1993) Bounds for rectilinear crossing numbers. J. Graph Theory 17 333–348.CrossRefGoogle Scholar
[6]Bollobás, B. and Scott, A. D. (1993) Judicious partitions of graphs. Period. Math. Hungar. 26 125–137.CrossRefGoogle Scholar
[7]Bredon, G. E. (1993) Topology and Geometry, Vol. 139 of Graduate Texts in Mathematics, Springer.CrossRefGoogle Scholar
[8]Bukh, B., Matoušek, J. and Nivasch, G.Lower bounds for weak epsilon-nets and stair-convexity. Israel J. Math. 182 199–228.CrossRefGoogle Scholar
[9]Conway, J. H. and Gordon, C. M. (1983) Knots and links in spatial graphs. J. Graph Theory 7 445–453.CrossRefGoogle Scholar
[10]Dey, T. K. (1998) Improved bounds for planar k-sets and related problems. Discrete Comput. Geom. 19 373–382.CrossRefGoogle Scholar
[11]Diestel, R. (2005) Graph Theory, Vol. 173 of Graduate Texts in Mathematics, third edition, Springer.Google Scholar
[12]Fox, J., Gromov, M., Lafforgue, V., Naor, A. and Pach, J. (2010) Overlap properties of geometric expanders. J. Reine Angew. Math., to appear. arXiv:1005.1392Google Scholar
[13]Karasev, R. N. (2007) Tverberg's transversal conjecture and analogues of nonembeddability theorems for transversals. Discrete Comput. Geom. 38 513–525.CrossRefGoogle Scholar
[14]Kostochka, A. and Pyber, L. (1988) Small topological complete subgraphs of ‘dense’ graphs. Combinatorica 8 83–86.CrossRefGoogle Scholar
[15]Krivelevich, M. and B. Sudakov, B. (2006) Pseudo-random graphs. In More Sets, Graphs and Numbers, Vol. 15 of Bolyai Soc. Math. Stud., Springer, pp. 199–262.CrossRefGoogle Scholar
[16]Lehec, J. (2009) On the Yao-Yao partition theorem. Arch. Math. (Basel) 92 366–376. arXiv:1011.2123CrossRefGoogle Scholar
[17]Leighton, F. T. (1984) New lower bound techniques for VLSI. Math. Systems Theory 17 47–70.CrossRefGoogle Scholar
[18]Nivasch, G. (2009) Weak epsilon-nets, Davenport–Schinzel sequences, and related problems. PhD thesis, Tel Aviv University. people.inf.ethz.ch/gnivasch/publications/papers/phd_thesis.pdfGoogle Scholar
[19]Pach, J., Shahrokhi, F. and Szegedy, M. (1996) Applications of the crossing number. Algorithmica 16 111–117. www.cims.nyu.edu/string~pach/publications/mario.pdfCrossRefGoogle Scholar
[20]Pach, J. and Tóth, G. (1997) Graphs drawn with few crossings per edge. Combinatorica 17 427–439.CrossRefGoogle Scholar
[21]Riskin, A. (1996) The crossing number of a cubic plane polyhedral map plus an edge. Studia Sci. Math. Hungar. 31 405–413.Google Scholar
[22]Sachs, H. (1983) On a spatial analogue of Kuratowski's theorem on planar graphs: An open problem. In Graph Theory: Łagów 1981, Vol. 1018 of Lecture Notes in Mathematics, Springer, pp. 230–241.CrossRefGoogle Scholar
[23]Székely, L. A. (1997) Crossing numbers and hard Erdős problems in discrete geometry. Combin. Probab. Comput. 6 353–358.CrossRefGoogle Scholar
[24]Viro, J. (2009) Lines joining components of a link. J. Knot Theory Ramifications 18 865–888. arXiv:math/0511527CrossRefGoogle Scholar
[25]Yao, A. C. and Yao, F. F. (1985) A general approach to d-dimensional geometric queries. In Proc. 17th Annual ACM Symposium on Theory of Computing: STOC '85, ACM, pp. 163–168.CrossRefGoogle Scholar
[26]Živaljević, R. T. (1999) The Tverberg–Vrećica problem and the combinatorial geometry on vector bundles. Israel J. Math. 111 53–76.CrossRefGoogle Scholar