\newcommand{\CCA}Combinatorica \newcommand{\JCTB}J. Combin. Theory B \newcommand{\JCTA}J. Combin. Theory A \newcommand{\CPC}Combin. Prob. Comput. \newcommand{\EJC}Europ. J. Combin. \newcommand{\ELJC}Electr. J. Combin. \newcommand{\JGT}J. Graph Theory \newcommand{\ADV}Advances in Math. \newcommand{\ADVA}Advances in Applied Math. \newcommand{\GAFA}Geom. Func. Anal. \def\STOC#1 Proc. #1$^\text {th}$ ACM Symp. on Theory of Comput. \def\FOCS#1 Proc. #1$^\text {th}$ Ann. IEEE Symp. on Found. Comp. Science \def\SODA#1 Proc. #1$^\text {th}$ Ann. ACM-SIAM Symp. on Discrete Algorithms \newcommand{\DCG}Discr. Comput. Geom. \newcommand{\DM}Discr. Math. \newcommand{\DAM}Discr. Applied Math. \newcommand{\SDM}SIAM J. Discr. Math. \newcommand{\TIT}IEEE Trans. Inform. Theory \newcommand{\LAA}Linear Algebra Appl.

• Miklós Ajtai, János Komlós, and Endre Szemerédi, A note on Ramsey numbers, J. Combin. Theory Ser. A 29 (1980), no. 3, 354–360. MR 600598, DOI 10.1016/0097-3165(80)90030-8
• A. Y. Alfakih, Graph connectivity and universal rigidity of bar frameworks. part 3, Discrete Appl. Math. 217 (2017), no. part 3, 707–710. MR 3579945, DOI 10.1016/j.dam.2016.10.008
• A. Y. Alfakih and Yinyu Ye, On affine motions and bar frameworks in general position, Linear Algebra Appl. 438 (2013), no. 1, 31–36. MR 2993361, DOI 10.1016/j.laa.2012.08.031
• F. Alizadeh: Combinatorial optimization with semi-definite matrices, in: Integer Programming and Combinatorial Optimization (Proceedings of IPCO ’92), (eds. E. Balas, G. Cornuéjols and R. Kannan), Carnegie Mellon University Printing (1992), 385–405.
• Farid Alizadeh, Interior point methods in semidefinite programming with applications to combinatorial optimization, SIAM J. Optim. 5 (1995), no. 1, 13–51. MR 1315703, DOI 10.1137/0805002
• N. Alon, Eigenvalues and expanders, Combinatorica 6 (1986), no. 2, 83–96. Theory of computing (Singer Island, Fla., 1984). MR 875835, DOI 10.1007/BF02579166
• Noga Alon, The Shannon capacity of a union, Combinatorica 18 (1998), no. 3, 301–310. MR 1721946, DOI 10.1007/PL00009824
• Noga Alon, Explicit Ramsey graphs and orthonormal labelings, Electron. J. Combin. 1 (1994), Research Paper 12, approx. 8. MR 1302331, DOI 10.37236/1192
• N. Alon: Lovász, vectors, graphs and codes, https://www.tau.ac.il/~nogaa/PDFS/ll70.pdf
• N. Alon, I. Balla, L. Gishboliner, A. Mond and F. Mousset: The Minrank of Random Graphs over Arbitrary Fields, https://arxiv.org/abs/1809.01873
• Noga Alon, Eldar Fischer, Michael Krivelevich, and Mario Szegedy, Efficient testing of large graphs, Combinatorica 20 (2000), no. 4, 451–476. MR 1804820, DOI 10.1007/s004930070001
• Noga Alon and Nabil Kahale, Approximating the independence number via the $\theta$-function, Math. Programming 80 (1998), no. 3, Ser. A, 253–264. MR 1603356, DOI 10.1007/BF01581168
• N. Alon and L. Lovász, Unextendible product bases, J. Combin. Theory Ser. A 95 (2001), no. 1, 169–179. MR 1840483, DOI 10.1006/jcta.2000.3122
• Noga Alon and Eyal Lubetzky, The Shannon capacity of a graph and the independence numbers of its powers, IEEE Trans. Inform. Theory 52 (2006), no. 5, 2172–2176. MR 2234473, DOI 10.1109/TIT.2006.872856
• 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
• N. Alon and P. D. Seymour, A counterexample to the rank-coloring conjecture, J. Graph Theory 13 (1989), no. 4, 523–525. MR 1010585, DOI 10.1002/jgt.3190130413
• Noga Alon, Paul Seymour, and Robin Thomas, Planar separators, SIAM J. Discrete Math. 7 (1994), no. 2, 184–193. MR 1271990, DOI 10.1137/S0895480191198768
• Noga Alon and Joel H. Spencer, The probabilistic method, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1992. With an appendix by Paul Erdős; A Wiley-Interscience Publication. MR 1140703
• Noga Alon and Mario Szegedy, Large sets of nearly orthogonal vectors, Graphs Combin. 15 (1999), no. 1, 1–4. MR 1684496
• Andris Ambainis, Julia Kempe, and Or Sattath, A quantum Lovász local lemma, J. ACM 59 (2012), no. 5, Art. 24, 24. MR 2995823, DOI 10.1145/2371656.2371659
• B. Andrásfai, On critical graphs, Theory of Graphs (Internat. Sympos., Rome, 1966) Gordon and Breach, New York; Dunod, Paris, 1967, pp. 9–19 (English, with French summary). MR 0221964
• E. M. Andreev, Convex polyhedra in Lobačevskiĭ spaces, Mat. Sb. (N.S.) 81 (123) (1970), 445–478 (Russian). MR 0259734
• E. M. Andreev, Convex polyhedra of finite volume in Lobačevskiĭ space, Mat. Sb. (N.S.) 83 (125) (1970), 256–260 (Russian). MR 0273510
• Omer Angel and Oded Schramm, Uniform infinite planar triangulations, Comm. Math. Phys. 241 (2003), no. 2-3, 191–213. MR 2013797, DOI 10.1007/978-1-4419-9675-6_{1}6
• L. Asimow and B. Roth, The rigidity of graphs, Trans. Amer. Math. Soc. 245 (1978), 279–289. MR 511410, DOI 10.1090/S0002-9947-1978-0511410-9
• L. Babai and P. Frankl: Linear Algebra Methods in Combinatorics, with Applications to Geometry and Computer Science, Univ. Chicago Dept. Computer Sci. 1992 (unpublished preliminary version 2, 216 pages).
• Roland Bacher and Yves Colin de Verdière, Multiplicités des valeurs propres et transformations étoile-triangle des graphes, Bull. Soc. Math. France 123 (1995), no. 4, 517–533 (French, with English and French summaries). MR 1373946
• E. G. Bajmóczy and I. Bárány, On a common generalization of Borsuk’s and Radon’s theorem, Acta Math. Acad. Sci. Hungar. 34 (1979), no. 3-4, 347–350 (1980). MR 565677, DOI 10.1007/BF01896131
• S. Beigi: Entanglement-assisted zero-error capacity is upper bounded by the Lovasz theta function, Phys. Rev. A 82 (2010), 010303(R).
• J. S. Bell, On the Einstein Podolsky Rosen paradox, Phys. Phys. Fiz. 1 (1964), no. 3, 195–200. MR 3790629, DOI 10.1103/PhysicsPhysiqueFizika.1.195
• I. Benjamini and L. Lovász: Global Information from Local Observation, Proc. 43rd Ann. Symp. on Found. of Comp. Sci. (2002) 701–710.
• Itai Benjamini and László Lovász, Harmonic and analytic functions on graphs, J. Geom. 76 (2003), no. 1-2, 3–15. Combinatorics, 2002 (Maratea). MR 2005527, DOI 10.1007/s00022-033-1697-8
• Itai Benjamini and Oded Schramm, Harmonic functions on planar and almost planar graphs and manifolds, via circle packings, Invent. Math. 126 (1996), no. 3, 565–587. MR 1419007, DOI 10.1007/s002220050109
• Itai Benjamini and Oded Schramm, Random walks and harmonic functions on infinite planar graphs using square tilings, Ann. Probab. 24 (1996), no. 3, 1219–1238. MR 1411492, DOI 10.1214/aop/1065725179
• Itai Benjamini and Oded Schramm, Recurrence of distributional limits of finite planar graphs, Electron. J. Probab. 6 (2001), no. 23, 13. MR 1873300, DOI 10.1214/EJP.v6-96
• Charles H. Bennett, David P. DiVincenzo, Tal Mor, Peter W. Shor, John A. Smolin, and Barbara M. Terhal, Unextendible product bases and bound entanglement, Phys. Rev. Lett. 82 (1999), no. 26, 5385–5388. MR 1789694, DOI 10.1103/PhysRevLett.82.5385
• Claude Berge, Graphs and hypergraphs, North-Holland Mathematical Library, Vol. 6, North-Holland Publishing Co., Amsterdam-London; American Elsevier Publishing Co., Inc., New York, 1973. Translated from the French by Edward Minieka. MR 0357172
• A. Björner and L. Lovász, Pseudomodular lattices and continuous matroids, Acta Sci. Math. (Szeged) 51 (1987), no. 3-4, 295–308. MR 940934
• W. Blaschke: Uber affine Geometrie VII: Neue Extremeingenschaften von Ellipse und Ellipsoid, Ber. Verh. Sächs. Akad. Wiss. Math. Phys. Klass 69 (1917), 412–420.
• Avrim Blum and David Karger, An $\~O(n^{3/14})$-coloring algorithm for $3$-colorable graphs, Inform. Process. Lett. 61 (1997), no. 1, 49–53. MR 1439867, DOI 10.1016/S0020-0190(96)00190-1
• B. Bollobás, On generalized graphs, Acta Math. Acad. Sci. Hungar. 16 (1965), 447–452 (English, with Russian summary). MR 183653, DOI 10.1007/BF01904851
• Alexander I. Bobenko, Christian Mercat, and Yuri B. Suris, Linear and nonlinear theories of discrete analytic functions. Integrable structure and isomonodromic Green’s function, J. Reine Angew. Math. 583 (2005), 117–161. MR 2146854, DOI 10.1515/crll.2005.2005.583.117
• Alexander I. Bobenko and Boris A. Springborn, Variational principles for circle patterns and Koebe’s theorem, Trans. Amer. Math. Soc. 356 (2004), no. 2, 659–689. MR 2022715, DOI 10.1090/S0002-9947-03-03239-2
• Thomas Böhme, On spatial representations of graphs, Contemporary methods in graph theory, Bibliographisches Inst., Mannheim, 1990, pp. 151–167. MR 1126225
• Christian Borgs, Jennifer Chayes, and László Lovász, Moments of two-variable functions and the uniqueness of graph limits, Geom. Funct. Anal. 19 (2010), no. 6, 1597–1619. MR 2594615, DOI 10.1007/s00039-010-0044-0
• C. Borgs, J. T. Chayes, L. Lovász, V. T. Sós, and K. Vesztergombi, Convergent sequences of dense graphs. I. Subgraph frequencies, metric properties and testing, Adv. Math. 219 (2008), no. 6, 1801–1851. MR 2455626, DOI 10.1016/j.aim.2008.07.008
• J. Bourgain, On Lipschitz embedding of finite metric spaces in Hilbert space, Israel J. Math. 52 (1985), no. 1-2, 46–52. MR 815600, DOI 10.1007/BF02776078
• J. Bourgain and V. D. Milman, New volume ratio properties for convex symmetric bodies in $\textbf {R}^n$, Invent. Math. 88 (1987), no. 2, 319–340. MR 880954, DOI 10.1007/BF01388911
• R. Bricard: Mémoire sur la théorie de l’octaedre articulé, J. Math. Pures Appl. 5 (1897), 113–148.
• Graham R. Brightwell and Edward R. Scheinerman, Representations of planar graphs, SIAM J. Discrete Math. 6 (1993), no. 2, 214–229. MR 1215229, DOI 10.1137/0406017
• Bo Brinkman and Moses Charikar, On the impossibility of dimension reduction in $l_1$, J. ACM 52 (2005), no. 5, 766–788. MR 2176562, DOI 10.1145/1089023.1089026
• R. L. Brooks, C. A. B. Smith, A. H. Stone, and W. T. Tutte, The dissection of rectangles into squares, Duke Math. J. 7 (1940), 312–340. MR 3040
• Andries E. Brouwer and Willem H. Haemers, Spectra of graphs, Universitext, Springer, New York, 2012. MR 2882891, DOI 10.1007/978-1-4614-1939-6
• A. Cabello, S. Severini, A. Winter: Graph-Theoretic Approach to Quantum Correlations, Phys. Rev. Lett. 112 (2014), 040401.
• P. J. Cameron, J.-M. Goethals, J. J. Seidel, and E. E. Shult, Line graphs, root systems, and elliptic geometry, J. Algebra 43 (1976), no. 1, 305–327. MR 441787, DOI 10.1016/0021-8693(76)90162-9
• The electrical resistance of a graph captures its commute and cover times, \STOC21 (1989), 574–586.
• John L. Cardy, Critical percolation in finite geometries, J. Phys. A 25 (1992), no. 4, L201–L206. MR 1151081
• Dmitry Chelkak and Stanislav Smirnov, Discrete complex analysis on isoradial graphs, Adv. Math. 228 (2011), no. 3, 1590–1630. MR 2824564, DOI 10.1016/j.aim.2011.06.025
• Dmitry Chelkak and Stanislav Smirnov, Universality in the 2D Ising model and conformal invariance of fermionic observables, Invent. Math. 189 (2012), no. 3, 515–580. MR 2957303, DOI 10.1007/s00222-011-0371-2
• Jianxin Chen and Nathaniel Johnston, The minimum size of unextendible product bases in the bipartite case (and some multipartite cases), Comm. Math. Phys. 333 (2015), no. 1, 351–365. MR 3294952, DOI 10.1007/s00220-014-2186-7
• Joseph Cheriyan and John H. Reif, Directed $s$-$t$ numberings, rubber bands, and testing digraph $k$-vertex connectivity, Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms (Orlando, FL, 1992) ACM, New York, 1992, pp. 335–344. MR 1173905
• Marek Chrobak and Shin-ichi Nakano, Minimum-width grid drawings of plane graphs, Comput. Geom. 11 (1998), no. 1, 29–54. MR 1633561, DOI 10.1016/S0925-7721(98)00016-9
• Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas, The strong perfect graph theorem, Ann. of Math. (2) 164 (2006), no. 1, 51–229. MR 2233847, DOI 10.4007/annals.2006.164.51
• F. R. K. Chung, Labelings of graphs, Selected topics in graph theory, 3, Academic Press, San Diego, CA, 1988, pp. 151–168. MR 1205400
• 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
• Julia Chuzhoy, Excluded grid theorem: improved and simplified, STOC’15—Proceedings of the 2015 ACM Symposium on Theory of Computing, ACM, New York, 2015, pp. 645–654. MR 3388244, DOI 10.1145/2746539.2746551
• V. Chvátal, On certain polytopes associated with graphs, J. Combinatorial Theory Ser. B 18 (1975), 138–154. MR 371732, DOI 10.1016/0095-8956(75)90041-6
• V. Chvátal and J. Komlós, Some combinatorial theorems on monotonicity, Canad. Math. Bull. 14 (1971), 151–157. MR 337676, DOI 10.4153/CMB-1971-028-8
• Amin Coja-Oghlan, The Lovász number of random graphs, Approximation, randomization, and combinatorial optimization, Lecture Notes in Comput. Sci., vol. 2764, Springer, Berlin, 2003, pp. 228–239. MR 2080795, DOI 10.1007/978-3-540-45198-3_{2}0
• Amin Coja-Oghlan and Anusch Taraz, Exact and approximative algorithms for coloring $G(n,p)$, Random Structures Algorithms 24 (2004), no. 3, 259–278. MR 2068869, DOI 10.1002/rsa.20007
• Yves Colin de Verdière, Sur la multiplicité de la première valeur propre non nulle du laplacien, Comment. Math. Helv. 61 (1986), no. 2, 254–270 (French). MR 856089, DOI 10.1007/BF02621914
• Yves Colin de Verdière, Sur un nouvel invariant des graphes et un critère de planarité, J. Combin. Theory Ser. B 50 (1990), no. 1, 11–21 (French). MR 1070462, DOI 10.1016/0095-8956(90)90093-F
• Yves Colin de Verdière, Un principe variationnel pour les empilements de cercles, Invent. Math. 104 (1991), no. 3, 655–669 (French). MR 1106755, DOI 10.1007/BF01245096
• Yves Colin de Verdière, Multiplicities of eigenvalues and tree-width of graphs, J. Combin. Theory Ser. B 74 (1998), no. 2, 121–146. MR 1654157, DOI 10.1006/jctb.1998.1834
• Yves Colin de Verdière, Spectres de graphes, Cours Spécialisés [Specialized Courses], vol. 4, Société Mathématique de France, Paris, 1998 (French, with English and French summaries). MR 1652692
• David Conlon and Jacob Fox, Bounds for graph regularity and removal lemmas, Geom. Funct. Anal. 22 (2012), no. 5, 1191–1256. MR 2989432, DOI 10.1007/s00039-012-0171-x
• Robert Connelly, A counterexample to the rigidity conjecture for polyhedra, Inst. Hautes Études Sci. Publ. Math. 47 (1977), 333–338. MR 488071
• Robert Connelly, Rigidity and energy, Invent. Math. 66 (1982), no. 1, 11–33. MR 652643, DOI 10.1007/BF01404753
• Robert Connelly, Rigidity, Handbook of convex geometry, Vol. A, B, North-Holland, Amsterdam, 1993, pp. 223–271. MR 1242981
• Robert Connelly, Generic global rigidity, Discrete Comput. Geom. 33 (2005), no. 4, 549–563. MR 2132290, DOI 10.1007/s00454-004-1124-4
• R. Connelly, S.J. Gortler and L. Theran: Generic global and universal rigidity, https://arxiv.org/abs/1604.07475v1
• Robert Connelly, Steven J. Gortler, and Louis Theran, Affine rigidity and conics at infinity, Int. Math. Res. Not. IMRN 13 (2018), 4084–4102. MR 3829178, DOI 10.1093/imrn/rnx014
• R. Courant and D. Hilbert, Methods of mathematical physics. Vol. I, Interscience Publishers, Inc., New York, N.Y., 1953. MR 0065391
• T.S. Cubitt, D. Leung, W. Matthews, A. Winter: Improving zero-error classical communication with entanglement, Phys. Rev. Lett. 104 (2010), 230503.
• Toby S. Cubitt, Debbie Leung, William Matthews, and Andreas Winter, Zero-error channel capacity and simulation assisted by non-local correlations, IEEE Trans. Inform. Theory 57 (2011), no. 8, 5509–5523. MR 2849372, DOI 10.1109/TIT.2011.2159047
• E. Brian Davies, Graham M. L. Gladwell, Josef Leydold, and Peter F. Stadler, Discrete nodal domain theorems, Linear Algebra Appl. 336 (2001), 51–60. MR 1855391, DOI 10.1016/S0024-3795(01)00313-5
• C. Delorme and S. Poljak, Laplacian eigenvalues and the maximum cut problem, Math. Programming 62 (1993), no. 3, Ser. A, 557–574. MR 1251892, DOI 10.1007/BF01585184
• Charles Delorme and Svatopluk Poljak, Combinatorial properties and the complexity of a max-cut approximation, European J. Combin. 14 (1993), no. 4, 313–333. MR 1226579, DOI 10.1006/eujc.1993.1035
• Michel Marie Deza and Monique Laurent, Geometry of cuts and metrics, Algorithms and Combinatorics, vol. 15, Springer-Verlag, Berlin, 1997. MR 1460488, DOI 10.1007/978-3-642-04295-9
• A. Dress and L. Lovász, On some combinatorial properties of algebraic matroids, Combinatorica 7 (1987), no. 1, 39–48. MR 905150, DOI 10.1007/BF02579199
• Runyao Duan, Simone Severini, and Andreas Winter, Zero-error communication via quantum channels, noncommutative graphs, and a quantum Lovász number, IEEE Trans. Inform. Theory 59 (2013), no. 2, 1164–1174. MR 3015725, DOI 10.1109/TIT.2012.2221677
• Chandan Dubey, Uriel Feige, and Walter Unger, Hardness results for approximating the bandwidth, J. Comput. System Sci. 77 (2011), no. 1, 62–90. MR 2767125, DOI 10.1016/j.jcss.2010.06.006
• R. J. Duffin, Basic properties of discrete analytic functions, Duke Math. J. 23 (1956), 335–363. MR 78441
• R. J. Duffin, Potential theory on a rhombic lattice, J. Combinatorial Theory 5 (1968), 258–272. MR 232005
• R. J. Duffin and Elmor L. Peterson, The discrete analogue of a class of entire functions, J. Math. Anal. Appl. 21 (1968), 619–642. MR 224840, DOI 10.1016/0022-247X(68)90268-0
• Art M. Duval and Victor Reiner, Perron-Frobenius type results and discrete versions of nodal domain theorems, Linear Algebra Appl. 294 (1999), no. 1-3, 259–268. MR 1693975, DOI 10.1016/S0024-3795(99)00090-7
• I. A. Dynnikov and S. P. Novikov, Geometry of the triangle equation on two-manifolds, Mosc. Math. J. 3 (2003), no. 2, 419–438, 742 (English, with English and Russian summaries). Dedicated to Vladimir I. Arnold on the occasion of his 65th birthday. MR 2025267, DOI 10.17323/1609-4514-2003-3-2-419-438
• Jack Edmonds, Submodular functions, matroids, and certain polyhedra, Combinatorial Structures and their Applications (Proc. Calgary Internat. Conf., Calgary, Alta., 1969) Gordon and Breach, New York, 1970, pp. 69–87. MR 0270945
• Pál Erdős, On even subgraphs of graphs, Mat. Lapok 18 (1967), 283–288 (Hungarian, with English summary). MR 238731
• N. G. de Bruijn and P. Erdös, A colour problem for infinite graphs and a problem in the theory of relations, Nederl. Akad. Wetensch. Proc. Ser. A. 54 = Indagationes Math. 13 (1951), 369–373. MR 0046630
• Paul Erdős and Tibor Gallai, On the minimal number of vertices representing the edges of a graph, Magyar Tud. Akad. Mat. Kutató Int. Közl. 6 (1961), 181–203 (English, with Russian summary). MR 144332
• Paul Erdős, Frank Harary, and William T. Tutte, On the dimension of a graph, Mathematika 12 (1965), 118–122. MR 188096, DOI 10.1112/S0025579300005222
• P. Erdős, A. Hajnal, and J. W. Moon, A problem in graph theory, Amer. Math. Monthly 71 (1964), 1107–1110. MR 170339, DOI 10.2307/2311408
• P. Erdős and L. Lovász, Problems and results on $3$-chromatic hypergraphs and some related questions, Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vols. I, II, III, Colloq. Math. Soc. János Bolyai, Vol. 10, North-Holland, Amsterdam, 1975, pp. 609–627. MR 0382050
• István Fáry, On straight line representation of planar graphs, Acta Univ. Szeged. Sect. Sci. Math. 11 (1948), 229–233. MR 26311
• Uriel Feige, Randomized graph products, chromatic numbers, and the Lovász $\vartheta$-function, Combinatorica 17 (1997), no. 1, 79–90. MR 1466577, DOI 10.1007/BF01196133
• Uriel Feige, Approximating the bandwidth via volume respecting embeddings, J. Comput. System Sci. 60 (2000), no. 3, 510–539. 30th Annual ACM Symposium on Theory of Computing (Dallas, TX, 1998). MR 1770195, DOI 10.1006/jcss.1999.1682
• Uriel Feige and Michael Langberg, The $\rm RPR^2$ rounding technique for semidefinite programs, J. Algorithms 60 (2006), no. 1, 1–23. MR 2228942, DOI 10.1016/j.jalgor.2004.11.003
• Jacqueline Ferrand, Fonctions préharmoniques et fonctions préholomorphes, Bull. Sci. Math. (2) 68 (1944), 152–180 (French). MR 13411
• Charles M. Fiduccia, Edward R. Scheinerman, Ann Trenk, and Jennifer S. Zito, Dot product representations of graphs, Discrete Math. 181 (1998), no. 1-3, 113–138. MR 1600755, DOI 10.1016/S0012-365X(97)00049-6
• L. R. Ford Jr. and D. R. Fulkerson, Flows in networks, Princeton University Press, Princeton, N.J., 1962. MR 0159700
• Jacob Fox and László Miklós Lovász, A tight lower bound for Szemerédi’s regularity lemma, Combinatorica 37 (2017), no. 5, 911–951. MR 3737374, DOI 10.1007/s00493-016-3274-4
• A. Föppl: Theorie des Fachwerks, Verlag Arthur Felix, Leipzig, 1880.
• Jean-Claude Fournier, Pavage des figures planes sans trous par des dominos: fondement graphique de l’algorithme de Thurston et parallélisation, C. R. Acad. Sci. Paris Sér. I Math. 320 (1995), no. 1, 107–112 (French, with English and French summaries). MR 1320841, DOI 10.1016/0304-3975(95)00204-9
• P. Frankl and H. Maehara, The Johnson-Lindenstrauss lemma and the sphericity of some graphs, J. Combin. Theory Ser. B 44 (1988), no. 3, 355–362. MR 941443, DOI 10.1016/0095-8956(88)90043-3
• P. Frankl and H. Maehara, On the contact dimensions of graphs, Discrete Comput. Geom. 3 (1988), no. 1, 89–96. MR 918182, DOI 10.1007/BF02187899
• P. Frankl and R. M. Wilson, Intersection theorems with geometric consequences, Combinatorica 1 (1981), no. 4, 357–368. MR 647986, DOI 10.1007/BF02579457
• Hubert de Fraysseix, Patrice Ossona de Mendez, and Pierre Rosenstiehl, On triangle contact graphs, Combin. Probab. Comput. 3 (1994), no. 2, 233–246. MR 1288442, DOI 10.1017/S0963548300001139
• H. de Fraysseix, J. Pach, and R. Pollack, How to draw a planar graph on a grid, Combinatorica 10 (1990), no. 1, 41–51. MR 1075065, DOI 10.1007/BF02122694
• Alan Frieze and Ravi Kannan, Quick approximation to matrices and applications, Combinatorica 19 (1999), no. 2, 175–220. MR 1723039, DOI 10.1007/s004930050052
• Z. Füredi and J. Komlós, The eigenvalues of random symmetric matrices, Combinatorica 1 (1981), no. 3, 233–241. MR 637828, DOI 10.1007/BF02579329
• Zoltán Füredi and Richard Stanley, Sets of vectors with many orthogonal pairs, Graphs Combin. 8 (1992), no. 4, 391–394. MR 1554361, DOI 10.1007/BF02351595
• M. R. Garey and D. S. Johnson, The complexity of near-optimal graph coloring, J. Assoc. Comp. Mach. 23 (1976), no. 1, 43–49. MR 0426496, DOI 10.1145/321921.321926
• James Geelen and Satoru Iwata, Matroid matching via mixed skew-symmetric matrices, Combinatorica 25 (2005), no. 2, 187–215. MR 2127610, DOI 10.1007/s00493-005-0013-7
• M. Giustina, M.A.M. Versteegh, S. Wengerowsky, J. Handsteiner, A. Hochrainer, K. Phelan, F. Steinlechner, J. Kofler, J.-A. Larsson,C. Abellan, W. Amaya, V. Pruneri, M.W. Mitchell, J. Beyer, T. Gerrits, A.E. Lita, L.K. Shalm, S.W. Nam, T. Scheidl, R. Ursin, B. Wittmann, A. Zeilinger: A significant-loophole-free test of Bell’s theorem with entangled photons, Phys. Rev. Lett. 115 (2015), 250401.
• Herman Gluck, Almost all simply connected closed surfaces are rigid, Geometric topology (Proc. Conf., Park City, Utah, 1974) Lecture Notes in Math., Vol. 438, Springer, Berlin, 1975, pp. 225–239. MR 0400239
• Michel X. Goemans and David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. Assoc. Comput. Mach. 42 (1995), no. 6, 1115–1145. MR 1412228, DOI 10.1145/227683.227684
• Steven J. Gortler and Dylan P. Thurston, Characterizing the universal rigidity of generic frameworks, Discrete Comput. Geom. 51 (2014), no. 4, 1017–1036. MR 3216675, DOI 10.1007/s00454-014-9590-9
• Steven J. Gortler, Alexander D. Healy, and Dylan P. Thurston, Characterizing generic global rigidity, Amer. J. Math. 132 (2010), no. 4, 897–939. MR 2663644, DOI 10.1353/ajm.0.0132
• Jack Graver, Brigitte Servatius, and Herman Servatius, Combinatorial rigidity, Graduate Studies in Mathematics, vol. 2, American Mathematical Society, Providence, RI, 1993. MR 1251062, DOI 10.1090/gsm/002
• M. Grötschel, L. Lovász, and A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization, Combinatorica 1 (1981), no. 2, 169–197. MR 625550, DOI 10.1007/BF02579273
• M. Grötschel, L. Lovász, and A. Schrijver, Polynomial algorithms for perfect graphs, Topics on perfect graphs, North-Holland Math. Stud., vol. 88, North-Holland, Amsterdam, 1984, pp. 325–356. MR 778770, DOI 10.1016/S0304-0208(08)72943-8
• M. Grötschel, L. Lovász, and A. Schrijver, Relaxations of vertex packing, J. Combin. Theory Ser. B 40 (1986), no. 3, 330–343. MR 842998, DOI 10.1016/0095-8956(86)90087-0
• M. Grötschel, L. Lovász, A. Schrijver: Geometric Algorithms and Combinatorial Optimization, Springer (1988).
• Branko Grünbaum and Theodore S. Motzkin, On polyhedral graphs, Proc. Sympos. Pure Math., Vol. VII, Amer. Math. Soc., Providence, R.I., 1963, pp. 285–290. MR 0153005
• Venkatesan Guruswami, Maximum cut on line and total graphs, Discrete Appl. Math. 92 (1999), no. 2-3, 217–221. MR 1697554, DOI 10.1016/S0166-218X(99)00056-6
• Willem Haemers, On some problems of Lovász concerning the Shannon capacity of a graph, IEEE Trans. Inform. Theory 25 (1979), no. 2, 231–232. MR 521317, DOI 10.1109/TIT.1979.1056027
• A. Hajnal, A theorem on $k$-saturated graphs, Canadian J. Math. 17 (1965), 720–724. MR 179103, DOI 10.4153/CJM-1965-072-1
• Johan Håstad, Some optimal inapproximability results, STOC ’97 (El Paso, TX), ACM, New York, 1999, pp. 1–10. MR 1715618
• Johan Håstad, Clique is hard to approximate within $n^{1-\epsilon }$, Acta Math. 182 (1999), no. 1, 105–142. MR 1687331, DOI 10.1007/BF02392825
• Zheng-Xu He and O. Schramm, Hyperbolic and parabolic packings, Discrete Comput. Geom. 14 (1995), no. 2, 123–149. MR 1331923, DOI 10.1007/BF02570699
• Zheng-Xu He and Oded Schramm, On the convergence of circle packings to the Riemann map, Invent. Math. 125 (1996), no. 2, 285–305. MR 1395721, DOI 10.1007/s002220050076
• Bruce Hendrickson, Conditions for unique graph realizations, SIAM J. Comput. 21 (1992), no. 1, 65–84. MR 1148818, DOI 10.1137/0221008
• L. Henneberg: Die graphische Statik der starren Systeme, Leipzig, 1911.
• B. Hensen, H. Bernien, A.E. Dréau, A. Reiserer, N. Kalb, M.S. Blok, J. Ruitenberg, R.F.L. Vermeulen, R.N. Schouten, C. Abellán, W. Amaya, V. Pruneri, M.W. Mitchell, M. Markham, D.J. Twitchen, D. Elkouss, S. Wehner, T.H. Taminiau and R. Hanson: Loophole-free Bell inequality violation using electron spins separated by 1.3 kilometres, Nature 526 (2015), 682–686.
• Jürgen Herzog, Antonio Macchia, Sara Saeedi Madani, and Volkmar Welker, On the ideal of orthogonal representations of a graph in $\Bbb {R}^2$, Adv. in Appl. Math. 71 (2015), 146–173. MR 3406962, DOI 10.1016/j.aam.2015.09.009
• J. Hladký, I. Rocha: Independent sets, cliques, and colorings in graphons, https://arxiv.org/abs/1712.07367
• Alan J. Hoffman, Some recent results on spectral properties of graphs, Beiträge zur Graphentheorie (Kolloquium, Manebach, 1967) Teubner, Leipzig, 1968, pp. 75–80. MR 0245462
• A. J. Hoffman, On graphs whose least eigenvalue exceeds $-1-\sqrt {2}$, Linear Algebra Appl. 16 (1977), no. 2, 153–165. MR 469826, DOI 10.1016/0024-3795(77)90027-1
• Alan J. Hoffman, On eigenvalues and colorings of graphs, Graph Theory and its Applications (Proc. Advanced Sem., Math. Research Center, Univ. of Wisconsin, Madison, Wis., 1969) Academic Press, New York, 1970, pp. 79–91. MR 0284373
• Hein van der Holst, A short proof of the planarity characterization of Colin de Verdière, J. Combin. Theory Ser. B 65 (1995), no. 2, 269–272. MR 1358989, DOI 10.1006/jctb.1995.1054
• H. van der Holst: Topological and Spectral Graph Characterizations, Ph.D. Thesis, University of Amsterdam, Amsterdam, 1996.
• Hein van der Holst, Two tree-width-like graph invariants, Combinatorica 23 (2003), no. 4, 633–651. MR 2046827, DOI 10.1007/s00493-003-0038-8
• Hein van der Holst, Monique Laurent, and Alexander Schrijver, On a minor-monotone graph invariant, J. Combin. Theory Ser. B 65 (1995), no. 2, 291–304. MR 1358991, DOI 10.1006/jctb.1995.1056
• Hein van der Holst, László Lovász, and Alexander Schrijver, On the invariance of Colin de Verdière’s graph parameter under clique sums, Linear Algebra Appl. 226/228 (1995), 509–517. MR 1344582, DOI 10.1016/0024-3795(95)00160-S
• H. van der Holst, L. Lovász, and A. Schrijver, The Colin de Verdière graph parameter, Graph theory and combinatorial biology (Balatonlelle, 1996) Bolyai Soc. Math. Stud., vol. 7, János Bolyai Math. Soc., Budapest, 1999, pp. 29–85. MR 1673503
• M. Howard, J. Wallman, V. Veitch and J. Emerson: Contextuality supplies the ‘magic’ for quantum computation, Nature 510 (2014), 351–355.
• Jacob E. Goodman and Joseph O’Rourke (eds.), Handbook of discrete and computational geometry, 2nd ed., Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2004. MR 2082993, DOI 10.1201/9781420035315
• Masao Iri, On an extension of the maximum-flow minimum-cut theorem to multicommodity flows, J. Operations Res. Soc. Japan 13 (1970/71), 129–135. MR 292487
• R. Isaacs, Monodiffric functions, Natl. Bureau Standards App. Math. Series 18 (1952), 257–266.
• Bill Jackson and Tibor Jordán, Connected rigidity matroids and unique realizations of graphs, J. Combin. Theory Ser. B 94 (2005), no. 1, 1–29. MR 2130278, DOI 10.1016/j.jctb.2004.11.002
• Bill Jackson and J. C. Owen, A characterisation of the generic rigidity of 2-dimensional point-line frameworks, J. Combin. Theory Ser. B 119 (2016), 96–121. MR 3486339, DOI 10.1016/j.jctb.2015.12.007
• Bill Jackson and Peter Keevash, Necessary conditions for the global rigidity of direction-length frameworks, Discrete Comput. Geom. 46 (2011), no. 1, 72–85. MR 2794358, DOI 10.1007/s00454-011-9326-z
• William B. Johnson and Joram Lindenstrauss, Extensions of Lipschitz mappings into a Hilbert space, Conference in modern analysis and probability (New Haven, Conn., 1982) Contemp. Math., vol. 26, Amer. Math. Soc., Providence, RI, 1984, pp. 189–206. MR 737400, DOI 10.1090/conm/026/737400
• Mark Jerrum and Alistair Sinclair, Approximating the permanent, SIAM J. Comput. 18 (1989), no. 6, 1149–1178. MR 1025467, DOI 10.1137/0218077
• Johan Jonasson and Oded Schramm, On the cover time of planar graphs, Electron. Comm. Probab. 5 (2000), 85–90. MR 1781842, DOI 10.1214/ECP.v5-1022
• Ferenc Juhász, The asymptotic behaviour of Lovász’ $\theta$ function for random graphs, Combinatorica 2 (1982), no. 2, 153–155. MR 685042, DOI 10.1007/BF02579314
• G. A. Kabatjanskiĭ and V. I. Levenšteĭn, Bounds for packings on the sphere and in space, Problemy Peredači Informacii 14 (1978), no. 1, 3–25 (Russian). MR 0514023
• Ross J. Kang, László Lovász, Tobias Müller, and Edward R. Scheinerman, Dot product representations of planar graphs, Electron. J. Combin. 18 (2011), no. 1, Paper 216, 14. MR 2853073, DOI 10.37236/703
• D. Karger, R. Motwani and M. Sudan: Approximate graph coloring by semidefinite programming, \FOCS35 (1994), 2–13.
• H. Karloff and U. Zwick: A 7/8-Approximation Algorithm for MAX 3SAT? \FOCS38 (1997), 406–415.
• B. S. Kashin and S. V. Konyagin, Systems of vectors in Hilbert space, Trudy Mat. Inst. Steklov. 157 (1981), 64–67, 235 (Russian). Number theory, mathematical analysis and their applications. MR 651759
• G. Katona and G. Korvin, Functions defined on a directed graph, Theory of Graphs (Proc. Colloq., Tihany, 1966) Academic Press, New York, 1968, pp. 209–213. MR 0233736
• Ken-Ichi Kawarabayashi and Mikkel Thorup, Coloring 3-colorable graphs with less than $n^{1/5}$ colors, J. ACM 64 (2017), no. 1, Art. 4, 23. MR 3634492, DOI 10.1145/3001582
• R. Kenyon, The Laplacian and Dirac operators on critical planar graphs, Invent. Math. 150 (2002), no. 2, 409–439. MR 1933589, DOI 10.1007/s00222-002-0249-4
• Richard Kenyon, Conformal invariance of domino tiling, Ann. Probab. 28 (2000), no. 2, 759–795. MR 1782431, DOI 10.1214/aop/1019160260
• Richard Kenyon, Lectures on dimers, Statistical mechanics, IAS/Park City Math. Ser., vol. 16, Amer. Math. Soc., Providence, RI, 2009, pp. 191–230. MR 2523460, DOI 10.1090/pcms/016/04
• Richard Kenyon and Jean-Marc Schlenker, Rhombic embeddings of planar quad-graphs, Trans. Amer. Math. Soc. 357 (2005), no. 9, 3443–3458 (English, with English and French summaries). MR 2146632, DOI 10.1090/S0002-9947-04-03545-7
• Sanjeev Khanna, Nathan Linial, and Shmuel Safra, On the hardness of approximating the chromatic number, Combinatorica 20 (2000), no. 3, 393–415. MR 1774844, DOI 10.1007/s004930070013
• Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell, Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?, SIAM J. Comput. 37 (2007), no. 1, 319–357. MR 2306295, DOI 10.1137/S0097539705447372
• Christer O. Kiselman, Functions on discrete sets holomorphic in the sense of Isaacs, or monodiffric functions of the first kind, Sci. China Ser. A 48 (2005), no. suppl., 86–96. MR 2156493, DOI 10.1007/BF02884698
• Alexander A. Klyachko, M. Ali Can, Sinem Binicioğlu, and Alexander S. Shumovsky, Simple test for hidden variables in spin-1 systems, Phys. Rev. Lett. 101 (2008), no. 2, 020403, 4. MR 2430247, DOI 10.1103/PhysRevLett.101.020403
• Donald E. Knuth, The sandwich theorem, Electron. J. Combin. 1 (1994), Article 1, approx. 48. MR 1269161, DOI 10.37236/1193
• P. Koebe: Kontaktprobleme der konformen Abbildung, Berichte über die Verhandlungen Sächs. Akad. Wiss., Math.–Phys. Klasse, 88 (1936) 141–164.
• S. V. Konjagin, Systems of vectors in Euclidean space and an extremal problem for polynomials, Mat. Zametki 29 (1981), no. 1, 63–74, 155 (Russian). MR 604151
• Bernhard Korte and Jens Vygen, Combinatorial optimization, 4th ed., Algorithms and Combinatorics, vol. 21, Springer-Verlag, Berlin, 2008. Theory and algorithms. MR 2369759
• Andreĭ Kotlov, Rank and chromatic number of a graph, J. Graph Theory 26 (1997), no. 1, 1–8. MR 1464336, DOI 10.1002/(SICI)1097-0118(199709)26:1<1::AID-JGT1>3.3.CO;2-U
• Andreĭ Kotlov, Spectral characterization of tree-width-two graphs, Combinatorica 20 (2000), no. 1, 147–152. MR 1770529, DOI 10.1007/s004930070038
• Andreĭ Kotlov, Minors and strong products, European J. Combin. 22 (2001), no. 4, 511–512. MR 1829745, DOI 10.1006/eujc.2000.0428
• Andrew Kotlov and László Lovász, The rank and size of graphs, J. Graph Theory 23 (1996), no. 2, 185–189. MR 1408346, DOI 10.1002/(SICI)1097-0118(199610)23:2<185::AID-JGT9>3.3.CO;2-X
• Andrew Kotlov, László Lovász, and Santosh Vempala, The Colin de Verdière number and sphere representations of a graph, Combinatorica 17 (1997), no. 4, 483–521. MR 1645686, DOI 10.1007/BF01195002
• Greg Kuperberg, From the Mahler conjecture to Gauss linking integrals, Geom. Funct. Anal. 18 (2008), no. 3, 870–892. MR 2438998, DOI 10.1007/s00039-008-0669-4
• G. Laman, On graphs and rigidity of plane skeletal structures, J. Engrg. Math. 4 (1970), 331–340. MR 269535, DOI 10.1007/BF01534980
• D. G. Larman and C. A. Rogers, The realization of distances within sets in Euclidean space, Mathematika 19 (1972), 1–24. MR 319055, DOI 10.1112/S0025579300004903
• Monique Laurent and Svatopluk Poljak, On the facial structure of the set of correlation matrices, SIAM J. Matrix Anal. Appl. 17 (1996), no. 3, 530–547. MR 1397243, DOI 10.1137/0617031
• M. Laurent and F. Rendl: Semidefinite Programming and Integer Programming, in: Discrete Optimization, Handbooks in Operations Research and Management Science 12 (2005), 393–514.
• M. Laurent and A. Varvitsiotis, Positive semidefinite matrix completion, universal rigidity and the strong Arnold property, Linear Algebra Appl. 452 (2014), 292–317. MR 3201103, DOI 10.1016/j.laa.2014.03.015
• F.T. Leighton and S. Rao, An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms, \FOCS29 (1988), 422-431.
• Yong Lin, Gábor Lippner, Dan Mangoubi, and Shing-Tung Yau, Nodal geometry of graphs on surfaces, Discrete Contin. Dyn. Syst. 28 (2010), no. 3, 1291–1298. MR 2644790, DOI 10.3934/dcds.2010.28.1291
• Nathan Linial, Eran London, and Yuri Rabinovich, The geometry of graphs and some of its algorithmic applications, Combinatorica 15 (1995), no. 2, 215–245. MR 1337355, DOI 10.1007/BF01200757
• N. Linial, L. Lovász, and A. Wigderson, Rubber bands, convex embeddings and graph connectivity, Combinatorica 8 (1988), no. 1, 91–102. MR 951998, DOI 10.1007/BF02122557
• Richard J. Lipton and Robert Endre Tarjan, A separator theorem for planar graphs, SIAM J. Appl. Math. 36 (1979), no. 2, 177–189. MR 524495, DOI 10.1137/0136016
• L. Lovász, Normal hypergraphs and the perfect graph conjecture, Discrete Math. 2 (1972), no. 3, 253–267. MR 302480, DOI 10.1016/0012-365X(72)90006-4
• László Lovász, On minimax theorems of combinatorics, Mat. Lapok 26 (1975), no. 3-4, 209–264 (1978) (Hungarian). MR 510823
• L. Lovász, Flats in matroids and geometric graphs, Combinatorial surveys (Proc. Sixth British Combinatorial Conf., Royal Holloway Coll., Egham, 1977) Academic Press, London, 1977, pp. 45–86. MR 0480111
• L. Lovász, Some finite basis theorems on graph theory, Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976) Colloq. Math. Soc. János Bolyai, vol. 18, North-Holland, Amsterdam-New York, 1978, pp. 717–729. MR 519305
• László Lovász, Topological and algebraic methods in graph theory, Graph theory and related topics (Proc. Conf., Univ. Waterloo, Waterloo, Ont., 1977) Academic Press, New York-London, 1979, pp. 1–14. MR 538032
• László Lovász, On the Shannon capacity of a graph, IEEE Trans. Inform. Theory 25 (1979), no. 1, 1–7. MR 514926, DOI 10.1109/TIT.1979.1055985
• L. Lovász, Selecting independent lines from a family of lines in a space, Acta Sci. Math. (Szeged) 42 (1980), no. 1-2, 121–131. MR 576945
• L. Lovász, Submodular functions and convexity, Mathematical programming: the state of the art (Bonn, 1982) Springer, Berlin, 1983, pp. 235–257. MR 717403
• L. Lovász, Self-dual polytopes and the chromatic number of distance graphs on the sphere, Acta Sci. Math. (Szeged) 45 (1983), no. 1-4, 317–323. MR 708798
• László Lovász, Singular spaces of matrices and their application in combinatorics, Bol. Soc. Brasil. Mat. (N.S.) 20 (1989), no. 1, 87–99. MR 1129080, DOI 10.1007/BF02585470
• László Lovász, Combinatorial problems and exercises, 2nd ed., North-Holland Publishing Co., Amsterdam, 1993. MR 1265492
• L. Lovász, Random walks on graphs: a survey, Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993) Bolyai Soc. Math. Stud., vol. 2, János Bolyai Math. Soc., Budapest, 1996, pp. 353–397. MR 1395866
• László Lovász, Steinitz representations of polyhedra and the Colin de Verdière number, J. Combin. Theory Ser. B 82 (2001), no. 2, 223–236. MR 1842113, DOI 10.1006/jctb.2000.2027
• L. Lovász, Semidefinite programs and combinatorial optimization, Recent advances in algorithms and combinatorics, CMS Books Math./Ouvrages Math. SMC, vol. 11, Springer, New York, 2003, pp. 137–194. MR 1952986, DOI 10.1007/0-387-22444-0_{6}
• László Lovász, Graph minor theory, Bull. Amer. Math. Soc. (N.S.) 43 (2006), no. 1, 75–86. MR 2188176, DOI 10.1090/S0273-0979-05-01088-8
• László Lovász, Large networks and graph limits, American Mathematical Society Colloquium Publications, vol. 60, American Mathematical Society, Providence, RI, 2012. MR 3012035, DOI 10.1090/coll/060
• L. Lovász and M. D. Plummer, Matching theory, North-Holland Mathematics Studies, vol. 121, North-Holland Publishing Co., Amsterdam; North-Holland Publishing Co., Amsterdam, 1986. Annals of Discrete Mathematics, 29. MR 859549
• L. Lovász, M. Saks, and A. Schrijver, Orthogonal representations and connectivity of graphs, Linear Algebra Appl. 114/115 (1989), 439–454. MR 986889, DOI 10.1016/0024-3795(89)90475-8
• László Lovász and Alexander Schrijver, A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs, Proc. Amer. Math. Soc. 126 (1998), no. 5, 1275–1285. MR 1443840, DOI 10.1090/S0002-9939-98-04244-0
• L. Lovász and A. Schrijver, On the null space of a Colin de Verdière matrix, Ann. Inst. Fourier (Grenoble) 49 (1999), no. 3, 1017–1026 (English, with English and French summaries). Symposium à la Mémoire de François Jaeger (Grenoble, 1998). MR 1703435
• László Lovász and Balázs Szegedy, Limits of dense graph sequences, J. Combin. Theory Ser. B 96 (2006), no. 6, 933–957. MR 2274085, DOI 10.1016/j.jctb.2006.05.002
• László Lovász and Balázs Szegedy, Szemerédi’s lemma for the analyst, Geom. Funct. Anal. 17 (2007), no. 1, 252–270. MR 2306658, DOI 10.1007/s00039-007-0599-6
• L. Lovász and B. Szegedy: The graph theoretic moment problem, https://arxiv.org/abs/1010.5159
• L. Lovász and K. Vesztergombi, Geometric representations of graphs, Paul Erdős and his mathematics, II (Budapest, 1999) Bolyai Soc. Math. Stud., vol. 11, János Bolyai Math. Soc., Budapest, 2002, pp. 471–498. MR 1954739
• L. Lovász and Y. Yemini, On generic rigidity in the plane, SIAM J. Algebraic Discrete Methods 3 (1982), no. 1, 91–98. MR 644960, DOI 10.1137/0603009
• A. Lubotzky, R. Phillips, and P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988), no. 3, 261–277. MR 963118, DOI 10.1007/BF02126799
• Hiroshi Maehara and Vojtěch Rödl, On the dimension to represent a graph by a unit distance graph, Graphs Combin. 6 (1990), no. 4, 365–367. MR 1092585, DOI 10.1007/BF01787703
• Avner Magen, Dimensionality reductions in $l_2$ that preserve volumes and distance to affine spaces, Discrete Comput. Geom. 38 (2007), no. 1, 139–153. MR 2322120, DOI 10.1007/s00454-007-1329-4
• P. Mani, Automorphismen von polyedrischen Graphen, Math. Ann. 192 (1971), 279–303 (German). MR 296808, DOI 10.1007/BF02075357
• G. A. Margulis, Explicit constructions of expanders, Problemy Peredači Informacii 9 (1973), no. 4, 71–80 (Russian). MR 0484767
• J. H. Mason, Matroids as the study of geometrical configurations, Higher combinatorics (Proc. NATO Advanced Study Inst., Berlin, 1976) NATO Adv. Study Inst. Ser. C: Math. Phys. Sci., vol. 31, Reidel, Dordrecht-Boston, Mass., 1977, pp. 133–176. MR 519783
• Pascal Massart, Concentration inequalities and model selection, Lecture Notes in Mathematics, vol. 1896, Springer, Berlin, 2007. Lectures from the 33rd Summer School on Probability Theory held in Saint-Flour, July 6–23, 2003; With a foreword by Jean Picard. MR 2319879
• Jiří Matoušek, On embedding expanders into $l_p$ spaces, Israel J. Math. 102 (1997), 189–197. MR 1489105, DOI 10.1007/BF02773799
• Jiří Matoušek, Lectures on discrete geometry, Graduate Texts in Mathematics, vol. 212, Springer-Verlag, New York, 2002. MR 1899299, DOI 10.1007/978-1-4613-0039-7
• Jiří Matoušek, Using the Borsuk-Ulam theorem, Universitext, Springer-Verlag, Berlin, 2003. Lectures on topological methods in combinatorics and geometry; Written in cooperation with Anders Björner and Günter M. Ziegler. MR 1988723
• Jiří Matoušek, On variants of the Johnson-Lindenstrauss lemma, Random Structures Algorithms 33 (2008), no. 2, 142–156. MR 2436844, DOI 10.1002/rsa.20218
• J. Matoušek: Lecture notes on metric embeddings, http://kam.mff.cuni.cz/~matousek/ba-a4.pdf
• J. Matoušek and A. Naor: Open problems on embeddings of finite metric spaces http://kam.mff.cuni.cz/~matousek/metrop.ps
• R. J. McEliece, E. R. Rodemich, and H. C. Rumsey Jr., The Lovász bound and some generalizations, J. Combin. Inform. System Sci. 3 (1978), no. 3, 134–152. MR 505587
• Christian Mercat, Discrete Riemann surfaces and the Ising model, Comm. Math. Phys. 218 (2001), no. 1, 177–216. MR 1824204, DOI 10.1007/s002200000348
• C. Mercat: Discrete polynomials and discrete holomorphic approximation (2002) http://arxiv.org/abs/math-ph/0206041
• Christian Mercat, Exponentials form a basis of discrete holomorphic functions on a compact, Bull. Soc. Math. France 132 (2004), no. 2, 305–326 (English, with English and French summaries). MR 2076370, DOI 10.24033/bsmf.2467
• Mirko M. Milić, General passive networks–solvability, degeneracies, and order of complexity, IEEE Trans. Circuits and Systems CAS-2 (1974), 177–183. MR 444328, DOI 10.1109/TCS.1974.1083845
• Gary L. Miller, Shang-Hua Teng, William Thurston, and Stephen A. Vavasis, Separators for sphere-packings and nearest neighbor graphs, J. ACM 44 (1997), no. 1, 1–29. MR 1438463, DOI 10.1145/256292.256294
• Bojan Mohar and Svatopluk Poljak, Eigenvalues and max-cut problem, Czechoslovak Math. J. 40(115) (1990), no. 2, 343–352. MR 1046300
• Susan Morey and Rafael H. Villarreal, Edge ideals: algebraic and combinatorial properties, Progress in commutative algebra 1, de Gruyter, Berlin, 2012, pp. 85–126. MR 2932582
• T. S. Motzkin and E. G. Straus, Maxima for graphs and a new proof of a theorem of Turán, Canadian J. Math. 17 (1965), 533–540. MR 175813, DOI 10.4153/CJM-1965-053-6
• Abbe Mowshowitz, Graphs, groups and matrices, Proceedings of the Twenty-Fifth Summer Meeting of the Canadian Mathematical Congress (Lakehead Univ., Thunder Bay, Ont., 1971) Lakehead Univ., Thunder Bay, Ont., 1971, pp. 509–522. MR 0337682
• C. St. J. A. Nash-Williams, Random walk and electric currents in networks, Proc. Cambridge Philos. Soc. 55 (1959), 181–194. MR 124932, DOI 10.1017/s0305004100033879
• C. St. J. A. Nash-Williams, Decomposition of finite graphs into forests, J. London Math. Soc. 39 (1964), 12. MR 161333, DOI 10.1112/jlms/s1-39.1.12
• Yurii Nesterov and Arkadii Nemirovskii, Interior-point polynomial algorithms in convex programming, SIAM Studies in Applied Mathematics, vol. 13, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1994. MR 1258086, DOI 10.1137/1.9781611970791
• Noam Nisan and Avi Wigderson, On rank vs. communication complexity, 35th Annual Symposium on Foundations of Computer Science (Santa Fe, NM, 1994) IEEE Comput. Soc. Press, Los Alamitos, CA, 1994, pp. 831–836. MR 1489253, DOI 10.1109/SFCS.1994.365711
• Cyriel van Nuffelen, Research Problems: A Bound for the Chromatic Number of a Graph, Amer. Math. Monthly 83 (1976), no. 4, 265–266. MR 1538027, DOI 10.2307/2318218
• Michael L. Overton, On minimizing the maximum eigenvalue of a symmetric matrix, SIAM J. Matrix Anal. Appl. 9 (1988), no. 2, 256–268. SIAM Conference on Linear Algebra in Signals, Systems, and Control (Boston, Mass., 1986). MR 938560, DOI 10.1137/0609021
• James G. Oxley, Matroid theory, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, 1992. MR 1207587
• János Pach and Pankaj K. Agarwal, Combinatorial geometry, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1995. A Wiley-Interscience Publication. MR 1354145, DOI 10.1002/9781118033203
• M. Petersdorf and H. Sachs, Spektrum und Automorphismengruppe eines Graphen, Combinatorial theory and its applications, I-III (Proc. Colloq., Balatonfüred, 1969) North-Holland, Amsterdam, 1970, pp. 891–907 (German). MR 0309792
• Asher Peres, Two simple proofs of the Kochen-Specker theorem, J. Phys. A 24 (1991), no. 4, L175–L178. MR 1104166
• Svatopluk Poljak and Franz Rendl, Nonpolyhedral relaxations of graph-bisection problems, SIAM J. Optim. 5 (1995), no. 3, 467–487. MR 1344666, DOI 10.1137/0805024
• H. Pollaczek-Geiringer: Über die Gliederung ebener Fachwerke, Z. Angew. Math. und Mech. 7 (1927), 58–72.
• Georg Pólya, Über eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Straßennetz, Math. Ann. 84 (1921), no. 1-2, 149–160 (German). MR 1512028, DOI 10.1007/BF01458701
• Lorant Porkolab and Leonid Khachiyan, On the complexity of semidefinite programs, J. Global Optim. 10 (1997), no. 4, 351–365. MR 1457182, DOI 10.1023/A:1008203903341
• A. M. Raigorodskii, On the chromatic numbers of spheres in ${\Bbb R}^n$, Combinatorica 32 (2012), no. 1, 111–123. MR 2927634, DOI 10.1007/s00493-012-2709-9
• Motakuri V. Ramana, An exact duality theory for semidefinite programming and its complexity implications, Math. Programming 77 (1997), no. 2, Ser. B, 129–162. Semidefinite programming. MR 1461379, DOI 10.1016/S0025-5610(96)00082-2
• András Recski, Matroid theory and its applications in electric network theory and in statics, Algorithms and Combinatorics, vol. 6, Springer-Verlag, Berlin; Akadémiai Kiadó (Publishing House of the Hungarian Academy of Sciences), Budapest, 1989. MR 1027839, DOI 10.1007/978-3-662-22143-3
• J. Reiterman, V. Rödl, and E. Šiňajová, Embeddings of graphs in Euclidean spaces, Discrete Comput. Geom. 4 (1989), no. 4, 349–364. MR 996768, DOI 10.1007/BF02187736
• J. Reiterman, V. Rödl, and E. Šiňajová, On embedding of graphs into Euclidean spaces of small dimension, J. Combin. Theory Ser. B 56 (1992), no. 1, 1–8. MR 1182453, DOI 10.1016/0095-8956(92)90002-F
• Jürgen Richter-Gebert, Realization spaces of polytopes, Lecture Notes in Mathematics, vol. 1643, Springer-Verlag, Berlin, 1996. MR 1482230, DOI 10.1007/BFb0093761
• Igor Rivin, A characterization of ideal polyhedra in hyperbolic $3$-space, Ann. of Math. (2) 143 (1996), no. 1, 51–70. MR 1370757, DOI 10.2307/2118652
• Igor Rivin, Combinatorial optimization in geometry, Adv. in Appl. Math. 31 (2003), no. 1, 242–271. MR 1985831, DOI 10.1016/S0196-8858(03)00093-9
• Neil Robertson and P. D. Seymour, Graph minors. III. Planar tree-width, J. Combin. Theory Ser. B 36 (1984), no. 1, 49–64. MR 742386, DOI 10.1016/0095-8956(84)90013-3
• Neil Robertson and P. D. Seymour, Graph minors. V. Excluding a planar graph, J. Combin. Theory Ser. B 41 (1986), no. 1, 92–114. MR 854606, DOI 10.1016/0095-8956(86)90030-4
• Neil Robertson and P. D. Seymour, Graph minors. XVI. Excluding a non-planar graph, J. Combin. Theory Ser. B 89 (2003), no. 1, 43–76. MR 1999736, DOI 10.1016/S0095-8956(03)00042-X
• Neil Robertson, Paul Seymour, and Robin Thomas, Sachs’ linkless embedding conjecture, J. Combin. Theory Ser. B 64 (1995), no. 2, 185–227. MR 1339849, DOI 10.1006/jctb.1995.1032
• Burt Rodin and Dennis Sullivan, The convergence of circle packings to the Riemann mapping, J. Differential Geom. 26 (1987), no. 2, 349–360. MR 906396
• Moshe Rosenfeld, Almost orthogonal lines in $E^d$, Applied geometry and discrete mathematics, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 4, Amer. Math. Soc., Providence, RI, 1991, pp. 489–492. MR 1116372, DOI 10.1090/dimacs/004/38
• Horst Sachs, Coin graphs, polyhedra, and conformal mapping, Discrete Math. 134 (1994), no. 1-3, 133–138. Algebraic and topological methods in graph theory (Lake Bled, 1991). MR 1303402, DOI 10.1016/0012-365X(93)E0068-F
• L. A. Santaló, An affine invariant for convex bodies of $n$-dimensional space, Portugal. Math. 8 (1949), 155–161 (Spanish). MR 39293
• Arthur Sard, The measure of the critical values of differentiable maps, Bull. Amer. Math. Soc. 48 (1942), 883–890. MR 7523, DOI 10.1090/S0002-9904-1942-07811-6
• Rolf Schneider, Convex bodies: the Brunn-Minkowski theory, Encyclopedia of Mathematics and its Applications, vol. 44, Cambridge University Press, Cambridge, 1993. MR 1216521, DOI 10.1017/CBO9780511526282
• W. Schnyder: Embedding planar graphs on the grid, Proc. First Annual ACM-SIAM Symp. on Discrete Algorithms, SIAM, Philadelphia (1990), 138–148;
• Oded Schramm, Existence and uniqueness of packings with specified combinatorics, Israel J. Math. 73 (1991), no. 3, 321–341. MR 1135221, DOI 10.1007/BF02773845
• Oded Schramm, How to cage an egg, Invent. Math. 107 (1992), no. 3, 543–560. MR 1150601, DOI 10.1007/BF01231901
• Oded Schramm, Square tilings with prescribed combinatorics, Israel J. Math. 84 (1993), no. 1-2, 97–118. MR 1244661, DOI 10.1007/BF02761693
• Oded Schramm, Scaling limits of loop-erased random walks and uniform spanning trees, Israel J. Math. 118 (2000), 221–288. MR 1776084, DOI 10.1007/BF02803524
• Oded Schramm, Conformally invariant scaling limits: an overview and a collection of problems, International Congress of Mathematicians. Vol. I, Eur. Math. Soc., Zürich, 2007, pp. 513–543. MR 2334202, DOI 10.4171/022-1/20
• Alexander Schrijver, A comparison of the Delsarte and Lovász bounds, IEEE Trans. Inform. Theory 25 (1979), no. 4, 425–429. MR 536232, DOI 10.1109/TIT.1979.1056072
• Alexander Schrijver, Combinatorial optimization. Polyhedra and efficiency. Vol. B, Algorithms and Combinatorics, vol. 24, Springer-Verlag, Berlin, 2003. Matroids, trees, stable sets; Chapters 39–69. MR 1956925
• K. Schütte and B. L. van der Waerden, Das Problem der dreizehn Kugeln, Math. Ann. 125 (1953), 325–334 (German). MR 53537, DOI 10.1007/BF01343127
• J. T. Schwartz, Fast probabilistic algorithms for verification of polynomial identities, J. Assoc. Comput. Mach. 27 (1980), no. 4, 701–717. MR 594695, DOI 10.1145/322217.322225
• Farhad Shahrokhi and D. W. Matula, The maximum concurrent flow problem, J. Assoc. Comput. Mach. 37 (1990), no. 2, 318–334. MR 1072261, DOI 10.1145/77600.77620
• L.K Shalm, E. Meyer-Scott, B.G. Christensen, P. Bierhorst, M.A. Wayne, M.J. Stevens, T. Gerrits, S. Glancy, D.R. Hamel, M.S. Allman, K.J. Coakley, S.D. Dyer, C. Hodge, A.E. Lita, V.B. Verma, C. Lambrocco, E. Tortorici, A.L. Migdall, Y. Zhang, D.R. Kumor, W.H. Farr, F. Marsili, M.D. Shaw, J.A. Stern, C. Abellán, W. Amaya, V. Pruneri, T. Jennewein, M.W. Mitchell, P.G. Kwiat, J.C. Bienfang, R.P. Mirin, E. Knill, S.W. Nam: Strong loophole-free test of local realism, Phy. Rev. Lett. 115 (2015), 250402.
• Stanislav Smirnov, Critical percolation in the plane: conformal invariance, Cardy’s formula, scaling limits, C. R. Acad. Sci. Paris Sér. I Math. 333 (2001), no. 3, 239–244 (English, with English and French summaries). MR 1851632, DOI 10.1016/S0764-4442(01)01991-7
• Stanislav Smirnov, Conformal invariance in random cluster models. I. Holomorphic fermions in the Ising model, Ann. of Math. (2) 172 (2010), no. 2, 1435–1467. MR 2680496, DOI 10.4007/annals.2010.172.1441
• Stanislav Smirnov, Discrete complex analysis and probability, Proceedings of the International Congress of Mathematicians. Volume I, Hindustan Book Agency, New Delhi, 2010, pp. 595–621. MR 2827906
• Daniel A. Spielman, Algorithms, graph theory, and linear equations in Laplacian matrices, Proceedings of the International Congress of Mathematicians. Volume IV, Hindustan Book Agency, New Delhi, 2010, pp. 2698–2722. MR 2827990
• D.A. Spielman and S.-H. Teng: Disk Packings and Planar Separators, 12th Annual ACM Symposium on Computational Geometry (1996a), 349–358.
• Daniel A. Spielman and Shang-Hua Teng, Spectral partitioning works: planar graphs and finite element meshes, 37th Annual Symposium on Foundations of Computer Science (Burlington, VT, 1996) IEEE Comput. Soc. Press, Los Alamitos, CA, 1996, pp. 96–105. MR 1450607, DOI 10.1109/SFCS.1996.548468
• 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
• E. Steinitz: Polyeder und Raumabteilungen, in: Encyclopädie der Math. Wissenschaften 3 (Geometrie) 3AB12, 1–139, 1922.
• Kenneth Stephenson, Introduction to circle packing, Cambridge University Press, Cambridge, 2005. The theory of discrete analytic functions. MR 2131318
• L. Surányi, On line critical graphs, Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vols. I, II, III, Colloq. Math. Soc. János Bolyai, Vol. 10, North-Holland, Amsterdam, 1975, pp. 1411–1444. MR 0401554
• M. Szegedy: A note on the $\theta$ number of Lovász and the generalized Delsarte bound, \FOCS35 (1994), 36–39.
• E. Szemerédi, On sets of integers containing no $k$ elements in arithmetic progression, Acta Arith. 27 (1975), 199–245. MR 369312, DOI 10.4064/aa-27-1-199-245
• Endre Szemerédi, Regular partitions of graphs, Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976) Colloq. Internat. CNRS, vol. 260, CNRS, Paris, 1978, pp. 399–401 (English, with French summary). MR 540024
• Roberto Tamassia, On embedding a graph in the grid with the minimum number of bends, SIAM J. Comput. 16 (1987), no. 3, 421–444. MR 889400, DOI 10.1137/0216030
• Roberto Tamassia, Graph drawing, Handbook of discrete and computational geometry, CRC Press Ser. Discrete Math. Appl., CRC, Boca Raton, FL, 1997, pp. 815–832. MR 1730200
• Roberto Tamassia and Ioannis G. Tollis, Planar grid embedding in linear time, IEEE Trans. Circuits and Systems 36 (1989), no. 9, 1230–1234. MR 1009276, DOI 10.1109/31.34669
• Terence Tao, Szemerédi’s regularity lemma revisited, Contrib. Discrete Math. 1 (2006), no. 1, 8–28. MR 2212136
• W.P. Thurston: The finite Riemann Mapping Theorem, lecture at the International Symposium at Purdue University on the occasion of the proof of the Bieberbach Conjecture (1985).
• W. Thurston: Groups, tilings and finite state automata, AMS colloquim lectures, Summer 1989.
• William P. Thurston, Three-dimensional geometry and topology. Vol. 1, Princeton Mathematical Series, vol. 35, Princeton University Press, Princeton, NJ, 1997. Edited by Silvio Levy. MR 1435975
• W. T. Tutte, The factorization of linear graphs, J. London Math. Soc. 22 (1947), 107–111. MR 23048, DOI 10.1112/jlms/s1-22.2.107
• W. T. Tutte, On the problem of decomposing a graph into $n$ connected factors, J. London Math. Soc. 36 (1961), 221–230. MR 140438, DOI 10.1112/jlms/s1-36.1.221
• 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
• Robert J. Vanderbei, Linear programming, 2nd ed., International Series in Operations Research & Management Science, vol. 37, Kluwer Academic Publishers, Boston, MA, 2001. Foundations and extensions. MR 1845638, DOI 10.1007/978-1-4757-5662-3
• Virginia Vassilevska Williams, Multiplying matrices faster than Coppersmith-Winograd [extended abstract], STOC’12—Proceedings of the 2012 ACM Symposium on Theory of Computing, ACM, New York, 2012, pp. 887–898. MR 2961552, DOI 10.1145/2213977.2214056
• Vijay V. Vazirani, Approximation algorithms, Springer-Verlag, Berlin, 2001. MR 1851303
• Lieven Vandenberghe and Stephen Boyd, Semidefinite programming, SIAM Rev. 38 (1996), no. 1, 49–95. MR 1379041, DOI 10.1137/1038003
• B. L. van der Waerden, Algebra. Teil I, Die Grundlehren der mathematischen Wissenschaften, Band 33, Springer-Verlag, Berlin, 1964 (German). Sechste Auflage der modernen Algebra. MR 0177027
• K. Wagner: Bemerkungen zum Vierfarbenproblem, Jahresber. der Deutschen Math.-Ver. 46 (1936), 26–32.
• Walter Whiteley, Infinitesimally rigid polyhedra. I. Statics of frameworks, Trans. Amer. Math. Soc. 285 (1984), no. 2, 431–465. MR 752486, DOI 10.1090/S0002-9947-1984-0752486-6
• Hassler Whitney, On the Abstract Properties of Linear Dependence, Amer. J. Math. 57 (1935), no. 3, 509–533. MR 1507091, DOI 10.2307/2371182
• Henry Wolkowicz, Some applications of optimization in matrix theory, Linear Algebra Appl. 40 (1981), 101–118. MR 629610, DOI 10.1016/0024-3795(81)90143-9
• Henry Wolkowicz, Romesh Saigal, and Lieven Vandenberghe (eds.), Handbook of semidefinite programming, International Series in Operations Research & Management Science, vol. 27, Kluwer Academic Publishers, Boston, MA, 2000. Theory, algorithms, and applications. MR 1778223, DOI 10.1007/978-1-4615-4381-7
• Doron Zeilberger, A new approach to the theory of discrete analytic functions, J. Math. Anal. Appl. 57 (1977), no. 2, 350–367. MR 450576, DOI 10.1016/0022-247X(77)90265-7
• Doron Zeilberger and Harry Dym, Further properties of discrete analytic functions, J. Math. Anal. Appl. 58 (1977), no. 2, 405–418. MR 435417, DOI 10.1016/0022-247X(77)90218-9
• Sheng-biao Hu, The Laplacian eigenvalue of graphs, J. Math. (Wuhan) 27 (2007), no. 6, 661–663 (English, with English and Chinese summaries). MR 2367618
• Richard Zippel, Probabilistic algorithms for sparse polynomials, Symbolic and algebraic computation (EUROSAM ’79, Internat. Sympos., Marseille, 1979) Lecture Notes in Comput. Sci., vol. 72, Springer, Berlin-New York, 1979, pp. 216–226. MR 575692

