Crossing Numbers and Hard Erdős Problems in Discrete Geometry
From MaRDI portal
Publication:4354594
DOI10.1017/S0963548397002976zbMath0882.52007OpenAlexW2101764588WikidataQ55954540 ScholiaQ55954540MaRDI QIDQ4354594
Publication date: 11 February 1998
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1017/s0963548397002976
Extremal problems in graph theory (05C35) Erd?s problems and related topics of discrete geometry (52C10)
Related Items
Distinct distances with \(\ell_p\) metrics ⋮ The Szemerédi-Trotter theorem in the complex plane ⋮ On the Origins, Nature, and Impact of Bourgain’s Discretized Sum-Product Theorem ⋮ Additive combinatorics and graph theory ⋮ Space Crossing Numbers ⋮ RATIONAL DISTANCES WITH RATIONAL ANGLES ⋮ Incidences with Curves in ℝ d ⋮ GHOST CHIMNEYS ⋮ Unit Distances in Three Dimensions ⋮ Iterated point-line configurations grow doubly-exponentially ⋮ On the diameter of separated point sets with many nearly equal distances ⋮ On the number of edges of separated multigraphs ⋮ Sumsets of semiconvex sets ⋮ An incidence estimate and a Furstenberg type estimate for tubes in \(\mathbb{R}^2\) ⋮ On distinct distances between a variety and a point set ⋮ On sets of directions determined by subsets of \(\mathbb R^d\) ⋮ Cutting algebraic curves into pseudo-segments and applications ⋮ The crossing number of twisted graphs ⋮ The crossing number of locally twisted cubes \(L T Q_n\) ⋮ On bipartite distinct distances in the plane ⋮ Crossings between non-homotopic edges ⋮ Combinatorics. Abstracts from the workshop held January 1--7, 2023 ⋮ From art and circuit design to geometry and combinatorics ⋮ A crossing lemma for multigraphs ⋮ Crossings in grid drawings ⋮ Progress on Dirac's conjecture ⋮ Degrees of nonlinearity in forbidden 0-1 matrix problems ⋮ Classification of maps sending lines into translates of a curve ⋮ Finite point configurations in the plane, rigidity and Erdős problems ⋮ The number of unit distances is almost linear for most norms ⋮ Distinct distances on non-ruled surfaces and between circles ⋮ Improved Bounds for Incidences Between Points and Circles ⋮ Distinct distances between points and lines ⋮ On triple intersections of three families of unit circles ⋮ Distinct Distances from Three Points ⋮ On the Richter–Thomassen Conjecture about Pairwise Intersecting Closed Curves ⋮ Rotation and crossing numbers for join products ⋮ On distinct sums and distinct distances. ⋮ On a Question of Bourgain about Geometric Incidences ⋮ An incidence theorem in higher dimensions ⋮ A successful concept for measuring non-planarity of graphs: The crossing number. ⋮ On totally positive matrices and geometric incidences ⋮ The number of crossings in multigraphs with no empty lens ⋮ On the \(k\)-planar local crossing number ⋮ A combinatorial problem on polynomials and rational functions ⋮ Drawing outerplanar graphs using three edge lengths ⋮ Szemerédi-Trotter-type theorems in dimension 3 ⋮ Robust Tverberg and Colourful Carathéodory Results via Random Choice ⋮ Solving linear equations in a vector space over a finite field ⋮ A Combinatorial Distinction Between Unit Circles and Straight Lines: How Many Coincidences Can they Have? ⋮ On locally Gabriel geometric graphs ⋮ Highly incidental patterns on a quadratic hypersurface in \(\mathbb{R}^4\) ⋮ Near optimal bounds for the Erdős distinct distances problem in high dimensions ⋮ Forbidden paths and cycles in ordered graphs and matrices ⋮ Incidences between points and lines in \({\mathbb {R}}^4\) ⋮ Algebraic methods in sum-product phenomena ⋮ A note on the number of different inner products generated by a finite set of vectors ⋮ A bipartite strengthening of the crossing Lemma ⋮ On loops intersecting at most once ⋮ Nearly equal distances and Szemerédi's regularity lemma ⋮ Radial points in the plane ⋮ Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique ⋮ On the connectivity of visibility graphs ⋮ Simple algorithms for partial point set pattern matching under rigid motion ⋮ Structure and generation of crossing-critical graphs ⋮ Crossing numbers of imbalanced graphs ⋮ Incidences in Three Dimensions and Distinct Distances in the Plane ⋮ Incidences with curves in \(\mathbb{R}^d\) ⋮ General lower bounds for the minor crossing number of graphs ⋮ A Bipartite Strengthening of the Crossing Lemma ⋮ Planar point sets determine many pairwise crossing segments ⋮ Unit distances and diameters in Euclidean spaces ⋮ A Szemerédi-Trotter type theorem in \(\mathbb R^4\) ⋮ Degenerate crossing numbers ⋮ Many touchings force many crossings ⋮ The number of crossings in multigraphs with no empty lens ⋮ ALGORITHMS FOR POINT SET MATCHING WITH k-DIFFERENCES ⋮ Geometric incidence theorems via Fourier analysis ⋮ Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition ⋮ Distinct distances in planar point sets with forbidden 4-point patterns ⋮ Extremal problems on triangle areas in two and three dimensions ⋮ Cardinalities of \(k\)-distance sets in Minkowski spaces ⋮ On distinct distances among points in general position and other related problems ⋮ Quantitative Restrictions on Crossing Patterns ⋮ From harmonic analysis to arithmetic combinatorics ⋮ Turán’s Brick Factory Problem: The Status of the Conjectures of Zarankiewicz and Hill ⋮ 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 ⋮ Crossings Between Non-homotopic Edges ⋮ Graph minors and the crossing number of graphs ⋮ A crossing lemma for multigraphs
