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

DOI10.1090/MEMO/0845MaRDI QIDQ3377334zbMATH OpenOpenAlexWikidataFDO

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)

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

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)

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.

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

Cited in

(21)

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

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)