A sharp threshold for random graphs with a monochromatic triangle in every edge coloring
| dc.creator | Friedgut, Ehud | |
| dc.creator | Rodl, Vojtech | |
| dc.creator | Rucinski, Andrzej | |
| dc.creator | Tetali, Prasad | |
| dc.date | 2003-01-19 | |
| dc.date | 2004-10-18 | |
| dc.date.accessioned | 2026-07-07T04:54:32Z | |
| dc.date.available | 2026-07-07T04:54:32Z | |
| dc.description | 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<c<\hat c<C$ such that for any $\eps > 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édi's Regularity Lemma to a certain hypergraph setting. | |
| dc.description | 101 pages, Final version - to appear in Memoirs of the A.M.S | |
| dc.identifier | https://arxiv.org/abs/math/0301200 | |
| dc.identifier | http://arxiv.org/abs/math/0301200 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/66290 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C15; 05C55 | |
| dc.title | A sharp threshold for random graphs with a monochromatic triangle in every edge coloring | |
| dc.type | text |