For two graphs, G and F, and an integer r ≥ 2 we write G → (F)r if every r-coloring of the edges of G results in a monochromatic copy of F. In 1995, the first two authors established a threshold edge probability for the Ramsey property G(n, p) → (F)r, where G(n, p) is a random graph obtained by including each edge of the complete graph on n vertices, independently, with probability p. The original proof was based on the regularity lemma of Szemerédi and this led to tower-type dependencies between the involved parameters. Here, for r = 2, we provide a self-contained proof of a quantitative version of the Ramsey threshold theorem with only double exponential dependencies between the constants. As a corollary we obtain a double exponential upper bound on the 2-color Folkman numbers. By a different proof technique, a similar result was obtained independently by Conlon and Gowers.
3
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
In 1968 Erdős and Hajnal introduced shift graphs as graphs whose vertices are the k-element subsets of [n] = {1,...,n} (or of an infinite cardinal κ ) and with two k-sets $A = {a₁,...,a_{k}}$ and $B = {b₁,...,b_{k}}$ joined if $a₁ < a₂ = b₁ < a₃ = b₂ < ⋯ < a_k = b_{k-1} < b_k$. They determined the chromatic number of these graphs. In this paper we extend this definition and study the chromatic number of graphs defined similarly for other types of mutual position with respect to the underlying ordering. As a consequence of our result, we show the existence of a graph with interesting disparity of chromatic behavior of finite and infinite subgraphs. For any cardinal κ and integer l, there exists a graph G with |V(G)| = χ(G) = κ but such that, for any finite subgraph F ⊂ G, $χ(F)≤ log_{(l)}|V(F|$, where $log_{(l)}$ is the l-iterated logarithm. This answers a question raised by Erdős, Hajnal and Shelah.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.