54 citations · 245 across the 46 of their papers we have counts for
50 papers
Ample sets in Cartesian products
Victor Chepoi, Matthew Maat
Ample sets of hypercubes, introduced by A. Dress in 1995, constitute a combinatorial structure with rich properties and important examples. Ample sets can be characterized in a mul…
Geometry of ample/lopsided sets
Hans--Jürgen Bandelt, Victor Chepoi, Andreas Dress +1
Lopsided sets were introduced by Jim Lawrence in 1983 when he studied the subsets of that encode the intersection pattern of a convex set with the orthants of ${\…
Cell structure of mediangle graphs
Victor Chepoi, Anthony Genevois, Kolja Knauer
Mediangle graphs are a common generalization of median graphs (1-sekeleta of CAT(0) cube complexes) and Coxeter graphs (Cayley graphs of Coxeter systems). Answering a question moti…
Separation axiom for geodesic convexity in graphs
Victor Chepoi
Semispaces of a convexity space are maximal convex sets missing a point. The separation axiom asserts that any point and any convex set not containing…
Geometry of convex geometries
Jérémie Chalopin, Victor Chepoi, Kolja Knauer
We prove that any convex geometry on points and any ideal of can be realized as the intersection pat…
Boundary rigidity of finite CAT(0) cube complexes
Jérémie Chalopin, Victor Chepoi
In this note, we prove that finite CAT(0) cube complexes can be reconstructed from their boundary distances (computed in their 1-skeleta). This result was conjectured by Haslegrave…
Non-Clashing Teaching Maps for Balls in Graphs
Jérémie Chalopin, Victor Chepoi, Fionn Mc Inerney +1
Recently, Kirkpatrick et al. [ALT 2019] and Fallat et al. [JMLR 2023] introduced non-clashing teaching and showed it is the most efficient machine teaching model satisfying the Gol…
Modules and PQ-trees in Robinson spaces
Mikhael Carmona, Victor Chepoi, Guyslain Naves +1
A Robinson space is a dissimilarity space on points for which there exists a compatible order, {\it i.e.} a total order on such that implies that $d(x,y…
Sample compression schemes for balls in graphs
Jérémie Chalopin, Victor Chepoi, Fionn Mc Inerney +2
One of the open problems in machine learning is whether any set-family of VC-dimension admits a sample compression scheme of size . In this paper, we study this problem f…
ABC(T)-graphs: an axiomatic characterization of the median procedure in graphs with connected and G-connected medians
Laurine Bénéteau, Jérémie Chalopin, Victor Chepoi +1
The median function is a location/consensus function that maps any profile (a finite multiset of vertices) to the set of vertices that minimize the distance sum to vertices fro…
A simple and optimal algorithm for strict circular seriation
Mikhael Carmona, Victor Chepoi, Guyslain Naves +1
Recently, Armstrong, Guzmán, and Sing Long (2021), presented an optimal time algorithm for strict circular seriation (called also the recognition of strict quasi-circular…
First-order logic axiomatization of metric graph theory
Jérémie Chalopin, Manoj Changat, Victor Chepoi +1
The main goal of this note is to provide a First-Order Logic with Betweenness (FOLB) axiomatization of the main classes of graphs occurring in Metric Graph Theory, in analogy to Ta…
Modules in Robinson Spaces
Mikhael Carmona, Victor Chepoi, Guyslain Naves +1
A Robinson space is a dissimilarity space (i.e., a set of size and a dissimilarity on ) for which there exists a total order on such that imp…
Graphs with -connected medians
Laurine Bénéteau, Jérémie Chalopin, Victor Chepoi +1
The median of a graph with weighted vertices is the set of all vertices minimizing the sum of weighted distances from to the vertices of . For any integer ,…
Graphs with convex balls
Jérémie Chalopin, Victor Chepoi, Ugo Giocanti
In this paper, we investigate the graphs in which all balls are convex and the groups acting on them geometrically (which we call CB-graphs and CB-groups). These graphs have been i…
Labeled sample compression schemes for complexes of oriented matroids
Victor Chepoi, Kolja Knauer, Manon Philibert
We show that the topes of a complex of oriented matroids (abbreviated COM) of VC-dimension admit a proper labeled sample compression scheme of size . This considerably exten…
Distance labeling schemes for -free bridged graphs
Victor Chepoi, Arnaud Labourel, Sébastien Ratel
-Approximate distance labeling schemes are schemes that label the vertices of a graph with short labels in such a way that the -approximation of the distance between any two…
Ample completions of OMs and CUOMs
Victor Chepoi, Kolja Knauer, Manon Philibert
This paper considers completions of COMs (complexes oriented matroids) to ample partial cubes of the same VC-dimension. We show that these exist for OMs (oriented matroids) and CUO…
Helly groups
Jérémie Chalopin, Victor Chepoi, Anthony Genevois +2
Helly graphs are graphs in which every family of pairwise intersecting balls has a non-empty intersection. This is a classical and widely studied class of graphs. In this article w…
Medians in median graphs and their cube complexes in linear time
Laurine Bénéteau, Jérémie Chalopin, Victor Chepoi +1
The median of a set of vertices of a graph is the set of all vertices of minimizing the sum of distances from to all vertices of . In this paper, we present…
Two-dimensional partial cubes
Victor Chepoi, Kolja Knauer, Manon Philibert
We investigate the structure of two-dimensional partial cubes, i.e., of isometric subgraphs of hypercubes whose vertex set defines a set family of VC-dimension at most 2. Equivalen…
Unlabeled sample compression schemes and corner peelings for ample and maximum classes
Jérémie Chalopin, Victor Chepoi, Shay Moran +1
We examine connections between combinatorial notions that arise in machine learning and topological notions in cubical/simplicial geometry. These connections enable to export resul…
1-Safe Petri nets and special cube complexes: equivalence and applications
Jérémie Chalopin, Victor Chepoi
Nielsen, Plotkin, and Winskel (1981) proved that every 1-safe Petri net unfolds into an event structure . By a result of Thiagarajan (1996 and 2002), these unfol…
Distance and routing labeling schemes for cube-free median graphs
Victor Chepoi, Arnaud Labourel, Sebastien Ratel
Distance labeling schemes are schemes that label the vertices of a graph with short labels in such a way that the distance between any two vertices and can be determined ef…