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$.
more »
« less
Algorithms for Radon Partitions with Tolerance
Let P be a set n points in a ddimensional 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):
 1718994
 NSFPAR ID:
 10196125
 Date Published:
 Journal Name:
 Lecture notes in computer science
 Volume:
 12016
 ISSN:
 03029743
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


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{outneighbor} 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 outneighbor $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)=n1$, $\F(D)=n2$, 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 nonnegative integer $k$ with $k
more » « less 
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(cd)+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}_{d1}$ , 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}$ .more » « less

Abstract Let f : ℙ 1 → ℙ 1 {f:\mathbb{P}^{1}\to\mathbb{P}^{1}} be a map of degree > 1 {>1} defined over a function field k = K ( X ) {k=K(X)} , where K is a number field and X is a projective curve over K . For each point a ∈ ℙ 1 ( k ) {a\in\mathbb{P}^{1}(k)} satisfying a dynamical stability condition, we prove that the Call–Silverman canonical height for specialization f t {f_{t}} at point a t {a_{t}} , for t ∈ X ( ℚ ¯ ) {t\in X(\overline{\mathbb{Q}})} outside a finite set, induces a Weil height on the curve X ; i.e., we prove the existence of a ℚ {\mathbb{Q}} divisor D = D f , a {D=D_{f,a}} on X so that the function t ↦ h ^ f t ( a t )  h D ( t ) {t\mapsto\hat{h}_{f_{t}}(a_{t})h_{D}(t)} is bounded on X ( ℚ ¯ ) {X(\overline{\mathbb{Q}})} for any choice of Weil height associated to D . We also prove a local version, that the local canonical heights t ↦ λ ^ f t , v ( a t ) {t\mapsto\hat{\lambda}_{f_{t},v}(a_{t})} differ from a Weil function for D by a continuous function on X ( ℂ v ) {X(\mathbb{C}_{v})} , at each place v of the number field K . These results were known for polynomial maps f and all points a ∈ ℙ 1 ( k ) {a\in\mathbb{P}^{1}(k)} without the stability hypothesis,[21, 14],and for maps f that are quotients of endomorphisms of elliptic curves E over k and all points a ∈ ℙ 1 ( k ) {a\in\mathbb{P}^{1}(k)} . [32, 29].Finally, we characterize our stability condition in terms of the geometry of the induced map f ~ : X × ℙ 1 ⇢ X × ℙ 1 {\tilde{f}:X\times\mathbb{P}^{1}\dashrightarrow X\times\mathbb{P}^{1}} over K ; and we prove the existence of relative Néron models for the pair ( f , a ) {(f,a)} , when a is a Fatou point at a place γ of k , where the local canonical height λ ^ f , γ ( a ) {\hat{\lambda}_{f,\gamma}(a)} can be computed as an intersection number.more » « less

We model the societal task of redistricting political districts as a partitioning problem: Given a set of n points in the plane, each belonging to one of two parties, and a parameter k, our goal is to compute a partition P of the plane into regions so that each region contains roughly s = n/k points. P should satisfy a notion of "local" fairness, which is related to the notion of core, a wellstudied concept in cooperative game theory. A region is associated with the majority party in that region, and a point is unhappy in P if it belongs to the minority party. A group D of roughly s contiguous points is called a deviating group with respect to P if majority of points in D are unhappy in P. The partition P is locally fair if there is no deviating group with respect to P.This paper focuses on a restricted case when points lie in 1D. The problem is nontrivial even in this case. We consider both adversarial and "beyond worstcase" settings for this problem. For the former, we characterize the input parameters for which a locally fair partition always exists; we also show that a locally fair partition may not exist for certain parameters. We then consider input models where there are "runs" of red and blue points. For such clustered inputs, we show that a locally fair partition may not exist for certain values of s, but an approximate locally fair partition exists if we allow some regions to have smaller sizes. We finally present a polynomialtime algorithm for computing a locally fair partition if one exists.more » « less