Triangle-free subgraphs of random graphs

DOI10.1016/J.ENDM.2015.06.055MaRDI QIDQ322274zbMATH OpenOpenAlexFDO

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

Publication date 14 October 2016

Full work available at URL https://arxiv.org/abs/1507.05226, http://eprints.lse.ac.uk/64640/1/__lse.ac.uk_storage_LIBRARY_Secondary_libfile_shared_repository_Content_Allen%2C%20Peter_Triangle-free%20subgraphs_Allen_Triangle-free%20subgraphs_2015.pdf

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)

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.

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

Cites work

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

Cited in

(10)

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

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)