论文标题
次要类别中单调特性的可检验性和本地认证
Testability and local certification of monotone properties in minor-closed classes
论文作者
论文摘要
Graph属性测试区域中的主要问题是了解哪些图形属性为\ Emph {可测试}，这意味着，对于任何输入图$ G $的疑问，测试人员可以不断地进行许多查询，可以很好地决定$ G $是否满足该属性，还是远离满足该属性的范围。在密集的模型和界度模型中，可检验的特性得到充分了解，但是当允许图形具有无限度时，在稀疏图类中几乎不知道。这是\ emph {稀疏模型}的设置。 我们证明，对于任何适当的次要类$ \ MATHCAL {G} $，任何单调属性（即，在取下子图下关闭的任何属性）均可在稀疏模型中从$ \ MATHCAL {G} $中进行测试。这扩展了Czumaj和Sohler（Focs'19）的结果，后者证明了这是有限的许多禁止子图的单调性能。例如，我们的结果意味着，对于任何整数$ k $和$ t $，$ k $ - $ k_t $ - minor-minor免费图的可溶性在稀疏型号中都是可测试的。 Elek最近证明，在恒定时间内近似证明标签方案可以验证来自次要类别的次封闭类的有界度图的单调性能。我们再次证明，在他的结果中可以省略有限程度的假设。
The main problem in the area of graph 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 forbidden subgraphs. 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.
