An official website of the United States government
Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to non-federal websites. Their policies may differ from this site.
-
Let $${\bf A}$$ be an $$n\times m$$ matrix over $$\mathbf{GF}_2$$ where each column consists of $$k$$ ones, and let $$M$$ be an arbitrary fixed binary matroid. The matroid growth rate theorem implies that there is a constant $$C_M$$ such that $$m\geq C_M n^2$$ implies that the binary matroid induced by {\bf A} contains $$M$$ as a minor. We prove that if the columns of $${\bf A}={\bf A}_{n,m,k}$$ are chosen \emph{randomly}, then there are constants $$k_M, L_M$$ such that $$k\geq k_M$$ and $$m\geq L_M n$$ implies that $${\bf A}$$ contains $$M$$ as a minor w.h.p.more » « less
-
The game of plates and olives was originally formulated by Nicolaescu and encodes the evolution of the topology of the sublevel sets of Morse functions. We consider a random variant of this game. The process starts with an empty table. There are four different types of moves: (1) add a new plate to the table, (2) combine two plates and their olives onto one plate, removing the second plate from the table, (3) add an olive to a plate, and (4) remove an olive from a plate. We show that with high probability the number of olives is linear as the total number of moves goes to infinity. Furthermore, we prove that the number of olives is concentrated around its expectation.more » « less
-
We consider arbitrary graphs $$G$$ with $$n$$ vertices and minimum degree at least $$\delta n$$ where $$\delta>0$$ is constant.\\ (a) If the conductance of $$G$$ is sufficiently large then we obtain an asymptotic expression for the cover time $$C_G$$ of $$G$$ as the solution to an explicit transcendental equation.\\ (b) If the conductance is not large enough to apply (a), but the mixing time of a random walk on $$G$$ is of a lesser magnitude than the cover time, then we can obtain an asymptotic deterministic estimate via a decomposition into a bounded number of dense subgraphs with high conductance. \\ (c) If $$G$$ fits neither (a) nor (b) then we give a deterministic asymptotic (2+o(1))-approximation of $$C_G$$.more » « less
-
In this paper we study the randomly edge colored graph that is obtained by adding randomly colored random edges to an arbitrary randomly edge colored dense graph. In particular we ask how many colors and how many random edges are needed so that the resultant graph contains a fixed number of edge disjoint rainbow Hamilton cycles w.h.p. We also ask when in the resultant graph every pair of vertices is connected by a rainbow path w.h.p.more » « less
-
We establish sharp threshold for the connectivity of certain random graphs whose (dependent) edges are determined by uniform distributions on generalized Orlicz balls, crucially using their negative correlation properties. We also show existence of a unique giant component for such random graphs.more » « less
-
We consider the allocation problem in which $$m \leq (1-\epsilon) dn $$ items are to be allocated to $$n$$ bins with capacity $$d$$. The items $$x_1,x_2,\ldots,x_m$$ arrive sequentially and when item $$x_i$$ arrives it is given two possible bin locations $$p_i=h_1(x_i),q_i=h_2(x_i)$$ via hash functions $$h_1,h_2$$. We consider a random walk procedure for inserting items and show that the expected time insertion time is constant provided $$\epsilon = \Omega\left(\sqrt{ \frac{ \log d}{d}} \right).$$more » « less
-
Assume that the edges of the complete graph K n are given independent uniform [0, 1] weights. We consider the expected minimum total weight μ k of k ⩽ 2 edge-disjoint spanning trees. When k is large we show that μ k ≈ k 2 . Most of the paper is concerned with the case k = 2. We show that m 2 tends to an explicitly defined constant and that μ 2 ≈ 4.1704288. . . .more » « less
-
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
Full Text Available