Testing linear inequalities of subgraph statistics. Issue 3 (2nd December 2020)

• Record Type: Journal Article
• Authors: Gishboliner, Lior; Shapira, Asaf; Stagni, Henrique
• Is Part Of: Random structures & algorithms. Volume 58:Issue 3(2021)
• Page Start: 468
• Page End: 479
• Publication Date: 2020-12-02
• Subjects: graph property testing -- subgraph density; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20983
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : Property testers are fast randomized algorithms whose task is to distinguish between inputs satisfying some predetermined property 𝒫 and those that are far from satisfying it. A landmark result of Alon et al. states that for any finite family of graphs ℱ, the property of being induced ℱ ‐free (i.e., not containing an induced copy of any F ∈ ℱ ) is testable. Goldreich and Shinkar conjectured that one can extend this by showing that for any linear inequality involving the densities of the graphs F ∈ ℱ in the input graph, the property of satisfying this inequality is testable. Our main result in this paper disproves this conjecture. The proof deviates significantly from prior nontestability results in this area. The main idea is to use a linear inequality relating induced subgraph densities in order to encode the property of being a quasirandom graph.