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. 

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$$.