Algorithms for Radon Partitions with Tolerance
Let P be a set n points in a d-dimensional space. Tverberg theorem says that, if n is at least (k − 1)(d + 1), then P can be par- titioned into k sets whose convex hulls intersect. Partitions with this property are called Tverberg partitions. A partition has tolerance t if the partition remains a Tverberg partition after removal of any set of t points from P. A tolerant Tverberg partition exists in any dimensions provided that n is sufficiently large. Let N(d,k,t) be the smallest value of n such that tolerant Tverberg partitions exist for any set of n points in R d . Only few exact values of N(d,k,t) are known. In this paper, we study the problem of finding Radon partitions (Tver- berg partitions for k = 2) for a given set of points. We develop several algorithms and found new lower bounds for N(d,2,t).  more » « less
Award ID(s):
NSF-PAR ID:
10196125
Author(s) / Creator(s):
Date Published:
Journal Name:
Lecture notes in computer science
Volume:
12016
ISSN:
0302-9743
Format(s):
Medium: X
1. Let $\Omega_q$ denote the set of proper $[q]$-colorings of the random graph $G_{n,m}, m=dn/2$ and let $H_q$ be the graph with vertex set $\Omega_q$ and an edge $\set{\s,\t}$ where $\s,\t$ are mappings $[n]\to[q]$ iff $h(\s,\t)=1$. Here $h(\s,\t)$ is the Hamming distance $|\set{v\in [n]:\s(v)\neq\t(v)}|$. We show that w.h.p. $H_q$ contains a single giant component containing almost all colorings in $\Omega_q$ if $d$ is sufficiently large and $q\geq \frac{cd}{\log d}$ for a constant $c>3/2$.
2. Let $D$ be a simple digraph (directed graph) with vertex set $V(D)$ and arc set $A(D)$ where $n=|V(D)|$, and each arc is an ordered pair of distinct vertices. If $(v,u) \in A(D)$, then $u$ is considered an \emph{out-neighbor} of $v$ in $D$. Initially, we designate each vertex to be either filled or empty. Then, the following color change rule (CCR) is applied: if a filled vertex $v$ has exactly one empty out-neighbor $u$, then $u$ will be filled. If all vertices in $V(D)$ are eventually filled under repeated applications of the CCR, then the initial set is called a \emph{zero forcing set} (ZFS); if not, it is a \emph{failed zero forcing set} (FZFS). We introduce the \emph{failed zero forcing number} $\F(D)$ on a digraph, which is the maximum cardinality of any FZFS. The \emph{zero forcing number}, $\Z(D)$, is the minimum cardinality of any ZFS. We characterize digraphs that have $\F(D)<\Z(D)$ and determine $\F(D)$ for several classes of digraphs including de Bruijn and Kautz digraphs. We also characterize digraphs with $\F(D)=n-1$, $\F(D)=n-2$, and $\F(D)=0$, which leads to a characterization of digraphs in which any vertex is a ZFS. Finally, we show that for any integer $n \geq 3$ and any non-negative integer $k$ with $k more » « less 3. Holmsen, Kynčl and Valculescu recently conjectured that if a finite set$X$with$\ell n$points in$\mathbb{R}^{d}$that is colored by$m$different colors can be partitioned into$n$subsets of$\ell$points each, such that each subset contains points of at least$d$different colors, then there exists such a partition of$X$with the additional property that the convex hulls of the$n$subsets are pairwise disjoint. We prove a continuous analogue of this conjecture, generalized so that each subset contains points of at least$c$different colors, where we also allow$c$to be greater than$d$. Furthermore, we give lower bounds on the fraction of the points each of the subsets contains from$c$different colors. For example, when$n\geqslant 2$,$d\geqslant 2$,$c\geqslant d$with$m\geqslant n(c-d)+d$are integers, and$\unicode[STIX]{x1D707}_{1},\ldots ,\unicode[STIX]{x1D707}_{m}$are$m$positive finite absolutely continuous measures on$\mathbb{R}^{d}$, we prove that there exists a partition of$\mathbb{R}^{d}$into$n$convex pieces which equiparts the measures$\unicode[STIX]{x1D707}_{1},\ldots ,\unicode[STIX]{x1D707}_{d-1}$, and in addition every piece of the partition has positive measure with respect to at least$c$of the measures$\unicode[STIX]{x1D707}_{1},\ldots ,\unicode[STIX]{x1D707}_{m}\$ .