{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,4]],"date-time":"2026-10-04T09:54:53Z","timestamp":1791107693321,"version":"4.1.0"},"reference-count":20,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2008,1]]},"abstract":"<jats:p>In this paper we consider the problem of testing whether a graph is triangle-free and, more generally, whether it is H-free, for a fixed subgraph H. The algorithm should accept graphs that are triangle-free and reject graphs that are far from being triangle-free in the sense that a constant fraction of the edges should be removed in order to obtain a triangle-free graph. The algorithm is allowed a small probability of error. This problem has been studied quite extensively in the past, but the focus was on dense graphs, that is, when $d = \\Theta(n)$, where d is the average degree in the graph and n is the number of vertices. Here we study the complexity of the problem in general graphs, that is, for varying d. In this model a testing algorithm is allowed to ask neighbor queries (i.e., \u201cWhat is the ith neighbor of vertex v?\u201d), vertex-pair queries (i.e., \u201cIs there an edge between vertices v and u?\u201d), and degree queries (i.e., \u201cWhat is the degree of vertex v?\u201d). Our main finding is a lower bound of $\\Omega(n^{1\/3})$ on the necessary number of queries that holds for every $d &lt; n^{1-\\nu(n)}$, where $\\nu(n) = o(1)$. Since when $d = \\Theta(n)$ the number of queries sufficient for testing has been known to be independent of n, we observe an abrupt, threshold-like behavior of the complexity of testing around n. This lower bound holds for testing H-freeness of every nonbipartite subgraph H. Additionally, we provide sublinear upper bounds for testing triangle-freeness that are at most quadratic in the stated lower bounds, and we describe a transformation from certain one-sided error lower bounds for testing subgraph-freeness to two-sided error lower bounds. Finally, in the course of our analysis we show that dense random Cayley graphs behave like quasi-random graphs in the sense that relatively large subsets of vertices have the \u201ccorrect\u201d edge density. The result for subsets of this size cannot be obtained from the known spectral techniques that only supply such estimates for much larger subsets.<\/jats:p>","DOI":"10.1137\/07067917x","type":"journal-article","created":{"date-parts":[[2008,4,18]],"date-time":"2008-04-18T18:06:43Z","timestamp":1208542003000},"page":"786-819","source":"Crossref","is-referenced-by-count":27,"title":["Testing Triangle-Freeness in General Graphs"],"prefix":"10.1137","volume":"22","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tali","family":"Kaufman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Krivelevich","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dana","family":"Ron","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2008,4,18]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10056"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070001"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1109\/18.412676"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240050203"},{"key":"R5","unstructured":"N. Alon and A. Shapira,\n                      A characterization of easily testable induced subgraphs\n                      , in Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM, New York, SIAM, Philadelphia, 2004, pp. 942\u2013951."},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.008"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.32.12.331"},{"key":"R8","first-page":"97","volume":"75","author":"Fischer E.","year":"2001","journal-title":"Bullet. Eur. Assoc. Theoret. Comput. Sci. EATCS"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0078-7"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-005-0018-2"},{"key":"R12","unstructured":"L. Gugelmann,\n                      Testing Triangle-Freeness in General Graphs: Lower Bounds\n                      , Bachelor thesis, Dept. of Mathematics, ETH, Zurich, 2006."},{"key":"R13","unstructured":"S. Janson, T. \u0141uczak, and A. Ruci\u0144ski,\n                      Random graphs\n                      , Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000."},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703436424"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10013"},{"key":"R16","unstructured":"T. Rast,\n                      Testing Triangle-Freeness in General Graphs: Upper Bounds\n                      , Bachelor thesis, Dept. of Mathematics, ETH, Zurich, 2006."},{"key":"R17","unstructured":"D. Ron,\n                      Property testing\n                      , in Handbook of Randomized Computing, Volume II, S. Rajasekaran, P. M. Pardalos, J. H. Reif, and J. Rolim, eds., Kluwer Academic Publishers, Dordrecht, The Netherlands, 2001, pp. 597\u2013649."},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"R19","first-page":"939","volume":"18","author":"Ruzsa I. Z.","year":"1976","journal-title":"Coll. Math. Soc. J. Bolyai.","ISSN":"https:\/\/id.crossref.org\/issn\/0139-3383","issn-type":"print"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.28.12.561"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/07067917X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:02:17Z","timestamp":1787320937000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/07067917X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,1]]}},"alternative-id":["10.1137\/07067917X"],"URL":"https:\/\/doi.org\/10.1137\/07067917x","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,1]]}}}