On the triangle space of a random graph

DOI10.4310/JOC.2013.V4.N2.A4zbMATH Open1275.05049arXiv1207.6717MaRDI QIDQ376548FDOQ376548

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

Publication date: 5 November 2013

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

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.

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

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

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)

Cited In (18)

• A triangle process on regular graphs
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Title not available (Why is that?)
• 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
• Triangle‐factors in pseudorandom graphs
• Triangles in random cubic planar graphs
• Triangles in randomly perturbed graphs
• Triangle-free subgraphs of hypergraphs
• 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)