Colin Cooper

activity

20242026

collaborators

Showing math.COShow all

5 papers · 1 filter

math.CO2026

Edge disjoint Hamilton cycles in random digraphs of constant minimum degree

Colin Cooper, Alan Frieze

We study the existence of directed Hamilton cycles in random digraphs with $m$ edges where we condition on minimum in- and out-degree $\d \ge k+1$, where $k \geq 1$ . Denote such a r…

math.CO2025

Cover time of random subgraphs of the hypercube

Colin Cooper, Alan Frieze, Wesley Pegden

$Q_{n, p}$ , the random subgraph of the $n$ -vertex hypercube $Q_{n}$ , is obtained by independently retaining each edge of $Q_{n}$ with probability $p$ . We give precise values for the cov…

math.CO2025

Rainbow copies of spanning subgraphs

Colin Cooper, Alan Frieze

Let $G_{n, p}^{[κ]}$ denote the space of $n$ -vertex edge coloured graphs, where each edge occurs independently with probability $p$ . The colour of each existing edge is chosen indep…

math.CO2024

WalkSAT is linear on random 2-SAT

Petra Berenbrink, Amin Coja-Oghlan, Colin Cooper +3

In an influential article Papadimitriou [FOCS 1991] proved that a local search algorithm called WalkSAT finds a satisfying assignment of a satisfiable 2-CNF with $n$ variables in $…

math.CO2024

Random walks on edge colored random graphs

Colin Cooper, Alan Frieze

We consider random walks on edge coloured random graphs, where the colour of an edge reflects the cost of using it. In the simplest instance, the edges are coloured red or blue. Bl…