Premium
Testing linear inequalities of subgraph statistics
Author(s) -
Gishboliner Lior,
Shapira Asaf,
Stagni Henrique
Publication year - 2021
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20983
Subject(s) - conjecture , mathematics , property (philosophy) , combinatorics , inequality , graph , linear inequality , induced subgraph , discrete mathematics , vertex (graph theory) , mathematical analysis , philosophy , epistemology
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.