UCLA

Aschenbrenner et al. have studied Vapnik-Chervonenkis density (VC-density) in the model-theoretic context. We investigate it further by computing it in some common structures: trees, Shelah-Spencer graphs, and an additive reduct of the field of p-adic numbers. In the theory of infinite trees we establish an optimal bound on the VC-density function. This generalizes a result of Simon showing that trees are dp-minimal. In Shelah-Spencer graphs we provide an upper bound on a formula-by-formula basis and show that there isn't a uniform lower bound, forcing the VC-density function to be infinite. In addition we show that Shelah-Spencer graphs do not have a finite dp-rank, so they are not dp-minimal. There is a linear bound for the VC-density function in the field of p-adic numbers, but it is not known to be optimal. We investigate a certain P-minimal additive reduct of the field of p-adic numbers and use a cell decomposition result of Leenknegt to compute an optimal bound for that structure. Finally, following the results of Podewski and Ziegler we show that superflat graphs are dp-minimal.