{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:39:52Z","timestamp":1787337592455,"version":"build-2736575974"},"reference-count":43,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2008,1]]},"abstract":"<jats:p>Extending the Szemer\u00e9di regularity lemma for graphs, P. Frankl and V. R\u00f6dl [Random Structures Algorithms, 20 (2002), pp. 131\u2013164] established a 3-graph regularity lemma triple systems ${\\cal G}_n$ admit bounded partitions of their edge sets, most classes of which consist of regularly distributed triples. Many applications of this lemma require a companion counting lemma [B. Nagle and V. R\u00f6dl, Random Structures Algorithms, 23 (2003), pp. 264\u2013332] allowing one to find and enumerate subhypergraphs of a given isomorphism type in a \u201cdense and regular\u201d environment created by the 3-graph regularity lemma. Combined applications of these lemmas are known as the 3-graph regularity method. In this paper, we provide an algorithmic version of the 3-graph regularity lemma which, as we show, is compatible with a counting lemma. We also discuss some applications.<\/jats:p>","DOI":"10.1137\/060652385","type":"journal-article","created":{"date-parts":[[2008,3,26]],"date-time":"2008-03-26T18:07:13Z","timestamp":1206554833000},"page":"1728-1776","source":"Crossref","is-referenced-by-count":7,"title":["An Algorithmic Version of the Hypergraph Regularity Method"],"prefix":"10.1137","volume":"37","author":[{"given":"P. E.","family":"Haxell","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"B.","family":"Nagle","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"V.","family":"R\u00f6dl","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2008,3,26]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1005"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"N. Alon, R. Duke, H. Lefmann, V. R\u00f6dl, and R. Yuster,\n                      The algorithmic aspects of the Regularity Lemma (extended abstract)\n                      , in Proceedings of the IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 1992, pp. 473\u2013481.","DOI":"10.1109\/SFCS.1992.267804"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"N. Alon, A. Shapira, and B. Sudakov,\n                      Additive approximation for edge-deletion problems\n                      , in Proceedings of the IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 2005, pp. 419\u2013428.","DOI":"10.1109\/SFCS.2005.11"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240020208"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-1991-1077279-1"},{"key":"R6","unstructured":"A. Czygrinow and B. Nagle,\n                      On small subsystems of uniformly distributed\n                      3\n                      -graphs\n                      , submitted."},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799351729"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10058"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"D. Dor and M. Tarsi,\n                      Graph decomposition is NPC\u2014a complete proof of Holyer's conjecture\n                      , in Proceedings of the ACM Symposium on Theory of Computing, ACM, New York, 1992, pp. 252\u2013263.","DOI":"10.1145\/129712.129737"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793247634"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10017"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1007\/BF02351586"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"A. Frieze and R. Kannan,\n                      The Regularity Lemma and approximation schemes for dense problems\n                      , in Proceedings of the IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 1996, pp. 12\u201320.","DOI":"10.1109\/SFCS.1996.548459"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050052"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548305007236"},{"key":"R16","unstructured":"W. T. Gowers,\n                      Hypergraph Regularity and the Multidimensional Szemer\u00e9di Theorem\n                      , preprint, Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Cambridge, UK, 2004."},{"key":"R17","doi-asserted-by":"crossref","unstructured":"P. Haxell, B. Nagle, and V. R\u00f6dl,\n                      An algorithmic version of the hypergraph regularity method (extended abstract)\n                      , in Proceedings of the IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 2005, pp. 439\u2013446.","DOI":"10.1109\/SFCS.2005.17"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10075"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1007\/s004930170003"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548302005503"},{"key":"R21","unstructured":"Y. Kohayakawa, B. Nagle, and V. R\u00f6dl,\n                      Efficient testing of hypergraphs\n                      , in ICALP 2002, 29th International Colloquium on Automata, Languages and Programming (Malaga, Spain), Lecture Notes in Comput. Sci. 2286, Springer-Verlag, Berlin, 2002, pp. 278\u2013292."},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.2001.3217"},{"key":"R23","unstructured":"Y. Kohayakawa, V. R\u00f6dl, and L. Thoma,\n                      An optimal algorithm for checking regularity (extended abstract)\n                      , in Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2002), San Francisco, CA, 2002, pp. 277\u2013286."},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702408223"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"J. Koml\u00f3s, A. Shokoufandeh, M. Simonovits, and E. Szemer\u00e9di,\n                      The regularity lemma and its applications in graph theory\n                      , in Theoretical Aspects of Computer Science (Tehran, 2000), Lecture Notes in Comput. Sci. 2292, Springer-Verlag, Berlin, 2002, pp. 84\u2013112.","DOI":"10.1007\/3-540-45878-6_3"},{"key":"R26","first-page":"295","volume":"2","author":"Koml\u00f3s J.","year":"1996","journal-title":"in Combinatorics, Paul Erd\u00f6s is Eighty"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10094"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(00)00280-6"},{"key":"R29","first-page":"1","volume":"26","author":"Nagle B.","year":"2006","journal-title":"Random Structures Algorithms","ISSN":"https:\/\/id.crossref.org\/issn\/1042-9832","issn-type":"print"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548304006546"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.1997.2785"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548305007042"},{"key":"R33","unstructured":"V. R\u00f6dl, M. Schacht, M. Siggers, and N. Tokushige,\n                      Fractional packings of hypergraphs\n                      , J. Combin. Theory Ser. B, to appear."},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1007\/BF02771992"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20017"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20108"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-004-0556-1"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548303005959"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.4064\/aa-27-1-199-245"},{"key":"R40","unstructured":"E. Szemer\u00e9di,\n                      Regular partitions of graphs\n                      , in Probl\u00e8mes Combinatoires et Th\u00e9orie des Graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), J.C. Bermond, J.C. Fournier, M. Las Vergnas, and D. Sotteau, eds., Colloq. Internat. CNRS 260, CNRS, Paris, 1978, pp. 399\u2013401."},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2005.11.006"},{"key":"R42","unstructured":"T. Tao,\n                      The Gaussian primes contain arbitrarily shaped constellations\n                      , J. Anal. Math., to appear."},{"key":"R43","first-page":"381","volume":"75","author":"Thomason A.","year":"1989","journal-title":"in Graph Theory and Combinatorics (Cambridge, 1988), Discrete Math."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/060652385","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:19:37Z","timestamp":1787336377000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/060652385"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1]]},"references-count":43,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2008,1]]}},"alternative-id":["10.1137\/060652385"],"URL":"https:\/\/doi.org\/10.1137\/060652385","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,1]]}}}