Testing linear inequalities of subgraph statistics

DOI10.1002/rsa.20983zbMath1522.68740OpenAlexW3110274972MaRDI QIDQ6049999

Asaf Shapira, Lior Gishboliner, Henrique Stagni

Publication date: 11 October 2023

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2020/11728/

zbMATH Keywords

subgraph densitygraph property testing

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Density (toughness, etc.) (05C42)

Related Items (1)

Local-vs-global combinatorics

Cites Work

• Unnamed Item
• Unnamed Item
• Two-sided error proximity oblivious testing
• On Proximity-Oblivious Testing
• Property testing and its connection to learning and approximation
• Three theorems regarding testing graph properties
• Testing subgraphs in large graphs
• Robust Characterizations of Polynomials with Applications to Program Testing
• Introduction to Property Testing
• On a problem of K. Zarankiewicz
• Quasi-random graphs
• Efficient testing of large graphs

This page was built for publication: Testing linear inequalities of subgraph statistics