A. Frieze

activity

20052025

most citedAssessing significance in a Markov chain without mixing

86 citations · 344 across the 93 of their papers we have counts for

collaborators

Showing 2017Show all

12 papers · 1 filter

math.CO2017

A note on the localization number of random graphs: diameter two case

Andrzej Dudek, Alan Frieze, Wesley Pegden

We study the localization game on dense random graphs. In this game, a {\em cop} $x$ tries to locate a {\em robber} $y$ by asking for the graph distance of $y$ from every vertex in…

math.CO2017

A note on dispersing particles on a line

Alan Frieze, Wesley Pegden

We consider a synchronous dispersion process introduced in \cite{CRRS} and we show that on the infinite line the final set of occupied sites takes up $O (n)$ space, where $n$ is the…

math.CO2017★ 12 cited

Adding random edges to create the square of a Hamilton cycle

Patrick Bennett, Andrzej Dudek, Alan Frieze

We consider how many random edges need to be added to a graph of order $n$ with minimum degree $α n$ in order that it contains the square of a Hamilton cycle w.h.p..

math.CO2017

Pattern Colored Hamilton Cycles in Random Graphs

Michael Anastos, Alan Frieze

We consider the existence of patterned Hamilton cycles in randomly colored random graphs. Given a string $Π$ over a set of colors ${1, 2, \dots, r}$ , we say that a Hamilton cycle i…

cs.DS2017

Balanced Allocation Through Random Walk

Alan Frieze, Samantha Petti

We consider the allocation problem in which $m \leq (1 - ε) d n$ items are to be allocated to $n$ bins with capacity $d$ . The items $x_{1}, x_{2}, \dots, x_{m}$ arrive sequentially and when…

math.CO2017★ 1 cited

The covertime of a biased random walk on $G_{n, p}$

Colin Cooper, Alan Frieze, Samantha Petti

We analyze the covertime of a biased random walk on the random graph $G_{n, p}$ . The walk is biased towards visiting vertices of low degree and this makes the covertime less than in…

stat.AP2017

An analysis of the Act 43 Wisconsin Assembly district map using the $ε$ test

Maria Chikina, Alan Frieze, Wesley Pegden

In previous work [arXiv:1608.02014], we developed a rigorous statistical test for outlier status in a reversible Markov Chain, and demonstrated its utilization with an application…

math.CO2017

On Rainbow Hamilton Cycles in Random Hypergraphs

Andrzej Dudek, Sean English, Alan Frieze

Let $H_{n, p, r}^{(k)}$ denote a randomly colored random hypergraph, constructed on the vertex set $[n]$ by taking each $k$ -tuple independently with probability $p$ , and then indepen…

math.PR2017

Notes on Growing a Tree in a Graph

Luc Devroye, Vida Dujmović, Alan Frieze +3

We study the height of a spanning tree $T$ of a graph $G$ obtained by starting with a single vertex of $G$ and repeatedly selecting, uniformly at random, an edge of $G$ with exactl…

math.CO2017

Constraining the clustering transition for colorings of sparse random graphs

Michael Anastos, Alan Frieze, Wesley Pegden

Let $Ω_{q}$ denote the set of proper $q$ -colorings of the random graph $G_{n, m}, m = d n /2$ and let $H_{q}$ be the graph with vertex set $Ω_{q}$ and an edge ${σ, τ}$ where $σ, τ$ are mappin…

math.PR2017

Diffusion limited aggregation in the Boolean lattice

Alan Frieze, Wesley Pegden

In the Diffusion Limited Aggregation (DLA) process on on $Z^{2}$ , or more generally $Z^{d}$ , particles aggregate to an initially occupied origin by arrivals on a rand…

cs.DM2017

Randomly coloring simple hypergraphs with fewer colors

Michael Anastos, Alan Frieze

We study the problem of constructing a (near) uniform random proper $q$ -coloring of a simple $k$ -uniform hypergraph with $n$ vertices and maximum degree $Δ$ . (Proper in that no edg…

A note on the localization number of random graphs: diameter two case

A note on dispersing particles on a line

Adding random edges to create the square of a Hamilton cycle

Pattern Colored Hamilton Cycles in Random Graphs

Balanced Allocation Through Random Walk

The covertime of a biased random walk on Gn,p​

An analysis of the Act 43 Wisconsin Assembly district map using the ε​ test

On Rainbow Hamilton Cycles in Random Hypergraphs

Notes on Growing a Tree in a Graph

Constraining the clustering transition for colorings of sparse random graphs

Diffusion limited aggregation in the Boolean lattice

Randomly coloring simple hypergraphs with fewer colors

The covertime of a biased random walk on $G_{n, p}$

An analysis of the Act 43 Wisconsin Assembly district map using the $ε$ test