zbMATH — the first resource for mathematics

Testing subgraphs in large graphs. (English) Zbl 1027.68095
Summary: Let \(H\) be a fixed graph with \(h\) vertices, let \(G\) be a graph on \(n\) vertices, and suppose that at least \(\varepsilon n^2\) edges have to be deleted from it to make it \(H\)-free. It is known that in this case \(G\) contains at least \(f(\varepsilon ,H)n^h\) copies of \(H\). We show that the largest possible function \(f(\varepsilon, H)\) is polynomial in \(\varepsilon\) if and only if \(H\) is bipartite. This implies that there is a one-sided error property tester for checking \(H\)-freeness, whose query complexity is polynomial in \(1/\varepsilon\), if and only if \(H\) is bipartite.

68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI
[1] and The algorithmic aspects of the Regularity Lemma, Proc. 33rd IEEE FOCS, IEEE, Pittsburgh, 1992, pp. 473-481; · Zbl 0915.05102
[2] Alon, J Alg 16 pp 80– (1994)
[3] and Efficient testing of large graphs, Proc 40th Annu Symp Foundations of Computer Science (FOCS), IEEE, New York, 1999, 656-666;
[4] Alon, Combinatorica 20 pp 451– (2000)
[5] and Regular languages are testable with a constant number of queries, Proc 40th Annu Symp Foundations of Computer Science (FOCS), IEEE, New York, 1999, 645-655;
[6] Alon, SIAM J Comput 30 pp 1842– (2001)
[7] Alon, SIAM J Discrete Math 15 pp 211– (2002)
[8] Behrend, Proc Nat Acad Sci USA 32 pp 331– (1946)
[9] Bollob?s, Ann Discrete Math 3 pp 29– (1978)
[10] Bourgain, Geom Funct Anal 9 pp 968– (1999)
[11] and Testing hypergraph coloring, Proc ICALP, Heraklion, Crete, 2001, pp. 493-505. · Zbl 0986.05047
[12] Frieze, Combinatorica 19 pp 175– (1999)
[13] Goldreich, Combinatorica 20 pp 301– (2000)
[14] and Property testing and its connection to learning and approximation, Proc 37th Annu IEEE FOCS, Burlington, Vermont, 1996, pp. 339-348;
[15] Goldreich, J ACM 45 pp 653– (1998)
[16] and Property testing in bounded degree graphs, Proc 29th STOC, El Paso, Texas, 1997, pp. 406-415. · Zbl 0963.68154
[17] and Three theorems regarding testing graph properties, Proc 42nd IEEE FOCS, IEEE, Las Vegas, Nevada, 2001, pp. 460-469.
[18] Heath-Brown, J Lond Math Soc 35 pp 385– (1987)
[19] Hell, Discrete Math 109 pp 117– (1992)
[20] K?v?ri, Coll Math 3 pp 50– (1954)
[21] R?dl, Graphs Combinat 1 pp 91– (1985)
[22] ?Property testing,? and Handbook of randomized algorithms, (Editors), Kluwer Academic, Dordrecht, 2001, Vol. II, pp. 597-649.
[23] Roth, J Lond Math Soc 28 pp 104– (1953)
[24] Rubinfeld, SIAM J Comput 25 pp 252– (1996)
[25] Regular partitions of graphs, Proc Coll Int CNRS, J. C. Bermond, J. C. Fournier, M. Las Vergnas, and D. Sotteau, (Editors), Orsay, 1978, pp. 399-401.
[26] Szemer?di, Acta Math Acad Sci Hung 56 pp 155– (1990)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.