Fetching the paper…
Reading the bibliography…
Recent works of Alon-Shapira and R\"odl-Schacht have demonstrated that every hereditary property of undirected graphs or hypergraphs is testable with one-sided error; informally, this means that if a graph or hypergraph satisfies that property "locally" with sufficiently high probability, then it can be perturbed (or "repaired") into a graph or hypergraph which satisfies that property "globally".
Ruzsa I. & Szemerédi E., “Triple systems with no six points carrying three triangles”, Colloq. Math. Soc. J. Bolyai 18
1978
Earlier work this paper cites.
Szemerédi E., “Regular partitions of graphs”, in “Problémes Combinatoires et Théorie des Graphes, Proc. Colloque Inter. CNRS,” (Bermond, Fournier, Las Vergnas, Sotteau, eds.), CNRS Paris, 1978, 399–401;
1978
Earlier work this paper cites.
D. Hoover, Relations on probability spaces and arrays of random variables , unpublished, 1979
1979
Earlier work this paper cites.
D. Aldous, Representations for partially exchangeable arrays of random variables , J. Multivariate Anal. 11
1981
Earlier work this paper cites.
D. Aldous, On exchangeability and conditional independence , Exchangeability in probability and statistics (Rome, 1981) 165–170, North-Holland, Amsterdam, 1982
1982
Earlier work this paper cites.
D. Hoover, Row-columns exchangeability and a generalized model for exchangeability , Exchangeability in probability and statistics (Rome, 1981), 281–291, North-Holland, Amsterdam, 1982
1982
Earlier work this paper cites.
D. Aldous, Exchangeability and related topics , École d’été de probabilités de Saint-Flour, XIII—1983, Lecture Notes in Math. 1117, 1–198, Springer, Berlin 1985
1985
Earlier work this paper cites.
Chung F., Graham R., Wilson R., “Quasi-random graphs”, Combinatorica 9
1989
Earlier work this paper cites.
Graham R.L., Rothschild B.L. & Spencer J.H., “Ramsey Theory”, John Wiley & Sons, New York, 1990;
1990
Cited alongside, same era.
Szemerédi E., “Integer sets containing no arithmetic progressions”, Acta Math. Hungar. 56
1990
Cited alongside, same era.
O. Kallenberg, Symmetries on random arrays and set-indexed processes , J. Theoret. Probab. 5
1992
Cited alongside, same era.
Rubinfeld R. & Sudan M., “Robust characterization of polynomials with applications to program testing”, SIAM Journal on Computing , 25
1996
Cited alongside, same era.
Goldreich O., Goldwasser S., & Ron D., “Property testing and its connection to learning and approximation”, Journal of the ACM , pages 653–750, July 1998;
1998
Cited alongside, same era.
Lovász L. & Szegedy B., “Limits of dense graph sequences”, Microsoft Corporation Technical Report TR-2004-79, 2004, available online at http://research.microsoft.com/users/lovasz/limits.pdf ;
2004
Later among the works it cites.
Rödl V. & Skokan J., “Regularity lemma for k k -uniform hypergraphs”, Random Struct. Algorithms 25
2004
Later among the works it cites.
Alon N. & Shapira A., “Every monotone graph property is testable”, Proc. of the 37 th 37^{\mathrm{th}} ACM STOC, Baltimore, ACM Press, 2005, available online at http://www.math.tau.ac.il/~nogaa/PDFS/MonotoneSTOC.pdf ;
2005
Later among the works it cites.
Lovász L. & Szegedy B., “Graphs limits and testing hereditary graph properties”, Microsoft Corporation Technical Report TR-2005-110, 2005, available online at http://research.microsoft.com/users/lovasz/heredit-test.pdf ;
2005
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Alon N., Fischer E., Krivelevich M. & Szegedy M., “Efficient testing of large graphs”, Combinatorica 𝟐𝟎 \mathbf{20} (4) (2000), 451 – 476;
2000
Cited alongside, same era.
Katz J., & Trevisan L., “On the efficiency of local decoding procedures for error-correcting codes”, in Proc. of 32nd STOC, pages 80–86, ACM, 2000;
2000
Cited alongside, same era.
Kohayakawa Y., Nagle B. & Rödl V., “Efficient Testing of Hypergraphs”, extended abstract in Proceedings of the 29th International Colloquium on Automata, Languages and Programming , Springer-Verlag, London, 2002;
2002
Cited alongside, same era.
Alon N. & Shapira A., “A Characterization of the (natural) Graph Properties Testable with One-Sided Error”, preprint, available online at http://www.math.tau.ac.il/~nogaa/PDFS/heredit2.pdf ;
Cited in the paper.
Austin T., “On exchangeable random variables and the statistics of large graphs and hypergraphs”, preprint, available online at arXiv.org : 0801.1698;
Cited in the paper.
Borgs C., Chayes J., Lovasz L., Sos V., Veztergombi K., “Convergent sequences of dense graphs I: subgraph frequencies, metric properties, and testing”, preprint, available at arXiv.org :math/0702004;
Cited in the paper.
Elek G. & Szegedy B., “Limits of Hypergraphs, Removal and Regularity Lemmas. A Non-standard approach”, preprint, available at arXiv.org :0705.2179;
Cited in the paper.
Goldreich O. & Sudan M., “Locally testable codes and PCPs of almost-linear length”, Journal of the ACM 53
2006
Later among the works it cites.
Rödl V. & Skokan J., “Applications of the regularity lemma for uniform hypergraphs”, Random Struct. Algorithms 28
2006
Later among the works it cites.
Avart C., Rödl V., Schacht M., “Every monotone 3-graph property is testable”, SIAM J. Discrete Math. 21
2007
Later among the works it cites.