4 papers
Non-uniform Kahn-Kalai, spread, variants, and applications
Thinula De Silva, Pu Gao
Building on B.Park and Vondrak's recent generalization of the J.Park-Pham Theorem (formerly known as Kahn-Kalai conjecture) to non-uniform probability measures, this paper introduc…
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…
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…
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…