{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T11:50:56Z","timestamp":1782906656131,"version":"3.54.5"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,3,9]],"date-time":"2020-03-09T00:00:00Z","timestamp":1583712000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,3,9]],"date-time":"2020-03-09T00:00:00Z","timestamp":1583712000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001711","name":"SNSF","doi-asserted-by":"crossref","award":["200021-175573"],"award-info":[{"award-number":["200021-175573"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Dr. Max R\u00f6ssler, the Walter Haefner Foundation and the ETH Zurich Foundation"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2020,10]]},"DOI":"10.1007\/s00454-020-00185-0","type":"journal-article","created":{"date-parts":[[2020,3,9]],"date-time":"2020-03-09T16:03:50Z","timestamp":1583769830000},"page":"654-670","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Orthonormal Representations of H-Free Graphs"],"prefix":"10.1007","volume":"64","author":[{"given":"Igor","family":"Balla","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shoham","family":"Letzter","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Benny","family":"Sudakov","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,3,9]]},"reference":[{"key":"185_CR1","doi-asserted-by":"publisher","first-page":"12","DOI":"10.37236\/1192","volume":"1","author":"N Alon","year":"1994","unstructured":"Alon, N.: Explicit Ramsey graphs and orthonormal labelings. Electron. J. Comb. 1, 12 (1994)","journal-title":"Electron. J. Comb."},{"issue":"1\u20132","key":"185_CR2","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1017\/S0963548307008917","volume":"18","author":"N Alon","year":"2009","unstructured":"Alon, N.: Perturbed identity matrices have high rank: proof and applications. Comb. Probab. Comput. 18(1\u20132), 3\u201315 (2009)","journal-title":"Comb. Probab. Comput."},{"issue":"3","key":"185_CR3","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/BF01581168","volume":"80","author":"N Alon","year":"1998","unstructured":"Alon, N., Kahale, N.: Approximating the independence number via the $$\\vartheta $$-function. Math. Program. 80(3), 253\u2013264 (1998)","journal-title":"Math. Program."},{"issue":"1","key":"185_CR4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/PL00021187","volume":"15","author":"N Alon","year":"1999","unstructured":"Alon, N., Szegedy, M.: Large sets of nearly orthogonal vectors. Graphs Comb. 15(1), 1\u20134 (1999)","journal-title":"Graphs Comb."},{"key":"185_CR5","series-title":"Classics in Applied Mathematics","volume-title":"Introduction to Matrix Analysis","author":"R Bellman","year":"1997","unstructured":"Bellman, R.: Introduction to Matrix Analysis. Classics in Applied Mathematics, vol. 19. SIAM, Philadelphia (1997)"},{"issue":"2","key":"185_CR6","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0095-8956(74)90052-5","volume":"16","author":"JA Bondy","year":"1974","unstructured":"Bondy, J.A., Simonovits, M.: Cycles of even length in graphs. J. Comb. Theory Ser. B 16(2), 97\u2013105 (1974)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"185_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1017\/S0963548316000134","volume":"26","author":"B Bukh","year":"2017","unstructured":"Bukh, B., Jiang, Z.: A bound on the number of edges in graphs without an even cycle. Comb. Probab. Comput. 26(1), 1\u201315 (2017)","journal-title":"Comb. Probab. Comput."},{"key":"185_CR8","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548320000012","author":"B Bukh","year":"2020","unstructured":"Bukh, B., Tait, M.: Tur\u00e1n number of theta graphs. Combin. Probab. Comput. (2020). https:\/\/doi.org\/10.1017\/S0963548320000012","journal-title":"Combin. Probab. Comput."},{"issue":"1","key":"185_CR9","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/S0304-3975(99)00185-1","volume":"235","author":"B Codenotti","year":"2000","unstructured":"Codenotti, B., Pudl\u00e1k, P., Resta, G.: Some structural properties of low-rank matrices related to computational complexity. Theor. Comput. Sci. 235(1), 89\u2013107 (2000)","journal-title":"Theor. Comput. Sci."},{"issue":"8","key":"185_CR10","doi-asserted-by":"publisher","first-page":"1945","DOI":"10.1016\/j.laa.2010.11.052","volume":"434","author":"L Deaett","year":"2011","unstructured":"Deaett, L.: The minimum semidefinite rank of a triangle-free graph. Linear Algebra Appl. 434(8), 1945\u20131955 (2011)","journal-title":"Linear Algebra Appl."},{"key":"185_CR11","series-title":"Graduate Texts in Mathematics","volume-title":"Graph Theory","author":"R Diestel","year":"2012","unstructured":"Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173. Springer, Berlin (2012)"},{"issue":"1","key":"185_CR12","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1002\/jgt.3190020107","volume":"2","author":"P Erd\u0151s","year":"1978","unstructured":"Erd\u0151s, P., Faudree, R.J., Rousseau, C.C., Schelp, R.H.: On cycle-complete graph Ramsey numbers. J. Graph Theory 2(1), 53\u201364 (1978)","journal-title":"J. Graph Theory"},{"key":"185_CR13","unstructured":"Fallat, S., Hogben, L.: Variants on the minimum rank problem: a survey II (2014). arXiv:1102.5142"},{"key":"185_CR14","doi-asserted-by":"crossref","unstructured":"Feige, U.: Randomized graph products, chromatic numbers, and the Lov\u00e1sz $$\\vartheta $$-function. In: 27th Annual ACM Symposium on Theory of Computing, pp. 635\u2013640. ACM Press, New York (1995)","DOI":"10.1145\/225058.225281"},{"issue":"1","key":"185_CR15","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1006\/jcta.1996.0067","volume":"75","author":"Z F\u00fcredi","year":"1996","unstructured":"F\u00fcredi, Z.: New asymptotics for bipartite Tur\u00e1n numbers. J. Comb. Theory Ser. A 75(1), 141\u2013144 (1996)","journal-title":"J. Comb. Theory Ser. A"},{"key":"185_CR16","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1007\/BF02351595","volume":"8","author":"Z F\u00fcredi","year":"1992","unstructured":"F\u00fcredi, Z., Stanley, R.: Sets of vectors with many orthogonal pairs (research problem). Graphs Comb. 8, 391\u2013394 (1992)","journal-title":"Graphs Comb."},{"issue":"11","key":"185_CR17","doi-asserted-by":"publisher","first-page":"6990","DOI":"10.1109\/TIT.2018.2810384","volume":"64","author":"A Golovnev","year":"2018","unstructured":"Golovnev, A., Regev, O., Weinstein, O.: The minrank of random graphs. IEEE Trans. Inform. Theory 64(11), 6990\u20136995 (2018)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"185_CR18","unstructured":"Haviv, I.: On minrank and the Lov\u00e1sz theta function (2018). arXiv:1802.03920"},{"issue":"4","key":"185_CR19","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1145\/3322817","volume":"11","author":"I Haviv","year":"2019","unstructured":"Haviv, I.: On minrank and forbidden subgraphs. ACM Trans. Comput. Theory 11(4), 20 (2019)","journal-title":"ACM Trans. Comput. Theory"},{"key":"185_CR20","doi-asserted-by":"publisher","first-page":"55","DOI":"10.37236\/327","volume":"17","author":"G Haynes","year":"2010","unstructured":"Haynes, G., Park, C., Schaeffer, A., Webster, J., Mitchell, L.H.: Orthogonal vector coloring. Electron. J. Comb. 17, 55 (2010)","journal-title":"Electron. J. Comb."},{"key":"185_CR21","first-page":"67","volume":"157","author":"BS Kashin","year":"1983","unstructured":"Kashin, B.S., Konyagin, S.V.: Systems of vectors in Hilbert space. Proc. Steklov Inst. Math. 157, 67\u201370 (1983)","journal-title":"Proc. Steklov Inst. Math."},{"key":"185_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.37236\/1193","volume":"1","author":"DE Knuth","year":"1994","unstructured":"Knuth, D.E.: The sandwich theorem. Electron. J. Comb. 1, 1 (1994)","journal-title":"Electron. J. Comb."},{"issue":"1","key":"185_CR23","first-page":"63","volume":"29","author":"SV Konyagin","year":"1981","unstructured":"Konyagin, S.V.: Systems of vectors in Euclidean space and an extremal problem for polynomials. Mat. Zametki 29(1), 63\u201374 (1981). (in Russian)","journal-title":"Mat. Zametki"},{"key":"185_CR24","doi-asserted-by":"publisher","first-page":"50","DOI":"10.4064\/cm-3-1-50-57","volume":"3","author":"T K\u00f6v\u00e1ri","year":"1954","unstructured":"K\u00f6v\u00e1ri, T., S\u00f3s, V.T., Tur\u00e1n, P.: On a problem of K. Zarankiewicz. Colloq. Math. 3, 50\u201357 (1954)","journal-title":"Zarankiewicz. Colloq. Math."},{"key":"185_CR25","doi-asserted-by":"crossref","unstructured":"Krivelevich, M., Sudakov, B.: Pseudo-random graphs. In: More Sets, Graphs and Numbers. In: Bolyai Society Mathematical Studies, vol. 15, pp. 199\u2013262. Springer, Berlin (2006)","DOI":"10.1007\/978-3-540-32439-3_10"},{"issue":"1","key":"185_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","volume":"25","author":"L Lov\u00e1sz","year":"1979","unstructured":"Lov\u00e1sz, L.: On the Shannon capacity of a graph. IEEE Trans. Inform. Theory 25(1), 1\u20137 (1979)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"185_CR27","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1016\/0024-3795(89)90475-8","volume":"114\u2013115","author":"L Lov\u00e1sz","year":"1989","unstructured":"Lov\u00e1sz, L., Saks, M., Schrijver, A.: Orthogonal representations and connectivity of graphs. Linear Algebra Appl. 114\u2013115, 439\u2013454 (1989)","journal-title":"Linear Algebra Appl."},{"issue":"4","key":"185_CR28","first-page":"143","volume":"6","author":"J Ne\u0161et\u0159il","year":"1997","unstructured":"Ne\u0161et\u0159il, J., Rosenfeld, M.: Embedding graphs in Euclidean spaces, an exploration guided by Paul Erd\u0151s. Geombinatorics 6(4), 143\u2013155 (1997)","journal-title":"Geombinatorics"},{"issue":"2","key":"185_CR29","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/s004930200015","volume":"22","author":"P Pudl\u00e1k","year":"2002","unstructured":"Pudl\u00e1k, P.: Cycles of nonzero elements in low rank matrices. Combinatorica 22(2), 321\u2013334 (2002)","journal-title":"Combinatorica"},{"key":"185_CR30","doi-asserted-by":"crossref","unstructured":"Rosenfeld, M.: Almost orthogonal lines in $${\\mathbb{E}}^d$$. In: Applied Geometry and Discrete Mathematics. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 4, pp. 489\u2013492. AMS, Providence (1991)","DOI":"10.1090\/dimacs\/004\/38"},{"key":"185_CR31","first-page":"3","volume":"14","author":"LG Schnirelmann","year":"1930","unstructured":"Schnirelmann, L.G.: On the additive properties of numbers. Proc. Don Polytech. Inst. Novocherkassk 14, 3\u201327 (1930). (in Russian)","journal-title":"Proc. Don Polytech. Inst. Novocherkassk"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-020-00185-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-020-00185-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-020-00185-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,18]],"date-time":"2022-10-18T02:04:45Z","timestamp":1666058685000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-020-00185-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,9]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,10]]}},"alternative-id":["185"],"URL":"https:\/\/doi.org\/10.1007\/s00454-020-00185-0","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,3,9]]},"assertion":[{"value":"5 May 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 January 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 February 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 March 2020","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}