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
Additional Information
- Daniel A. Spielman
- Affiliation: Department of Computer Science, Yale University
- Received by editor(s): July 29, 2016
- Published electronically: September 8, 2016
- © Copyright 2016 American Mathematical Society
- Journal: Bull. Amer. Math. Soc. 54 (2017), 45-61
- MSC (2010): Primary 05C50
- DOI: https://doi.org/10.1090/bull/1557
- MathSciNet review: 3584097