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)

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