Vision and Around

Dedicated to my research and life

Vertex Coverage of Random Polytope - 2

| Comments

Recall from last post that we are interested in this problem: Given \(n\) i.i.d. uniformly random samples \(\mathbf x_1, \cdots, \mathbf x_n\) from \(\mathbb S^{d-1}\) (\(n > d\)), consider the induced convex polytope \(\mathcal K_n = \operatorname{\mathbf{conv}}\left(\mathbf x_1, \cdots, \mathbf x_n\right)\). Now sample \(m\) more i.i.d. uniformly random points \(\mathbf z_1, \cdots, \mathbf z_m\) from \(\mathbb S^{d-1}\) independent of first \(n\) points we sampled. For each of the \(m\) points, say \(\mathbf z_i\), treat it as canonical vector and color the facet this vector is incident on \(\mathcal K_n\) in red (with probability one, such point will only hit the interior of a facet rather than other degenerate faces). Determine how large \(m\) needs to be in order to ensure 1) all \(n\) vertices of \(\mathcal K_n\) are colored; and 2) one can find a connected path within the colored region to connect any two vetices. In other words, if we only retain colored vertices and edges and ignore other higher-dimensional faces, the resulting graph is connected. We will call such an event coverage of vertices.

From simulation, it seems one needs at most \(m \leq O\left(n \log n\right)\) to ensure the desired coverage with high probability. Here I present a heuristic argument showing \(m\) only needs to be at most a low-order polynomial in \(n\). Suppose we require something stronger: all edges get colored. By the celebrated Balinski’s theorem, this implies vertex coverage we desire.

Theorem 1 (Balinski’s Theorem) The undirected graph from the vertices and edges of a \(d\)-dimensional convex polytope is \(d\)-connected, i.e., the graph remains connected if one removes any \(d-1\) or fewer vertices and the associated edges from the graph.

Now from the generation model, we expect \(\mathcal K_n\) to be regular both in combinatorial and geometric properties. So on average, the spherical simplex cut by each facet from the sphere has normalized spherical measure \(1/\#\mathrm{facets}\) and each edge is touched by \(\#\mathrm{facets}/\#\mathrm{edges}\) facets. So \[\begin{align*} & \mathbb P\left[\exists\; \text{an edge not colored with $m$ samples}\right] \newline \leq\; & \#\mathrm\; \times \; \mathbb P\left[\text{a fixed edge not colored with $m$ samples}\right] \newline \approx \; & \#\mathrm\; \times \; \left(1-\frac{1}{\#\mathrm{facets}} \frac{\#\mathrm{facets}}{\#\mathrm{edges}}\right)^m \newline \leq \; & \#\mathrm\times \exp\left(-\frac{m}{\#\mathrm{edges}}\right) \newline =\; & \exp\left(-\frac{m}{\#\mathrm{edges}} + \log \#\mathrm{edges}\right). \end{align*}\] Note that \(\#\mathrm{edges} \leq n^2/2\), and it is enough to take \[\begin{align} m = O\left(n^2 \log n\right) \end{align}\] to ensure all edges get colored with some nontrivial constant probability or \(m = O\left(n^3\right)\) to ensure high probability. The order is likely to be loose, as in the random model \(\#\mathrm{edges}\) could be order-of-magnitude smaller than \(O\left(n^2\right)\), and also one may only need to cover a fraction of edges to ensure vertex coverage. Of course to make the argument rigorous, one needs in addition to also work on extreme quantities such as 1) minimum normalized spherical measure one spherical simplex subtends; and 2) minimum number of facets one edge will touch in \(\mathcal K_n\).