Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Ramsey Properties of Random Graphs and Folkman Numbers

100%

Rödl V., Ruciński A., Schacht M.

Discussiones Mathematicae Graph Theory

2017

tom 37

nr 3

755-776

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.

Avoiding rainbow 2-connected subgraphs

100%

Gorgol I.

Open Mathematics

2017

tom 15

nr 1

393-397

While defining the anti-Ramsey number Erdős, Simonovits and Sós mentioned that the extremal colorings may not be unique. In the paper we discuss the uniqueness of the colorings, generalize the idea of their construction and show how to use it to construct the colorings of the edges of complete split graphs avoiding rainbow 2-connected subgraphs. These colorings give the lower bounds for adequate anti-Ramsey numbers.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Open Mathematics

1 Gorgol I.

1 Ruciński A.

1 Rödl V.

1 Schacht M.

2 2017

Wyniki wyszukiwania

Ramsey Properties of Random Graphs and Folkman Numbers

Avoiding rainbow 2-connected subgraphs