Testing properties of graphs and functions

2008/03/08 by Lovasz, Laszlo, Szegedy, Balazs · 3 citations
#05C99 #68Q99 #Combinatorics (math.CO) #FOS: Mathematics #Functional Analysis (math.FA)

paper · doi:10.48550/arxiv.0803.1248

Abstract

We define an analytic version of the graph property testing problem, which can be formulated as studying an unknown 2-variable symmetric function through sampling from its domain and studying the random graph obtained when using the function values as edge probabilities. We give a characterization of properties testable this way, and extend a number of results about ``large graphs'' to this setting. These results can be applied to the original graph-theoretic property testing.

Cited by

• Banach-valued graph limits: Graphon representability and Banach-space structure
• Using dense graph limit theory to count cocycles of random simplicial complexes
• Minor-excluded graphs and soficity

Related

• Testing Graphs against an Unknown Distribution
• Contemplations on Testing Graph Properties
• Deterministic vs Non-deterministic Graph Property Testing
• Practical methods for graph two-sample testing
• Testing linear inequalities of subgraph statistics