4 papers · 1 filter
The satisfiability threshold and solution space of random uniquely extendable constraint satisfaction problems
Pu Gao, Theodore Morrison
We study the satisfiability threshold and solution-space geometry of random constraint satisfaction problems defined over uniquely extendable (UE) constraints. Motivated by a conje…
Sandwiching between random regular graphs and Erdős-Rényi graphs: configuration model and unions of perfect matchings
Pu Gao, Mikhail Isaev, Xavier Perez-Gimenez
We establish new couplings among several random graph and multigraph models related to the random regular graph , including the configuration model and unions of random per…
The dimension of sparse and co-sparse random graph orders
Pu Gao, Arnav Kumar
A random graph order is a partial order obtained from a random graph on by taking the transitive closure of the adjacency relation. The dimension of the random graph orders f…
On the pre- and post-positional semi-random graph processes
Pu Gao, Hidde Koerts
We study the semi-random graph process, and a variant process recently suggested by Nick Wormald. We show that these two processes are asymptotically equally fast in constructing a…