Testing properties of graphs and functions

DOI10.1007/S11856-010-0060-7MaRDI QIDQ607829zbMATH OpenOpenAlexWikidataFDO

Authors Balázs Szegedy, László Lovász

Publication date 6 December 2010

Published in Israel Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0803.1248

zbMATH Keywords

Graph property testingtestable graph property

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

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.

Recommendations

• Property testing and its connection to learning and approximation
• scientific article; zbMATH DE number 1241385
• Efficient testing of large graphs
• A characterization of constant-sample testable properties
• Algorithmic and analysis techniques in property testing

Cites work

• A combinatorial characterization of the testable graph properties, it's all about regularity
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Counting graph homomorphisms
• Graph limits and parameter testing
• Limits of dense graph sequences
• Property testing and its connection to learning and approximation
• Szemerédi's lemma for the analyst
• Testing versus estimation of graph properties
• What is the furthest graph from a hereditary property?

Cited in

(37)

• Earthmover Resilience and Testing in Ordered Structures
• Quasi-random words and limits of word sequences
• Sparse halves in dense triangle-free graphs
• Finitely forcible graph limits are universal
• Limits of kernel operators and the spectral regularity lemma
• From quasirandom graphs to graph limits and graphlets
• Estimating and understanding exponential random graph models
• On a question of Vera T. Sós about size forcing of graphons
• The cut metric for probability distributions
• Limits of multi-relational graphs
• Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Graphon convergence of random cographs
• Testing permutation properties through subpermutations
• Property testing. A learning theory perspective
• A characterization of constant-sample testable properties
• Tilings in graphons
• Testing piecewise functions
• A canonical form for testing Boolean function properties
• Cut-norm and entropy minimization over \(\text{weak}^{\ast}\) limits
• Finitely forcible graphons with an almost arbitrary structure
• Testing 2-asummability using a property of canonical extremal vertices
• Differential calculus on graphon space
• Contemplations on Testing Graph Properties
• First order convergence of matroids
• First order limits of sparse graphs: plane trees and path-width
• Compactness and finite forcibility of graphons
• Minimizing the number of 5-cycles in graphs with given edge-density
• On derivatives of graphon parameters
• Non-deterministic graph property testing
• Very large graphs
• Densities in large permutations and parameter testing
• Weak regularity and finitely forcible graph limits
• First-Order Convergence and Roots
• Finitely forcible graphons and permutons
• Deterministic vs non-deterministic graph property testing
• Graph limits and parameter testing

This page was built for publication: Testing properties of graphs and functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q607829)