Testing linear inequalities of subgraph statistics

DOI10.1002/RSA.20983MaRDI QIDQ6049999zbMATH OpenOpenAlexFDO

Authors Lior Gishboliner, Asaf Shapira, 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 algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Density (toughness, etc.) (05C42)

Recommendations

• scientific article; zbMATH DE number 6469238
• Testing linear-invariant non-linear properties
• Efficient testing of large graphs
• Easily testable graph properties
• Testing linear-invariant non-linear properties

Cites work

• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Efficient testing of large graphs
• Introduction to Property Testing
• Large networks and graph limits
• On Proximity-Oblivious Testing
• On a problem of K. Zarankiewicz
• Property testing and its connection to learning and approximation
• Quasi-random graphs
• Robust Characterizations of Polynomials with Applications to Program Testing
• Testing subgraphs in large graphs
• Three theorems regarding testing graph properties
• Two-sided error proximity oblivious testing

Cited in

(1)

• Local-vs-global combinatorics

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

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