On the triangle space of a random graph

DOI10.4310/JOC.2013.V4.N2.A4MaRDI QIDQ376548zbMATH OpenFDO

Authors B. DeMarco, A. Hamm, J. Kahn

Publication date 5 November 2013

Published in Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1207.6717, http://intlpress.com/site/pub/pages/journals/items/joc/content/vols/0004/0002/a004/index.html

zbMATH Keywords

thresholdstability theoremhomology of the clique complexKahle's conjecture

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Extremal problems in graph theory (05C35) Simplicial sets and complexes in algebraic topology (55U10) Combinatorial probability (60C05) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Arithmetic progressions (11B25)

Abstract: Settling a first case of a conjecture of M. Kahle on the homology of the clique complex of the random graph $G=G_{n,p}$, we show, roughly speaking, that (with high probability) the triangles of $G$ span its cycle space whenever each of its edges lies in a triangle (which happens (w.h.p.) when $p$ is at least about $sqrt(3/2)lnn/n$, and not below this unless $p$ is very small.) We give two related proofs of this statement, together with a relatively simple proof of a fundamental "stability" theorem for triangle-free subgraphs of $G_{n,p}$, originally due to Kohayakawa, L uczak and R"odl, that underlies the first of our proofs.

Recommendations

• Random triangles in random graphs
• On triangle-free random graphs
• Triangles in random graphs
• Triangles in randomly perturbed graphs
• The number of triangles in random intersection graphs
• Triangles in random cubic planar graphs
• Triangle-free subgraphs of random graphs
• Triangle-free subgraphs of random graphs
• scientific article; zbMATH DE number 1775054

Cited in

(18)

• A triangle process on regular graphs
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• scientific article; zbMATH DE number 5853068 (Why is no real title available?)
• Mantel's theorem for random graphs
• Limit laws for the number of triangles in the generalized random graphs with random node weights
• On the cycle space of a random graph
• For which densities are random triangle-free graphs almost surely bipartite?
• Triangulated Laman graphs, local stochastic matrices, and limits of their products
• Homological connectivity in random Čech complexes
• Triangles in random cubic planar graphs
• Triangle‐factors in pseudorandom graphs
• Triangle-free subgraphs of hypergraphs
• Triangles in randomly perturbed graphs
• The question of the collapsibility of random 3-regular graphs
• Sharp vanishing thresholds for cohomology of random flag complexes
• KOLMOGOROV BOUNDS FOR THE NORMAL APPROXIMATION OF THE NUMBER OF TRIANGLES IN THE ERDŐS–RÉNYI RANDOM GRAPH
• Random processes with convex coordinates on triangular graphs
• Approximating the cumulant generating function of triangles in the Erdös-Rényi random graph

This page was built for publication: On the triangle space of a random graph

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