A sharp threshold for random graphs with a monochromatic triangle in every edge coloring

DOI10.1090/MEMO/0845zbMATH Open1087.05052arXivmath/0301200OpenAlexW2164025052WikidataQ106094339 ScholiaQ106094339MaRDI QIDQ3377334FDOQ3377334

Authors: Ehud Friedgut, Vojtěch Rödl, Andrzej Ruciński, Prasad Tetali 

Publication date: 21 March 2006

Published in: Memoirs of the American Mathematical Society (Search for Journal in Brave)

Abstract: Let $R$ be the set of all finite graphs $G$ with the Ramsey property that every coloring of the edges of $G$ by two colors yields a monochromatic triangle. In this paper we establish a sharp threshold for random graphs with this property. Let $G(n,p)$ be the random graph on $n$ vertices with edge probability $p$. We prove that there exists a function $hatc=hatc(n)$ with $0<c<hatc<C$ such that for any $eps>0$, as $n$ tends to infinity ${\displaystyle }$Pr[G(n,(1-eps)hat c/sqrt{n}) in R ] o 0${\displaystyle }$ and ${\displaystyle }$Pr [ G(n,(1+eps)hat c/sqrt{n}) in R ] o 1.${\displaystyle }$ A crucial tool that is used in the proof and is of independent interest is a generalization of Szemer'edi's Regularity Lemma to a certain hypergraph setting.

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

Recommendations

• Random graphs with monochromatic triangles in every edge coloring
• A randomized version of Ramsey's theorem
• Sharp thresholds for certain Ramsey properties of random graphs
• Ramsey games near the critical threshold
• Threshold Functions for Ramsey Properties

zbMATH Keywords

Ramsey theoryregularity lemmaedge-colouring

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55)

Cited In (21)

• An algorithmic framework for obtaining lower bounds for random Ramsey problems
• Upper tails for subgraph counts in random graphs
• Every monotone graph property has a sharp threshold
• Additive combinatorics: with a view towards computer science and cryptography -- an exposition
• Combinatorial theorems in sparse random sets
• A randomized version of Ramsey's theorem
• Hunting for sharp thresholds
• A sharp threshold for van der Waerden's theorem in random subsets
• Random sum-free subsets of abelian groups
• Ramsey properties of random discrete structures
• Towards the 0-statement of the Kohayakawa-Kreuter conjecture
• The Sharp Threshold for Maximum-Size Sum-Free Subsets in Even-Order Abelian Groups
• Sharp thresholds for Ramsey properties of strictly balanced nearly bipartite graphs
• Random graphs with monochromatic triangles in every edge coloring
• The chromatic discrepancy of graphs
• Coloring the edges of a random graph without a monochromatic giant component
• Large cycles in random generalized Johnson graphs
• Towards the Kohayakawa-Kreuter conjecture on asymmetric Ramsey properties
• Counting sum-free sets in abelian groups
• An asymmetric random Rado theorem: 1-statement
• Symmetric and asymmetric Ramsey properties in random hypergraphs

This page was built for publication: A sharp threshold for random graphs with a monochromatic triangle in every edge coloring

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