The main problem in the area of property testing is to understand which graph properties are \emph{testable}, which means that with constantly many queries to any input graph $G$, a tester can decide with good probability whether $G$ satisfies the property, or is far from satisfying the property. Testable properties are well understood in the dense model and in the bounded degree model, but little is known in sparse graph classes when graphs are allowed to have unbounded degree. This is the setting of the \emph{sparse model}. We prove that for any proper minor-closed class $\mathcal{G}$, any monotone property (i.e., any property that is closed under taking subgraphs) is testable for graphs from $\mathcal{G}$ in the sparse model. This extends a result of Czumaj and Sohler (FOCS'19), who proved it for monotone properties with finitely many obstructions. Our result implies for instance that for any integers $k$ and $t$, $k$-colorability of $K_t$-minor free graphs is testable in the sparse model. Elek recently proved that monotone properties of bounded degree graphs from minor-closed classes that are closed under disjoint union can be verified by an approximate proof labeling scheme in constant time. We show again that the assumption of bounded degree can be omitted in his result.
翻译:属性测试领域的主要问题是了解哪些图形属性为 emph{ 测试}, 这意味着,如果对任何输入图形不断进行多次查询, 测试者可以非常概率地决定$G$是否满足属性, 或者远远不能满足属性。 测试属性在密度模型和约束度模型中是完全理解的, 但当图形允许不受限制程度时, 稀薄的图形类别中却鲜为人知。 这是设置 emph{ 偏差模型 。 我们证明, 对于任何适当的小封闭类$\ mathcal{ G} 美元, 任何单调属性( 即使用子图表中关闭的任何属性) 都可以对来自 $\ macal{ G} 或稀薄模型中的图表进行测试。 这延伸了Czumaj 和 Sohler (FOCS'19) 的结果, 后者以有限的阻力证明了单调性属性。 我们的结果表明, 对于任何小不关闭类的 $k美元和 $t$@G}, 任何单调的属性(即使用在子下关闭的基数度的平面的平面的平面的平面图, 的平面的平面的平面的平面图的平面的平质的平质的平质的平面的平质的平质的平质的平质的平面的平质的平。