Remote Access Bulletin of the American Mathematical Society

Bulletin of the American Mathematical Society

ISSN 1088-9485(online) ISSN 0273-0979(print)

 
 

 

Graphs, Vectors, and Matrices


Author: Daniel A. Spielman
Journal: Bull. Amer. Math. Soc. 54 (2017), 45-61
MSC (2010): Primary 05C50
DOI: https://doi.org/10.1090/bull/1557
Published electronically: September 8, 2016
MathSciNet review: 3584097
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [AA91] Charles A. Akemann and Joel Anderson, Lyapunov theorems for operator algebras, Mem. Amer. Math. Soc. 94 (1991), no. 458, iv+88. MR 1086563, https://doi.org/10.1090/memo/0458
  • [ABH98] 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, https://doi.org/10.1137/S0097539795285771
  • [AM85] 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, https://doi.org/10.1016/0095-8956(85)90092-9
  • [BFU94] 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, https://doi.org/10.1137/S0097539792232021
  • [Big74] Norman Biggs, Algebraic graph theory, Cambridge University Press, London, 1974. Cambridge Tracts in Mathematics, No. 67. MR 0347649
  • [Brä14] Petter Brändén.
    Hyperbolic polynomials and the Marcus-Spielman-Srivastava theorem.
    arXiv preprint arXiv:1412.0245, 2014.
  • [BSS12] Joshua Batson, Daniel A. Spielman, and Nikhil Srivastava, Twice-Ramanujan sparsifiers, SIAM J. Comput. 41 (2012), no. 6, 1704-1721. MR 3029269, https://doi.org/10.1137/090772873
  • [BSST13] 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.
  • [Che70] Jeff Cheeger, A lower bound for the smallest eigenvalue of the Laplacian, in Problems in analysis (Papers dedicated to Salomon Bochner, 1969) Princeton Univ. Press, Princeton, N. J., 1970, pp. 195-199. MR 0402831
  • [Chu97] 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
  • [Dod84] Jozef Dodziuk, Difference equations, isoperimetric inequality and transience of certain random walks, Trans. Amer. Math. Soc. 284 (1984), no. 2, 787-794. MR 743744, https://doi.org/10.2307/1999107
  • [FM99] Alan M. Frieze and Michael Molloy, Splitting an expander graph, J. Algorithms 33 (1999), no. 1, 166-172. MR 1712697, https://doi.org/10.1006/jagm.1999.1023
  • [Fri08] 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, https://doi.org/10.1090/memo/0910
  • [God81] C. D. Godsil, Matchings and walks in graphs, J. Graph Theory 5 (1981), no. 3, 285-297. MR 625070, https://doi.org/10.1002/jgt.3190050310
  • [God93] C. D. Godsil, Algebraic combinatorics, Chapman and Hall Mathematics Series, Chapman & Hall, New York, 1993. MR 1220704
  • [GR01] Chris Godsil and Gordon Royle, Algebraic graph theory, Graduate Texts in Mathematics, vol. 207, Springer-Verlag, New York, 2001. MR 1829620
  • [Hal70] K. M. Hall.
    An $ r$-dimensional quadratic placement algorithm.
    Management Science, 17 (1970), 219-229.
  • [HL72] Ole J. Heilmann and Elliott H. Lieb, Theory of monomer-dimer systems, Comm. Math. Phys. 25 (1972), 190-232. MR 0297280
  • [HLW06] Shlomo Hoory, Nathan Linial, and Avi Wigderson, Expander graphs and their applications, Bull. Amer. Math. Soc. (N.S.) 43 (2006), no. 4, 439-561 (electronic). MR 2247919, https://doi.org/10.1090/S0273-0979-06-01126-8
  • [KR93] 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, https://doi.org/10.1007/BF01164627
  • [KS59] Richard V. Kadison and I. M. Singer, Extensions of pure states, Amer. J. Math. 81 (1959), 383-400. MR 0123922
  • [LPS88] A. Lubotzky, R. Phillips, and P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988), no. 3, 261-277. MR 963118, https://doi.org/10.1007/BF02126799
  • [LS88] 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, https://doi.org/10.2307/2000925
  • [Mar88] 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
  • [MSS14] 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.
  • [MSS15a] 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, https://doi.org/10.4007/annals.2015.182.1.7
  • [MSS15b] 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, https://doi.org/10.4007/annals.2015.182.1.8
  • [MSS15c] 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
  • [Nao12] 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
  • [Nil91] A. Nilli, On the second eigenvalue of a graph, Discrete Math. 91 (1991), no. 2, 207-210. MR 1124768, https://doi.org/10.1016/0012-365X(91)90112-F
  • [Pap76] Ch. H. Papadimitriou, The NP-completeness of the bandwidth minimization problem, Computing 16 (1976), no. 3, 263-270 (English, with German summary). MR 0411243
  • [Rud99] M. Rudelson, Random vectors in the isotropic position, J. Funct. Anal. 164 (1999), no. 1, 60-72. MR 1694526, https://doi.org/10.1006/jfan.1998.3384
  • [SJ89] 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, https://doi.org/10.1016/0890-5401(89)90067-9
  • [Spi] 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.
  • [Sri13] N. Srivastava, Windows on theory: Discrepancy, graphs, and the Kadison-Singer problem, Asia Pac. Math. Newsl. 3 (2013), no. 4, 15-20. MR 3156130
  • [SS11] Daniel A. Spielman and Nikhil Srivastava, Graph sparsification by effective resistances, SIAM J. Comput. 40 (2011), no. 6, 1913-1926. MR 2863199, https://doi.org/10.1137/080734029
  • [ST11] Daniel A. Spielman and Shang-Hua Teng, Spectral sparsification of graphs, SIAM J. Comput. 40 (2011), no. 4, 981-1025. MR 2825307, https://doi.org/10.1137/08074489X
  • [ST14] 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, https://doi.org/10.1137/090771430
  • [Tao13] 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/.
  • [Tro12] Joel A. Tropp, User-friendly tail bounds for sums of random matrices, Found. Comput. Math. 12 (2012), no. 4, 389-434. MR 2946459, https://doi.org/10.1007/s10208-011-9099-z
  • [Tut63] W. T. Tutte, How to draw a graph, Proc. London Math. Soc. (3) 13 (1963), 743-767. MR 0158387
  • [Var85] N. Th. Varopoulos, Isoperimetric inequalities and Markov chains, J. Funct. Anal. 63 (1985), no. 2, 215-239. MR 803093, https://doi.org/10.1016/0022-1236(85)90086-2
  • [Wea04] Nik Weaver, The Kadison-Singer problem in discrepancy theory, Discrete Math. 278 (2004), no. 1-3, 227-239. MR 2035401, https://doi.org/10.1016/S0012-365X(03)00253-X

Similar Articles

Retrieve articles in Bulletin of the American Mathematical Society with MSC (2010): 05C50

Retrieve articles in all journals with MSC (2010): 05C50


Additional Information

Daniel A. Spielman
Affiliation: Department of Computer Science, Yale University

DOI: https://doi.org/10.1090/bull/1557
Received by editor(s): July 29, 2016
Published electronically: September 8, 2016
Article copyright: © Copyright 2016 American Mathematical Society

American Mathematical Society