86 citations · 344 across the 93 of their papers we have counts for
16 papers · 1 filter
A note on the rank of a sparse random matrix
Colin Cooper, Alan Frieze, Wesley Pegden
Let be a random matrix with entries from some field where there are exactly non-zero entries in each column, whose locations are…
Hamiltonicity of random graphs in the stochastic block model
Michael Anastos, Alan Frieze, Pu Gao
We study the Hamiltonicity of the following model of a random graph. Suppose that we partition [n] into V_1,V_2,...,V_k and add edge {x,y} to our graph with probability p if there…
Localization Game for Random Graphs
Andrzej Dudek, Sean English, Alan Frieze +2
We consider the localization game played on graphs in which a cop tries to determine the exact location of an invisible robber by exploiting distance probes. The corresponding grap…
Minimum-weight combinatorial structures under random cost-constraints
Alan Frieze, Wesley Pegden, Gregory Sorkin +1
Recall that Janson showed that if the edges of the complete graph are assigned exponentially distributed independent random weights, then the expected length of a shortest pa…
Giant descendant trees, matchings and independent sets in the age-biased attachment graphs
Huseyin Acan, Alan Frieze, Boris Pittel
We study two models of an age-biased graph process: the -version of the preferential attachment graph model (PAM) and the uniform attachment graph model (UAM), with attachme…
A note on randomly colored matchings in random bipartite graphs
Alan Frieze
We are given a bipartite graph that contains at least one perfect matching and where each edge is colored from a set $Q=\{c_1,c_2,\ldots,c_q}\$. Let $Q_i=\set{e\in E(G):c(e)=c_i}$,…
A scaling limit for the length of the longest cycle in a sparse random graph
Michael Anastos, Alan Frieze
We discuss the length of the longest cycle in a sparse random graph . constant. We show that for large there is a function such that $L_n(c)/n\to f(c)…
A randomly weighted minimum arborescence with a random cost constraint
Alan Frieze, Tomasz Tkocz
We study the minimum spanning arborescence problem on the complete digraph where an edge has a weight and a cost , each of which is an independent unifor…
Hamilton cycles in random graphs with minimum degree at least 3: an improved analysis
Michael Anastos, Alan Frieze
In this paper we consider the existence of Hamilton cycles in the random graph . This a random graph chosen uniformly from the set of graphs with vertex set $[…
A note on spanning -cycles in random graphs
Alan Frieze
We find the threshold for the existence of a collection of edge disjoint copies of that form a cyclic structure and span all vertices of . We use a recent result of…
A randomly weighted minimum spanning tree with a random cost constraint
Alan Frieze, Tomasz Tkocz
We study the minimum spanning tree problem on the complete graph where an edge has a weight and a cost , each of which is an independent copy of the random var…
Separating effect from significance in Markov chain tests
Maria Chikina, Alan Frieze, Jonathan Mattingly +1
We give qualitative and quantitative improvements to theorems which enable significance testing in Markov Chains, with a particular eye toward the goal of enabling strong, interpre…
Random graphs with a fixed maximum degree
Alan Frieze, Tomasz Tkocz
We study the component structure of the random graph . Here and is sampled uniformly from , the set of graphs with vertex set ,…
The game chromatic number of a random hypergraph
Debsoumya Chakraborti, Alan Frieze, Mihir Hasabnis
We consider the following game, played on a -uniform hypergraph . There are colors available and two players take it in turns to color vertices. A partial coloring is pro…
On random multi-dimensional assignment problems
Alan Frieze, Wesley Pegden, Tomasz Tkocz
We study random multidimensional assignment problems where the costs decompose into the sum of independent random variables. In particular, in three dimensions, we assume that the…
Hamilton Cycles in Random Graphs: a bibliography
Alan Frieze
We provide an annotated bibliography for the study of Hamilton cycles in random graphs and hypergraphs.