Colin Cooper

collaborators

3 papers

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 $…