\newcommand{\CCA}Combinatorica \newcommand{\JCTB}J. Combin. Theory B \newcommand{\JCTA}J. Combin. Theory A \newcommand{\CPC}Combin. Prob. Comput. \newcommand{\EJC}Europ. J. Combin. \newcommand{\ELJC}Electr. J. Combin. \newcommand{\JGT}J. Graph Theory \newcommand{\ADV}Advances in Math. \newcommand{\ADVA}Advances in Applied Math. \newcommand{\GAFA}Geom. Func. Anal. \def\STOC#1 Proc. #1$^\text {th}$ ACM Symp. on Theory of Comput. \def\FOCS#1 Proc. #1$^\text {th}$ Ann. IEEE Symp. on Found. Comp. Science \def\SODA#1 Proc. #1$^\text {th}$ Ann. ACM-SIAM Symp. on Discrete Algorithms \newcommand{\DCG}Discr. Comput. Geom. \newcommand{\DM}Discr. Math. \newcommand{\DAM}Discr. Applied Math. \newcommand{\SDM}SIAM J. Discr. Math. \newcommand{\TIT}IEEE Trans. Inform. Theory \newcommand{\LAA}Linear Algebra Appl.

• Miklós Ajtai, János Komlós, and Endre Szemerédi, A note on Ramsey numbers, J. Combin. Theory Ser. A 29 (1980), no. 3, 354–360. MR 600598, DOI 10.1016/0097-3165(80)90030-8
• A. Y. Alfakih, Graph connectivity and universal rigidity of bar frameworks. part 3, Discrete Appl. Math. 217 (2017), no. part 3, 707–710. MR 3579945, DOI 10.1016/j.dam.2016.10.008
• A. Y. Alfakih and Yinyu Ye, On affine motions and bar frameworks in general position, Linear Algebra Appl. 438 (2013), no. 1, 31–36. MR 2993361, DOI 10.1016/j.laa.2012.08.031
• F. Alizadeh: Combinatorial optimization with semi-definite matrices, in: Integer Programming and Combinatorial Optimization (Proceedings of IPCO ’92), (eds. E. Balas, G. Cornuéjols and R. Kannan), Carnegie Mellon University Printing (1992), 385–405.
• Farid Alizadeh, Interior point methods in semidefinite programming with applications to combinatorial optimization, SIAM J. Optim. 5 (1995), no. 1, 13–51. MR 1315703, DOI 10.1137/0805002
• N. Alon, Eigenvalues and expanders, Combinatorica 6 (1986), no. 2, 83–96. Theory of computing (Singer Island, Fla., 1984). MR 875835, DOI 10.1007/BF02579166
• Noga Alon, The Shannon capacity of a union, Combinatorica 18 (1998), no. 3, 301–310. MR 1721946, DOI 10.1007/PL00009824
• Noga Alon, Explicit Ramsey graphs and orthonormal labelings, Electron. J. Combin. 1 (1994), Research Paper 12, approx. 8. MR 1302331
• N. Alon: Lovász, vectors, graphs and codes, https://www.tau.ac.il/~nogaa/PDFS/ll70.pdf
• N. Alon, I. Balla, L. Gishboliner, A. Mond and F. Mousset: The Minrank of Random Graphs over Arbitrary Fields, https://arxiv.org/abs/1809.01873
• Noga Alon, Eldar Fischer, Michael Krivelevich, and Mario Szegedy, Efficient testing of large graphs, Combinatorica 20 (2000), no. 4, 451–476. MR 1804820, DOI 10.1007/s004930070001
• Noga Alon and Nabil Kahale, Approximating the independence number via the $\theta$-function, Math. Programming 80 (1998), no. 3, Ser. A, 253–264. MR 1603356, DOI 10.1007/BF01581168
• N. Alon and L. Lovász, Unextendible product bases, J. Combin. Theory Ser. A 95 (2001), no. 1, 169–179. MR 1840483, DOI 10.1006/jcta.2000.3122
• Noga Alon and Eyal Lubetzky, The Shannon capacity of a graph and the independence numbers of its powers, IEEE Trans. Inform. Theory 52 (2006), no. 5, 2172–2176. MR 2234473, DOI 10.1109/TIT.2006.872856
• 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
• N. Alon and P. D. Seymour, A counterexample to the rank-coloring conjecture, J. Graph Theory 13 (1989), no. 4, 523–525. MR 1010585, DOI 10.1002/jgt.3190130413
• Noga Alon, Paul Seymour, and Robin Thomas, Planar separators, SIAM J. Discrete Math. 7 (1994), no. 2, 184–193. MR 1271990, DOI 10.1137/S0895480191198768
• Noga Alon and Joel H. Spencer, The probabilistic method, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1992. With an appendix by Paul Erdős; A Wiley-Interscience Publication. MR 1140703
• Noga Alon and Mario Szegedy, Large sets of nearly orthogonal vectors, Graphs Combin. 15 (1999), no. 1, 1–4. MR 1684496
• Andris Ambainis, Julia Kempe, and Or Sattath, A quantum Lovász local lemma, J. ACM 59 (2012), no. 5, Art. 24, 24. MR 2995823, DOI 10.1145/2371656.2371659

