{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,11]],"date-time":"2026-06-11T17:59:35Z","timestamp":1781200775939,"version":"3.54.1"},"reference-count":31,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2025,7,7]],"date-time":"2025-07-07T00:00:00Z","timestamp":1751846400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2025,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Counting independent sets in graphs and hypergraphs under a variety of restrictions is a classical question with a long history. It is the subject of the celebrated container method which found numerous spectacular applications over the years. We consider the question of how many independent sets we can have in a graph under structural restrictions. We show that any <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000124_inline1.png\"\/><jats:tex-math>\n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-vertex graph with independence number <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000124_inline2.png\"\/><jats:tex-math>\n$\\alpha$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> without <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000124_inline3.png\"\/><jats:tex-math>\n$bK_a$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> as an induced subgraph has at most <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000124_inline4.png\"\/><jats:tex-math>\n$n^{O(1)} \\cdot \\alpha ^{O(\\alpha )}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> independent sets. This substantially improves the trivial upper bound of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000124_inline5.png\"\/><jats:tex-math>\n$n^{\\alpha },$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> whenever <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000124_inline6.png\"\/><jats:tex-math>\n$\\alpha \\le n^{o(1)}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and gives a characterisation of graphs forbidding which allows for such an improvement. It is also in general tight up to a constant in the exponent since there exist triangle-free graphs with <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000124_inline7.png\"\/><jats:tex-math>\n$\\alpha ^{\\Omega (\\alpha )}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> independent sets. We also prove that if one in addition assumes the ground graph is chi-bounded one can improve the bound to <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000124_inline8.png\"\/><jats:tex-math>\n$n^{O(1)} \\cdot 2^{O(\\alpha )}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> which is tight up to a constant factor in the exponent.<\/jats:p>","DOI":"10.1017\/s0963548325000124","type":"journal-article","created":{"date-parts":[[2025,7,7]],"date-time":"2025-07-07T03:22:44Z","timestamp":1751858564000},"page":"625-634","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":1,"title":["Counting independent sets in structured graphs"],"prefix":"10.1017","volume":"34","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1055-3309","authenticated-orcid":false,"given":"Matija","family":"Buci\u0107","sequence":"first","affiliation":[{"name":"Princeton University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Maria","family":"Chudnovsky","sequence":"additional","affiliation":[{"name":"Princeton University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Julien","family":"Codsi","sequence":"additional","affiliation":[{"name":"Princeton University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2025,7,7]]},"reference":[{"key":"S0963548325000124_ref18","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2024.12.009"},{"key":"S0963548325000124_ref5","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20973"},{"key":"S0963548325000124_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02772952"},{"key":"S0963548325000124_ref26","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2024.199.2.8"},{"key":"S0963548325000124_ref4","doi-asserted-by":"publisher","DOI":"10.1142\/9789813272880_0172"},{"key":"S0963548325000124_ref24","doi-asserted-by":"publisher","DOI":"10.1007\/BF02773386"},{"key":"S0963548325000124_ref12","doi-asserted-by":"publisher","DOI":"10.1090\/proc\/13728"},{"key":"S0963548325000124_ref31","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22601"},{"key":"S0963548325000124_ref22","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(82)90204-7"},{"key":"S0963548325000124_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2024.10.007"},{"key":"S0963548325000124_ref9","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-2014-12068-5"},{"key":"S0963548325000124_ref3","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-2014-00816-X"},{"key":"S0963548325000124_ref28","first-page":"56","article-title":"On the number of independent sets in extenders","volume":"13","author":"Sapozhenko","year":"2001","journal-title":"Diskret. Mat."},{"key":"S0963548325000124_ref30","doi-asserted-by":"publisher","DOI":"10.1007\/s00222-014-0562-8"},{"key":"S0963548325000124_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2023.10.006"},{"key":"S0963548325000124_ref21","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70708-8"},{"key":"S0963548325000124_ref8","unstructured":"[8] Chudnovsky, M. , Hajebi, S. , Lokshtanov, D. and Spirkl, S. (2024) Tree independence number II. Three-path-configurations. Three-path-configurations, arXiv\u00a0preprint arXiv: 2405.00265."},{"key":"S0963548325000124_ref19","doi-asserted-by":"publisher","DOI":"10.37236\/9223"},{"key":"S0963548325000124_ref15","first-page":"v+125","article-title":"The triangle-free process and the Ramsey number \n\n\n\n$R(3,k)$","volume":"263","author":"Pontiveros","year":"2020","journal-title":"Mem. Amer. Math. Soc."},{"key":"S0963548325000124_ref7","unstructured":"[7] Buci\u0107, M. , Fox, J. and Pham, H. T. (2024) Equivalence between Erd\u0151s-Hajnal and polynomial R\u00f6dl and Nikiforov conjectures, arXiv\u00a0preprint arXiv: 2403.08303."},{"key":"S0963548325000124_ref17","doi-asserted-by":"publisher","DOI":"10.1093\/imrn\/rnaf025"},{"key":"S0963548325000124_ref20","first-page":"349","volume-title":"Reducibility Among Combinatorial Problems (1972), Ideas That Created the Future\u2014Classic Papers of Computer Science","author":"Karp","year":"2021"},{"key":"S0963548325000124_ref27","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2015.02.005"},{"key":"S0963548325000124_ref23","doi-asserted-by":"publisher","DOI":"10.4064\/cm-3-1-50-57"},{"key":"S0963548325000124_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/BF02759942"},{"key":"S0963548325000124_ref29","first-page":"454","article-title":"Asymptotics of the number of sum-free sets in abelian groups of even order","volume":"383","author":"Sapozhenko","year":"2002","journal-title":"Dokl. Akad. Nauk"},{"key":"S0963548325000124_ref10","first-page":"51:1","volume-title":"51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs)","author":"Dallard","year":"2024"},{"key":"S0963548325000124_ref16","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20344"},{"key":"S0963548325000124_ref25","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548317000542"},{"key":"S0963548325000124_ref14","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(89)90268-9"},{"key":"S0963548325000124_ref6","article-title":"On polynomial degree-boundedness","volume":"5","author":"Bourneuf","year":"2024","journal-title":"Adv. Comb."}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548325000124","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,16]],"date-time":"2025-09-16T00:12:19Z","timestamp":1757981539000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548325000124\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,7]]},"references-count":31,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,9]]}},"alternative-id":["S0963548325000124"],"URL":"https:\/\/doi.org\/10.1017\/s0963548325000124","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,7,7]]},"assertion":[{"value":"\u00a9 The Author(s), 2025. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution-NonCommercial-NoDerivatives licence (https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/), which permits non-commercial re-use, distribution, and reproduction in any medium, provided the original work is unaltered and is properly cited. The written permission of Cambridge University Press must be obtained for commercial re-use or in order to create a derivative work.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}