Testing Linear Inequalities of Subgraph Statistics

Authors Lior Gishboliner, Asaf Shapira, Henrique Stagni



PDF
Thumbnail PDF

File

LIPIcs.ITCS.2020.43.pdf
  • Filesize: 431 kB
  • 9 pages

Document Identifiers

Author Details

Lior Gishboliner
  • School of Mathematical Sciences, Tel Aviv University, Tel Aviv, 69978, Israel
Asaf Shapira
  • School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel
Henrique Stagni
  • Departamento de Ciencia da Computacao, Instituto de Matematica e Estatistica, Universidade de Sao Paulo, Brazil

Cite AsGet BibTex

Lior Gishboliner, Asaf Shapira, and Henrique Stagni. Testing Linear Inequalities of Subgraph Statistics. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 43:1-43:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ITCS.2020.43

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. Since these algorithms operate by inspecting a small randomly selected portion of the input, the most natural property one would like to be able to test is whether the input does not contain certain forbidden small substructures. In the setting of graphs, such a result was obtained by Alon et al., who proved 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. It is natural to ask if one can go one step further and prove that more elaborate properties involving induced subgraphs are also testable. One such generalization of the result of Alon et al. was formulated by Goldreich and Shinkar who conjectured that for any finite family of graphs ℱ, and any linear inequality involving the densities of the graphs F ∈ ℱ in the input graph, the property of satisfying this inequality can be tested in a certain restricted model of graph property testing. Our main result in this paper disproves this conjecture in the following strong form: some properties of this type are not testable even in the classical (i.e. unrestricted) model of graph property testing. The proof deviates significantly from prior non-testability 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 pseudo-random graph.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Discrete mathematics
Keywords
  • graph property testing
  • subgraph statistics

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. N. Alon, E. Fischer, M. Krivelevich, and M. Szegedy. Efficient testing of large graphs. Combinatorica, 20:451-476, 2000. Google Scholar
  2. F.R.K Chung, R.L Graham, and R.M. Wilson. Quasi-random graphs. Combinatorica, 9:345-362, 1989. Google Scholar
  3. O. Goldreich. Introduction to Property Testing. Cambridge University Press, 2017. Google Scholar
  4. O. Goldreich, S. Goldwasser, and D. Ron. Property testing and its connection to learning and approximation. J. ACM, 45:653-750, 1998. Google Scholar
  5. O. Goldreich and D. Ron. On proximity oblivious testing. SIAM J. Comput, 40:534–566, 2011. Google Scholar
  6. O. Goldreich and I. Shinkar. Two-sided error proximity oblivious testing. Random Structures Algorithms, 48:341-383, 2016. Google Scholar
  7. O. Goldreich and L. Trevisan. Three theorems regarding testing graph properties. Random Structures Algorithms, 23:23-57, 2003. Google Scholar
  8. O. Goldreich and L. Trevisan. Errata to Three theorems regarding testing graph properties. available from http://www.wisdom.weizmann.ac.il/~oded/p_ttt.html, 2005.
  9. L. Lovász. Large networks and graph limits. Providence: American Mathematical Society, 2012. Google Scholar
  10. R. Rubinfeld and M. Sudan. Robust characterizations of polynomials with applications to program testing. SIAM J. Comput., 25:252-271, 1996. Google Scholar
  11. A. Sidorenko. A correlation inequality for bipartite graphs. Graphs and Combinatorics, 9:201-204, 1993. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail