2025/04/03 by Bourneuf, Romain, Charbit, Pierre, Thomassé, Stéphan · 6 citations
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2504.02992
In its Euclidean form, the Dense Neighborhood Lemma (DNL) asserts that if V is a finite set of points of ℝN such that for each v ∈ V the ball B(v,1) intersects V on at least δ|V| points, then for every ε >0, the points of V can be covered with f(δ,ε) balls B(v,1+ε) with v ∈ 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 ε-clustering with size exponential in ε-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 Vapnik-Cervonenkis 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 ((3t-8)/(3t-5)+ε)⋅ n-regular Kt-free graphs have bounded chromatic number. Similarly, triangle-free graphs with minimum degree n/3-n1-ε have bounded chromatic number (this does not hold with n/3-n1-o(1)). For tournaments, DNL implies that the domination number is bounded in terms of the fractional chromatic number. Also, (1/2-ε)-majority digraphs have bounded domination, independently of the number of voters.