Triangle-free subgraphs of random graphs

DOI10.1016/J.ENDM.2015.06.055zbMATH Open1346.05262arXiv1507.05226OpenAlexW1467234846MaRDI QIDQ322274FDOQ322274

Authors: Peter Allen, Julia Böttcher, Barnaby Roberts, Yoshiharu Kohayakawa 

Publication date: 14 October 2016

Abstract: Recently there has been much interest in studying random graph analogues of well known classical results in extremal graph theory. Here we follow this trend and investigate the structure of triangle-free subgraphs of $G(n,p)$ with high minimum degree. We prove that asymptotically almost surely each triangle-free spanning subgraph of $G(n,p)$ with minimum degree at least $$ is $mathcalO(p^{-1}n)$-close to bipartite, and each spanning triangle-free subgraph of $G(n,p)$ with minimum degree at least $(frac13+varepsilon)pn$ is $mathcalO(p^{-1}n)$-close to $r$-partite for some $r=r(varepsilon)$. These are random graph analogues of a result by Andr'asfai, ErdH{o}s, and S'os [Discrete Math. 8 (1974), 205-218], and a result by Thomassen [Combinatorica 22 (2002), 591--596]. We also show that our results are best possible up to a constant factor.

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

Recommendations

• Triangle-free subgraphs of random graphs
• Triangle-Free Graphs with High Minimal Degrees
• Density conditions for triangles in multipartite graphs
• For which densities are random triangle-free graphs almost surely bipartite?
• On triangle-free random graphs

zbMATH Keywords

random graphschromatic thresholdsparse regularityAndrásfai-Erdős-Sós theorem

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cites Work

• On the connection between chromatic number, maximal clique and minimal degree of a graph
• On \(K^ 4\)-free subgraphs of random graphs
• On the chromatic number of triangle-free graphs of large minimum degree
• On a valence problem in extremal graph theory
• Mantel's theorem for random graphs
• Szemerédi’s Regularity Lemma for Sparse Graphs
• On the KŁR conjecture in random graphs

Cited In (10)

• Title not available (Why is that?)
• No dense subgraphs appear in the triangle-free graph process
• For which densities are random triangle-free graphs almost surely bipartite?
• Bipartite induced density in triangle-free graphs
• On the minimal degree implying equality of the largest triangle-free and bipartite subgraphs
• Triangle-Free Graphs with High Minimal Degrees
• On the triangle space of a random graph
• Random cyclic triangle-free graphs of prime order
• Triangle-free subgraphs of random graphs
• Extremal subgraphs of random graphs

This page was built for publication: Triangle-free subgraphs of random graphs

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