3 papers
math.CO2026
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…
math.CO2025
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…
math.CO2025
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…