Graphs, Vectors, and Matrices

Spielman, Daniel

doi:10.1090/bull/1557

Graphs, Vectors, and Matrices
HTML articles powered by AMS MathViewer

by Daniel A. Spielman PDF

Bull. Amer. Math. Soc. 54 (2017), 45-61 Request permission

Abstract:

This survey accompanies the Josiah Williard Gibbs Lecture that I gave at the 2016 Joint Mathematics Meetings. It provides an introduction to three topics: algebraic and spectral graph theory, the sparsification of graphs, and the recent resolution of the Kadison–Singer Problem. The first and third are connected by the second.

References

Charles A. Akemann and Joel Anderson, Lyapunov theorems for operator algebras, Mem. Amer. Math. Soc. 94 (1991), no. 458, iv+88. MR 1086563, DOI 10.1090/memo/0458
Jonathan E. Atkins, Erik G. Boman, and Bruce Hendrickson, A spectral algorithm for seriation and the consecutive ones problem, SIAM J. Comput. 28 (1999), no. 1, 297–310. MR 1630473, DOI 10.1137/S0097539795285771
N. Alon and V. D. Milman, $\lambda _1,$ isoperimetric inequalities for graphs, and superconcentrators, J. Combin. Theory Ser. B 38 (1985), no. 1, 73–88. MR 782626, DOI 10.1016/0095-8956(85)90092-9
Andrei Z. Broder, Alan M. Frieze, and Eli Upfal, Existence and construction of edge-disjoint paths on expander graphs, SIAM J. Comput. 23 (1994), no. 5, 976–989. MR 1293269, DOI 10.1137/S0097539792232021
Norman Biggs, Algebraic graph theory, Cambridge Tracts in Mathematics, No. 67, Cambridge University Press, London, 1974. MR 0347649, DOI 10.1017/CBO9780511608704
Petter Brändén. Hyperbolic polynomials and the Marcus-Spielman-Srivastava theorem. arXiv preprint arXiv:1412.0245, 2014.
Joshua Batson, Daniel A. Spielman, and Nikhil Srivastava, Twice-Ramanujan sparsifiers, SIAM J. Comput. 41 (2012), no. 6, 1704–1721. MR 3029269, DOI 10.1137/090772873
Joshua Batson, Daniel A. Spielman, Nikhil Srivastava, and Shang-Hua Teng. Spectral sparsification of graphs: Theory and algorithms. Commun. ACM, 56 (2013), no. 8. 87–94.
Jeff Cheeger, A lower bound for the smallest eigenvalue of the Laplacian, Problems in analysis (Papers dedicated to Salomon Bochner, 1969) Princeton Univ. Press, Princeton, N. J., 1970, pp. 195–199. MR 0402831
Fan R. K. Chung, Spectral graph theory, CBMS Regional Conference Series in Mathematics, vol. 92, Published for the Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 1997. MR 1421568
Jozef Dodziuk, Difference equations, isoperimetric inequality and transience of certain random walks, Trans. Amer. Math. Soc. 284 (1984), no. 2, 787–794. MR 743744, DOI 10.1090/S0002-9947-1984-0743744-X
Alan M. Frieze and Michael Molloy, Splitting an expander graph, J. Algorithms 33 (1999), no. 1, 166–172. MR 1712697, DOI 10.1006/jagm.1999.1023
Joel Friedman, A proof of Alon’s second eigenvalue conjecture and related problems, Mem. Amer. Math. Soc. 195 (2008), no. 910, viii+100. MR 2437174, DOI 10.1090/memo/0910
C. D. Godsil, Matchings and walks in graphs, J. Graph Theory 5 (1981), no. 3, 285–297. MR 625070, DOI 10.1002/jgt.3190050310
C. D. Godsil, Algebraic combinatorics, Chapman and Hall Mathematics Series, Chapman & Hall, New York, 1993. MR 1220704
Chris Godsil and Gordon Royle, Algebraic graph theory, Graduate Texts in Mathematics, vol. 207, Springer-Verlag, New York, 2001. MR 1829620, DOI 10.1007/978-1-4613-0163-9
K. M. Hall. An $r$-dimensional quadratic placement algorithm. Management Science, 17 (1970), 219–229.
Ole J. Heilmann and Elliott H. Lieb, Theory of monomer-dimer systems, Comm. Math. Phys. 25 (1972), 190–232. MR 297280, DOI 10.1007/BF01877590
Shlomo Hoory, Nathan Linial, and Avi Wigderson, Expander graphs and their applications, Bull. Amer. Math. Soc. (N.S.) 43 (2006), no. 4, 439–561. MR 2247919, DOI 10.1090/S0273-0979-06-01126-8
D. J. Klein and M. Randić, Resistance distance, J. Math. Chem. 12 (1993), no. 1-4, 81–95. Applied graph theory and discrete mathematics in chemistry (Saskatoon, SK, 1991). MR 1219566, DOI 10.1007/BF01164627
Richard V. Kadison and I. M. Singer, Extensions of pure states, Amer. J. Math. 81 (1959), 383–400. MR 123922, DOI 10.2307/2372748
A. Lubotzky, R. Phillips, and P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988), no. 3, 261–277. MR 963118, DOI 10.1007/BF02126799
Gregory F. Lawler and Alan D. Sokal, Bounds on the $L^2$ spectrum for Markov chains and Markov processes: a generalization of Cheeger’s inequality, Trans. Amer. Math. Soc. 309 (1988), no. 2, 557–580. MR 930082, DOI 10.1090/S0002-9947-1988-0930082-9
G. A. Margulis, Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators, Problemy Peredachi Informatsii 24 (1988), no. 1, 51–60 (Russian); English transl., Problems Inform. Transmission 24 (1988), no. 1, 39–46. MR 939574
Adam W. Marcus, Daniel A. Spielman, and Nikhil Srivastava, Ramanujan graphs and the solution of the Kadison-Singer problem. In Proceedings of the International Congress of Mathematicians, volume III, pages 363–386. Kyung Moon SA, 2014.
Adam W. Marcus, Daniel A. Spielman, and Nikhil Srivastava, Interlacing families I: Bipartite Ramanujan graphs of all degrees, Ann. of Math. (2) 182 (2015), no. 1, 307–325. MR 3374962, DOI 10.4007/annals.2015.182.1.7
Adam W. Marcus, Daniel A. Spielman, and Nikhil Srivastava, Interlacing families II: Mixed characteristic polynomials and the Kadison-Singer problem, Ann. of Math. (2) 182 (2015), no. 1, 327–350. MR 3374963, DOI 10.4007/annals.2015.182.1.8
Adam W. Marcus, Daniel A. Spielman, and Nikhil Srivastava, Interlacing families IV: Bipartite Ramanujan graphs of all sizes, 2015 IEEE 56th Annual Symposium on Foundations of Computer Science—FOCS 2015, IEEE Computer Soc., Los Alamitos, CA, 2015, pp. 1358–1377. MR 3473375, DOI 10.1109/FOCS.2015.87
Assaf Naor, Sparse quadratic forms and their geometric applications [following Batson, Spielman and Srivastava], Astérisque 348 (2012), Exp. No. 1033, viii, 189–217. Séminaire Bourbaki: Vol. 2010/2011. Exposés 1027–1042. MR 3050716
A. Nilli, On the second eigenvalue of a graph, Discrete Math. 91 (1991), no. 2, 207–210. MR 1124768, DOI 10.1016/0012-365X(91)90112-F
Ch. H. Papadimitriou, The NP-completeness of the bandwidth minimization problem, Computing 16 (1976), no. 3, 263–270 (English, with German summary). MR 411243, DOI 10.1007/BF02280884
M. Rudelson, Random vectors in the isotropic position, J. Funct. Anal. 164 (1999), no. 1, 60–72. MR 1694526, DOI 10.1006/jfan.1998.3384
Alistair Sinclair and Mark Jerrum, Approximate counting, uniform generation and rapidly mixing Markov chains, Inform. and Comput. 82 (1989), no. 1, 93–133. MR 1003059, DOI 10.1016/0890-5401(89)90067-9
Daniel Spielman. Laplacian linear equations, sparsification, local graph clustering, low-stretch spanning trees, etc. from http://cs-www.cs.yale.edu/homes/spielman/precon/precon.html.
N. Srivastava, Discrepancy, graphs, and the Kadison-Singer problem, Asia Pac. Math. Newsl. 3 (2013), no. 4, 15–20. MR 3156130
Daniel A. Spielman and Nikhil Srivastava, Graph sparsification by effective resistances, SIAM J. Comput. 40 (2011), no. 6, 1913–1926. MR 2863199, DOI 10.1137/080734029
Daniel A. Spielman and Shang-Hua Teng, Spectral sparsification of graphs, SIAM J. Comput. 40 (2011), no. 4, 981–1025. MR 2825307, DOI 10.1137/08074489X
Daniel A. Spielman and Shang-Hua Teng, Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems, SIAM J. Matrix Anal. Appl. 35 (2014), no. 3, 835–885. MR 3228466, DOI 10.1137/090771430
Terence Tao. What’s new: Real stable polynomials and the Kadison-Singer problem, 2013. from https://terrytao.wordpress.com/2013/11/04/real-stable-polynomials-and-the-kadison-singer-problem/.
Joel A. Tropp, User-friendly tail bounds for sums of random matrices, Found. Comput. Math. 12 (2012), no. 4, 389–434. MR 2946459, DOI 10.1007/s10208-011-9099-z
W. T. Tutte, How to draw a graph, Proc. London Math. Soc. (3) 13 (1963), 743–767. MR 158387, DOI 10.1112/plms/s3-13.1.743
N. Th. Varopoulos, Isoperimetric inequalities and Markov chains, J. Funct. Anal. 63 (1985), no. 2, 215–239. MR 803093, DOI 10.1016/0022-1236(85)90086-2
Nik Weaver, The Kadison-Singer problem in discrepancy theory, Discrete Math. 278 (2004), no. 1-3, 227–239. MR 2035401, DOI 10.1016/S0012-365X(03)00253-X