一句话：证明 nowhere dense 图类中一阶可定义集合系统的 VC 密度上界为 O(|A|^{|x|ε})，并给出准宽与稳定性的构造性新证。
论文研究 nowhere dense（无处稠密）图类中一阶逻辑定义集合系统的类型数量与 VC 密度。作者证明：对任意 nowhere dense 图类 ℒ 和一阶公式 φ(x,y)，从 G∈ℒ 及节点子集 A 出发，由 φ 在 G 中以 x 的赋值参数化得到的 A^{|y|} 子集数量对任意 ε>0 都受 O(|A|^{|x|ε}) 控制，从而给出该图类中一阶可定义集合系统 VC 密度的最优界。此外，文章给出两个新证明：一是 nowhere dense 图类一致准宽（uniformly quasi-wide）并有显式多项式上界；二是用组合方法重新证明 Adler 与 Adler 的稳定性结果，且证明完全有穷、构造性，给出 margins 和 ladder indices 的显式可计算上界。
We prove that for every class of graphs ℒ which is nowhere dense, as defined by Nešetřil and Ossona de Mendez [28, 29], and for every first order formula φ(x, y), whenever one draws a graph G ∈ ℒ and a subset of its nodes A, the number of subsets of A|y| which are of the form {u ∈ A|y|: G |= φ(ū, v)} for some valuation ū of x in G is bounded by O(|A||x|ε), for every ε > 0. This provides optimal bounds on the VC-density of first-order definable set systems in nowhere dense graph classes. We also give two new proofs of upper bounds on quantities in nowhere dense classes which are relevant for their logical treatment. Firstly, we provide a new proof of the fact that nowhere dense classes are uniformly quasi-wide, implying explicit, polynomial upper bounds on the functions relating the two notions. Secondly, we give a new combinatorial proof of the result of Adler and Adler [1] stating that every nowhere dense class of graphs is stable. In contrast to the previous proofs of the above results, our proofs are completely finitistic and constructive, and yield explicit and computable upper bounds on quantities related to uniform quasi-wideness (margins) and stability (ladder indices).
DOI 原文 ·
@inproceedings{paperbot4348,
title = {On the number of types in sparse graphs},
author = {Michał Pilipczuk and Sebastian Siebertz and Szymon Toruńczyk},
booktitle = {LICS},
year = {2018},
doi = {10.1145/3209108.3209178}
}