{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,21]],"date-time":"2025-06-21T04:06:03Z","timestamp":1750478763599,"version":"3.41.0"},"reference-count":0,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2003,5,20]],"date-time":"2003-05-20T00:00:00Z","timestamp":1053388800000},"content-version":"unspecified","delay-in-days":19,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2003,5]]},"abstract":"<jats:p>This is a continuation of our work on quasi-random graph properties. The class of quasi-random graphs is defined by certain equivalent graph properties possessed by random graphs. One of the most important of these properties is that, for fixed <jats:inline-formula>$\\nu$<\/jats:inline-formula>, every fixed sample graph <jats:inline-formula>$L_\\nu$<\/jats:inline-formula> has the same frequency in <jats:inline-formula>$G_n$<\/jats:inline-formula> as in the <jats:inline-formula>$p$<\/jats:inline-formula>-random graph. (This holds for both induced and not necessarily induced containment.) In [9] we proved that, if the frequency of just <jats:italic>one<\/jats:italic> fixed <jats:inline-formula>$L_\\nu$<\/jats:inline-formula> \u2013 as a <jats:italic>not necessarily induced subgraph<\/jats:italic> \u2013 in every \u2018large\u2019 induced subgraph <jats:inline-formula>$F_h\\subseteq G_n$<\/jats:inline-formula> is the same as for the random graphs, then <jats:inline-formula>$(G_n)$<\/jats:inline-formula> is quasi-random. Here we shall investigate the analogous problem for <jats:italic>induced<\/jats:italic> subgraphs <jats:inline-formula>$L_\\nu$<\/jats:inline-formula>. In such cases <jats:inline-formula>$(G_n)$<\/jats:inline-formula> is not necessarily quasi-random.<\/jats:p>\n\t  <jats:p>We shall prove, <jats:italic>among other things<\/jats:italic>, that, for every <jats:italic>regular<\/jats:italic> sample graph <jats:inline-formula>$L_\\nu$<\/jats:inline-formula>, <jats:inline-formula>$\\nu\\geqslant 4$<\/jats:inline-formula>, if the number of induced copies of <jats:inline-formula>$L_\\nu$<\/jats:inline-formula> in every induced <jats:inline-formula>$F_h\\subseteq G_n$<\/jats:inline-formula> is asymptotically the same as in a <jats:inline-formula>$p$<\/jats:inline-formula>-random graph (up to an error term <jats:inline-formula>$o(n^\\nu)$<\/jats:inline-formula>), then <jats:inline-formula>$(G_n)$<\/jats:inline-formula> is the union of (at most) two quasi-random graph sequences, with possibly distinct attached probabilities (assuming that <jats:inline-formula>$p\\in (0,1)$<\/jats:inline-formula>, <jats:inline-formula>$e(L_\\nu)&gt;0$<\/jats:inline-formula>, and <jats:inline-formula>$L_\\nu\\ne K_\\nu$<\/jats:inline-formula>).<\/jats:p>\n\t  <jats:p>We conjecture the same conclusion for every <jats:inline-formula>$L_\\nu$<\/jats:inline-formula> with <jats:inline-formula>$\\nu\\ge 4$<\/jats:inline-formula>, <jats:italic>i.e.<\/jats:italic>, even if we drop the assumption of regularity.<\/jats:p>\n\t  <jats:p>We shall reduce the general problem to solving a system of polynomials. This gives a \u2018simple\u2019 algorithm to decide the problem for every given <jats:inline-formula>$L_\\nu$<\/jats:inline-formula>.<\/jats:p>","DOI":"10.1017\/s0963548303005613","type":"journal-article","created":{"date-parts":[[2003,5,22]],"date-time":"2003-05-22T08:58:54Z","timestamp":1053593934000},"page":"319-344","source":"Crossref","is-referenced-by-count":14,"title":["Hereditary Extended Properties, Quasi-Random Graphs and Induced Subgraphs"],"prefix":"10.1017","volume":"12","author":[{"given":"MIKL\u00d3S","family":"SIMONOVITS","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"VERA T.","family":"S\u00d3S","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2003,5,20]]},"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548303005613","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,20]],"date-time":"2025-06-20T19:54:22Z","timestamp":1750449262000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548303005613\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,5]]},"references-count":0,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2003,11]]}},"alternative-id":["S0963548303005613"],"URL":"https:\/\/doi.org\/10.1017\/s0963548303005613","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"type":"print","value":"0963-5483"},{"type":"electronic","value":"1469-2163"}],"subject":[],"published":{"date-parts":[[2003,5]]}}}