Rosenstiehl, Gordon and Breach, New York (1967), 9–19.

• B. Andrásfai, On critical graphs, Theory of Graphs (Internat. Sympos., Rome, 1966) gordon and Breach, New York; Dunod, Paris, 1967, pp. 9–19 (English, with French summary). MR 0221964
• E. M. Andreev, Convex polyhedra in Lobačevskiĭ spaces, Mat. Sb. (N.S.) 81 (123) (1970), 445–478 (Russian). MR 0259734
• E. M. Andreev, Convex polyhedra of finite volume in Lobačevskiĭ space, Mat. Sb. (N.S.) 83 (125) (1970), 256–260 (Russian). MR 0273510
• Omer Angel and Oded Schramm, Uniform infinite planar triangulations, Comm. Math. Phys. 241 (2003), no. 2-3, 191–213. MR 2013797, DOI 10.1007/978-1-4419-9675-6_16
• L. Asimow and B. Roth, The rigidity of graphs, Trans. Amer. Math. Soc. 245 (1978), 279–289. MR 511410, DOI 10.2307/1998867
• L. Babai and P. Frankl: Linear Algebra Methods in Combinatorics, with Applications to Geometry and Computer Science, Univ. Chicago Dept. Computer Sci. 1992 (unpublished preliminary version 2, 216 pages).
• Roland Bacher and Yves Colin de Verdière, Multiplicités des valeurs propres et transformations étoile-triangle des graphes, Bull. Soc. Math. France 123 (1995), no. 4, 517–533 (French, with English and French summaries). MR 1373946
• E. G. Bajmóczy and I. Bárány, On a common generalization of Borsuk’s and Radon’s theorem, Acta Math. Acad. Sci. Hungar. 34 (1979), no. 3-4, 347–350 (1980). MR 565677, DOI 10.1007/BF01896131
• S. Beigi: Entanglement-assisted zero-error capacity is upper bounded by the Lovasz theta function, Phys. Rev. A 82 (2010), 010303(R).
• J. S. Bell, On the Einstein Podolsky Rosen paradox, Phys. Phys. Fiz. 1 (1964), no. 3, 195–200. MR 3790629, DOI 10.1103/PhysicsPhysiqueFizika.1.195
• I. Benjamini and L. Lovász: Global Information from Local Observation, Proc. 43rd Ann. Symp. on Found. of Comp. Sci. (2002) 701–710.
• Itai Benjamini and László Lovász, Harmonic and analytic functions on graphs, J. Geom. 76 (2003), no. 1-2, 3–15. Combinatorics, 2002 (Maratea). MR 2005527, DOI 10.1007/s00022-033-1697-8
• Itai Benjamini and Oded Schramm, Harmonic functions on planar and almost planar graphs and manifolds, via circle packings, Invent. Math. 126 (1996), no. 3, 565–587. MR 1419007, DOI 10.1007/s002220050109
• Itai Benjamini and Oded Schramm, Random walks and harmonic functions on infinite planar graphs using square tilings, Ann. Probab. 24 (1996), no. 3, 1219–1238. MR 1411492, DOI 10.1214/aop/1065725179
• Itai Benjamini and Oded Schramm, Recurrence of distributional limits of finite planar graphs, Electron. J. Probab. 6 (2001), no. 23, 13. MR 1873300, DOI 10.1214/EJP.v6-96
• Charles H. Bennett, David P. DiVincenzo, Tal Mor, Peter W. Shor, John A. Smolin, and Barbara M. Terhal, Unextendible product bases and bound entanglement, Phys. Rev. Lett. 82 (1999), no. 26, 5385–5388. MR 1789694, DOI 10.1103/PhysRevLett.82.5385
• Claude Berge, Graphs and hypergraphs, North-Holland Publishing Co., Amsterdam-London; American Elsevier Publishing Co., Inc., New York, 1973. Translated from the French by Edward Minieka; North-Holland Mathematical Library, Vol. 6. MR 0357172
• A. Björner and L. Lovász, Pseudomodular lattices and continuous matroids, Acta Sci. Math. (Szeged) 51 (1987), no. 3-4, 295–308. MR 940934
• W. Blaschke: Uber affine Geometrie VII: Neue Extremeingenschaften von Ellipse und Ellipsoid, Ber. Verh. Sächs. Akad. Wiss. Math. Phys. Klass 69 (1917), 412–420.
• Avrim Blum and David Karger, An $\tilde {O}(n^{3/14})$-coloring algorithm for $3$-colorable graphs, Inform. Process. Lett. 61 (1997), no. 1, 49–53. MR 1439867, DOI 10.1016/S0020-0190(96)00190-1
• B. Bollobás, On generalized graphs, Acta Math. Acad. Sci. Hungar. 16 (1965), 447–452 (English, with Russian summary). MR 0183653, DOI 10.1007/BF01904851
• Alexander I. Bobenko, Christian Mercat, and Yuri B. Suris, Linear and nonlinear theories of discrete analytic functions. Integrable structure and isomonodromic Green’s function, J. Reine Angew. Math. 583 (2005), 117–161. MR 2146854, DOI 10.1515/crll.2005.2005.583.117
• Alexander I. Bobenko and Boris A. Springborn, Variational principles for circle patterns and Koebe’s theorem, Trans. Amer. Math. Soc. 356 (2004), no. 2, 659–689. MR 2022715, DOI 10.1090/S0002-9947-03-03239-2
• Thomas Böhme, On spatial representations of graphs, Contemporary methods in graph theory, Bibliographisches Inst., Mannheim, 1990, pp. 151–167. MR 1126225
• Christian Borgs, Jennifer Chayes, and László Lovász, Moments of two-variable functions and the uniqueness of graph limits, Geom. Funct. Anal. 19 (2010), no. 6, 1597–1619. MR 2594615, DOI 10.1007/s00039-010-0044-0
• C. Borgs, J. T. Chayes, L. Lovász, V. T. Sós, and K. Vesztergombi, Convergent sequences of dense graphs. I. Subgraph frequencies, metric properties and testing, Adv. Math. 219 (2008), no. 6, 1801–1851. MR 2455626, DOI 10.1016/j.aim.2008.07.008
• J. Bourgain, On Lipschitz embedding of finite metric spaces in Hilbert space, Israel J. Math. 52 (1985), no. 1-2, 46–52. MR 815600, DOI 10.1007/BF02776078
• J. Bourgain and V. D. Milman, New volume ratio properties for convex symmetric bodies in $\textbf {R}^n$, Invent. Math. 88 (1987), no. 2, 319–340. MR 880954, DOI 10.1007/BF01388911
• R. Bricard: Mémoire sur la théorie de l’octaedre articulé, J. Math. Pures Appl. 5 (1897), 113–148.
• Graham R. Brightwell and Edward R. Scheinerman, Representations of planar graphs, SIAM J. Discrete Math. 6 (1993), no. 2, 214–229. MR 1215229, DOI 10.1137/0406017
• Bo Brinkman and Moses Charikar, On the impossibility of dimension reduction in $l_1$, J. ACM 52 (2005), no. 5, 766–788. MR 2176562, DOI 10.1145/1089023.1089026
• R. L. Brooks, C. A. B. Smith, A. H. Stone, and W. T. Tutte, The dissection of rectangles into squares, Duke Math. J. 7 (1940), 312–340. MR 0003040
• Andries E. Brouwer and Willem H. Haemers, Spectra of graphs, Universitext, Springer, New York, 2012. MR 2882891, DOI 10.1007/978-1-4614-1939-6
• A. Cabello, S. Severini, A. Winter: Graph-Theoretic Approach to Quantum Correlations, Phys. Rev. Lett. 112 (2014), 040401.
• P. J. Cameron, J.-M. Goethals, J. J. Seidel, and E. E. Shult, Line graphs, root systems, and elliptic geometry, J. Algebra 43 (1976), no. 1, 305–327. MR 0441787, DOI 10.1016/0021-8693(76)90162-9
• The electrical resistance of a graph captures its commute and cover times, \STOC21 (1989), 574–586.
• John L. Cardy, Critical percolation in finite geometries, J. Phys. A 25 (1992), no. 4, L201–L206. MR 1151081
• Dmitry Chelkak and Stanislav Smirnov, Discrete complex analysis on isoradial graphs, Adv. Math. 228 (2011), no. 3, 1590–1630. MR 2824564, DOI 10.1016/j.aim.2011.06.025
• Dmitry Chelkak and Stanislav Smirnov, Universality in the 2D Ising model and conformal invariance of fermionic observables, Invent. Math. 189 (2012), no. 3, 515–580. MR 2957303, DOI 10.1007/s00222-011-0371-2
• Jianxin Chen and Nathaniel Johnston, The minimum size of unextendible product bases in the bipartite case (and some multipartite cases), Comm. Math. Phys. 333 (2015), no. 1, 351–365. MR 3294952, DOI 10.1007/s00220-014-2186-7
• Joseph Cheriyan and John H. Reif, Directed $s$-$t$ numberings, rubber bands, and testing digraph $k$-vertex connectivity, Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms (Orlando, FL, 1992) ACM, New York, 1992, pp. 335–344. MR 1173905
• Marek Chrobak and Shin-ichi Nakano, Minimum-width grid drawings of plane graphs, Comput. Geom. 11 (1998), no. 1, 29–54. MR 1633561, DOI 10.1016/S0925-7721(98)00016-9
• Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas, The strong perfect graph theorem, Ann. of Math. (2) 164 (2006), no. 1, 51–229. MR 2233847, DOI 10.4007/annals.2006.164.51
• F. R. K. Chung, Labelings of graphs, Selected topics in graph theory, 3, Academic Press, San Diego, CA, 1988, pp. 151–168. MR 1205400

