A Dense Neighborhood Lemma: Applications of Partial Concept Classes to Domination and Chromatic Number
Romain Bourneuf, Pierre Charbit, Stéphan Thomassé
Abstract
In its Euclidean form, the Dense Neighborhood Lemma (DNL) asserts that if V is a finite set of points of such that for each the ball intersects V on at least points, then for every , the points of V can be covered with balls with . 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 , 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 -regular -free graphs have bounded chromatic number. Similarly, triangle-free graphs with minimum degree have bounded chromatic number (this does not hold with ). For tournaments, DNL implies that the domination number is bounded in terms of the fractional chromatic number. Also, -majority digraphs have bounded domination, independently of the number of voters.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
2 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- A Few Good Choices cites Six Candidates Suffice to Win a Voter Majority
- A Few Good Choices cites Approximately Dominating Sets in Elections
- Approximately Dominating Sets in Elections cites A Few Good Choices
- Approximately Dominating Sets in Elections cites Six Candidates Suffice to Win a Voter Majority
Cited by top-tier papers2
Builds on4
- Twin-width I: tractable FO model checkingÉdouard Bonnet, Eun Jung Kim, Stéphan Thomassé, Rémi WatrigantFOCS 2020 · 82 citations
- A Theory of PAC Learnability of Partial Concept ClassesNoga Alon, Steve Hanneke, Ron Holzman, Shay MoranFOCS 2021 · 11 citations
- Six Candidates Suffice to Win a Voter MajorityMoses Charikar, Alexandra Lassota, Prasanna Ramakrishnan, Adrian Vetta et al.STOC 2025 · 1 citation
- Approximately Dominating Sets in ElectionsMoses Charikar, Prasanna Ramakrishnan, Kangning WangSODA 2026
Related papers
- Pattern-Sparse Tree Decompositions in H-Minor-Free GraphsDániel Marx, Marcin Pilipczuk, Michal PilipczukSTOC 2026
- Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimensionGuillaume Ducoffe, Michel Habib, Laurent ViennotSODA 2020 · 19 citations
- Online epsilon Net & Piercing Set for Geometric ConceptsSujoy Bhore, Devdan Dey, Satyam SinghICLR 2025
- Multi-transversals for Triangles and the Tuza's ConjectureParinya Chalermsook, Samir Khuller, Pattara Sukprasert, Sumedha UniyalSODA 2020 · 5 citations
- A Tolerant Independent Set TesterCameron SethSTOC 2025 · 1 citation
