A Dense Neighborhood Lemma: Applications of Partial Concept Classes to Domination and Chromatic Number

In its Euclidean form, the Dense Neighborhood Lemma (DNL) asserts that if V is a finite set of points of $\mathbb{R}^{N}$ such that for each $v \in V$ the ball $B(v, 1)$ intersects V on at least $\delta|V|$ points, then for every $\varepsilon\gt0$, the points of V can be covered with $f(\delta, \varepsilon)$ balls $B(v, 1+\varepsilon)$ with $v \in V$. DNL also applies to other metric spaces and to abstract set systems, where elements are compared pairwise with respect to (near) disjointness. In its strongest form, DNL provides an $\varepsilon$-clustering with size exponential in $\varepsilon^{-1}$, which amounts to a Regularity Lemma with 0/1 densities of some trigraph. Trigraphs are graphs with additional red edges. They are natural instances of partial concept classes, introduced by Alon, Hanneke, Holzman and Moran [FOCS 2021]. This paper is mainly a combinatorial study of the generalization of VapnikCervonenkis dimension to partial concept classes. The main point is to show how trigraphs can sometimes explain the success of random sampling even though the VC-dimension of the underlying graph is unbounded. All the results presented here are effective in the sense of computation: they primarily rely on uniform sampling with the same success rate as in classical VC-dimension theory. Among some applications of DNL, we show that $\left(\frac{3 t-8}{3 t-5}+\varepsilon\right) \cdot n$-regular $K_{t}$-free graphs have bounded chromatic number. Similarly, triangle-free graphs with minimum degree $n / 3-n^{1-\varepsilon}$ have bounded chromatic number (this does not hold with $n / 3-n^{1-o(1)}$). For tournaments, DNL implies that the domination number is bounded in terms of the fractional chromatic number. Also, $(1 / 2-\varepsilon)$-majority digraphs have bounded domination, independently of the number of voters.