Series in Math. 92, Amer. Math. Soc., Providence, RI (1997).

• 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
• Julia Chuzhoy, Excluded grid theorem: improved and simplified, STOC’15—Proceedings of the 2015 ACM Symposium on Theory of Computing, ACM, New York, 2015, pp. 645–654. MR 3388244
• V. Chvátal, On certain polytopes associated with graphs, J. Combinatorial Theory Ser. B 18 (1975), 138–154. MR 0371732, DOI 10.1016/0095-8956(75)90041-6
• V. Chvátal and J. Komlós, Some combinatorial theorems on monotonicity, Canad. Math. Bull. 14 (1971), 151–157. MR 0337676, DOI 10.4153/CMB-1971-028-8
• Amin Coja-Oghlan, The Lovász number of random graphs, Approximation, randomization, and combinatorial optimization, Lecture Notes in Comput. Sci., vol. 2764, Springer, Berlin, 2003, pp. 228–239. MR 2080795, DOI 10.1007/978-3-540-45198-3_20
• Amin Coja-Oghlan and Anusch Taraz, Exact and approximative algorithms for coloring $G(n,p)$, Random Structures Algorithms 24 (2004), no. 3, 259–278. MR 2068869, DOI 10.1002/rsa.20007
• Yves Colin de Verdière, Sur la multiplicité de la première valeur propre non nulle du laplacien, Comment. Math. Helv. 61 (1986), no. 2, 254–270 (French). MR 856089, DOI 10.1007/BF02621914
• Yves Colin de Verdière, Sur un nouvel invariant des graphes et un critère de planarité, J. Combin. Theory Ser. B 50 (1990), no. 1, 11–21 (French). MR 1070462, DOI 10.1016/0095-8956(90)90093-F
• Yves Colin de Verdière, Un principe variationnel pour les empilements de cercles, Invent. Math. 104 (1991), no. 3, 655–669 (French). MR 1106755, DOI 10.1007/BF01245096
• Yves Colin de Verdière, Multiplicities of eigenvalues and tree-width of graphs, J. Combin. Theory Ser. B 74 (1998), no. 2, 121–146. MR 1654157, DOI 10.1006/jctb.1998.1834
• Yves Colin de Verdière, Spectres de graphes, Cours Spécialisés [Specialized Courses], vol. 4, Société Mathématique de France, Paris, 1998 (French, with English and French summaries). MR 1652692
• David Conlon and Jacob Fox, Bounds for graph regularity and removal lemmas, Geom. Funct. Anal. 22 (2012), no. 5, 1191–1256. MR 2989432, DOI 10.1007/s00039-012-0171-x
• Robert Connelly, A counterexample to the rigidity conjecture for polyhedra, Inst. Hautes Études Sci. Publ. Math. 47 (1977), 333–338. MR 0488071
• Robert Connelly, Rigidity and energy, Invent. Math. 66 (1982), no. 1, 11–33. MR 652643, DOI 10.1007/BF01404753
• Robert Connelly, Rigidity, Handbook of convex geometry, Vol. A, B, North-Holland, Amsterdam, 1993, pp. 223–271. MR 1242981
• Robert Connelly, Generic global rigidity, Discrete Comput. Geom. 33 (2005), no. 4, 549–563. MR 2132290, DOI 10.1007/s00454-004-1124-4
• R. Connelly, S.J. Gortler and L. Theran: Generic global and universal rigidity, https://arxiv.org/abs/1604.07475v1
• Robert Connelly, Steven J. Gortler, and Louis Theran, Affine rigidity and conics at infinity, Int. Math. Res. Not. IMRN 13 (2018), 4084–4102. MR 3829178, DOI 10.1093/imrn/rnx014
• R. Courant and D. Hilbert, Methods of mathematical physics. Vol. I, Interscience Publishers, Inc., New York, N.Y., 1953. MR 0065391
• T.S. Cubitt, D. Leung, W. Matthews, A. Winter: Improving zero-error classical communication with entanglement, Phys. Rev. Lett. 104 (2010), 230503.
• Toby S. Cubitt, Debbie Leung, William Matthews, and Andreas Winter, Zero-error channel capacity and simulation assisted by non-local correlations, IEEE Trans. Inform. Theory 57 (2011), no. 8, 5509–5523. MR 2849372, DOI 10.1109/TIT.2011.2159047
• E. Brian Davies, Graham M. L. Gladwell, Josef Leydold, and Peter F. Stadler, Discrete nodal domain theorems, Linear Algebra Appl. 336 (2001), 51–60. MR 1855391, DOI 10.1016/S0024-3795(01)00313-5
• C. Delorme and S. Poljak, Laplacian eigenvalues and the maximum cut problem, Math. Programming 62 (1993), no. 3, Ser. A, 557–574. MR 1251892, DOI 10.1007/BF01585184
• Charles Delorme and Svatopluk Poljak, Combinatorial properties and the complexity of a max-cut approximation, European J. Combin. 14 (1993), no. 4, 313–333. MR 1226579, DOI 10.1006/eujc.1993.1035
• Michel Marie Deza and Monique Laurent, Geometry of cuts and metrics, Algorithms and Combinatorics, vol. 15, Springer-Verlag, Berlin, 1997. MR 1460488, DOI 10.1007/978-3-642-04295-9
• A. Dress and L. Lovász, On some combinatorial properties of algebraic matroids, Combinatorica 7 (1987), no. 1, 39–48. MR 905150, DOI 10.1007/BF02579199
• Runyao Duan, Simone Severini, and Andreas Winter, Zero-error communication via quantum channels, noncommutative graphs, and a quantum Lovász number, IEEE Trans. Inform. Theory 59 (2013), no. 2, 1164–1174. MR 3015725, DOI 10.1109/TIT.2012.2221677
• Chandan Dubey, Uriel Feige, and Walter Unger, Hardness results for approximating the bandwidth, J. Comput. System Sci. 77 (2011), no. 1, 62–90. MR 2767125, DOI 10.1016/j.jcss.2010.06.006
• R. J. Duffin, Basic properties of discrete analytic functions, Duke Math. J. 23 (1956), 335–363. MR 0078441
• R. J. Duffin, Potential theory on a rhombic lattice, J. Combinatorial Theory 5 (1968), 258–272. MR 0232005
• R. J. Duffin and Elmor L. Peterson, The discrete analogue of a class of entire functions, J. Math. Anal. Appl. 21 (1968), 619–642. MR 0224840, DOI 10.1016/0022-247X(68)90268-0
• Art M. Duval and Victor Reiner, Perron-Frobenius type results and discrete versions of nodal domain theorems, Linear Algebra Appl. 294 (1999), no. 1-3, 259–268. MR 1693975, DOI 10.1016/S0024-3795(99)00090-7
• I. A. Dynnikov and S. P. Novikov, Geometry of the triangle equation on two-manifolds, Mosc. Math. J. 3 (2003), no. 2, 419–438, 742 (English, with English and Russian summaries). Dedicated to Vladimir I. Arnold on the occasion of his 65th birthday. MR 2025267, DOI 10.17323/1609-4514-2003-3-2-419-438
• Jack Edmonds, Submodular functions, matroids, and certain polyhedra, Combinatorial Structures and their Applications (Proc. Calgary Internat. Conf., Calgary, Alta., 1969) Gordon and Breach, New York, 1970, pp. 69–87. MR 0270945
• Pál Erdős, On even subgraphs of graphs, Mat. Lapok 18 (1967), 283–288 (Hungarian, with English summary). MR 0238731
• N. G. de Bruijn and P. Erdös, A colour problem for infinite graphs and a problem in the theory of relations, Nederl. Akad. Wetensch. Proc. Ser. A. 54 = Indagationes Math. 13 (1951), 369–373. MR 0046630
• Paul Erdős and Tibor Gallai, On the minimal number of vertices representing the edges of a graph. , Magyar Tud. Akad. Mat. Kutató Int. Közl. 6 (1961), 181–203 (English, with Russian summary). MR 0144332
• Paul Erdős, Frank Harary, and William T. Tutte, On the dimension of a graph, Mathematika 12 (1965), 118–122. MR 0188096, DOI 10.1112/S0025579300005222
• P. Erdős, A. Hajnal, and J. W. Moon, A problem in graph theory, Amer. Math. Monthly 71 (1964), 1107–1110. MR 0170339, DOI 10.2307/2311408
• P. Erdős and L. Lovász, Problems and results on $3$-chromatic hypergraphs and some related questions, Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. II, North-Holland, Amsterdam, 1975, pp. 609–627. Colloq. Math. Soc. János Bolyai, Vol. 10. MR 0382050
• István Fáry, On straight line representation of planar graphs, Acta Univ. Szeged. Sect. Sci. Math. 11 (1948), 229–233. MR 0026311
• Uriel Feige, Randomized graph products, chromatic numbers, and the Lovász $\vartheta$-function, Combinatorica 17 (1997), no. 1, 79–90. MR 1466577, DOI 10.1007/BF01196133
• Uriel Feige, Approximating the bandwidth via volume respecting embeddings, J. Comput. System Sci. 60 (2000), no. 3, 510–539. 30th Annual ACM Symposium on Theory of Computing (Dallas, TX, 1998). MR 1770195, DOI 10.1006/jcss.1999.1682
• Uriel Feige and Michael Langberg, The $\rm RPR^2$ rounding technique for semidefinite programs, J. Algorithms 60 (2006), no. 1, 1–23. MR 2228942, DOI 10.1016/j.jalgor.2004.11.003
• Jacqueline Ferrand, Fonctions préharmoniques et fonctions préholomorphes, Bull. Sci. Math. (2) 68 (1944), 152–180 (French). MR 0013411
• Charles M. Fiduccia, Edward R. Scheinerman, Ann Trenk, and Jennifer S. Zito, Dot product representations of graphs, Discrete Math. 181 (1998), no. 1-3, 113–138. MR 1600755, DOI 10.1016/S0012-365X(97)00049-6
• L. R. Ford Jr. and D. R. Fulkerson, Flows in networks, Princeton University Press, Princeton, N.J., 1962. MR 0159700
• Jacob Fox and László Miklós Lovász, A tight lower bound for Szemerédi’s regularity lemma, Combinatorica 37 (2017), no. 5, 911–951. MR 3737374, DOI 10.1007/s00493-016-3274-4
• A. Föppl: Theorie des Fachwerks, Verlag Arthur Felix, Leipzig, 1880.
• Jean-Claude Fournier, Pavage des figures planes sans trous par des dominos: fondement graphique de l’algorithme de Thurston et parallélisation, C. R. Acad. Sci. Paris Sér. I Math. 320 (1995), no. 1, 107–112 (French, with English and French summaries). MR 1320841, DOI 10.1016/0304-3975(95)00204-9
• P. Frankl and H. Maehara, The Johnson-Lindenstrauss lemma and the sphericity of some graphs, J. Combin. Theory Ser. B 44 (1988), no. 3, 355–362. MR 941443, DOI 10.1016/0095-8956(88)90043-3
• P. Frankl and H. Maehara, On the contact dimensions of graphs, Discrete Comput. Geom. 3 (1988), no. 1, 89–96. MR 918182, DOI 10.1007/BF02187899
• P. Frankl and R. M. Wilson, Intersection theorems with geometric consequences, Combinatorica 1 (1981), no. 4, 357–368. MR 647986, DOI 10.1007/BF02579457
• Hubert de Fraysseix, Patrice Ossona de Mendez, and Pierre Rosenstiehl, On triangle contact graphs, Combin. Probab. Comput. 3 (1994), no. 2, 233–246. MR 1288442, DOI 10.1017/S0963548300001139
• H. de Fraysseix, J. Pach, and R. Pollack, How to draw a planar graph on a grid, Combinatorica 10 (1990), no. 1, 41–51. MR 1075065, DOI 10.1007/BF02122694
• Alan Frieze and Ravi Kannan, Quick approximation to matrices and applications, Combinatorica 19 (1999), no. 2, 175–220. MR 1723039, DOI 10.1007/s004930050052
• Z. Füredi and J. Komlós, The eigenvalues of random symmetric matrices, Combinatorica 1 (1981), no. 3, 233–241. MR 637828, DOI 10.1007/BF02579329
• Zoltán Füredi and Richard Stanley, Sets of vectors with many orthogonal pairs, Graphs Combin. 8 (1992), no. 4, 391–394. MR 1554361, DOI 10.1007/BF02351595
• M. R. Garey and D. S. Johnson, The complexity of near-optimal graph coloring, J. Assoc. Comp. Mach. 23 (1976), no. 1, 43–49. MR 0426496, DOI 10.1145/321921.321926
• James Geelen and Satoru Iwata, Matroid matching via mixed skew-symmetric matrices, Combinatorica 25 (2005), no. 2, 187–215. MR 2127610, DOI 10.1007/s00493-005-0013-7
• M. Giustina, M.A.M. Versteegh, S. Wengerowsky, J. Handsteiner, A. Hochrainer, K. Phelan, F. Steinlechner, J. Kofler, J.-A. Larsson,C. Abellan, W. Amaya, V. Pruneri, M.W. Mitchell, J. Beyer, T. Gerrits, A.E. Lita, L.K. Shalm, S.W. Nam, T. Scheidl, R. Ursin, B. Wittmann, A. Zeilinger: A significant-loophole-free test of Bell’s theorem with entangled photons, Phys. Rev. Lett. 115 (2015), 250401.
• Herman Gluck, Almost all simply connected closed surfaces are rigid, Geometric topology (Proc. Conf., Park City, Utah, 1974) Springer, Berlin, 1975, pp. 225–239. Lecture Notes in Math., Vol. 438. MR 0400239
• Michel X. Goemans and David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. Assoc. Comput. Mach. 42 (1995), no. 6, 1115–1145. MR 1412228, DOI 10.1145/227683.227684
• Steven J. Gortler and Dylan P. Thurston, Characterizing the universal rigidity of generic frameworks, Discrete Comput. Geom. 51 (2014), no. 4, 1017–1036. MR 3216675, DOI 10.1007/s00454-014-9590-9
• Steven J. Gortler, Alexander D. Healy, and Dylan P. Thurston, Characterizing generic global rigidity, Amer. J. Math. 132 (2010), no. 4, 897–939. MR 2663644, DOI 10.1353/ajm.0.0132
• Jack Graver, Brigitte Servatius, and Herman Servatius, Combinatorial rigidity, Graduate Studies in Mathematics, vol. 2, American Mathematical Society, Providence, RI, 1993. MR 1251062, DOI 10.1090/gsm/002
• M. Grötschel, L. Lovász, and A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization, Combinatorica 1 (1981), no. 2, 169–197. MR 625550, DOI 10.1007/BF02579273
• M. Grötschel, L. Lovász, and A. Schrijver, Polynomial algorithms for perfect graphs, Topics on perfect graphs, North-Holland Math. Stud., vol. 88, North-Holland, Amsterdam, 1984, pp. 325–356. MR 778770, DOI 10.1016/S0304-0208(08)72943-8
• M. Grötschel, L. Lovász, and A. Schrijver, Relaxations of vertex packing, J. Combin. Theory Ser. B 40 (1986), no. 3, 330–343. MR 842998, DOI 10.1016/0095-8956(86)90087-0
• M. Grötschel, L. Lovász, A. Schrijver: Geometric Algorithms and Combinatorial Optimization, Springer (1988).
• Branko Grünbaum and Theodore S. Motzkin, On polyhedral graphs, Proc. Sympos. Pure Math., Vol. VII, Amer. Math. Soc., Providence, R.I., 1963, pp. 285–290. MR 0153005
• Venkatesan Guruswami, Maximum cut on line and total graphs, Discrete Appl. Math. 92 (1999), no. 2-3, 217–221. MR 1697554, DOI 10.1016/S0166-218X(99)00056-6
• Willem Haemers, On some problems of Lovász concerning the Shannon capacity of a graph, IEEE Trans. Inform. Theory 25 (1979), no. 2, 231–232. MR 521317, DOI 10.1109/TIT.1979.1056027
• A. Hajnal, A theorem on $k$-saturated graphs, Canad. J. Math. 17 (1965), 720–724. MR 0179103, DOI 10.4153/CJM-1965-072-1
• Johan Håstad, Some optimal inapproximability results, STOC ’97 (El Paso, TX), ACM, New York, 1999, pp. 1–10. MR 1715618
• Johan Håstad, Clique is hard to approximate within $n^{1-\epsilon }$, Acta Math. 182 (1999), no. 1, 105–142. MR 1687331, DOI 10.1007/BF02392825
• Zheng-Xu He and O. Schramm, Hyperbolic and parabolic packings, Discrete Comput. Geom. 14 (1995), no. 2, 123–149. MR 1331923, DOI 10.1007/BF02570699
• Zheng-Xu He and Oded Schramm, On the convergence of circle packings to the Riemann map, Invent. Math. 125 (1996), no. 2, 285–305. MR 1395721, DOI 10.1007/s002220050076
• Bruce Hendrickson, Conditions for unique graph realizations, SIAM J. Comput. 21 (1992), no. 1, 65–84. MR 1148818, DOI 10.1137/0221008
• L. Henneberg: Die graphische Statik der starren Systeme, Leipzig, 1911.
• B. Hensen, H. Bernien, A.E. Dréau, A. Reiserer, N. Kalb, M.S. Blok, J. Ruitenberg, R.F.L. Vermeulen, R.N. Schouten, C. Abellán, W. Amaya, V. Pruneri, M.W. Mitchell, M. Markham, D.J. Twitchen, D. Elkouss, S. Wehner, T.H. Taminiau and R. Hanson: Loophole-free Bell inequality violation using electron spins separated by 1.3 kilometres, Nature 526 (2015), 682–686.
• Jürgen Herzog, Antonio Macchia, Sara Saeedi Madani, and Volkmar Welker, On the ideal of orthogonal representations of a graph in $\mathbb {R}^2$, Adv. in Appl. Math. 71 (2015), 146–173. MR 3406962, DOI 10.1016/j.aam.2015.09.009
• J. Hladký, I. Rocha: Independent sets, cliques, and colorings in graphons, https://arxiv.org/abs/1712.07367
• Alan J. Hoffman, Some recent results on spectral properties of graphs, Beiträge zur Graphentheorie (Kolloquium, Manebach, 1967) Teubner, Leipzig, 1968, pp. 75–80. MR 0245462
• A. J. Hoffman, On graphs whose least eigenvalue exceeds $-1-\sqrt {2}$, Linear Algebra and Appl. 16 (1977), no. 2, 153–165. MR 0469826, DOI 10.1016/0024-3795(77)90027-1
• Alan J. Hoffman, On eigenvalues and colorings of graphs, Graph Theory and its Applications (Proc. Advanced Sem., Math. Research Center, Univ. of Wisconsin, Madison, Wis., 1969) Academic Press, New York, 1970, pp. 79–91. MR 0284373
• Hein van der Holst, A short proof of the planarity characterization of Colin de Verdière, J. Combin. Theory Ser. B 65 (1995), no. 2, 269–272. MR 1358989, DOI 10.1006/jctb.1995.1054
• H. van der Holst: Topological and Spectral Graph Characterizations, Ph.D. Thesis, University of Amsterdam, Amsterdam, 1996.
• Hein van der Holst, Two tree-width-like graph invariants, Combinatorica 23 (2003), no. 4, 633–651. MR 2046827, DOI 10.1007/s00493-003-0038-8
• Hein van der Holst, Monique Laurent, and Alexander Schrijver, On a minor-monotone graph invariant, J. Combin. Theory Ser. B 65 (1995), no. 2, 291–304. MR 1358991, DOI 10.1006/jctb.1995.1056
• Hein van der Holst, László Lovász, and Alexander Schrijver, On the invariance of Colin de Verdière’s graph parameter under clique sums, Linear Algebra Appl. 226/228 (1995), 509–517. MR 1344582, DOI 10.1016/0024-3795(95)00160-S
• H. van der Holst, L. Lovász, and A. Schrijver, The Colin de Verdière graph parameter, Graph theory and combinatorial biology (Balatonlelle, 1996) Bolyai Soc. Math. Stud., vol. 7, János Bolyai Math. Soc., Budapest, 1999, pp. 29–85. MR 1673503
• M. Howard, J. Wallman, V. Veitch and J. Emerson: Contextuality supplies the ‘magic’ for quantum computation, Nature 510 (2014), 351–355.
• Jacob E. Goodman and Joseph O’Rourke (eds.), Handbook of discrete and computational geometry, 2nd ed., Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2004. MR 2082993, DOI 10.1201/9781420035315
• Masao Iri, On an extension of the maximum-flow minimum-cut theorem to multicommodity flows, J. Operations Res. Soc. Japan 13 (1970/71), 129–135. MR 0292487
• R. Isaacs, Monodiffric functions, Natl. Bureau Standards App. Math. Series 18 (1952), 257–266.
• Bill Jackson and Tibor Jordán, Connected rigidity matroids and unique realizations of graphs, J. Combin. Theory Ser. B 94 (2005), no. 1, 1–29. MR 2130278, DOI 10.1016/j.jctb.2004.11.002
• Bill Jackson and J. C. Owen, A characterisation of the generic rigidity of 2-dimensional point-line frameworks, J. Combin. Theory Ser. B 119 (2016), 96–121. MR 3486339, DOI 10.1016/j.jctb.2015.12.007
• Bill Jackson and Peter Keevash, Necessary conditions for the global rigidity of direction-length frameworks, Discrete Comput. Geom. 46 (2011), no. 1, 72–85. MR 2794358, DOI 10.1007/s00454-011-9326-z
• William B. Johnson and Joram Lindenstrauss, Extensions of Lipschitz mappings into a Hilbert space, Conference in modern analysis and probability (New Haven, Conn., 1982) Contemp. Math., vol. 26, Amer. Math. Soc., Providence, RI, 1984, pp. 189–206. MR 737400, DOI 10.1090/conm/026/737400
• Mark Jerrum and Alistair Sinclair, Approximating the permanent, SIAM J. Comput. 18 (1989), no. 6, 1149–1178. MR 1025467, DOI 10.1137/0218077
• Johan Jonasson and Oded Schramm, On the cover time of planar graphs, Electron. Comm. Probab. 5 (2000), 85–90. MR 1781842, DOI 10.1214/ECP.v5-1022
• Ferenc Juhász, The asymptotic behaviour of Lovász’ $\theta$ function for random graphs, Combinatorica 2 (1982), no. 2, 153–155. MR 685042, DOI 10.1007/BF02579314
• G. A. Kabatjanskiĭ and V. I. Levenšteĭn, Bounds for packings on the sphere and in space, Problemy Peredači Informacii 14 (1978), no. 1, 3–25 (Russian). MR 0514023
• Ross J. Kang, László Lovász, Tobias Müller, and Edward R. Scheinerman, Dot product representations of planar graphs, Electron. J. Combin. 18 (2011), no. 1, Paper 216, 14. MR 2853073
• D. Karger, R. Motwani and M. Sudan: Approximate graph coloring by semidefinite programming, \FOCS35 (1994), 2–13.
• H. Karloff and U. Zwick: A 7/8-Approximation Algorithm for MAX 3SAT? \FOCS38 (1997), 406–415.
• B. S. Kashin and S. V. Konyagin, Systems of vectors in Hilbert space, Trudy Mat. Inst. Steklov. 157 (1981), 64–67, 235 (Russian). Number theory, mathematical analysis and their applications. MR 651759
• G. Katona and G. Korvin, Functions defined on a directed graph, Theory of Graphs (Proc. Colloq., Tihany, 1966) Academic Press, New York, 1968, pp. 209–213. MR 0233736
• Ken-Ichi Kawarabayashi and Mikkel Thorup, Coloring 3-colorable graphs with less than $n^{1/5}$ colors, J. ACM 64 (2017), no. 1, Art. 4, 23. MR 3634492, DOI 10.1145/3001582
• R. Kenyon, The Laplacian and Dirac operators on critical planar graphs, Invent. Math. 150 (2002), no. 2, 409–439. MR 1933589, DOI 10.1007/s00222-002-0249-4
• Richard Kenyon, Conformal invariance of domino tiling, Ann. Probab. 28 (2000), no. 2, 759–795. MR 1782431, DOI 10.1214/aop/1019160260
• Richard Kenyon, Lectures on dimers, Statistical mechanics, IAS/Park City Math. Ser., vol. 16, Amer. Math. Soc., Providence, RI, 2009, pp. 191–230. MR 2523460
• Richard Kenyon and Jean-Marc Schlenker, Rhombic embeddings of planar quad-graphs, Trans. Amer. Math. Soc. 357 (2005), no. 9, 3443–3458 (English, with English and French summaries). MR 2146632, DOI 10.1090/S0002-9947-04-03545-7
• Sanjeev Khanna, Nathan Linial, and Shmuel Safra, On the hardness of approximating the chromatic number, Combinatorica 20 (2000), no. 3, 393–415. MR 1774844, DOI 10.1007/s004930070013
• Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell, Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?, SIAM J. Comput. 37 (2007), no. 1, 319–357. MR 2306295, DOI 10.1137/S0097539705447372
• Christer O. Kiselman, Functions on discrete sets holomorphic in the sense of Isaacs, or monodiffric functions of the first kind, Sci. China Ser. A 48 (2005), no. suppl., 86–96. MR 2156493, DOI 10.1007/BF02884698
• Alexander A. Klyachko, M. Ali Can, Sinem Binicioğlu, and Alexander S. Shumovsky, Simple test for hidden variables in spin-1 systems, Phys. Rev. Lett. 101 (2008), no. 2, 020403, 4. MR 2430247, DOI 10.1103/PhysRevLett.101.020403
• Donald E. Knuth, The sandwich theorem, Electron. J. Combin. 1 (1994), Article 1, approx. 48. MR 1269161
• P. Koebe: Kontaktprobleme der konformen Abbildung, Berichte über die Verhandlungen Sächs. Akad. Wiss., Math.–Phys. Klasse, 88 (1936) 141–164.
• S. V. Konjagin, Systems of vectors in Euclidean space and an extremal problem for polynomials, Mat. Zametki 29 (1981), no. 1, 63–74, 155 (Russian). MR 604151
• Bernhard Korte and Jens Vygen, Combinatorial optimization, 4th ed., Algorithms and Combinatorics, vol. 21, Springer-Verlag, Berlin, 2008. Theory and algorithms. MR 2369759
• Andreĭ Kotlov, Rank and chromatic number of a graph, J. Graph Theory 26 (1997), no. 1, 1–8. MR 1464336, DOI 10.1002/(SICI)1097-0118(199709)26:1$\langle$1::AID-JGT1$\rangle$3.3.CO;2-U
• Andreĭ Kotlov, Spectral characterization of tree-width-two graphs, Combinatorica 20 (2000), no. 1, 147–152. MR 1770529, DOI 10.1007/s004930070038
• Andreĭ Kotlov, Minors and strong products, European J. Combin. 22 (2001), no. 4, 511–512. MR 1829745, DOI 10.1006/eujc.2000.0428
• Andrew Kotlov and László Lovász, The rank and size of graphs, J. Graph Theory 23 (1996), no. 2, 185–189. MR 1408346, DOI 10.1002/(SICI)1097-0118(199610)23:2$\langle$185::AID-JGT9$\rangle$3.3.CO;2-X
• Andrew Kotlov, László Lovász, and Santosh Vempala, The Colin de Verdière number and sphere representations of a graph, Combinatorica 17 (1997), no. 4, 483–521. MR 1645686, DOI 10.1007/BF01195002
• Greg Kuperberg, From the Mahler conjecture to Gauss linking integrals, Geom. Funct. Anal. 18 (2008), no. 3, 870–892. MR 2438998, DOI 10.1007/s00039-008-0669-4
• G. Laman, On graphs and rigidity of plane skeletal structures, J. Engrg. Math. 4 (1970), 331–340. MR 0269535, DOI 10.1007/BF01534980
• D. G. Larman and C. A. Rogers, The realization of distances within sets in Euclidean space, Mathematika 19 (1972), 1–24. MR 0319055, DOI 10.1112/S0025579300004903
• Monique Laurent and Svatopluk Poljak, On the facial structure of the set of correlation matrices, SIAM J. Matrix Anal. Appl. 17 (1996), no. 3, 530–547. MR 1397243, DOI 10.1137/0617031
• M. Laurent and F. Rendl: Semidefinite Programming and Integer Programming, in: Discrete Optimization, Handbooks in Operations Research and Management Science 12 (2005), 393–514.
• M. Laurent and A. Varvitsiotis, Positive semidefinite matrix completion, universal rigidity and the strong Arnold property, Linear Algebra Appl. 452 (2014), 292–317. MR 3201103, DOI 10.1016/j.laa.2014.03.015
• F.T. Leighton and S. Rao, An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms, \FOCS29 (1988), 422-431.
• Yong Lin, Gábor Lippner, Dan Mangoubi, and Shing-Tung Yau, Nodal geometry of graphs on surfaces, Discrete Contin. Dyn. Syst. 28 (2010), no. 3, 1291–1298. MR 2644790, DOI 10.3934/dcds.2010.28.1291
• Nathan Linial, Eran London, and Yuri Rabinovich, The geometry of graphs and some of its algorithmic applications, Combinatorica 15 (1995), no. 2, 215–245. MR 1337355, DOI 10.1007/BF01200757
• N. Linial, L. Lovász, and A. Wigderson, Rubber bands, convex embeddings and graph connectivity, Combinatorica 8 (1988), no. 1, 91–102. MR 951998, DOI 10.1007/BF02122557
• Richard J. Lipton and Robert Endre Tarjan, A separator theorem for planar graphs, SIAM J. Appl. Math. 36 (1979), no. 2, 177–189. MR 524495, DOI 10.1137/0136016
• L. Lovász, Normal hypergraphs and the perfect graph conjecture, Discrete Math. 2 (1972), no. 3, 253–267. MR 0302480, DOI 10.1016/0012-365X(72)90006-4
• László Lovász, On minimax theorems of combinatorics, Mat. Lapok 26 (1975), no. 3-4, 209–264 (1978) (Hungarian). MR 510823
• L. Lovász, Flats in matroids and geometric graphs, Combinatorial surveys (Proc. Sixth British Combinatorial Conf., Royal Holloway Coll., Egham, 1977) Academic Press, London, 1977, pp. 45–86. MR 0480111
• L. Lovász, Some finite basis theorems on graph theory, Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976) Colloq. Math. Soc. János Bolyai, vol. 18, North-Holland, Amsterdam-New York, 1978, pp. 717–729. MR 519305
• László Lovász, Topological and algebraic methods in graph theory, Graph theory and related topics (Proc. Conf., Univ. Waterloo, Waterloo, Ont., 1977) Academic Press, New York-London, 1979, pp. 1–14. MR 538032
• László Lovász, On the Shannon capacity of a graph, IEEE Trans. Inform. Theory 25 (1979), no. 1, 1–7. MR 514926, DOI 10.1109/TIT.1979.1055985
• L. Lovász, Selecting independent lines from a family of lines in a space, Acta Sci. Math. (Szeged) 42 (1980), no. 1-2, 121–131. MR 576945
• L. Lovász, Submodular functions and convexity, Mathematical programming: the state of the art (Bonn, 1982) Springer, Berlin, 1983, pp. 235–257. MR 717403
• L. Lovász, Self-dual polytopes and the chromatic number of distance graphs on the sphere, Acta Sci. Math. (Szeged) 45 (1983), no. 1-4, 317–323. MR 708798
• László Lovász, Singular spaces of matrices and their application in combinatorics, Bol. Soc. Brasil. Mat. (N.S.) 20 (1989), no. 1, 87–99. MR 1129080, DOI 10.1007/BF02585470
• László Lovász, Combinatorial problems and exercises, 2nd ed., North-Holland Publishing Co., Amsterdam, 1993. MR 1265492
• L. Lovász, Random walks on graphs: a survey, Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993) Bolyai Soc. Math. Stud., vol. 2, János Bolyai Math. Soc., Budapest, 1996, pp. 353–397. MR 1395866
• László Lovász, Steinitz representations of polyhedra and the Colin de Verdière number, J. Combin. Theory Ser. B 82 (2001), no. 2, 223–236. MR 1842113, DOI 10.1006/jctb.2000.2027
• L. Lovász, Semidefinite programs and combinatorial optimization, Recent advances in algorithms and combinatorics, CMS Books Math./Ouvrages Math. SMC, vol. 11, Springer, New York, 2003, pp. 137–194. MR 1952986, DOI 10.1007/0-387-22444-0_6
• László Lovász, Graph minor theory, Bull. Amer. Math. Soc. (N.S.) 43 (2006), no. 1, 75–86. MR 2188176, DOI 10.1090/S0273-0979-05-01088-8
• László Lovász, Large networks and graph limits, American Mathematical Society Colloquium Publications, vol. 60, American Mathematical Society, Providence, RI, 2012. MR 3012035, DOI 10.1090/coll/060
• L. Lovász and M. D. Plummer, Matching theory, North-Holland Mathematics Studies, vol. 121, North-Holland Publishing Co., Amsterdam; North-Holland Publishing Co., Amsterdam, 1986. Annals of Discrete Mathematics, 29. MR 859549
• L. Lovász, M. Saks, and A. Schrijver, Orthogonal representations and connectivity of graphs, Linear Algebra Appl. 114/115 (1989), 439–454. MR 986889, DOI 10.1016/0024-3795(89)90475-8
• László Lovász and Alexander Schrijver, A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs, Proc. Amer. Math. Soc. 126 (1998), no. 5, 1275–1285. MR 1443840, DOI 10.1090/S0002-9939-98-04244-0
• L. Lovász and A. Schrijver, On the null space of a Colin de Verdière matrix, Ann. Inst. Fourier (Grenoble) 49 (1999), no. 3, 1017–1026 (English, with English and French summaries). Symposium à la Mémoire de François Jaeger (Grenoble, 1998). MR 1703435
• László Lovász and Balázs Szegedy, Limits of dense graph sequences, J. Combin. Theory Ser. B 96 (2006), no. 6, 933–957. MR 2274085, DOI 10.1016/j.jctb.2006.05.002
• László Lovász and Balázs Szegedy, Szemerédi’s lemma for the analyst, Geom. Funct. Anal. 17 (2007), no. 1, 252–270. MR 2306658, DOI 10.1007/s00039-007-0599-6
• L. Lovász and B. Szegedy: The graph theoretic moment problem, https://arxiv.org/abs/1010.5159
• L. Lovász and K. Vesztergombi, Geometric representations of graphs, Paul Erdős and his mathematics, II (Budapest, 1999) Bolyai Soc. Math. Stud., vol. 11, János Bolyai Math. Soc., Budapest, 2002, pp. 471–498. MR 1954739
• L. Lovász and Y. Yemini, On generic rigidity in the plane, SIAM J. Algebraic Discrete Methods 3 (1982), no. 1, 91–98. MR 644960, DOI 10.1137/0603009
• A. Lubotzky, R. Phillips, and P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988), no. 3, 261–277. MR 963118, DOI 10.1007/BF02126799
• Hiroshi Maehara and Vojtěch Rödl, On the dimension to represent a graph by a unit distance graph, Graphs Combin. 6 (1990), no. 4, 365–367. MR 1092585, DOI 10.1007/BF01787703
• Avner Magen, Dimensionality reductions in $l_2$ that preserve volumes and distance to affine spaces, Discrete Comput. Geom. 38 (2007), no. 1, 139–153. MR 2322120, DOI 10.1007/s00454-007-1329-4
• P. Mani, Automorphismen von polyedrischen Graphen, Math. Ann. 192 (1971), 279–303 (German). MR 0296808, DOI 10.1007/BF02075357
• G. A. Margulis, Explicit constructions of expanders, Problemy Peredači Informacii 9 (1973), no. 4, 71–80 (Russian). MR 0484767
• J. H. Mason, Matroids as the study of geometrical configurations, Higher combinatorics (Proc. NATO Advanced Study Inst., Berlin, 1976), NATO Adv. Study Inst. Ser., Ser. C: Math. Phys. Sci., vol. 31, Reidel, Dordrecht-Boston, Mass., 1977, pp. 133–176. MR 519783
• Pascal Massart, Concentration inequalities and model selection, Lecture Notes in Mathematics, vol. 1896, Springer, Berlin, 2007. Lectures from the 33rd Summer School on Probability Theory held in Saint-Flour, July 6–23, 2003; With a foreword by Jean Picard. MR 2319879
• Jiří Matoušek, On embedding expanders into $l_p$ spaces, Israel J. Math. 102 (1997), 189–197. MR 1489105, DOI 10.1007/BF02773799
• Jiří Matoušek, Lectures on discrete geometry, Graduate Texts in Mathematics, vol. 212, Springer-Verlag, New York, 2002. MR 1899299, DOI 10.1007/978-1-4613-0039-7
• Jiří Matoušek, Using the Borsuk-Ulam theorem, Universitext, Springer-Verlag, Berlin, 2003. Lectures on topological methods in combinatorics and geometry; Written in cooperation with Anders Björner and Günter M. Ziegler. MR 1988723
• Jiří Matoušek, On variants of the Johnson-Lindenstrauss lemma, Random Structures Algorithms 33 (2008), no. 2, 142–156. MR 2436844, DOI 10.1002/rsa.20218
• J. Matoušek: Lecture notes on metric embeddings, http://kam.mff.cuni.cz/~matousek/ba-a4.pdf
• J. Matoušek and A. Naor: Open problems on embeddings of finite metric spaces http://kam.mff.cuni.cz/~matousek/metrop.ps
• R. J. McEliece, E. R. Rodemich, and H. C. Rumsey Jr., The Lovász bound and some generalizations, J. Combin. Inform. System Sci. 3 (1978), no. 3, 134–152. MR 505587
• Christian Mercat, Discrete Riemann surfaces and the Ising model, Comm. Math. Phys. 218 (2001), no. 1, 177–216. MR 1824204, DOI 10.1007/s002200000348
• C. Mercat: Discrete polynomials and discrete holomorphic approximation (2002) http://arxiv.org/abs/math-ph/0206041
• Christian Mercat, Exponentials form a basis of discrete holomorphic functions on a compact, Bull. Soc. Math. France 132 (2004), no. 2, 305–326 (English, with English and French summaries). MR 2076370, DOI 10.24033/bsmf.2467
• Mirko M. Milić, General passive networks–solvability, degeneracies, and order of complexity, IEEE Trans. Circuits and Systems CAS-21 (1974), 177–183. MR 0444328, DOI 10.1109/TCS.1974.1083845
• Gary L. Miller, Shang-Hua Teng, William Thurston, and Stephen A. Vavasis, Separators for sphere-packings and nearest neighbor graphs, J. ACM 44 (1997), no. 1, 1–29. MR 1438463, DOI 10.1145/256292.256294
• Bojan Mohar and Svatopluk Poljak, Eigenvalues and max-cut problem, Czechoslovak Math. J. 40(115) (1990), no. 2, 343–352. MR 1046300
• Susan Morey and Rafael H. Villarreal, Edge ideals: algebraic and combinatorial properties, Progress in commutative algebra 1, de Gruyter, Berlin, 2012, pp. 85–126. MR 2932582
• T. S. Motzkin and E. G. Straus, Maxima for graphs and a new proof of a theorem of Turán, Canad. J. Math. 17 (1965), 533–540. MR 0175813, DOI 10.4153/CJM-1965-053-6
• Abbe Mowshowitz, Graphs, groups and matrices, Proceedings of the Twenty-Fifth Summer Meeting of the Canadian Mathematical Congress (Lakehead Univ., Thunder Bay, Ont., 1971) Lakehead Univ., Thunder Bay, Ont., 1971, pp. 509–522. MR 0337682
• C. St. J. A. Nash-Williams, Random walk and electric currents in networks, Proc. Cambridge Philos. Soc. 55 (1959), 181–194. MR 0124932, DOI 10.1017/s0305004100033879
• C. St. J. A. Nash-Williams, Decomposition of finite graphs into forests, J. London Math. Soc. 39 (1964), 12. MR 0161333, DOI 10.1112/jlms/s1-39.1.12
• Yurii Nesterov and Arkadii Nemirovskii, Interior-point polynomial algorithms in convex programming, SIAM Studies in Applied Mathematics, vol. 13, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1994. MR 1258086, DOI 10.1137/1.9781611970791
• Noam Nisan and Avi Wigderson, On rank vs. communication complexity, 35th Annual Symposium on Foundations of Computer Science (Santa Fe, NM, 1994) IEEE Comput. Soc. Press, Los Alamitos, CA, 1994, pp. 831–836. MR 1489253, DOI 10.1109/SFCS.1994.365711
• Cyriel van Nuffelen, Research Problems: A Bound for the Chromatic Number of a Graph, Amer. Math. Monthly 83 (1976), no. 4, 265–266. MR 1538027, DOI 10.2307/2318218
• Michael L. Overton, On minimizing the maximum eigenvalue of a symmetric matrix, SIAM J. Matrix Anal. Appl. 9 (1988), no. 2, 256–268. SIAM Conference on Linear Algebra in Signals, Systems, and Control (Boston, Mass., 1986). MR 938560, DOI 10.1137/0609021
• James G. Oxley, Matroid theory, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, 1992. MR 1207587
• János Pach and Pankaj K. Agarwal, Combinatorial geometry, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1995. A Wiley-Interscience Publication. MR 1354145, DOI 10.1002/9781118033203
• M. Petersdorf and H. Sachs, Spektrum und Automorphismengruppe eines Graphen, Combinatorial Theory and its Applications, III (Proc. Colloq., Balatonfüred, 1969) North-Holland, Amsterdam, 1970, pp. 891–907 (German). MR 0309792
• Asher Peres, Two simple proofs of the Kochen-Specker theorem, J. Phys. A 24 (1991), no. 4, L175–L178. MR 1104166
• Svatopluk Poljak and Franz Rendl, Nonpolyhedral relaxations of graph-bisection problems, SIAM J. Optim. 5 (1995), no. 3, 467–487. MR 1344666, DOI 10.1137/0805024
• H. Pollaczek-Geiringer: Über die Gliederung ebener Fachwerke, Z. Angew. Math. und Mech. 7 (1927), 58–72.
• Georg Pólya, Über eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Straßennetz, Math. Ann. 84 (1921), no. 1-2, 149–160 (German). MR 1512028, DOI 10.1007/BF01458701
• Lorant Porkolab and Leonid Khachiyan, On the complexity of semidefinite programs, J. Global Optim. 10 (1997), no. 4, 351–365. MR 1457182, DOI 10.1023/A:1008203903341
• A. M. Raigorodskii, On the chromatic numbers of spheres in ${\mathbb {R}}^n$, Combinatorica 32 (2012), no. 1, 111–123. MR 2927634, DOI 10.1007/s00493-012-2709-9
• Motakuri V. Ramana, An exact duality theory for semidefinite programming and its complexity implications, Math. Programming 77 (1997), no. 2, Ser. B, 129–162. Semidefinite programming. MR 1461379, DOI 10.1016/S0025-5610(96)00082-2
• András Recski, Matroid theory and its applications in electric network theory and in statics, Algorithms and Combinatorics, vol. 6, Springer-Verlag, Berlin; Akadémiai Kiadó (Publishing House of the Hungarian Academy of Sciences), Budapest, 1989. MR 1027839, DOI 10.1007/978-3-662-22143-3
• J. Reiterman, V. Rödl, and E. Šiňajová, Embeddings of graphs in Euclidean spaces, Discrete Comput. Geom. 4 (1989), no. 4, 349–364. MR 996768, DOI 10.1007/BF02187736
• J. Reiterman, V. Rödl, and E. Šiňajová, On embedding of graphs into Euclidean spaces of small dimension, J. Combin. Theory Ser. B 56 (1992), no. 1, 1–8. MR 1182453, DOI 10.1016/0095-8956(92)90002-F
• Jürgen Richter-Gebert, Realization spaces of polytopes, Lecture Notes in Mathematics, vol. 1643, Springer-Verlag, Berlin, 1996. MR 1482230, DOI 10.1007/BFb0093761
• Igor Rivin, A characterization of ideal polyhedra in hyperbolic $3$-space, Ann. of Math. (2) 143 (1996), no. 1, 51–70. MR 1370757, DOI 10.2307/2118652
• Igor Rivin, Combinatorial optimization in geometry, Adv. in Appl. Math. 31 (2003), no. 1, 242–271. MR 1985831, DOI 10.1016/S0196-8858(03)00093-9
• Neil Robertson and P. D. Seymour, Graph minors. III. Planar tree-width, J. Combin. Theory Ser. B 36 (1984), no. 1, 49–64. MR 742386, DOI 10.1016/0095-8956(84)90013-3
• Neil Robertson and P. D. Seymour, Graph minors. V. Excluding a planar graph, J. Combin. Theory Ser. B 41 (1986), no. 1, 92–114. MR 854606, DOI 10.1016/0095-8956(86)90030-4
• Neil Robertson and P. D. Seymour, Graph minors. XVI. Excluding a non-planar graph, J. Combin. Theory Ser. B 89 (2003), no. 1, 43–76. MR 1999736, DOI 10.1016/S0095-8956(03)00042-X
• Neil Robertson, Paul Seymour, and Robin Thomas, Sachs’ linkless embedding conjecture, J. Combin. Theory Ser. B 64 (1995), no. 2, 185–227. MR 1339849, DOI 10.1006/jctb.1995.1032
• Burt Rodin and Dennis Sullivan, The convergence of circle packings to the Riemann mapping, J. Differential Geom. 26 (1987), no. 2, 349–360. MR 906396
• Moshe Rosenfeld, Almost orthogonal lines in $E^d$, Applied geometry and discrete mathematics, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 4, Amer. Math. Soc., Providence, RI, 1991, pp. 489–492. MR 1116372
• Horst Sachs, Coin graphs, polyhedra, and conformal mapping, Discrete Math. 134 (1994), no. 1-3, 133–138. Algebraic and topological methods in graph theory (Lake Bled, 1991). MR 1303402, DOI 10.1016/0012-365X(93)E0068-F
• L. A. Santaló, An affine invariant for convex bodies of $n$-dimensional space, Portugaliae Math. 8 (1949), 155–161 (Spanish). MR 0039293
• Arthur Sard, The measure of the critical values of differentiable maps, Bull. Amer. Math. Soc. 48 (1942), 883–890. MR 0007523, DOI 10.1090/S0002-9904-1942-07811-6
• Rolf Schneider, Convex bodies: the Brunn-Minkowski theory, Encyclopedia of Mathematics and its Applications, vol. 44, Cambridge University Press, Cambridge, 1993. MR 1216521, DOI 10.1017/CBO9780511526282
• W. Schnyder: Embedding planar graphs on the grid, Proc. First Annual ACM-SIAM Symp. on Discrete Algorithms, SIAM, Philadelphia (1990), 138–148;
• Oded Schramm, Existence and uniqueness of packings with specified combinatorics, Israel J. Math. 73 (1991), no. 3, 321–341. MR 1135221, DOI 10.1007/BF02773845
• Oded Schramm, How to cage an egg, Invent. Math. 107 (1992), no. 3, 543–560. MR 1150601, DOI 10.1007/BF01231901
• Oded Schramm, Square tilings with prescribed combinatorics, Israel J. Math. 84 (1993), no. 1-2, 97–118. MR 1244661, DOI 10.1007/BF02761693
• Oded Schramm, Scaling limits of loop-erased random walks and uniform spanning trees, Israel J. Math. 118 (2000), 221–288. MR 1776084, DOI 10.1007/BF02803524
• Oded Schramm, Conformally invariant scaling limits: an overview and a collection of problems, International Congress of Mathematicians. Vol. I, Eur. Math. Soc., Zürich, 2007, pp. 513–543. MR 2334202, DOI 10.4171/022-1/20
• Alexander Schrijver, A comparison of the Delsarte and Lovász bounds, IEEE Trans. Inform. Theory 25 (1979), no. 4, 425–429. MR 536232, DOI 10.1109/TIT.1979.1056072
• Alexander Schrijver, Combinatorial optimization. Polyhedra and efficiency. Vol. B, Algorithms and Combinatorics, vol. 24, Springer-Verlag, Berlin, 2003. Matroids, trees, stable sets; Chapters 39–69. MR 1956925
• K. Schütte and B. L. van der Waerden, Das Problem der dreizehn Kugeln, Math. Ann. 125 (1953), 325–334 (German). MR 0053537, DOI 10.1007/BF01343127
• J. T. Schwartz, Fast probabilistic algorithms for verification of polynomial identities, J. Assoc. Comput. Mach. 27 (1980), no. 4, 701–717. MR 594695, DOI 10.1145/322217.322225
• Farhad Shahrokhi and D. W. Matula, The maximum concurrent flow problem, J. Assoc. Comput. Mach. 37 (1990), no. 2, 318–334. MR 1072261, DOI 10.1145/77600.77620
• L.K Shalm, E. Meyer-Scott, B.G. Christensen, P. Bierhorst, M.A. Wayne, M.J. Stevens, T. Gerrits, S. Glancy, D.R. Hamel, M.S. Allman, K.J. Coakley, S.D. Dyer, C. Hodge, A.E. Lita, V.B. Verma, C. Lambrocco, E. Tortorici, A.L. Migdall, Y. Zhang, D.R. Kumor, W.H. Farr, F. Marsili, M.D. Shaw, J.A. Stern, C. Abellán, W. Amaya, V. Pruneri, T. Jennewein, M.W. Mitchell, P.G. Kwiat, J.C. Bienfang, R.P. Mirin, E. Knill, S.W. Nam: Strong loophole-free test of local realism, Phy. Rev. Lett. 115 (2015), 250402.
• Stanislav Smirnov, Critical percolation in the plane: conformal invariance, Cardy’s formula, scaling limits, C. R. Acad. Sci. Paris Sér. I Math. 333 (2001), no. 3, 239–244 (English, with English and French summaries). MR 1851632, DOI 10.1016/S0764-4442(01)01991-7
• Stanislav Smirnov, Conformal invariance in random cluster models. I. Holomorphic fermions in the Ising model, Ann. of Math. (2) 172 (2010), no. 2, 1435–1467. MR 2680496, DOI 10.4007/annals.2010.172.1441
• Stanislav Smirnov, Discrete complex analysis and probability, Proceedings of the International Congress of Mathematicians. Volume I, Hindustan Book Agency, New Delhi, 2010, pp. 595–621. MR 2827906
• Daniel A. Spielman, Algorithms, graph theory, and linear equations in Laplacian matrices, Proceedings of the International Congress of Mathematicians. Volume IV, Hindustan Book Agency, New Delhi, 2010, pp. 2698–2722. MR 2827990
• D.A. Spielman and S.-H. Teng: Disk Packings and Planar Separators, 12th Annual ACM Symposium on Computational Geometry (1996a), 349–358.
• Daniel A. Spielman and Shang-Hua Teng, Spectral partitioning works: planar graphs and finite element meshes, 37th Annual Symposium on Foundations of Computer Science (Burlington, VT, 1996) IEEE Comput. Soc. Press, Los Alamitos, CA, 1996, pp. 96–105. MR 1450607, DOI 10.1109/SFCS.1996.548468
• 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
• E. Steinitz: Polyeder und Raumabteilungen, in: Encyclopädie der Math. Wissenschaften 3 (Geometrie) 3AB12, 1–139, 1922.
• Kenneth Stephenson, Introduction to circle packing, Cambridge University Press, Cambridge, 2005. The theory of discrete analytic functions. MR 2131318
• L. Surányi, On line critical graphs, Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. III, North-Holland, Amsterdam, 1975, pp. 1411–1444. Colloq. Math. Soc. Jańos Bolyai, Vol. 10. MR 0401554
• M. Szegedy: A note on the $\theta$ number of Lovász and the generalized Delsarte bound, \FOCS35 (1994), 36–39.
• E. Szemerédi, On sets of integers containing no $k$ elements in arithmetic progression, Acta Arith. 27 (1975), 199–245. Collection of articles in memory of Juriĭ Vladimirovič Linnik. MR 0369312, DOI 10.4064/aa-27-1-199-245
• Endre Szemerédi, Regular partitions of graphs, Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976) Colloq. Internat. CNRS, vol. 260, CNRS, Paris, 1978, pp. 399–401 (English, with French summary). MR 540024
• Roberto Tamassia, On embedding a graph in the grid with the minimum number of bends, SIAM J. Comput. 16 (1987), no. 3, 421–444. MR 889400, DOI 10.1137/0216030
• Roberto Tamassia, Graph drawing, Handbook of discrete and computational geometry, CRC Press Ser. Discrete Math. Appl., CRC, Boca Raton, FL, 1997, pp. 815–832. MR 1730200
• Roberto Tamassia and Ioannis G. Tollis, Planar grid embedding in linear time, IEEE Trans. Circuits and Systems 36 (1989), no. 9, 1230–1234. MR 1009276, DOI 10.1109/31.34669
• Terence Tao, Szemerédi’s regularity lemma revisited, Contrib. Discrete Math. 1 (2006), no. 1, 8–28. MR 2212136
• W.P. Thurston: The finite Riemann Mapping Theorem, lecture at the International Symposium at Purdue University on the occasion of the proof of the Bieberbach Conjecture (1985).
• W. Thurston: Groups, tilings and finite state automata, AMS colloquim lectures, Summer 1989.
• William P. Thurston, Three-dimensional geometry and topology. Vol. 1, Princeton Mathematical Series, vol. 35, Princeton University Press, Princeton, NJ, 1997. Edited by Silvio Levy. MR 1435975
• W. T. Tutte, The factorization of linear graphs, J. London Math. Soc. 22 (1947), 107–111. MR 0023048, DOI 10.1112/jlms/s1-22.2.107
• W. T. Tutte, On the problem of decomposing a graph into $n$ connected factors, J. London Math. Soc. 36 (1961), 221–230. MR 0140438, DOI 10.1112/jlms/s1-36.1.221
• W. T. Tutte, How to draw a graph, Proc. London Math. Soc. (3) 13 (1963), 743–767. MR 0158387, DOI 10.1112/plms/s3-13.1.743
• Robert J. Vanderbei, Linear programming, 2nd ed., International Series in Operations Research & Management Science, vol. 37, Kluwer Academic Publishers, Boston, MA, 2001. Foundations and extensions. MR 1845638, DOI 10.1007/978-1-4757-5662-3
• Virginia Vassilevska Williams, Multiplying matrices faster than Coppersmith-Winograd [extended abstract], STOC’12—Proceedings of the 2012 ACM Symposium on Theory of Computing, ACM, New York, 2012, pp. 887–898. MR 2961552, DOI 10.1145/2213977.2214056
• Vijay V. Vazirani, Approximation algorithms, Springer-Verlag, Berlin, 2001. MR 1851303
• Lieven Vandenberghe and Stephen Boyd, Semidefinite programming, SIAM Rev. 38 (1996), no. 1, 49–95. MR 1379041, DOI 10.1137/1038003
• B. L. van der Waerden, Algebra. Teil I, Sechste Auflage der modernen Algebra. Die Grundlehren der Mathematischen Wissenschaften, Band 33, Springer-Verlag, Berlin, 1964 (German). MR 0177027
• K. Wagner: Bemerkungen zum Vierfarbenproblem, Jahresber. der Deutschen Math.-Ver. 46 (1936), 26–32.
• Walter Whiteley, Infinitesimally rigid polyhedra. I. Statics of frameworks, Trans. Amer. Math. Soc. 285 (1984), no. 2, 431–465. MR 752486, DOI 10.2307/1999446
• Hassler Whitney, On the Abstract Properties of Linear Dependence, Amer. J. Math. 57 (1935), no. 3, 509–533. MR 1507091, DOI 10.2307/2371182
• Henry Wolkowicz, Some applications of optimization in matrix theory, Linear Algebra Appl. 40 (1981), 101–118. MR 629610, DOI 10.1016/0024-3795(81)90143-9
• Henry Wolkowicz, Romesh Saigal, and Lieven Vandenberghe (eds.), Handbook of semidefinite programming, International Series in Operations Research & Management Science, vol. 27, Kluwer Academic Publishers, Boston, MA, 2000. Theory, algorithms, and applications. MR 1778223, DOI 10.1007/978-1-4615-4381-7
• Doron Zeilberger, A new approach to the theory of discrete analytic functions, J. Math. Anal. Appl. 57 (1977), no. 2, 350–367. MR 0450576, DOI 10.1016/0022-247X(77)90265-7
• Doron Zeilberger and Harry Dym, Further properties of discrete analytic functions, J. Math. Anal. Appl. 58 (1977), no. 2, 405–418. MR 0435417, DOI 10.1016/0022-247X(77)90218-9
• Sheng-biao Hu, The Laplacian eigenvalue of graphs, J. Math. (Wuhan) 27 (2007), no. 6, 661–663 (English, with English and Chinese summaries). MR 2367618
• Richard Zippel, Probabilistic algorithms for sparse polynomials, Symbolic and algebraic computation (EUROSAM ’79, Internat. Sympos., Marseille, 1979) Lecture Notes in Comput. Sci., vol. 72, Springer, Berlin-New York, 1979, pp. 216–226. MR 575692