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

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

2003-01-19

arxiv.org/abs/math/0301200v2

Mathematics

Combinatorics

101 pages, Final version - to appear in Memoirs of the A.M.S

Scientific paper

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 $\hat c=\hat c(n)$ with $0 0$, as $n$ tends to infinity $$Pr[G(n,(1-\eps)\hat c/\sqrt{n}) \in \R ] \to 0$$ and $$Pr [ G(n,(1+\eps)\hat c/\sqrt{n}) \in \R ] \to 1.$$ 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.

Affiliated with

Also associated with

No associations

Rating

A sharp threshold for random graphs with a monochromatic triangle in every edge coloring does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A sharp threshold for random graphs with a monochromatic triangle in every edge coloring, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A sharp threshold for random graphs with a monochromatic triangle in every edge coloring will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-444019