{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T02:28:20Z","timestamp":1740104900392,"version":"3.37.3"},"reference-count":29,"publisher":"Wiley","issue":"3-4","license":[{"start":{"date-parts":[[2002,10,16]],"date-time":"2002-10-16T00:00:00Z","timestamp":1034726400000},"content-version":"vor","delay-in-days":15,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"funder":[{"DOI":"10.13039\/501100000038","name":"NSERC","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]},{"name":"NSF","award":["DMS-0071261"],"award-info":[{"award-number":["DMS-0071261"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Random Struct Algorithms"],"published-print":{"date-parts":[[2002,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Szemer\u00e9di's Regularity Lemma is a well\u2010known and powerful tool in modern graph theory. This result led to a number of interesting applications, particularly in extremal graph theory. A regularity lemma for 3\u2010uniform hypergraphs developed by Frankl and R\u00f6dl [8] allows some of the Szemer\u00e9di Regularity Lemma graph applications to be extended to hypergraphs. An important development regarding Szemer\u00e9di's Lemma showed the equivalence between the property of \u03f5\u2010regularity of a bipartite graph<jats:italic>G<\/jats:italic>and an easily verifiable property concerning the neighborhoods of its vertices (Alon et al. [1]; cf. [6]). This characterization of \u03f5\u2010regularity led to an algorithmic version of Szemer\u00e9di's lemma [1]. Similar problems were also considered for hypergraphs. In [2], [9], [13], and [18], various descriptions of quasi\u2010randomness of<jats:italic>k<\/jats:italic>\u2010uniform hypergraphs were given. As in [1], the goal of this paper is to find easily verifiable conditions for the hypergraph regularity provided by [8]. The hypergraph regularity of [8] renders quasi\u2010random \u201cblocks of hyperedges\u201d which are very sparse. This situation leads to technical difficulties in its application. Moreover, as we show in this paper, some easily verifiable conditions analogous to those considered in [2] and [18] fail to be true in the setting of [8]. However, we are able to find some necessary and sufficient conditions for this hypergraph regularity. These conditions enable us to design an algorithmic version of a hypergraph regularity lemma in [8]. This algorithmic version is presented by the authors in [5]. \u00a9 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 293\u2013335, 2002<\/jats:p>","DOI":"10.1002\/rsa.10058","type":"journal-article","created":{"date-parts":[[2002,10,21]],"date-time":"2002-10-21T13:37:09Z","timestamp":1035207429000},"page":"293-335","source":"Crossref","is-referenced-by-count":11,"title":["On characterizing hypergraph regularity"],"prefix":"10.1002","volume":"21","author":[{"given":"Y.","family":"Dementieva","sequence":"first","affiliation":[]},{"given":"P. E.","family":"Haxell","sequence":"additional","affiliation":[]},{"given":"B.","family":"Nagle","sequence":"additional","affiliation":[]},{"given":"V.","family":"R\u00f6dl","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2002,10,16]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1005"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010108"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480197318301"},{"key":"e_1_2_1_5_2","unstructured":"Y.Dementieva Ph.D. Thesis Emory University Atlanta GA 2001."},{"key":"e_1_2_1_6_2","unstructured":"Y.Dementieva P.Haxell B.Nagle andV.R\u00f6dl An algorithmic version of hypergraph regularity lemma in preparation."},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793247634"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(85)80045-7"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10017"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02351586"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(88)90040-8"},{"key":"e_1_2_1_12_2","doi-asserted-by":"crossref","unstructured":"A.FriezeandR.Kannan The Regularity Lemma and approximation schemes for dense problems Proc IEEE Symp Found Comput Sci 1996 pp.12\u201320.","DOI":"10.1109\/SFCS.1996.548459"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050052"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(89)90093-9"},{"journal-title":"Random Struct Alg","article-title":"Integer and fractional packings in dense 3\u2010uniform hypergraphs","author":"Haxell P.","key":"e_1_2_1_15_2"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/s004930170003"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"journal-title":"Combinatorics, Probability and Computing","article-title":"Hereditary properties of triple systems","author":"Kohayakawa Y.","key":"e_1_2_1_18_2"},{"key":"e_1_2_1_19_2","unstructured":"Y.Kohayakawa V.R\u00f6dl andJ.Skokan Equivalent conditions of hypergraph regularity submitted."},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01196135"},{"key":"e_1_2_1_21_2","series-title":"Combinatorics, Paul Erd\u0151s is eighty","first-page":"295","volume-title":"Szemer\u00e9di's regularity lemma and its applications in graph theory","author":"Koml\u00f3s J.","year":"1993"},{"key":"e_1_2_1_22_2","unstructured":"B.Nagle Ph.D. Thesis Emory University Atlanta GA 1999."},{"journal-title":"Random Struct Alg","article-title":"Regularity properties for triple systems","author":"Nagle B.","key":"e_1_2_1_23_2"},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(00)00280-6"},{"key":"e_1_2_1_25_2","unstructured":"Y.Peng V.R\u00f6dl andJ.Skokan Counting small cliques in 3\u2010uniform hypergraphs submitted."},{"key":"e_1_2_1_26_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240050202"},{"key":"e_1_2_1_27_2","doi-asserted-by":"publisher","DOI":"10.2307\/2152833"},{"key":"e_1_2_1_28_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.1997.2785"},{"key":"e_1_2_1_29_2","unstructured":"V.R\u00f6dl A.Ruci\u0144ski andE.Szemer\u00e9di in preparation."},{"key":"e_1_2_1_30_2","unstructured":"E.Szemer\u00e9di \u201cRegular partitions of graphs \u201d Probl\u00e8mes en combinatoire et th\u00e9orie des graphes Proc Coll Int CNRS J.\u2010C. Bermond J.\u2010C. Fournier M. Las Vergnas D. Sotteau (Editors) 1978 pp.399\u2013401."}],"container-title":["Random Structures &amp; Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Frsa.10058","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.10058","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T21:07:23Z","timestamp":1733864843000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/rsa.10058"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,10]]},"references-count":29,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2002,10]]}},"alternative-id":["10.1002\/rsa.10058"],"URL":"https:\/\/doi.org\/10.1002\/rsa.10058","archive":["Portico"],"relation":{},"ISSN":["1042-9832","1098-2418"],"issn-type":[{"type":"print","value":"1042-9832"},{"type":"electronic","value":"1098-2418"}],"subject":[],"published":{"date-parts":[[2002,10]]}}}