Search for: All records

ABSTRACT We discuss the existence of Hamilton cycles in the random graph where there are restrictions caused by (i) coloring sequences, (ii) a subset of vertices must occur in a specific order, and (iii) there is a bound on the number of inversions in the associated permutation. 

ABSTRACT We study the fixation probability for two versions of the Moran process on the random graph at the threshold for connectivity. The Moran process models the spread of a mutant population in a network. Throughout the process, there are vertices of two types, mutants, and non‐mutants. Mutants have fitness and non‐mutants have fitness 1. The process starts with a unique individual mutant located at the vertex . In the Birth‐Death version of the process a random vertex is chosen proportionally to its fitness and then changes the type of a random neighbor to its own. The process continues until the set of mutants is empty or . In the Death‐Birth version, a uniform random vertex is chosen and then takes the type of a random neighbor, chosen according to fitness. The process again continues until the set of mutants is empty or . Thefixation probabilityis the probability that the process ends with . We show that asymptotically correct estimates of the fixation probability depend only on the degree of and its neighbors. In some cases we can provide values for these estimates and in other places we can only provide non‐linear recurrences that could be used to compute values. 

The greedy and nearest-neighbor TSP heuristics can both have $$\log n$$ approximation factors from optimal in worst case, even just for $$n$$ points in Euclidean space. In this note, we show that this approximation factor is only realized when the optimal tour is unusually short. In particular, for points from any fixed $$d$$-Ahlfor's regular metric space (which includes any $$d$$-manifold like the $$d$$-cube $[0,1]^d$ in the case $$d$$ is an integer but also fractals of dimension $$d$$ when $$d$$ is real-valued), our results imply that the greedy and nearest-neighbor heuristics have additive errors from optimal on the order of the optimal tour length through random points in the same space, for $d>1$. 

We prove that a polynomial fraction of the set of $$k$$-component forests in the $$m \times n$$ grid graph have equal numbers of vertices in each component, for any constant $$k$$. This resolves a conjecture of Charikar, Liu, Liu, and Vuong, and establishes the first provably polynomial-time algorithm for (exactly or approximately) sampling balanced grid graph partitions according to the spanning tree distribution, which weights each $$k$$-partition according to the product, across its $$k$$ pieces, of the number of spanning trees of each piece. Our result follows from a careful analysis of the probability a uniformly random spanning tree of the grid can be cut into balanced pieces. Beyond grids, we show that for a broad family of lattice-like graphs, we achieve balance up to any multiplicative $$(1 \pm \varepsilon)$$ constant with constant probability. More generally, we show that, with constant probability, components derived from uniform spanning trees can approximate any given partition of a planar region specified by Jordan curves. This implies polynomial-time algorithms for sampling approximately balanced tree-weighted partitions for lattice-like graphs. Our results have applications to understanding political districtings, where there is an underlying graph of indivisible geographic units that must be partitioned into $$k$$ population-balanced connected subgraphs. In this setting, tree-weighted partitions have interesting geometric properties, and this has stimulated significant effort to develop methods to sample them. 

We show that if an open set in $$\mathbb R^d$$ can be fibered by unit $$n$$-spheres, then $$d\le 2n+1$$, and if $d=2n+1$, then the spheres must be pairwise linked, and $$n\in \{0,1,3,7\}$$. For these values of $$n$$, we construct unit $$n$$-sphere fibrations in $$R^{2n+1}$$. 

Abstract If four people with Gaussian‐distributed heights stand at Gaussian positions on the plane, the probability that there are exactly two people whose height is above the average of the four is exactly the same as the probability that they stand in convex position; both probabilities are . We show that this is a special case of a more general phenomenon: The problem of determining the position of the mean among the order statistics of Gaussian random points on the real line (Youden's demon problem) is the same as a natural generalization of Sylvester's four point problem to Gaussian points in . Our main tool is the observation that the Gale dual of independent samples in itself can be taken to be a set of independent points (translated to have barycenter at the origin) when the distribution of the points is Gaussian. 

Let $$N=\binom{n}{2}$$ and $$s\geq 2$$. Let $$e_{i,j},\,i=1,2,\ldots,N,\,j=1,2,\ldots,s$$ be $$s$$ independent permutations of the edges $$E(K_n)$$ of the complete graph $$K_n$$. A MultiTree is a set $$I\subseteq [N]$$ such that the edge sets $$E_{I,j}$$ induce spanning trees for $$j=1,2,\ldots,s$$. In this paper we study the following question: what is the smallest $m=m(n)$ such that w.h.p. $[m]$ contains a MultiTree. We prove a hitting time result for $s=2$ and an $$O(n\log n)$$ bound for $$s\geq 3$$.