Arrow Research search

Author name cluster

Romain Bourneuf

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers
2 author rows

Possible papers

5

FOCS Conference 2025 Conference Paper

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

  • Romain Bourneuf
  • Pierre Charbit
  • Stéphan Thomassé

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.

Details

MFCS Conference 2025 Conference Paper

Graphs with No Long Claws: An Improved Bound for the Analog of the Gyárfás' Path Argument

  • Romain Bourneuf
  • Jana Masaríková
  • Wojciech Nadara
  • Marcin Pilipczuk

For a fixed integer t ⩾ 1, a (t-)long claw, denoted S_{t, t, t}, is the unique tree with three leaves, each at distance exactly t from the vertex of degree three. Majewski et al. [ICALP 2022, ACM ToCT 2024] proved an analog of the Gyárfás' path argument for S_{t, t, t}-free graphs: given an n-vertex S_{t, t, t}-free graph, one can delete neighborhoods of 𝒪(log n) vertices so that the remainder admits an extended strip decomposition (an appropriate generalization of partition into connected components) into particles of multiplicatively smaller size. In this work, we refine the argument of Majewski et al. to its arguably final form: we show that a constant number of neighborhoods suffice. The statement of Majewski et al. is one of the two pillars of a recent quasi-polynomial time algorithm for Maximum Weight Independent Set in S_{t, t, t}-free graphs [Gartland et al. , STOC 2024]; our work immediately improves the quasi-polynomial function in the running time bound. Furthermore, our result significantly simplifies known polynomial-time algorithms for Maximum Weight Independent Set in S_{t, t, t}-free graphs with an additional sparsity assumption such as bounded degree or excluding a fixed biclique as a subgraph.

Details