Lune

FOCS2025Top-tier venue

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 RN\mathbb{R}^{N} such that for each v∈Vv \in V the ball B(v,1)B(v, 1) intersects V on at least δ∣V∣\delta|V| points, then for every ε>0\varepsilon\gt0, the points of V can be covered with f(δ,ε)f(\delta, \varepsilon) balls B(v,1+ε)B(v, 1+\varepsilon) with v∈Vv \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 ε−1\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 (3t−83t−5+ε)⋅n\left(\frac{3 t-8}{3 t-5}+\varepsilon\right) \cdot n-regular KtK_{t}-free graphs have bounded chromatic number. Similarly, triangle-free graphs with minimum degree n/3−n1−εn / 3-n^{1-\varepsilon} have bounded chromatic number (this does not hold with n/3−n1−o(1)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−ε)(1 / 2-\varepsilon)-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.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

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
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers2

  1. A Few Good ChoicesHaoyu Song, Thành Nguyen, Young-San LinSODA 2026
  2. Approximately Dominating Sets in ElectionsMoses Charikar, Prasanna Ramakrishnan, Kangning WangSODA 2026

Builds on4

  1. Twin-width I: tractable FO model checkingÉdouard Bonnet, Eun Jung Kim, Stéphan Thomassé, Rémi WatrigantFOCS 2020 · 82 citations
  2. A Theory of PAC Learnability of Partial Concept ClassesNoga Alon, Steve Hanneke, Ron Holzman, Shay MoranFOCS 2021 · 11 citations
  3. Six Candidates Suffice to Win a Voter MajorityMoses Charikar, Alexandra Lassota, Prasanna Ramakrishnan, Adrian Vetta et al.STOC 2025 · 1 citation
  4. Approximately Dominating Sets in ElectionsMoses Charikar, Prasanna Ramakrishnan, Kangning WangSODA 2026

Related papers

  1. Pattern-Sparse Tree Decompositions in H-Minor-Free GraphsDániel Marx, Marcin Pilipczuk, Michal PilipczukSTOC 2026
  2. Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimensionGuillaume Ducoffe, Michel Habib, Laurent ViennotSODA 2020 · 19 citations
  3. Online epsilon Net & Piercing Set for Geometric ConceptsSujoy Bhore, Devdan Dey, Satyam SinghICLR 2025
  4. Multi-transversals for Triangles and the Tuza's ConjectureParinya Chalermsook, Samir Khuller, Pattara Sukprasert, Sumedha UniyalSODA 2020 · 5 citations
  5. A Tolerant Independent Set TesterCameron SethSTOC 2025 · 1 citation
Dusk over the sea between two cliffs drawn in fine vertical lines