Random triangles in random graphs

DOI10.1002/RSA.21013MaRDI QIDQ6074669zbMATH OpenOpenAlexFDO

Authors Annika Heckel

Publication date 12 October 2023

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/1802.08472

zbMATH Keywords

couplingrandom graphsrandom hypergraphs

Mathematics Subject Classification ID

Hypergraphs (05C65) Random graphs (graph-theoretic aspects) (05C80)

Abstract: In a recent paper, Oliver Riordan shows that for $rge4$ and $p$ up to and slightly larger than the threshold for a $K_r$-factor, the hypergraph formed by the copies of $K_r$ in $G(n,p)$ contains a copy of the binomial random hypergraph $H=H_r(n,pi)$ with $pisim{p}^{rchoose2}$. For $r=3$, he gives a slightly weaker result where the density in the random hypergraph is reduced by a constant factor. Recently, Jeff Kahn announced an asymptotically sharp bound for the threshold in Shamir's hypergraph matching problem for all $rge3$. With Riordan's result, this immediately implies an asymptotically sharp bound for the threshold of a $K_r$-factor in $G(n,p)$ for $rge4$. In this note, we resolve the missing case $r=3$ by modifying Riordan's argument. This means that Kahn's result also implies a sharp bound for triangle factors in $G(n,p)$.

Recommendations

• Random cliques in random graphs and sharp thresholds for F$$ F $$‐factors
• Threshold Functions for H-factors
• Triangle Factors in Random Graphs
• scientific article; zbMATH DE number 5630514
• Factors in random graphs

Cites work

• Factors in random graphs
• Fundamentals of Stein's method
• Two moments suffice for Poisson approximations: The Chen-Stein method

Cited in

(20)

• Random processes with convex coordinates on triangular graphs
• For which densities are random triangle-free graphs almost surely bipartite?
• A triangle process on regular graphs
• Approximating the cumulant generating function of triangles in the Erdös-Rényi random graph
• Limit laws for the number of triangles in the generalized random graphs with random node weights
• Asymptotics for Shamir's problem
• Triangles in random cubic planar graphs
• On the triangle space of a random graph
• Triangle Factors in Random Graphs
• Triangle‐factors in pseudorandom graphs
• Triangles in randomly perturbed graphs
• Random cliques in random graphs and sharp thresholds for F$$ F $$‐factors
• The hitting time of clique factors
• Spanning F-cycles in random graphs
• A robust Corrádi-Hajnal theorem
• A note on non-isomorphic edge-color classes in random graphs
• Searching for (sharp) thresholds in random structures: where are we now?
• The hitting time of clique factors (extended abstract)
• Clique factors in pseudorandom graphs
• Tiling random regular graphs efficiently

This page was built for publication: Random triangles in random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6074669)