REVIEW 3 cited by
Kim--Vu's sandwich conjecture is true for $d \gg \log^4 n$
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
abstract
Kim and Vu made the following conjecture (\textit{Advances in Mathematics}, 2004): if $d\gg \log n$, then the random $d$-regular graph $G(n,d)$ can be ``sandwiched'' between $G(n,p_*)$ and $G(n,p^*)$ where $p_*$ and $p^*$ are both asymptotically equal to $d/n$. This famous conjecture was previously proved for all $d\gg (n\log n)^{3/4}$. In this paper, we confirm the conjecture when $d \gg \log^4 n$. We also extend this result to near-regular degree sequences.
Forward citations
Cited by 3 Pith papers
-
Sums along the edges of bounded degree graphs
Random d-regular graphs have sum-sets of size n^{1-2/d} for every abelian group, proving a polynomial lower bound that is tight up to polylog factors.
-
Approximate Itai-Zehavi conjecture for random graphs
Erdős-Rényi and random regular graphs asymptotically satisfy the Itai-Zehavi conjecture, containing (1-o(1))np and (1-o(1))d independent spanning trees, with a d/4-factor guarantee for sparse regular graphs.
-
Monotonicity and decompositions of random regular graphs
For many pairs of degrees, the random lower-degree regular graph can be embedded inside the random higher-degree regular graph with high probability, and unions of random regular graphs can mimic a single random regul...
Discussion (0). Sign in to comment.