Crossing Numbers and Hard Erdős Problems in Discrete Geometry
The main aim of the author is to derive short proofs for a number of theorems in discrete geometry from the following theorem and from a generalization of this theorem. Theorem: For any simple graph \(G\) with \(n\) vertices and \(e\geq 4n\) edges, the crossing number of \(G\) on the plane is at least \(e^{3-}/(10n)^2\). [\textit{M. Ajtai}, \textit{V. Chvatal}, \textit{M. M. Newborn} and \textit{E. Szemerédi}, Ann. Discrete Math. 12, 9--12 (1982; Zbl 0502.05021) and \textit{F. T. Leighton} [Complexity issues in VLSI. Cambridge, MA: MIT Press (1983), pbk (2003)]. For the generalization of a simple graph drawn on an orientable or nonorientable compact 2-manifold see \textit{F. Shahrokhi}, \textit{L. Székely} \textit{O. Sýkora} and \textit{I. Vrtó}, Algorithmica 16, No. 1, 118--131 (1996; Zbl 0854.68074) and Adv. Math. 123, No. 2, 105--119 (1996; Zbl 0865.05036)]. (New) proofs are given for the following theorems (among other): -- For \(n\) points and \(\ell\) lines in the Euclidean plane, the number of incidences among the points and lines is at most \(c[(ne)^{2/3} +n+ \ell]\), where \(c\) is a constant. -- The number of unit distances among \(n\) points in the plane is at most \(cn^{4/3}\). -- When \(G\) is a multigraph with \(n\) nodes, \(e\) edges and maximum edge multiplicity \(m\), then either \(e<5nm\) or crossing number of \(G\geq ce^3/(n^2m)\). The last theorem has immediate consequence for incidences between points and curves in the plane.
- Unit distances and diameters in Euclidean spaces
- Degenerate crossing numbers
- Extremal problems on triangle areas in two and three dimensions
- On distinct distances among points in general position and other related problems
- Some provably hard crossing number problems
- Graphs drawn with few crossings per edge
- Cardinalities of k-distance sets in Minkowski spaces
- On distinct sums and distinct distances.
- A successful concept for measuring non-planarity of graphs: The crossing number.
- Additive combinatorics and graph theory
- The crossing number of locally twisted cubes \(L T Q_n\)
- Distinct distances between points and lines
- The number of crossings in multigraphs with no empty lens
- On the k-planar local crossing number
- Algebraic methods in sum-product phenomena
- A combinatorial problem on polynomials and rational functions
- On loops intersecting at most once
- On the number of edges of separated multigraphs
- An incidence estimate and a Furstenberg type estimate for tubes in \(\mathbb{R}^2\)
- On distinct distances between a variety and a point set
- The crossing number of twisted graphs
- A crossing lemma for multigraphs
- Rotation and crossing numbers for join products
- Solving linear equations in a vector space over a finite field
- Many touchings force many crossings
- Distinct distance estimates and low degree polynomial partitioning
- Three-point configurations determined by subsets of \({\mathbb{F}_q}^2\) via the Elekes-Sharir paradigm
- Sets with few distinct distances do not have heavy lines
- Iterated point-line configurations grow doubly-exponentially
- Cutting algebraic curves into pseudo-segments and applications
- Finite point configurations in the plane, rigidity and Erdős problems
- Forbidden paths and cycles in ordered graphs and matrices
- Nearly equal distances and Szemerédi's regularity lemma
- Simple algorithms for partial point set pattern matching under rigid motion
- On bipartite distinct distances in the plane
- Crossings between non-homotopic edges
- Distinct distances on non-ruled surfaces and between circles
- The Szemerédi-Trotter theorem in the complex plane
- Additive combinatorics: with a view towards computer science and cryptography -- an exposition
- Space crossing numbers
- Rational distances with rational angles
- Unit distances in three dimensions
- ON THE SATELLITE CROSSING NUMBER CONJECTURE
- Crossing numbers of imbalanced graphs
- Graph minors and the crossing number of graphs
- Incidences with curves in \(\mathbb{R}^{d}\)
- On sets of directions determined by subsets of \(\mathbb R^d\)
- On a Question of Bourgain about Geometric Incidences
- A combinatorial distinction between unit circles and straight lines: how many coincidences can they have?
- Geometric incidence theorems via Fourier analysis
- Crossings in grid drawings
- Progress on Dirac's conjecture
- Degrees of nonlinearity in forbidden 0-1 matrix problems
- An incidence theorem in higher dimensions
- On totally positive matrices and geometric incidences
- Robust Tverberg and Colourful Carathéodory Results via Random Choice
- Drawing outerplanar graphs using three edge lengths
- Szemerédi-Trotter-type theorems in dimension 3
- On locally Gabriel geometric graphs
- Quantitative restrictions on crossing patterns
- Crossings Between Non-homotopic Edges
- Sumsets of semiconvex sets
- Highly incidental patterns on a quadratic hypersurface in \(\mathbb{R}^4\)
- The number of crossings in multigraphs with no empty lens
- Structure and generation of crossing-critical graphs
- A crossing lemma for multigraphs
- Incidences in three dimensions and distinct distances in the plane
- Incidences between points and lines in \({\mathbb {R}}^4\)
- Ghost chimneys
- Improved bounds for incidences between points and circles
- Distinct distances from three points
- On the Richter–Thomassen Conjecture about Pairwise Intersecting Closed Curves
- A Bipartite Strengthening of the Crossing Lemma
- Crossing Numbers and Parameterized Complexity
- ALGORITHMS FOR POINT SET MATCHING WITH k-DIFFERENCES
- From harmonic analysis to arithmetic combinatorics
- Turán's brick factory problem: the status of the conjectures of Zarankiewicz and Hill
- On the Origins, Nature, and Impact of Bourgain’s Discretized Sum-Product Theorem
- Radial points in the plane
- General lower bounds for the minor crossing number of graphs
- Combinatorics. Abstracts from the workshop held January 1--7, 2023
- From art and circuit design to geometry and combinatorics
- Classification of maps sending lines into translates of a curve
- The number of unit distances is almost linear for most norms
- Extremal problems for geometric hypergraphs
- The Dirac-Goodman-Pollack conjecture
- On forbidden configurations in point-line incidence graphs
- Semi-algebraic off-line range searching and biclique partitions in the plane
- On the number of digons in arrangements of pairwise intersecting circles
- General position subset selection in line arrangements
- Improving the crossing lemma by characterizing dense 2-planar and 3-planar graphs
- Approximate incidence geometry in the plane
- More unit distances in arbitrary norms
- Bounds on distinct and repeated dot product trees
- On the number of edges of separated multigraphs
- On the number of incidences when avoiding an induced biclique in geometric settings
- Unit and distinct distances in typical norms
- Complexity of non-abelian cut-and-project sets of polytopal type. I: Special homogeneous Lie groups
- Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique
- On the connectivity of visibility graphs
This page was built for publication: Crossing Numbers and Hard Erdős Problems in Discrete Geometry
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4354594)
