{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,24]],"date-time":"2025-12-24T12:36:34Z","timestamp":1766579794707,"version":"3.40.4"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,3,7]],"date-time":"2025-03-07T00:00:00Z","timestamp":1741305600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,3,7]],"date-time":"2025-03-07T00:00:00Z","timestamp":1741305600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100008899","name":"University of South Carolina","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100008899","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2025,4]]},"abstract":"Abstract<\/jats:title>\n Given integers \n \n $$n> k > 0$$<\/jats:tex-math>\n \n \n n<\/mml:mi>\n ><\/mml:mo>\n k<\/mml:mi>\n ><\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, and a set of integers \n \n $$L \\subset [0, k-1]$$<\/jats:tex-math>\n \n \n L<\/mml:mi>\n \u2282<\/mml:mo>\n [<\/mml:mo>\n 0<\/mml:mn>\n ,<\/mml:mo>\n k<\/mml:mi>\n -<\/mml:mo>\n 1<\/mml:mn>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, an L<\/jats:italic>-system<\/jats:italic> is a family of sets \n \n $$\\mathcal {F}\\subset \\left( {\\begin{array}{c}[n]\\\\ k\\end{array}}\\right) $$<\/jats:tex-math>\n \n \n F<\/mml:mi>\n \u2282<\/mml:mo>\n \n \n \n \n \n \n [<\/mml:mo>\n n<\/mml:mi>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mtd>\n <\/mml:mtr>\n \n \n \n \n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mtd>\n <\/mml:mtr>\n <\/mml:mtable>\n <\/mml:mrow>\n <\/mml:mfenced>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> such that \n \n $$|F \\cap F'| \\in L$$<\/jats:tex-math>\n \n \n \n |<\/mml:mo>\n F<\/mml:mi>\n \u2229<\/mml:mo>\n <\/mml:mrow>\n \n F<\/mml:mi>\n \u2032<\/mml:mo>\n <\/mml:msup>\n \n |<\/mml:mo>\n \u2208<\/mml:mo>\n L<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> for distinct \n \n $$F, F'\\in \\mathcal {F}$$<\/jats:tex-math>\n \n \n F<\/mml:mi>\n ,<\/mml:mo>\n \n F<\/mml:mi>\n \u2032<\/mml:mo>\n <\/mml:msup>\n \u2208<\/mml:mo>\n F<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>. L<\/jats:italic>-systems correspond to independent sets in a certain generalized Johnson graph G<\/jats:italic>(n<\/jats:italic>,\u00a0k<\/jats:italic>,\u00a0L<\/jats:italic>), so that the maximum size of an L<\/jats:italic>-system is equivalent to finding the independence number of the graph G<\/jats:italic>(n<\/jats:italic>,\u00a0k<\/jats:italic>,\u00a0L<\/jats:italic>). The Lov\u00e1sz number<\/jats:italic>\n \n \n $$\\vartheta (G)$$<\/jats:tex-math>\n \n \n \u03d1<\/mml:mi>\n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> is a semidefinite programming approximation of the independence number \n \n $$\\alpha $$<\/jats:tex-math>\n \n \u03b1<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> of a graph G<\/jats:italic>. In this paper, we determine the leading order term of \n \n $$\\vartheta (G(n, k, L))$$<\/jats:tex-math>\n \n \n \u03d1<\/mml:mi>\n (<\/mml:mo>\n G<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n ,<\/mml:mo>\n k<\/mml:mi>\n ,<\/mml:mo>\n L<\/mml:mi>\n )<\/mml:mo>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> of any generalized Johnson graph with k<\/jats:italic> and L<\/jats:italic> fixed and \n \n $$n\\rightarrow \\infty $$<\/jats:tex-math>\n \n \n n<\/mml:mi>\n \u2192<\/mml:mo>\n \u221e<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>. As an application of this theorem, we give an explicit construction of a graph G<\/jats:italic> on n<\/jats:italic> vertices with a large gap between the Lov\u00e1sz number and the Shannon capacity c<\/jats:italic>(G<\/jats:italic>). Specifically, we prove that for any \n \n $$\\epsilon > 0$$<\/jats:tex-math>\n \n \n \u03f5<\/mml:mi>\n ><\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, for infinitely many n<\/jats:italic> there is a generalized Johnson graph G<\/jats:italic> on n<\/jats:italic> vertices which has ratio \n \n $$\\vartheta (G)\/c(G) = \\Omega (n^{1-\\epsilon })$$<\/jats:tex-math>\n \n \n \u03d1<\/mml:mi>\n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \/<\/mml:mo>\n c<\/mml:mi>\n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n =<\/mml:mo>\n \u03a9<\/mml:mi>\n \n (<\/mml:mo>\n \n n<\/mml:mi>\n \n 1<\/mml:mn>\n -<\/mml:mo>\n \u03f5<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, which improves on all known constructions. The graph G<\/jats:italic>\n a fortiori<\/jats:italic> also has ratio \n \n $$\\vartheta (G)\/\\alpha (G) = \\Omega (n^{1-\\epsilon })$$<\/jats:tex-math>\n \n \n \u03d1<\/mml:mi>\n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \/<\/mml:mo>\n \u03b1<\/mml:mi>\n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n =<\/mml:mo>\n \u03a9<\/mml:mi>\n \n (<\/mml:mo>\n \n n<\/mml:mi>\n \n 1<\/mml:mn>\n -<\/mml:mo>\n \u03f5<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, which greatly improves on the best known explicit construction.<\/jats:p>","DOI":"10.1007\/s00493-025-00136-4","type":"journal-article","created":{"date-parts":[[2025,3,7]],"date-time":"2025-03-07T10:51:50Z","timestamp":1741344710000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["L-Systems and the Lov\u00e1sz Number"],"prefix":"10.1007","volume":"45","author":[{"given":"William","family":"Linz","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,3,7]]},"reference":[{"key":"136_CR1","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/BF01581168","volume":"80","author":"N Alon","year":"1998","unstructured":"Alon, N., Kahale, A.: Approximating the independence number via the $$\\vartheta $$-function. Math. Program. 80, 253\u2013264 (1998)","journal-title":"Math. Program."},{"issue":"6","key":"136_CR2","doi-asserted-by":"publisher","first-page":"3340","DOI":"10.1109\/TIT.2018.2889108","volume":"65","author":"B Bukh","year":"2019","unstructured":"Bukh, B., Cox, C.: On a fractional version of Haemers\u2019 bound. IEEE Trans. Inform. Theory 65(6), 3340\u20133348 (2019)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"136_CR3","unstructured":"Delsarte, P.: An algebraic approach to the association schemes of coding theory. Philips Res. Rep. Suppl., (10):vi+97 (1973). https:\/\/users.wpi.edu\/~martin\/RESEARCH\/philips.pdf"},{"key":"136_CR4","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1112\/plms\/s3-36.2.369","volume":"36","author":"M Deza","year":"1978","unstructured":"Deza, M., Erd\u0151s, P., Frankl, P.: Intersection properties of systems of finite sets. Proc. Lond. Math. Soc. 36, 369\u2013384 (1978)","journal-title":"Proc. Lond. Math. Soc."},{"key":"136_CR5","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/BF01196133","volume":"17","author":"U Feige","year":"1997","unstructured":"Feige, U.: Randomized graph products, chromatic numbers, and the Lov\u00e1sz $$\\vartheta $$-function. Combinatorica 17, 79\u201390 (1997)","journal-title":"Combinatorica"},{"key":"136_CR6","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1016\/0097-3165(85)90035-4","volume":"39","author":"P Frankl","year":"1985","unstructured":"Frankl, P., F\u00fcredi, Z.: Forbidding just one intersection. J. Combin. Theory Ser. A 39, 160\u2013176 (1985)","journal-title":"J. Combin. Theory Ser. A"},{"issue":"4","key":"136_CR7","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/BF02579457","volume":"1","author":"P Frankl","year":"1981","unstructured":"Frankl, P., Wilson, R.M.: Intersection theorems with geometric consequences. Combinatorica 1(4), 357\u2013368 (1981)","journal-title":"Combinatorica"},{"issue":"1","key":"136_CR8","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/0012-365X(83)90081-X","volume":"47","author":"Z F\u00fcredi","year":"1983","unstructured":"F\u00fcredi, Z.: On finite set-systems whose every intersection is a kernel of a star. Discrete Math. 47(1), 129\u2013132 (1983)","journal-title":"Discrete Math."},{"key":"136_CR9","doi-asserted-by":"crossref","unstructured":"F\u00fcredi, Z.: Tur\u00e1n type problems. In: Surveys in Combinatorics, 1991 (Guildford, 1991), vol. 166 of London Mathematical Society Lecture Notes Series, pp. 253\u2013300. Cambridge University Press, Cambridge (1991)","DOI":"10.1017\/CBO9780511666216.010"},{"issue":"2","key":"136_CR10","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1109\/TIT.1979.1056027","volume":"25","author":"W Haemers","year":"1979","unstructured":"Haemers, W.: On some problems of Lov\u00e1sz concerning the Shannon capacity of a graph. IEEE Trans. Inform. Theory 25(2), 231\u2013232 (1979)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"136_CR11","unstructured":"Haemers, W.: An upper bound for the Shannon capacity of a graph. In: Algebraic Methods in Graph Theory, vols. I, II (Szeged, 1978), vol. 25 of Colloquia mathematica Societatis J\u00e1nos Bolyai, pp. 267\u2013272. North-Holland, Amsterdam (1981)"},{"key":"136_CR12","unstructured":"Haviv, I.: On minrank and the Lov\u00e1sz theta function. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and techniques, vol. 116 of LIPIcs. Leibniz International Proceedings in Informatics, pp. Art. No. 13, 15. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern (2018)"},{"key":"136_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.37236\/1193","volume":"1","author":"D Knuth","year":"1994","unstructured":"Knuth, D.: The sandwich theorem. Electron. J. Combin. 1, 1\u201348 (1994)","journal-title":"Electron. J. Combin."},{"key":"136_CR14","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz, L.: On the Shannon capacity of a graph. IEEE. Trans. Inform. Theory, pp. 1\u20137 (1979)","DOI":"10.1109\/TIT.1979.1055985"},{"issue":"8","key":"136_CR15","doi-asserted-by":"publisher","first-page":"3544","DOI":"10.1109\/TIT.2009.2023702","volume":"55","author":"E Lubetzky","year":"2009","unstructured":"Lubetzky, E., Stav, U.: Nonlinear index coding outperforming the linear optimum. IEEE Trans. Inform. Theory 55(8), 3544\u20133551 (2009)","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"3","key":"136_CR16","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1007\/BF01261326","volume":"16","author":"R Peeters","year":"1996","unstructured":"Peeters, R.: Orthogonal representations over finite fields and the chromatic number of graphs. Combinatorica 16(3), 417\u2013431 (1996)","journal-title":"Combinatorica"},{"key":"136_CR17","first-page":"737","volume":"12","author":"D Ray-Chaudhuri","year":"1975","unstructured":"Ray-Chaudhuri, D., Wilson, R.M.: On $$t$$-designs. Osaka J. Math. 12, 737\u2013744 (1975)","journal-title":"Osaka J. Math."},{"issue":"4","key":"136_CR18","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. Inform. Theory 25(4), 425\u2013429 (1979)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"136_CR19","unstructured":"Schrijver, A.: Association schemes and the Shannon capacity: Eberlein polynomials and the Erdos-Ko-Rado theorem. In: Algebraic Methods in Graph Theory, vols. I, II (Szeged, 1978), vol. 25 of Colloquia mathematica Societatis J\u00e1nos Bolyai, pp. 671\u2013688. North-Holland, Amsterdam (1981)"},{"key":"136_CR20","doi-asserted-by":"crossref","unstructured":"Shannon, C.E.: The zero error capacity of a noisy channel. In: Institute of Radio Engineers Transactions on Information Theory, IT-2(September), 8\u201319 (1956)","DOI":"10.1109\/TIT.1956.1056798"},{"key":"136_CR21","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/BF02579226","volume":"4","author":"RM Wilson","year":"1984","unstructured":"Wilson, R.M.: The exact bound in the Erdos-Ko-Rado theorem. Combinatorica 4, 247\u2013257 (1984)","journal-title":"Combinatorica"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-025-00136-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-025-00136-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-025-00136-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,6]],"date-time":"2025-05-06T09:06:19Z","timestamp":1746522379000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-025-00136-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,7]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,4]]}},"alternative-id":["136"],"URL":"https:\/\/doi.org\/10.1007\/s00493-025-00136-4","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"type":"print","value":"0209-9683"},{"type":"electronic","value":"1439-6912"}],"subject":[],"published":{"date-parts":[[2025,3,7]]},"assertion":[{"value":"4 September 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 May 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 December 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 March 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"12"}}