{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T02:17:04Z","timestamp":1790821024755,"version":"4.1.0"},"reference-count":35,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/501100002322","name":"Coordena\u00e7\u00e3o de Aperfei\u00e7oamento de Pessoal de N\u00edvel Superior","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002322","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001807","name":"Funda\u00e7\u00e3o de Amparo \u00e0 Pesquisa do Estado de S\u00e3o Paulo","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001807","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["2013\/03447-6"],"award-info":[{"award-number":["2013\/03447-6"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>The notion of duality is a key element in understanding the interplay between the stability and chromatic numbers of a graph. This notion is a central aspect in the celebrated theory of perfect graphs and is further and deeply developed in the context of the Lov\u00e1sz theta function and its equivalent characterizations and variants. The main achievement of this paper is the introduction of a new family of norms, providing upper bounds for the stability number, that are obtained through duality from the norms motivated by Hoffman's lower bound for the chromatic number, and which achieve the (complementary) Lov\u00e1sz theta function at their optimum. As a consequence, our norms make it formal that Hoffman's bound for the chromatic number and the Delsarte--Hoffman ratio bound for the stability number are indeed dual. Further, we show that our new bounds strengthen the convex quadratic bounds for the stability number studied by Luz and Schrijver, and which achieve the Lov\u00e1sz theta function at their optimum. One of the key observations regarding weighted versions of these bounds is that, for any upper bound for the stability number of a graph which is a positive definite monotone gauge function, its gauge dual is a lower bound on the fractional chromatic number, and conversely. Our presentation is elementary and accessible to a wide audience.<\/jats:p>","DOI":"10.1137\/19m1306427","type":"journal-article","created":{"date-parts":[[2021,11,30]],"date-time":"2021-11-30T11:34:43Z","timestamp":1638272083000},"page":"2880-2907","source":"Crossref","is-referenced-by-count":3,"title":["Dual Hoffman Bounds for the Stability and Chromatic Numbers Based on Semidefinite Programming"],"prefix":"10.1137","volume":"35","author":[{"given":"Nathan Benedetto","family":"Proen\u00e7a","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marcel K.","family":"de Carli Silva","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1581-431X","authenticated-orcid":true,"given":"Gabriel","family":"Coutinho","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,11,30]]},"reference":[{"key":"atypb1","unstructured":"C. D. Aliprantis and K. C. Border,\n                      Infinite Dimensional Analysis\n                      , 3rd ed., Springer, Berlin, 2006."},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/17M1119020"},{"key":"atypb3","unstructured":"A. Ben-Israel and T. N. E. Greville,\n                      Generalized Inverses\n                      , Theory and Applications, 2nd ed., CMS Books Math.\/Ouvrages Math. SMC 15, Springer, New York, 2003."},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2005.10.002"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"S. Boyd and L. Vandenberghe,\n                      Convex Optimization\n                      , Cambridge University Press, Cambridge, UK, 2004,https:\/\/doi.org\/10.1017\/CBO9780511804441.","DOI":"10.1017\/CBO9780511804441"},{"key":"atypb6","first-page":"1","author":"Cvetkovi\u0107 D. M.","year":"1971","journal-title":"Serbia"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-016-1041-3"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.37236\/6404"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1137\/130940785"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584085"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"D. R. Fulkerson,\n                      Anti-blocking polyhedra\n                      , J. Combin. Theory Ser. B, 12 (1972), pp. 50-71.","DOI":"10.1016\/0095-8956(72)90032-9"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"C. Godsil and G. Royle,\n                      Algebraic Graph Theory\n                      , Grad. Texts in Math. 207, Springer, New York, 2001.","DOI":"10.1007\/978-1-4613-0163-9"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2007.10.007"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90087-0"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"M. Gr\u00c3\u00b6tschel, L. Lov\u00c3\u00a1sz, and A. Schrijver,\n                      Geometric Algorithms and Combinatorial Optimization\n                      , 2nd ed., Algorithms Combin. 2, Springer, Berlin, 1993,https:\/\/doi.org\/10.1007\/978-3-642-78240-4.","DOI":"10.1007\/978-3-642-78240-4"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1137\/050648237"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1979.1056027"},{"key":"atypb18","first-page":"79","author":"Hoffman A. J.","year":"1970","journal-title":"New York"},{"key":"atypb19","unstructured":"R. A. Horn and C. R. Johnson,\n                      Matrix Analysis\n                      , Cambridge University Press, Cambridge, UK, 1990."},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.37236\/1193"},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"S. Lang,\n                      Real and Functional Analysis\n                      , 3rd ed., Grad. Texts in Math. 142, Springer, New York, 1993,https:\/\/doi.org\/10.1007\/978-1-4612-0897-6.","DOI":"10.1007\/978-1-4612-0897-6"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1979.1055985"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(95)00042-9"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1007\/s11590-015-0911-6"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(00)00162-4"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480104429181"},{"key":"atypb27","first-page":"134","volume":"3","author":"McEliece R. J.","year":"1978","journal-title":"J. Combin. Inform. System Sci."},{"key":"atypb28","unstructured":"A. Nemirovski,\n                      Introduction to Linear Optimization\n                      , 2012,https:\/\/www2.isye.gatech.edu\/~nemirovs\/OPTI_LectureNotes.pdf."},{"key":"atypb29","unstructured":"M. W. Newman,\n                      Independent Sets and Eigenspaces\n                      , Ph. D. thesis, 2004,http:\/\/hdl.handle.net\/10012\/1151."},{"key":"atypb30","unstructured":"D. E. Roberson,\n                      Variations on a Theme: Graph Homomorphisms\n                      , Ph. D. thesis, 2013,https:\/\/uwspace.uwaterloo.ca\/handle\/10012\/7814."},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1007\/s10801-016-0665-y"},{"key":"atypb32","unstructured":"R. T. Rockafellar,\n                      Convex Analysis\n                      , Princeton Landmarks in Math., Princeton University Press, Princeton, NJ, 1997."},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1979.1056072"},{"key":"atypb34","unstructured":"A. Schrijver,\n                      Theory of Linear and Integer Programming\n                      , Wiley-Interscience Ser. Discrete Math., John Wiley & Sons, Chichester, UK, 1986."},{"key":"atypb35","unstructured":"M. Szegedy,\n                      A note on the theta number of Lov\u00c3\u00a1sz and the generalized Delsarte bound\n                      , in Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, 1994."}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/19M1306427","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:07:00Z","timestamp":1787317620000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/19M1306427"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/19M1306427"],"URL":"https:\/\/doi.org\/10.1137\/19m1306427","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}