Search

For any set system $H=(V,R), \ R \subseteq 2^V$, a subset $S \subseteq V$ is called \emph{shattered} if every $S' \subseteq S$ results from the intersection of $S$ with some set in $\R$. The \emph{VC-dimension} of $H$ is the size of a largest shattered set in $V$. In this paper, we focus on the problem of computing the VC-dimension of graphs. In particular, given a graph $G=(V,E)$, the VC-dimension of $G$ is defined as the VC-dimension of $(V, \mathcal N)$, where $\mathcal N$ contains each subset of $V$ that can be obtained as the closed neighborhood of some vertex $v \in V$ in $G$. Our main contribution is an algorithm for computing the VC-dimension of any graph, whose effectiveness is shown through experiments on various types of practical graphs, including graphs with millions of vertices. A key aspect of its efficiency resides in the fact that practical graphs have small VC-dimension, up to 8 in our experiments. As a side-product, we present several new bounds relating the graph VC-dimension to other classical graph theoretical notions. We also establish the $W[1]$-hardness of the graph VC-dimension problem by extending a previous result for arbitrary set systems.

Locally harmonic manifolds are Riemannian manifolds in which small geodesic spheres are isoparametric hypersurfaces, i.e., hypersurfaces whose nearby parallel hypersurfaces are of constant mean curvature. Flat and rank one symmetric spaces are examples of harmonic manifolds. Damek-Ricci spaces are non-compact harmonic manifolds, most of which are non-symmetric. Taking the limit of an "inflating" sphere through a point $p$ in a Damek-Ricci space as the center of the sphere runs out to infinity along a geodesic half-line $\gamma$ starting from $p$, we get a horosphere. Similarly to spheres, horospheres are also isoparametric hypersurfaces. In this paper, we define the sphere-like hypersurfaces obtained by "overinflating the horospheres" by pushing the center of the sphere beyond the point at infinity of $\gamma$ along a virtual prolongation of $\gamma$. They give a new family of isoparametric hypersurfaces in Damek-Ricci spaces connecting geodesic spheres to some of the isoparametric hypersurfaces constructed by J. C. D\'iaz-Ramos and M. Dom\'inguez-V\'azquez [arXiv:1111.0264] in Damek-Ricci spaces. We study the geometric properties of these isoparametric hypersurfaces, in particular their homogeneity and the totally geodesic condition for their focal varieties., Comment: 20 pages

