{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,2]],"date-time":"2023-10-02T10:40:05Z","timestamp":1696243205919},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2023,6,13]],"date-time":"2023-06-13T00:00:00Z","timestamp":1686614400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,6,13]],"date-time":"2023-06-13T00:00:00Z","timestamp":1686614400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2023,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The theta body of a graph, introduced by Gr\u00f6tschel, Lov\u00e1sz, and Schrijver (in\u00a01986), is a tractable relaxation of the independent-set polytope derived from the Lov\u00e1sz theta number. In this paper, we recursively extend the theta body, and hence the theta number, to hypergraphs. We obtain fundamental properties of this extension and relate it to the high-dimensional Hoffman bound of Filmus, Golubev, and Lifshitz. We discuss two applications: triangle-free graphs and Mantel\u2019s theorem, and bounds on the density of triangle-avoiding sets in the Hamming cube.<\/jats:p>","DOI":"10.1007\/s00493-023-00040-9","type":"journal-article","created":{"date-parts":[[2023,6,13]],"date-time":"2023-06-13T08:02:14Z","timestamp":1686643334000},"page":"909-938","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Recursive Theta Body for Hypergraphs"],"prefix":"10.1007","volume":"43","author":[{"given":"Davi","family":"Castro-Silva","sequence":"first","affiliation":[]},{"given":"Fernando M\u00e1rio","family":"de Oliveira Filho","sequence":"additional","affiliation":[]},{"given":"Lucas","family":"Slot","sequence":"additional","affiliation":[]},{"given":"Frank","family":"Vallentin","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,6,13]]},"reference":[{"key":"40_CR1","doi-asserted-by":"crossref","unstructured":"Bachoc, C., DeCorte, P.E.B., de Oliveira Filho, F.M., Vallentin, F.: Spectral bounds for the independence ratio and the chromatic number of an operator. Israel J. Math. 202, 227\u2013254 (2014)","DOI":"10.1007\/s11856-014-1070-7"},{"key":"40_CR2","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/978-1-4614-0769-0_9","volume-title":"Handbook on semidefinite, conic, and polynomial optimization","author":"C Bachoc","year":"2012","unstructured":"Bachoc, C., Gijswijt, D.C., Schrijver, A., Vallentin, F.: Invariant semidefinite programs. In: Anjos, M.F., Lasserre, J.B. (eds.) Handbook on semidefinite, conic, and polynomial optimization, pp. 219\u2013269. Springer, New York (2012)"},{"key":"40_CR3","doi-asserted-by":"publisher","first-page":"3307","DOI":"10.1090\/proc\/15940","volume":"150","author":"D Castro-Silva","year":"2022","unstructured":"Castro-Silva, D., de Oliveira Filho, F.M., Slot, L., Vallentin, F.: A recursive Lov\u00e1sz theta number for simplex-avoiding sets. Proceedings of the American Mathematical Society 150, 3307\u20133322 (2022)","journal-title":"Proceedings of the American Mathematical Society"},{"key":"40_CR4","doi-asserted-by":"publisher","first-page":"1944","DOI":"10.1137\/15M103114X","volume":"26","author":"E de Klerk","year":"2016","unstructured":"de Klerk, E., Vallentin, F.: On the turing model complexity of interior point methods for semidefinite programming. SIAM J. Optim. 26, 1944\u20131961 (2016)","journal-title":"SIAM J. Optim."},{"key":"40_CR5","first-page":"155","volume-title":"New Trends in Intuitive Geometry Bolyai Society Mathematical Studies","author":"FM de Oliveira Filho","year":"2019","unstructured":"de Oliveira Filho, F.M., Vallentin, F.: Computing upper bounds for the packing density of congruent copies of a convex body. In: Ambrus, G., B\u00e1r\u00e1ny, I., B\u00f6r\u00f6czky, K.J., Fejest\u00f3th, G., Pach, J. (eds.) New Trends in Intuitive Geometry Bolyai Society Mathematical Studies, pp. 155\u2013188. Springer, Berlin (2019)"},{"key":"40_CR6","unstructured":"Delsarte, P.: An Algebraic Approach to the Association Schemes of Coding Theory, Philips Research Reports Supplements 1973 No.\u00a010, Philips Research Laboratories, Eindhoven, (1973)"},{"key":"40_CR7","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1137\/0134012","volume":"34","author":"P Delsarte","year":"1978","unstructured":"Delsarte, P.: Hahn polynomials, discrete harmonics, and $$t$$-designs. SIAM J. Appl. Math. 34, 157\u2013166 (1978)","journal-title":"SIAM J. Appl. Math."},{"key":"40_CR8","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1512\/iumj.1976.25.25030","volume":"25","author":"CF Dunkl","year":"1976","unstructured":"Dunkl, C.F.: A Krawtchouk polynomial addition theorem and wreath products of symmetric groups. Indiana Univ. Math. J. 25, 335\u2013358 (1976)","journal-title":"Indiana Univ. Math. J."},{"key":"40_CR9","doi-asserted-by":"publisher","first-page":"627","DOI":"10.1137\/0509043","volume":"9","author":"CF Dunkl","year":"1978","unstructured":"Dunkl, C.F.: An addition theorem for Hahn polynomials: the spherical functions. SIAM J. Math. Anal. 9, 627\u2013637 (1978)","journal-title":"SIAM J. Math. Anal."},{"key":"40_CR10","doi-asserted-by":"publisher","first-page":"1005","DOI":"10.5802\/alco.190","volume":"4","author":"Y Filmus","year":"2021","unstructured":"Filmus, Y., Golubev, K., Lifshitz, N.: High dimensional Hoffman bound and applications in extremal combinatorics. Algebraic Comb. 4, 1005\u20131026 (2021)","journal-title":"Algebraic Comb."},{"key":"40_CR11","doi-asserted-by":"crossref","unstructured":"Godsil, C., Meagher, K.: Erdos-Ko-Rado theorems: algebraic approaches, Cambridge Studies in Advanced Mathematics, Cambridge University Press, Cambridge, (2016)","DOI":"10.1017\/CBO9781316414958"},{"key":"40_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric algorithms and combinatorial optimization, algorithms and combinatorics 2","author":"M Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric algorithms and combinatorial optimization, algorithms and combinatorics 2. Springer, Berlin (1988)"},{"key":"40_CR13","doi-asserted-by":"crossref","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Relaxations of vertex packing. J. Comb. Theory, Series B 40, 330\u2013343 (1986)","DOI":"10.1016\/0095-8956(86)90087-0"},{"key":"40_CR14","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/j.laa.2021.02.010","volume":"617","author":"WH Haemers","year":"2021","unstructured":"Haemers, W.H.: Hoffman\u2019s ratio bound. Linear Algebra Appl. 617, 215\u2013219 (2021)","journal-title":"Linear Algebra Appl."},{"key":"40_CR15","first-page":"79","volume-title":"Graph theory and its applications","author":"AJ Hoffman","year":"1970","unstructured":"Hoffman, A.J.: On eigenvalues and colorings of graphs. In: Harris, B. (ed.) Graph theory and its applications, pp. 79\u201391. Academic Press, New York (1970)"},{"key":"40_CR16","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems, in: Complexity of Computer Computations (Proceedings of a symposium on the complexity of computer computations, IBM Thomas J. Watson Research Center, Yorktown Heights, New York, 1972; R.E.\u00a0Miller and J.W.\u00a0Thatcher, eds.), Plenum Press, New York, pp.\u00a085\u2013103 (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"40_CR17","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1137\/0801013","volume":"1","author":"L Lov\u00e1sz","year":"1991","unstructured":"Lov\u00e1sz, L., Schrijver, A.: Cones of matrices and set-functions and $$0$$-$$1$$ optimization. SIAM J. Optim. 1, 166\u2013190 (1991)","journal-title":"SIAM J. Optim."},{"key":"40_CR18","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. Inf. Theory 25, 1\u20137 (1979)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"40_CR19","first-page":"60","volume":"10","author":"W Mantel","year":"1910","unstructured":"Mantel, W.: Vraagstuk XXVIII. Wiskundige Opgaven 10, 60\u201361 (1910)","journal-title":"Vraagstuk XXVIII. Wiskundige Opgaven"},{"key":"40_CR20","unstructured":"McEliece, R.J., Rodemich, E.R., Rumsey, H.C.: The Lov\u00e1sz bound and some generalizations. J. Comb., Inf. Syst. Sci. 3, 134\u2013152 (1978)"},{"key":"40_CR21","first-page":"3","volume":"25","author":"A Raymond","year":"2018","unstructured":"Raymond, A.: The Tur\u00e1n polytope. Electron. J. Comb. 25, 3 (2018)","journal-title":"Electron. J. Comb."},{"key":"40_CR22","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1109\/TIT.1979.1056072","volume":"25","author":"A Schrijver","year":"1979","unstructured":"Schrijver, A.: A comparison of the delsarte and Lov\u00e1sz bounds. IEEE Trans. Inf. Theory 25, 425\u2013429 (1979)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"40_CR23","volume-title":"Combinatorial optimization: polyhedra and efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial optimization: polyhedra and efficiency, vol. B. Springer, Berlin (2003)"},{"key":"40_CR24","doi-asserted-by":"publisher","first-page":"2859","DOI":"10.1109\/TIT.2005.851748","volume":"51","author":"A Schrijver","year":"2005","unstructured":"Schrijver, A.: New code upper bounds from the Terwilliger algebra and semidefinite programming. IEEE Trans. Inf. Theory 51, 2859\u20132866 (2005)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"40_CR25","volume-title":"Theory of linear and integer programming","author":"A Schrijver","year":"1986","unstructured":"Schrijver, A.: Theory of linear and integer programming. Wiley, Chicester (1986)"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-023-00040-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-023-00040-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-023-00040-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,1]],"date-time":"2023-10-01T19:01:29Z","timestamp":1696186889000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-023-00040-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,13]]},"references-count":25,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2023,10]]}},"alternative-id":["40"],"URL":"https:\/\/doi.org\/10.1007\/s00493-023-00040-9","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,13]]},"assertion":[{"value":"28 June 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 March 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 June 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}