Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory (Q579273): Difference between revisions

Let G be the bipartite graph whose vertices are the points and the hyperplanes of a finite geometry of dimension d and order q, in which a point is adjacent to all the hyperplanes to which it belongs. By estimating the size of the second largest eigenvalue of G, the author shows that G is highly expanding, in the following sense: Any set of x points, \(0<x<n\), is adjacent to at least \(n-(n^{1+1/d}/x)\) hyperplanes. (The number of points is \(n=(q^{d+1}-1)/(q-1).)\) Furthermore, these graphs have, up to a constant, the smallest possible number of edges among graphs with such high expansion property. Using geometries of dimension 4, the author obtains expanding graphs which are particularly well suited for sorting in rounds, and many bounds for the complexity of explicit algorithms for sorting in rounds are improved, cf. \textit{B. Bollobás} and the reviewer, Sorting and graphs, Graphs and order, The role of graphs in the theory of ordered sets and its applications, Proc. NATO Adv. Study. Inst., Banff/Can. 1984, NATO ASI Ser., Ser. C 147, 169-184 (1985; Zbl 0579.68041). In particular, the author gives an explicit algorithm for sorting in two rounds with \(O(n^{7/4})\) comparisons. (This was subsequently further improved by Pippenger.) The author also uses designs and geometries to give other explicit constructions of graphs which were previously proved to exist only by probabilistic arguments. For instance, he shows that the Ramsey number \(r(C_ 4,K_ n)>const\). \(n^{4/3}\).