{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,26]],"date-time":"2025-08-26T06:28:20Z","timestamp":1756189700019},"reference-count":38,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2020,3,24]],"date-time":"2020-03-24T00:00:00Z","timestamp":1585008000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2020,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>There has been substantial interest in estimating the value of a graph parameter, <jats:italic>i.e.<\/jats:italic> of a real-valued function defined on the set of finite graphs, by querying a randomly sampled substructure whose size is independent of the size of the input. Graph parameters that may be successfully estimated in this way are said to be <jats:italic>testable<\/jats:italic> or <jats:italic>estimable<\/jats:italic>, and the <jats:italic>sample complexity q<\/jats:italic><jats:sub><jats:italic>z<\/jats:italic><\/jats:sub> = <jats:italic>q<jats:sub>z<\/jats:sub><\/jats:italic>(<jats:italic>\u03b5<\/jats:italic>) of an estimable parameter <jats:italic>z<\/jats:italic> is the size of a random sample of a graph <jats:italic>G<\/jats:italic> required to ensure that the value of <jats:italic>z<\/jats:italic>(<jats:italic>G<\/jats:italic>) may be estimated within an error of <jats:italic>\u03b5<\/jats:italic> with probability at least 2\/3. In this paper, for any fixed monotone graph property <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000048_inline1.png\" \/><jats:tex-math>$\\mathcal{P}= \\text{Forb}\\!(\\mathcal{F}),$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> we study the sample complexity of estimating a bounded graph parameter <jats:italic>z<\/jats:italic><jats:sub><jats:italic \/><\/jats:sub> that, for an input graph <jats:italic>G<\/jats:italic>, counts the number of <jats:italic>spanning<\/jats:italic> subgraphs of <jats:italic>G<\/jats:italic> that satisfy<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000048_inline2.png\" \/><jats:tex-math>$\\mathcal{P}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. To improve upon previous upper bounds on the sample complexity, we show that the vertex set of any graph that satisfies a monotone property <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000048_inline2.png\" \/><jats:tex-math>$\\mathcal{P}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> may be partitioned equitably into a constant number of classes in such a way that the cluster graph induced by the partition is not far from satisfying a natural weighted graph generalization of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000048_inline2.png\" \/><jats:tex-math>$\\mathcal{P}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. Properties for which this holds are said to be <jats:italic>recoverable<\/jats:italic>, and the study of recoverable properties may be of independent interest.<\/jats:p>","DOI":"10.1017\/s0963548320000048","type":"journal-article","created":{"date-parts":[[2020,3,24]],"date-time":"2020-03-24T05:17:18Z","timestamp":1585027038000},"page":"616-632","update-policy":"http:\/\/dx.doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":4,"title":["Estimating parameters associated with monotone properties"],"prefix":"10.1017","volume":"29","author":[{"given":"Carlos","family":"Hoppen","sequence":"first","affiliation":[]},{"given":"Yoshiharu","family":"Kohayakawa","sequence":"additional","affiliation":[]},{"given":"Richard","family":"Lang","sequence":"additional","affiliation":[]},{"given":"Hanno","family":"Lefmann","sequence":"additional","affiliation":[]},{"given":"Henrique","family":"Stagni","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2020,3,24]]},"reference":[{"key":"S0963548320000048_ref26","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10078"},{"key":"S0963548320000048_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2003.08.001"},{"key":"S0963548320000048_ref4","doi-asserted-by":"publisher","DOI":"10.1137\/060667177"},{"key":"S0963548320000048_ref16","unstructured":"[16] Erd\u0151s, P. , Kleitman, D. J. and Rothschild, B. L. (1976) Asymptotic enumeration of Kn -free graphs. In Colloquio Internazionale sulle Teorie Combinatorie (Rome, 1973), Vol. II, Accademia Nazionale dei Lincei, Rome, pp. 19\u201327."},{"key":"S0963548320000048_ref10","unstructured":"[10] Bollob\u00e1s, B. (1998) Hereditary properties of graphs: Asymptotic enumeration, global structure, and colouring. Documenta Math. Extra Vol. ICM III 333\u2013342."},{"key":"S0963548320000048_ref32","doi-asserted-by":"publisher","DOI":"10.1090\/tran\/7414"},{"key":"S0963548320000048_ref12","doi-asserted-by":"crossref","first-page":"1191","DOI":"10.1007\/s00039-012-0171-x","article-title":"Bounds for graph regularity and removal lemmas","volume":"22","author":"Conlon","year":"2012","journal-title":"Geom. Funct. Anal."},{"key":"S0963548320000048_ref5","doi-asserted-by":"publisher","DOI":"10.1137\/06064888X"},{"key":"S0963548320000048_ref30","unstructured":"[30] Koml\u00f3s, J. and Simonovits, M. (1996) Szemer\u00e9di\u2019s regularity lemma and its applications in graph theory. In Combinatorics: Paul Erd\u0151s is Eighty (Keszthely 1993), Vol. 2 of Bolyai Society Mathematical Studies, J\u00e1nos Bolyai Mathematical Society, pp. 295\u2013352."},{"key":"S0963548320000048_ref35","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(94)00334-F"},{"key":"S0963548320000048_ref22","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-9078-6_129"},{"key":"S0963548320000048_ref20","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1017\/S0963548317000049","article-title":"On regularity lemmas and their algorithmic applications","volume":"26","author":"Fox","year":"2017","journal-title":"Combin. Probab. Comput."},{"key":"S0963548320000048_ref28","unstructured":"[28] Hoppen, C. , Kohayakawa, Y. , Lang, R. , Lefmann, H. and Stagni, H. (2016) Estimating parameters associated with monotone properties. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2016) ( Jansen, K. , Mathieu, C. , Rolim, J. D. P. and Umans, C. , eds), Vol. 60 of Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, pp. 35:1\u201335:13."},{"key":"S0963548320000048_ref17","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/BF02579292","article-title":"Supersaturated graphs and hypergraphs","volume":"3","author":"Erd\u0151s","year":"1983","journal-title":"Combinatorica"},{"key":"S0963548320000048_ref21","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050052"},{"key":"S0963548320000048_ref1","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1002\/rsa.10056","article-title":"Testing subgraphs in large graphs","volume":"21","author":"Alon","year":"2002","journal-title":"Random Struct. Alg."},{"key":"S0963548320000048_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070001"},{"key":"S0963548320000048_ref15","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/BF01788085","article-title":"The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent","volume":"2","author":"Erd\u0151s","year":"1986","journal-title":"Graphs Combin."},{"key":"S0963548320000048_ref7","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2009.170.371"},{"key":"S0963548320000048_ref38","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2005.11.006"},{"key":"S0963548320000048_ref9","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/jdq086"},{"key":"S0963548320000048_ref11","doi-asserted-by":"crossref","first-page":"1801","DOI":"10.1016\/j.aim.2008.07.008","article-title":"Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing","volume":"219","author":"Borgs","year":"2008","journal-title":"Adv. Math."},{"key":"S0963548320000048_ref13","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139506748.002"},{"key":"S0963548320000048_ref14","doi-asserted-by":"crossref","first-page":"598","DOI":"10.1137\/S0097539793247634","article-title":"A fast approximation algorithm for computing the frequencies of subgraphs in a given graph","volume":"24","author":"Duke","year":"1995","journal-title":"SIAM J. Comput."},{"key":"S0963548320000048_ref18","doi-asserted-by":"crossref","first-page":"482","DOI":"10.1137\/060652324","article-title":"Testing versus estimation of graph properties","volume":"37","author":"Fischer","year":"2007","journal-title":"SIAM J. Comput."},{"key":"S0963548320000048_ref19","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2011.174.1.17"},{"key":"S0963548320000048_ref33","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.03.002"},{"key":"S0963548320000048_ref23","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055404"},{"key":"S0963548320000048_ref24","doi-asserted-by":"crossref","unstructured":"[24] Goldreich, O. (2010) Property Testing: Current Research and Surveys, Vol. 6390 of Lecture Notes in Computer Science, Springer.10.1007\/978-3-642-16367-8","DOI":"10.1007\/978-3-642-16367-8"},{"key":"S0963548320000048_ref25","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"S0963548320000048_ref27","doi-asserted-by":"publisher","DOI":"10.1007\/PL00001621"},{"key":"S0963548320000048_ref29","unstructured":"[29] Jukna, S. (2001) Extremal Combinatorics: With Applications in Computer Science, second edition (2011), Texts in Theoretical Computer Science, Springer."},{"key":"S0963548320000048_ref31","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-007-0599-6"},{"key":"S0963548320000048_ref34","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305238"},{"key":"S0963548320000048_ref36","unstructured":"[36] Ruzsa, I. Z. and Szemer\u00e9di, E. (1978) Triple systems with no six points carrying three triangles. In Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. 18 of Colloquia Mathematica Societatis J\u00e1nos Bolyai, North-Holland, pp. 939\u2013945."},{"key":"S0963548320000048_ref37","first-page":"399","article-title":"Regular partitions of graphs","volume":"260","author":"Szemer\u00e9di","year":"1976","journal-title":"Colloq. Internat. CNRS"},{"key":"S0963548320000048_ref6","doi-asserted-by":"publisher","DOI":"10.1137\/050633445"},{"key":"S0963548320000048_ref2","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1006\/jagm.1994.1005","article-title":"The algorithmic aspects of the regularity lemma","volume":"16","author":"Alon","year":"1994","journal-title":"J. Algorithms"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548320000048","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,13]],"date-time":"2020-10-13T13:34:52Z","timestamp":1602596092000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548320000048\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,24]]},"references-count":38,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,7]]}},"alternative-id":["S0963548320000048"],"URL":"https:\/\/doi.org\/10.1017\/s0963548320000048","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,3,24]]},"assertion":[{"value":"\u00a9 Cambridge University Press 2020","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}