Report

László A. Székely University of South Carolina Supported in part by NSF DMS 071111 GraDR 2012 Crossing Number Workshop and Minischool Valtice, Czech Republic, May 21, 2012 Thickness Skewness Splitting number Vertex deletion number Page number Genus Crossing number “There were some kilns where the bricks were made and some open storage yards where the bricks were stored. All the kilns were connected by rail with all storage yards. … the trouble was only at crossings. The trucks generally jumped the rails there and the bricks fell out of them; in short this caused a lot of trouble and loss of time … The idea occurred to me that this loss of time could be minimized if the number of crossings of the rails had been minimized. But what is the minimum number of crossings?” (P. Turán remembering in 1977) ê n úê n -1úê m úê m -1ú cr ( K n,m ) = ê úê ê ú ú ê ú ë 2 ûë 2 ûë 2 ûë 2 û Proofs: Zarankiewicz (1954) Urbanik (1955) Gap found: Ringel and Kainen independently Pach-Tóth (1998): “Which crossing number is it anyway?” (Mohar 1995) Imre Lakatos: “Proofs and Refutations” applied Popper to mathematics analysing Euler’s polyhedral formula and the concept of real function 1 ê n úê n -1úê n - 2 úê n - 3ú cr ( K n ) = ê úê ú ê ú ê ú 4 ë 2 ûë 2 ûë 2 ûë 2 û Achieved in two distinct ways: Soup can drawing Throwing different slopes to different hemispheres Crossing Lemma Bisection width lower bound Graph embedding Crossing Lemma (Leighton, Ajtai-ChvátalNewborn-Szemerédi): For a simple graph G on n vertices and m edges, either m ≤ 4n or m3 cr (G ) ³ . 2 64n For a graph G on n vertices and m edges, with edge multiplicity up to M, either m ≤ CMn or m3 cr (G ) ³ C¢ . 2 Mn If n<< m << n2 æ n2 ö min ç cr (G ) 3 ÷ G m ø è converges to a constant (conjectured by Erdős and Guy) e ( A, B) = # of edges between A, B b (G ) = min e ( A, B) AÈB=V n A, B ³ 3 Leighton (1982), Sýkora-Vrťo (1993), PachShahrokhi-Szegedy (1994) 16cr (G) + å d i2 ³ b(G)2 1.582 G1=(V1,E1), G2=(V2,E2), |V1|≤|V2| Embedding ω: G1−>G2: a pair of injections (φ,ψ), where φ:V1−>V2 and ψ:E1−>(path set of G2) such that ψ(uv) is a φ(u)−φ(v) path for all uv in E1 For e εE2, μω(e)=|{f εE1 : e εψ(f)}| For u εV2, mω(u)=|{f εE1 : u εψ(f)}| μω(e1)=μω(e2)=2 μω=maxe (μω(e)) φ G2 G1 mω(u2) =3 μω=2 ψ mω(u1)=mω(u3)=2 G2 with drawing D(G2) G1 ω Two types of crossings occur in the induced drawing of G1: Induced drawing ID(G1) ◦ At crossing edges of G2 £ mw2 per crossings æ m v ö ( ) ÷ at v ◦ At vertices of G2 £ç w ç ÷ 2 è ø 1 2 cr (G1 ) £ cr (ID (G1 )) £ mw × cr (D (G2 )) + å mw2 ( v) 2 vÎV2 Leighton (1982) Shahrokhi-Sýkora-Sz-Vrťo (1994) Assume G1 is embedded into G2 by ω. Assume G2 is drawn as D(G2), inducing ID(G1). 1 2 cr (G1 ) £ cr (ID (G1 )) £ mw × cr (D (G2 )) + å mw2 ( v) 2 vÎV2 2 æ mw ( v) ö cr (G1 ) 1 mw ( v) cr (D (G2 )) ³ ç ÷ å £ d ( v) 2 mw 2 vÎV2 è mw ø mw cr (G1 ) 1 2 cr (D (G2 )) ³ - å d ( v) 2 mw 2 vÎV2 Let T(n,k,l,s) denote the minimum size of an luniform hypergraph on n vertices, such that any k-element subset contains at least s edges from the hypergraph. T(n,k,l) = T(n,k,l,1) Ringel observed that T(n,5,4) ≤ cr(Kn) Analogously if s ≤ crg(Kp) then T(n,p,4,s) ≤ crg(Kn) If G has no k independent nodes T(n,k,2) ≤ e(G) If G, the complement, has no k-clique, then æ n ö e (G ) £ ç ÷ - T ( n, k, 2) è 2 ø Counting method: count crossings in copies of Kn in a drawn copy of Kn+1: cr ( K n+1 ) n +1) cr ( K n ) cr ( K n ) cr ( K n+1 ) ( ³ Û £ n-3 And hence cr ( K n ) $lim n®¥ æ n ö ç ÷ è 4 ø æ n ö ç ÷ è 4 ø æ n +1 ö ç ÷ è 4 ø Katona-Nemetz-Simonovits (1964) on Turán numbers Improvement on a fixed-size problem induces infinitely many improvements deKlerk, Maharry, Pasechnik, Salazar, Richter (2004) 83% of Zarankiewicz conjecture Pach, Spencer, Tóth (1999) improvement on the Crossing Lemma (conjectured by Simonovits): if G has girth >2r and m>4n, then æ m r+2 ö cr (G ) ³ Wç r+1 ÷. èn ø As m2>cr(G), G has at most æ 1+ 1r ö m = Oç n ÷ è ø edges tight for r=2,3,5. Pach, Spencer, Tóth (1999) used the bisection width method to prove their girth theorem Alternative proof through Crossing Lemma and graph embedding (yielding explicit constant): Assume that G is drawn in its optimal drawing (and for simplicity assume that G is d-regular) Define Gr by joining vertices of G if their distance is r – they are joined by a unique rpath Draw Gr following closely the paths in the drawing of G nd ) ( C r 3 n 2 £ cr (G ) £ cr (G ) r ( d -1) r 2 first category 2r-2 + ( junk ) second category The number of incidences between n points and m lines on the plane is at most ( c n + m + ( nm) 2 3 ) This is tight up to a constant multiplicative factor Number of incidences = 7 The Erdős-Purdy Conjecture is true. The number of incidences between n points and m lines on the plane is at most 10 60 ( n + m + ( nm) 2 3 ) Alternatively, if n½ ≤ m ≤ n2, then the number of incidences is at most 10 60 ( nm) 2 3 Consider an “appropriate” “natural” graph drawn in the plane. Crossings, number of vertices or number of edges of this graph should be related to the quantity of interest. Set lower and upper bound for the crossing number of this graph Analyze the results in terms of the quantity of interest. Wlog every line has at least one point. The graph G is already drawn in the plane: ◦ Vertices are the points ◦ Edges are the line segments connecting two consecutive points on any one of the lines ◦ #of incidences on a line = #of edges on that line + 1 ◦ |E(G)| = #of incidences − m 3 æ m ö 1 ( # incidences - m) ³ cr G ³ ç ÷ ( ) 2 2 64 n è ø or #incidences - m £ 4n ( #incidences £ max m + 4n,32 ( mn) 3 + m 2 ) For all ε > 0, there is a constant cε such that the number of unit distances among n points on the plane is at most cε n1+ε Erdős’ construction shows that the number of unit distances can be n1+(c/log log n) (which is bigger than n logn, even bigger than n logkn). d 2 = x 2 + y 2 , where x, y are nonnegative integers 2 n = 7, 2 = 12 +12 11 unit distances 52 = 52 + 0 2 = 32 + 4 2 2 145 = 12 2 +12 = 82 + 9 2 cn3/2 Erdős 1946 o(n3/2) Józsa, Szemerédi 1973 n1.444… Beck, Spencer 1984 cn4/3 Spencer, Szemerédi, Trotter 1984 n points in the plane determine at most O(n4/3) unit distances. Proof by crossing number method: Draw unit circles around the points and define a drawn graph G. Vertices= the n points, edges connect consecutive points on the circles. m=2# unit distances. æ n ö m3 çè 2 ÷ø ³ cr ( G ) ³ 64n 2 . Among n points and n unit circles in the plane, what is the maximum number of incidences? The maximum number of incidences has the same magnitude of growth as the maximum number of unit distances among n points in the plane, as n goes to infinity. n = 2, 3 incidences Erdős-Hickerson-Pach (1989) Valtr Just topology cannot prove the Erdős unit distance conjecture. G G2 Embedding approach: consider the distance 2 multigraph G2 from G above. For simplicity, assume d unit circles passes through every point. nd ) ( ³ cr ( G ) ³ C 2 3 d n + nd 2 2 4 2 4 d n³ M Mn 2 M<d anyway, but M<<d would give improvement “Something else” is needed What could it be? E.g. Elekes-Simonovits-Szabó (2007): 3 points in the plane, n-n-n unit circles pass through them. # of points covered by all 3 families =O(n2−ε). Elekes: n real numbers have at least n5/4 distinct sums or products Pach, Sharir, and others: many more incidence bounds (points, translates of convex closed curves, etc.) Andrews (Iosevits proof): For a convex polygon in the plane with n lattice vertices n=O(area1/3) Dey: # of planar k-sets is at most 7n(k+2)1/3 Erdős conjecture (1946): The number of distinct distances among n points on the n plane is at least c log n Erdős’ matching construction is a square grid of size n½×n½. Cn1/2 Erdős 1946 Cn2/3 Moser 1952 Cn5/7 Fan Chung 1984 Cn(58/81)−ε Beck 1984 n4/5/logcn Fan Chung, Szemerédi, Trotter 1992 Cn3/4 from a single point Clarkson, Edelsbrunner, Guibas, Sharir, Welzl 1990 Cn4/5 from a single point Sz 1997 Cn6/7 Solymosi, Tóth 2001 Cn(4e/(5e-1))-o(1) Tardos 2002 Cn(19/22)-o(1) Katz 2003 Cn(48-14e)/(55-16e)-o(1) Katz, Tardos 2004 Cn/log n Nets, Katz 2010 Draw concentric circles around each point with radiuses = distances from point Very high edge-multiplicity is possible: Determine the quantity g ( n) = min max ( A + A , A × A ) AÍR A =n Clearly, g(n)=O(n2) g(n)=Ω(n1+ε) Erdős-Szemerédi 1983 g(n)=Ω(n32/31) Nathanson g(n)=Ω(n16/15) Ford g(n)=Ω(n5/4) Elekes 1997 Proof by Elekes: P = ( A × A) ´ ( A + A) = {( ab, c + d ) : a, b, c, d Î A} L = {{( ax, a¢ + x ) : x Î R} : a, a¢ Î A} L =n 2 n £ P £ g ( n) 5 ( 2 2 n £ # of incidences = O ( P L ) + P + L 3 2 3 ) Complex plane: P Ì {( w1, w2 ) : wi Î C} L Ì {{( w, aw + b) : w Î C} : a, b Î C} ( # of incidences = O ( P L ) 10 + P + L 7 ) Is there a proof not using Euler’s formula that planar graphs drawn in straight line segments have O(n) edges? Yes – Pinchasi (2007) Drawing triplet systems in C2: Every triplet is contained by a complex line Body of a triplet: convex hull in R4 Bodies may share vertex or boundary edge How many triplets can be drawn? O(n)? Abstract simplicial complex: finite family of finite sets, closed for taking subsets Its dimension: max set size minus 1 1-dimensional abstract simplicial complex can be identified with a graph Embedding in Euclidean space: (d+1)-sets span a d–dimensional simplex; simplices only overlap in spans of common subsets Embedded 1-dimensional simplicial complex: rectilinear drawing of a graph Theorem: every d–dimensional abstract simplicial complex embeds in R2d+1, but some does not embed in R2d. Two vertex sets: n points and m straight lines Edges: incidences Szemerédi-Trotter (1982) |E(G)|=O(n+m+(nm)2/3) Theorem: de Caen, S (1997) 3-path PcP’c’ # P3=O(nm) Implies Szemerédi-Trotter through AtkinsonWatterson-Moran (1960) s ( A) £ s ( AAT A ) nm 3 v’ v P P’ v v’ P P’ Is # C6=O(nm) in the incidence bipartite graph of points and straight lines? This would imply # P3=O(nm) Slightly fails (by log log n factor for m=n) Klavík, Kráľ, Mach (2011) Bisection width Embedding Convex crossing numbers Approximation algorithms Leighton (1982), Sýkora-Vrťo (1993), PachShahrokhi-Szegedy (1994) 16cr (G) + å d ³ b(G) 1.58 2 i 2 2 Leighton (1982) Shahrokhi-Sýkora-Sz-Vrťo (1994) Assume G1 is embedded into G2 by ω. Assume G2 is drawn as D(G2), inducing ID(G1). 1 2 cr (G1 ) £ cr (ID (G1 )) £ mw × cr (D (G2 )) + å mw2 ( v) 2 vÎV2 2 æ mw ( v) ö cr (G1 ) 1 mw ( v) cr (D (G2 )) ³ ç ÷ å £ d ( v) 2 mw 2 vÎV2 è mw ø mw cr (G1 ) 1 2 cr (D (G2 )) ³ - å d ( v) 2 mw 2 vÎV2