8 citations · 39 across the 17 of their papers we have counts for
19 papers · 1 filter
The satisfiability threshold of random linear equations over finite commutative rings
Pu Gao, Theodore Morrison
We extend the study of random linear equations over finite fields to equations over finite commutative rings. We characterize precisely when the satisfiability threshold occurs at…
When are random regular triangle-free graphs bipartite?
Gregory DeCamillis, Pu Gao
We study the structure of random -regular triangle-free graphs and show that a sharp phase transition occurs at . For smaller , asymptotic…
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…
Evolution of random representable matroids: minors, circuits, connectivity and the critical number
Pu Gao, Jacob Mausberg, Peter Nelson
We study the evolution of random matroids represented by the sequence of random matrices over where columns are added one after the other, and each column vector is…
Embedding theorems for random graphs with specified degrees
Pu Gao, Yuval Ohapkin
Given an symmetric matrix , let be the random graph obtained by independently including each edge with probability $…
The number of perfect matchings, and the nesting properties, of random regular graphs
Pu Gao
We prove that the number of perfect matchings in is asymptotically normal when is even, as , and . This is t…
Linear-time uniform generation of random sparse contingency tables with specified marginals
Andrii Arman, Pu Gao, Nicholas Wormald
We give an algorithm that generates a uniformly random contingency table with specified marginals, i.e. a matrix with non-negative integer values and specified row and column sums.…
Kim--Vu's sandwich conjecture is true for
Pu Gao, Mikhail Isaev, Brendan McKay
Kim and Vu made the following conjecture (\textit{Advances in Mathematics}, 2004): if , then the random -regular graph can be ``sandwiched'' between $G(n,p…
Subgraph probability of random graphs with specified degrees and applications to chromatic number and connectivity
Pu Gao, Yuval Ohapkin
Given a graphical degree sequence , let denote a uniformly random graph on vertex set where vertex has degree for every…
Counterexamples on matchings in hypergraphs and full rainbow matchings in graphs
Pu Gao, Reshma Ramadurai, Ian M. Wanless +1
A graph whose edges are coloured (not necessarily properly) contains a full rainbow matching if there is a matching that contains exactly one edge of each colour. We refute…
The satisfiability threshold for random linear equations
Peter Ayre, Amin Coja-Oghlan, Pu Gao +1
Let be a random matrix over the finite field with precisely non-zero entries per row and let be a random vector chosen independently of .…
Full rainbow matchings in graphs and hypergraphs
Pu Gao, Reshma Ramadurai, Ian Wanless +1
Let be a simple graph that is properly edge coloured with colours and let $\M=\{M_1,\ldots, M_m\}$ be the set of matchings induced by the colours in . Suppose that $…
The stripping process can be slow: part I
Pu Gao, Mike Molloy
Given an integer k, we consider the parallel k-stripping process applied to a hypergraph H: removing all vertices with degree less than k in each iteration until reaching the k-cor…
Enumeration of graphs with a heavy-tailed degree sequence
Pu Gao, Nicholas Wormald
In this paper, we asymptotically enumerate graphs with a given degree sequence d=(d_1,...,d_n) satisfying restrictions designed to permit heavy-tailed sequences in the sparse case…
Analysis of the parallel peeling algorithm: a short proof
Pu Gao
A recent paper by Jiang, Mitzenmacher and Thaler upper bounded the number of rounds needed in a parallel peeling algorithm applied to a random hypergraph whose edge density is belo…
On the Geometric Ramsey Number of Outerplanar Graphs
Josef Cibulka, Pu Gao, Marek Krčál +2
We prove polynomial upper bounds of geometric Ramsey numbers of pathwidth-2 outerplanar triangulations in both convex and general cases. We also prove that the geometric Ramsey num…
A transition of limiting distributions of large matchings in random graphs
Pu Gao, Cristiane M. Sato
We study the asymptotic distribution of the number of matchings of size in for a wide range of and for every $1\le \ell\le \lfloor n/2\rfl…
The first k-regular subgraph is large
Pu Gao
We prove that for sufficiently large k, there exist $0\leσ_k\le\eps_k\to 0$ as , such that asymptotically almost surely the first k-regular subgraph appeared in the ran…
Orientability thresholds for random hypergraphs
Pu Gao, Nicholas Wormald
Let be two fixed integers. Let $\orH$ be a random hypergraph whose hyperedges are all of cardinality . To {\em -orient} a hyperedge, we assign exactly of its vert…