86 citations · 344 across the 93 of their papers we have counts for
9 papers · 1 filter
On the cover time of dense graphs
Colin Cooper, Alan Frieze, Wesley Pegden
We consider arbitrary graphs with vertices and minimum degree at least where is constant. If the conductance of is sufficiently large then we obtain an asymp…
On the cover time of the emerging giant
Alan Frieze, Wesley Pegden, Tomasz Tkocz
Let . It is known that if then w.h.p. has a unique giant largest component. We show that if in addition, $\varepsil…
Finding perfect matchings in random cubic graphs in linear time
Michael Anastos, Alan Frieze
In a seminal paper on finding large matchings in sparse random graphs, Karp and Sipser proposed two algorithms for this task. The second algorithm has been intensely studied, but d…
A note on log-concave random graphs
Alan Frieze, Tomasz Tkocz
We establish a threshold for the connectivity of certain random graphs whose (dependent) edges are determined by the uniform distributions on generalized Orlicz balls, crucially us…
On the rank of a random binary matrix
C. Cooper, A. M. Frieze, W. Pegden
We study the rank of the random 0/1 matrix where each column is chosen independently from the set of 0/1 vectors with exactly 1's. Here…
On the connectivity threshold for colorings of random graphs and hypergraphs
Michael Anastos, Alan Frieze
Let denote the set of proper -colorings of the hypergraph . Let be the graph with vertex set and an edge ${σ,τ\}$ where are colorings iff $h(…
A random variant of the game of plates and olives
Andrzej Dudek, Sean English, Alan Frieze
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 varian…
How many randomly colored edges make a randomly colored dense graph rainbow hamiltonian or rainbow connected?
Michael Anastos, Alan Frieze
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…
The cover time of a biased random walk on a random cubic graph
Colin Cooper, Alan Frieze, Tony Johansson
We study a random walk that prefers tou se unvisited edges in the context of random cubic graphs. We establish asymptotically correct estimates for the vertex and edge cover times,…