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

homology of the clique complexKahle's conjecturestability theoremthreshold

Mathematics Subject Classification ID

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

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

(20)

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

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)