In this paper, we study temporal graphs arising from mobility models, where vertices correspond to agents moving in space and edges appear each time two agents meet. We propose a rather natural one-dimensional model. If each pair of agents meets exactly once, we get a simple temporal clique where the edges are ordered according to meeting times. In order to characterize which temporal cliques can be obtained as such `mobility graphs', we introduce the notion of forbidden patterns in temporal graphs. Furthermore, using a classical result in combinatorics, we count the number of such mobility cliques for a given number of agents, and show that not every temporal clique resulting from the 1D model can be realized with agents moving with different constant speeds. For the analogous circular problem, where agents are moving along a circle, we provide a characterization via circular forbidden patterns. Our characterization in terms of forbidden patterns can be extended to the case where each edge appears at most once. We also study the problem where pairs of agents are allowed to cross each other several times, using an approach from automata theory. We observe that in this case, there is no finite set of forbidden patterns that characterize such temporal graphs and nevertheless give a linear-time algorithm to recognize temporal graphs arising from this model.

The set $\mathcal S(G)$ of compact subgroups of a Hausdorff topological group $G$ can be equipped with the Vietoris topology. A compact subgroup $K\in\mathcal S(G)$ is isolated up to conjugacy if there is a neighborhood $\mathcal U\subseteq\mathcal S(G)$ of $K$ such that every $L\in\mathcal U$ is conjugate to $K$. In this paper, we characterize compact subgroups of a Lie group that are isolated up to conjugacy. Our characterization depends only on the intrinsic structure of $K$, the ambient Lie group $G$ and the embedding of $K$ into $G$ are irrelevant. In addition, we prove that any continuous homomorphism from a compact group $G$ onto a compact Lie group $H$ induces a continuous open map from $\mathcal S(G)$ onto $\mathcal S(H)$.

We study one of the key tools in data approximation and optimization: low-discrepancy colorings. Formally, given a finite set system $(X,\mathcal S)$, the \emph{discrepancy} of a two-coloring $\chi:X\to\{-1,1\}$ is defined as $\max_{S \in \mathcal S}|{\chi(S)}|$, where $\chi(S)=\sum\limits_{x \in S}\chi(x)$. We propose a randomized algorithm which, for any $d>0$ and $(X,\mathcal S)$ with dual shatter function $\pi^*(k)=O(k^d)$, returns a coloring with expected discrepancy $O\left({\sqrt{|X|^{1-1/d}\log|\mathcal S|}}\right)$ (this bound is tight) in time $\tilde O\left({|\mathcal S|\cdot|X|^{1/d}+|X|^{2+1/d}}\right)$, improving upon the previous-best time of $O\left(|\mathcal S|\cdot|X|^3\right)$ by at least a factor of $|X|^{2-1/d}$ when $|\mathcal S|\geq|X|$. This setup includes many geometric classes, families of bounded dual VC-dimension, and others. As an immediate consequence, we obtain an improved algorithm to construct $\varepsilon$-approximations of sub-quadratic size. Our method uses primal-dual reweighing with an improved analysis of randomly updated weights and exploits the structural properties of the set system via matchings with low crossing number -- a fundamental structure in computational geometry. In particular, we get the same $|X|^{2-1/d}$ factor speed-up on the construction time of matchings with crossing number $O\left({|X|^{1-1/d}}\right)$, which is the first improvement since the 1980s. The proposed algorithms are very simple, which makes it possible, for the first time, to compute colorings with near-optimal discrepancies and near-optimal sized approximations for abstract and geometric set systems in dimensions higher than $2$.

Given a triangle $\Delta$, we study the problem of determining the smallest enclosing and largest embedded isosceles triangles of $\Delta$ with respect to area and perimeter. This problem was initially posed by Nandakumar and was first studied by Kiss, Pach, and Somlai, who showed that if $\Delta'$ is the smallest area isosceles triangle containing $\Delta$, then $\Delta'$ and $\Delta$ share a side and an angle. In the present paper, we prove that for any triangle $\Delta$, every maximum area isosceles triangle embedded in $\Delta$ and every maximum perimeter isosceles triangle embedded in $\Delta$ shares a side and an angle with $\Delta$. Somewhat surprisingly, the case of minimum perimeter enclosing triangles is different: there are infinite families of triangles $\Delta$ whose minimum perimeter isosceles containers do not share a side and an angle with $\Delta$.

Around twenty years ago Ghys conjectured that finite subgroups of the diffeomorphism group of a compact smooth manifold M have an abelian normal subgroup of index at most a(M), where a(M) depends only on M. First we construct a family of counterexamples to this conjecture including, for example, the product space $T^2\times S^2$. Following the first appearance of our counterexample on the arXiv Ghys put forward a revised conjecture, which predicts only the existence of a nilpotent normal subgroup of index at most n(M). Our main result is the proof of the revised Ghys conjecture. More generally, we show that the same result holds for homeomorphism groups of not necessarily compact topological manifolds with finitely generated homology groups. Our proofs are based on finite group theoretic results which provide a general strategy for proving similar Jordan-type theorems.

If a finite p-group G acts continuously on a compact topological manifold M then, with some bound C depending on M alone, G has a subgroup H of index at most C such that the H-action on M has at most C stabilizer subgroups. This result plays a crucial role in the proof of a deep conjecture of Ghys.

B. Csik\'os and M. Horv\'ath proved that if a connected Riemannian manifold of dimension at least $4$ is harmonic, then the total scalar curvatures of tubes of small radius about a regular curve depend only on the length of the curve and the radius of the tube, and conversely, if the latter condition holds for cylinders, i.e., for tubes about geodesic segments, then the manifold is harmonic. In the present paper, we show that in contrast to the higher dimensional case, a connected 3-dimensional Riemannian manifold has the above mentioned property of tubes if and only if the manifold is a D'Atri space, furthermore, if the space has bounded sectional curvature, then it is enough to require the total scalar curvature condition just for cylinders to imply that the space is D'Atri. This result gives a negative answer to a question posed by L. Gheysens and L. Vanhecke. To prove these statements, we give a characterization of D'Atri spaces in terms of the total scalar curvature of geodesic hemispheres in any dimension.

The fundamental result of Li, Long, and Srinivasan on approximations of set systems has become a key tool across several communities such as learning theory, algorithms, computational geometry, combinatorics and data analysis. The goal of this paper is to give a modular, self-contained, intuitive proof of this result for finite set systems. The only ingredient we assume is the standard Chernoff's concentration bound. This makes the proof accessible to a wider audience, readers not familiar with techniques from statistical learning theory, and makes it possible to be covered in a single self-contained lecture in a geometry, algorithms or combinatorics course.

The VC-dimension of a set system is a way to capture its complexity and has been a key parameter studied extensively in machine learning and geometry communities. In this paper, we resolve two longstanding open problems on bounding the VC-dimension of two fundamental set systems: $k$-fold unions/intersections of half-spaces, and the simplices set system. Among other implications, it settles an open question in machine learning that was first studied in the 1989 foundational paper of Blumer, Ehrenfeucht, Haussler and Warmuth as well as by Eisenstat and Angluin and Johnson.

A graph $G$ is $H$-saturated for a graph $H$, if $G$ does not contain a copy of $H$ but adding any new edge to $G$ results in such a copy. An $H$-saturated graph on a given number of vertices always exists and the properties of such graphs, for example their highest density, have been studied intensively. A graph $G$ is $H$-induced-saturated if $G$ does not have an induced subgraph isomorphic to $H$, but adding an edge to $G$ from its complement or deleting an edge from $G$ results in an induced copy of $H$. It is not immediate anymore that $H$-induced-saturated graphs exist. In fact, Martin and Smith (2012) showed that there is no $P_4$-induced-saturated graph. Behrens et.al. (2016) proved that if $H$ belongs to a few simple classes of graphs such as a class of odd cycles of length at least $5$, stars of size at least $2$, or matchings of size at least $2$, then there is an $H$-induced-saturated graph. This paper addresses the existence question for $H$-induced-saturated graphs. It is shown that Cartesian products of cliques are $H$-induced-saturated graphs for $H$ in several infinite families, including large families of trees. A complete characterization of all connected graphs $H$ for which a Cartesian product of two cliques is an $H$-induced-saturated graph is given. Finally, several results on induced saturation for prime graphs and families of graphs are provided., Comment: 30 pages, 12 figures

We consider the volume of a Boolean expression of some congruent balls about a given system of centers in the $d$-dimensional Euclidean space. When the radius $r$ of the balls is large, this volume can be approximated by a polynomial of $r$, which will be computed up to an $O(r^{d-3})$ error term. We study how the top coefficients of this polynomial depend on the set of the centers. It is known that in the case of the union of the balls, the top coefficients are some constant multiples of the intrinsic volumes of the convex hull of the centers. Thus, the coefficients in the general case lead to generalizations of the intrinsic volumes, in particular, to a generalization of the mean width of a set. Some known results on the mean width, along with the theorem on its monotonicity under contractions are extended to the "Boolean analogues" of the mean width.

We show that the perimeter of the convex hull of finitely many disks lying in the hyperbolic or Euclidean plane, or in a hemisphere does not increase when the disks are rearranged so that the distances between their centers do not increase. This generalizes the theorem on the monotonicity of the perimeter of the convex hull of a finite set under contractions, proved in the Euclidean plane by V. N. Sudakov, R. Alexander, V. Capoyleas and J. Pach. We also prove that the area of the intersection of finitely many disks in the hyperbolic plane does not decrease after such a contractive rearrangement. The Euclidean analogue of the latter statement was proved by K. Bezdek and R. Connelly. Both theorems are proved by a suitable adaptation of a recently published method of I. Gorbovickis.

The authors showed in a preceding paper that in a connected locally harmonic manifold, the volume of a tube of small radius about a regularly parameterized simple arc depends only on the length of the arc and the radius. In this paper, we show that this property characterizes harmonic manifolds even if it is assumed only for tubes about geodesic segments. As a consequence, we obtain similar characterizations of harmonic manifolds in terms of the total mean curvature and the total scalar curvature of tubular hypersurfaces about curves. We find simple formulae expressing the volume, total mean curvature, and total scalar curvature of tubular hypersurfaces about a curve in a harmonic manifold as a function of the volume density function., Comment: 14 pages, grant numbers are updated

H. Hotelling proved that in the n-dimensional Euclidean or spherical space, the volume of a tube of small radius about a curve depends only on the length of the curve and the radius. A. Gray and L. Vanhecke extended Hotelling's theorem to rank one symmetric spaces computing the volumes of the tubes explicitly in these spaces. In the present paper, we generalize these results by showing that every harmonic manifold has the above tube property. We compute the volume of tubes in the Damek-Ricci spaces. We show that if a Riemannian manifold has the tube property, then it is a 2-stein D'Atri space. We also prove that a symmetric space has the tube property if and only if it is harmonic. Our results answer some questions posed by L. Vanhecke, T. J. Willmore, and G. Thorbergsson., Comment: 17 pages, no figures. This version is different from the journal version

We show that if $M$ is a compact smooth manifold diffeomorphic to the total space of an orientable $S^2$ bundle over the torus $T^2$, then its diffeomorphism group does not have the Jordan property, i.e., Diff$(M)$ contains a finite subgroup $G_n$ for any natural number $n$ such that every abelian subgroup of $G_n$ has index at leat $n$. This gives a counterexample to an old conjecture of Ghys., Comment: 4 pages