{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,21]],"date-time":"2025-06-21T09:10:02Z","timestamp":1750497002095,"version":"3.41.0"},"reference-count":0,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2005,4,11]],"date-time":"2005-04-11T00:00:00Z","timestamp":1113177600000},"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":[[2005,5]]},"abstract":"<jats:p>Many applications of Szemer\u00e9di's Regularity Lemma for graphs are based on the following counting result. If <jats:inline-formula>${\\mathcal G}$<\/jats:inline-formula> is an <jats:inline-formula>$s$<\/jats:inline-formula>-partite graph with partition <jats:inline-formula>$V({\\mathcal G}) =\\bigcup_{i=1}^{s} V_i$<\/jats:inline-formula>, <jats:inline-formula>$\\vert V_i\\vert =m$<\/jats:inline-formula> for all <jats:inline-formula>$i\\in [s]$<\/jats:inline-formula>, and all pairs <jats:inline-formula>$(V_i, V_j)$<\/jats:inline-formula>, <jats:inline-formula>$1\\leq i &lt; j\\leq s$<\/jats:inline-formula>, are <jats:inline-formula>$\\epsilon$<\/jats:inline-formula>-regular of density <jats:inline-formula>$d$<\/jats:inline-formula>, then <jats:inline-formula>$\\mathcal{G}$<\/jats:inline-formula> contains <jats:inline-formula>$(1\\pm f(\\epsilon))d^{({s\\atop 2})}m^s$<\/jats:inline-formula> cliques <jats:inline-formula>$K_{s}$<\/jats:inline-formula>, provided <jats:inline-formula>$\\epsilon&lt;\\epsilon(d)$<\/jats:inline-formula>, where <jats:inline-formula>$f(\\epsilon)$<\/jats:inline-formula> tends to 0 as <jats:inline-formula>$\\epsilon$<\/jats:inline-formula> tends to 0.<\/jats:p>\n\t  <jats:p>Guided by the regularity lemma for 3-uniform hypergraphs established earlier by Frankl and R\u00f6dl, Nagle and R\u00f6dl proved a corresponding counting lemma. Their proof is rather technical, mostly due to the fact that the \u2018quasi-random\u2019 hypergraph arising after application of Frankl and R\u00f6dl's regularity lemma is \u2018sparse\u2019, and consequently difficult to handle.<\/jats:p>\n\t  <jats:p>When the \u2018quasi-random\u2019 hypergraph is \u2018dense\u2019 Kohayakawa, R\u00f6dl and Skokan (<jats:italic>J. Combin. Theory Ser. A<\/jats:italic><jats:bold>97<\/jats:bold> 307\u2013352) found a simpler proof of the counting lemma. Their result applies even to <jats:inline-formula>$k$<\/jats:inline-formula>-uniform hypergraphs for arbitrary <jats:inline-formula>$k$<\/jats:inline-formula>. While the Frankl\u2013R\u00f6dl regularity lemma will not render the dense case, in this paper, for <jats:inline-formula>$k=3$<\/jats:inline-formula>, we are nevertheless able to reduce the harder, sparse case to the dense case.<\/jats:p>\n\t  <jats:p>Namely, we prove that a \u2018dense substructure\u2019 randomly chosen from the \u2018sparse <jats:inline-formula>$\\delta$<\/jats:inline-formula>-regular structure\u2019 is <jats:inline-formula>$\\delta$<\/jats:inline-formula>-regular as well. This allows us to count the number of cliques (and other subhypergraphs) using the Kohayakawa\u2013R\u00f6dl\u2013Skokan result, and provides an alternative proof of the counting lemma in the sparse case. Since the counting lemma in the dense case applies to <jats:inline-formula>$k$<\/jats:inline-formula>-uniform hypergraphs for arbitrary <jats:inline-formula>$k$<\/jats:inline-formula>, there is a possibility that the approach of this paper can be adopted to the general case as well.<\/jats:p>","DOI":"10.1017\/s0963548304006546","type":"journal-article","created":{"date-parts":[[2007,2,3]],"date-time":"2007-02-03T07:58:45Z","timestamp":1170489525000},"page":"371-413","source":"Crossref","is-referenced-by-count":5,"title":["Counting Small Cliques in 3-uniform Hypergraphs"],"prefix":"10.1017","volume":"14","author":[{"given":"Y.","family":"PENG","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"V.","family":"R\u00d6DL","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J.","family":"SKOKAN","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2005,4,11]]},"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548304006546","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,21]],"date-time":"2025-06-21T08:52:37Z","timestamp":1750495957000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548304006546\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,4,11]]},"references-count":0,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2005,7]]}},"alternative-id":["S0963548304006546"],"URL":"https:\/\/doi.org\/10.1017\/s0963548304006546","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"type":"print","value":"0963-5483"},{"type":"electronic","value":"1469-2163"}],"subject":[],"published":{"date-parts":[[2005,4,11]]}}}