{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T11:42:31Z","timestamp":1772451751007,"version":"3.50.1"},"reference-count":18,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2019,11,14]],"date-time":"2019-11-14T00:00:00Z","timestamp":1573689600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2020,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The inducibility of a graph <jats:italic>H<\/jats:italic> measures the maximum number of induced copies of <jats:italic>H<\/jats:italic> a large graph <jats:italic>G<\/jats:italic> can have. Generalizing this notion, we study how many induced subgraphs of fixed order <jats:italic>k<\/jats:italic> and size <jats:italic>\u2113<\/jats:italic> a large graph <jats:italic>G<\/jats:italic> on <jats:italic>n<\/jats:italic> vertices can have. Clearly, this number is <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" mimetype=\"image\" xlink:href=\"S0963548319000294_inline1.png\"\/><jats:tex-math>$\\left( {\\matrix{n \\cr k}}\\right)$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> for every <jats:italic>n<\/jats:italic>, <jats:italic>k<\/jats:italic> and <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" mimetype=\"image\" xlink:href=\"S0963548319000294_inline2.png\"\/><jats:tex-math>$\\ell \\in \\left\\{ {0,\\left( {\\matrix{k \\cr 2}} \\right)}\\right\\}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. We conjecture that for every <jats:italic>n<\/jats:italic>, <jats:italic>k<\/jats:italic> and <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" mimetype=\"image\" xlink:href=\"S0963548319000294_inline3.png\"\/><jats:tex-math>$0 \\lt \\ell \\lt \\left( {\\matrix{k \\cr 2}}\\right)$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> this number is at most <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" mimetype=\"image\" xlink:href=\"S0963548319000294_inline4.png\"\/><jats:tex-math>$ (1\/e + {o_k}(1)) {\\left( {\\matrix{n \\cr k}} \\right)}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. If true, this would be tight for <jats:italic>\u2113<\/jats:italic> \u2208 {1, <jats:italic>k<\/jats:italic> \u2212 1}.<\/jats:p><jats:p>In support of our \u2018Edge-statistics Conjecture\u2019, we prove that the corresponding density is bounded away from 1 by an absolute constant. Furthermore, for various ranges of the values of <jats:italic>\u2113<\/jats:italic> we establish stronger bounds. In particular, we prove that for \u2018almost all\u2019 pairs (<jats:italic>k<\/jats:italic>, <jats:italic>\u2113<\/jats:italic>) only a polynomially small fraction of the <jats:italic>k<\/jats:italic>-subsets of <jats:italic>V<\/jats:italic>(<jats:italic>G<\/jats:italic>) have exactly <jats:italic>\u2113<\/jats:italic> edges, and prove an upper bound of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" mimetype=\"image\" xlink:href=\"S0963548319000294_inline5.png\"\/><jats:tex-math>$ (1\/2 + {o_k}(1)){\\left( {\\matrix{n \\cr k}}\\right)}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> for <jats:italic>\u2113<\/jats:italic> = 1.<\/jats:p><jats:p>Our proof methods involve probabilistic tools, such as anti-concentration results relying on fourth moment estimates and Brun\u2019s sieve, as well as graph-theoretic and combinatorial arguments such as Zykov\u2019s symmetrization, Sperner\u2019s theorem and various counting techniques.<\/jats:p>","DOI":"10.1017\/s0963548319000294","type":"journal-article","created":{"date-parts":[[2019,11,14]],"date-time":"2019-11-14T12:14:27Z","timestamp":1573733667000},"page":"163-189","source":"Crossref","is-referenced-by-count":10,"title":["Edge-statistics on large graphs"],"prefix":"10.1017","volume":"29","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[]},{"given":"Dan","family":"Hefetz","sequence":"additional","affiliation":[]},{"given":"Michael","family":"Krivelevich","sequence":"additional","affiliation":[]},{"given":"Mykhaylo","family":"Tyomkyn","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2019,11,14]]},"reference":[{"key":"S0963548319000294_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0619-4"},{"key":"S0963548319000294_ref13","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548310000465"},{"key":"S0963548319000294_ref12","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"key":"S0963548319000294_ref9","unstructured":"[9] Fox, J. and Sauermann, L. (2018) A completion of the proof of the Edge-statistics Conjecture. arXiv:1809.01352"},{"key":"S0963548319000294_ref11","unstructured":"[11] Kr\u00e1l, D. , Norin, S. and Volec, J. (2018) A bound on the inducibility of cycles. arXiv:1801.01556"},{"key":"S0963548319000294_ref14","doi-asserted-by":"publisher","DOI":"10.1112\/jlms.12192"},{"key":"S0963548319000294_ref15","unstructured":"[15] Martinsson, A. , Mousset, F. , Noever, A. and Truji\u0107, M. (2018) The edge-statistics conjecture for \u2113 \u226a k 6\/5. arXiv:1809.02576"},{"key":"S0963548319000294_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.09.003"},{"key":"S0963548319000294_ref7","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1945-08454-7"},{"key":"S0963548319000294_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2018.04.008"},{"key":"S0963548319000294_ref18","first-page":"163","article-title":"On some properties of linear complexes","volume":"24","author":"Zykov","year":"1949","journal-title":"Mat. Sbornik N.S."},{"key":"S0963548319000294_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(75)90084-2"},{"key":"S0963548319000294_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2015.08.006"},{"key":"S0963548319000294_ref6","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190180610"},{"key":"S0963548319000294_ref17","unstructured":"[17] Yuster, R. (2018) On the exact maximum induced density of almost all graphs and their inducibility. arXiv:1801.01047"},{"key":"S0963548319000294_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01902206"},{"key":"S0963548319000294_ref8","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007443"},{"key":"S0963548319000294_ref3","volume-title":"The Probabilistic Method","author":"Alon","year":"2016"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548319000294","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,3,25]],"date-time":"2020-03-25T08:15:05Z","timestamp":1585124105000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548319000294\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,14]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,3]]}},"alternative-id":["S0963548319000294"],"URL":"https:\/\/doi.org\/10.1017\/s0963548319000294","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,11,14]]}}}