Wyniki wyszukiwania

1

Families of triples with high minimum degree are hamiltonian

100%

Rödl V., Ruciński A.

Discussiones Mathematicae Graph Theory

|

2014

|

tom 34

|

nr 2

361-381

EN

In this paper we show that every family of triples, that is, a 3-uniform hypergraph, with minimum degree at least [...] contains a tight Hamiltonian cycle

2

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Two variants of the size Ramsey number

100%

Kurek A., Ruciński A.

Discussiones Mathematicae Graph Theory

|

2005

|

tom 25

|

nr 1-2

141-149

EN

Given a graph H and an integer r ≥ 2, let G → (H,r) denote the Ramsey property of a graph G, that is, every r-coloring of the edges of G results in a monochromatic copy of H. Further, let $m(G) = max_{F ⊆ G}|E(F)|/|V(F)|$ and define the Ramsey density $m_{inf}(H,r)$ as the infimum of m(G) over all graphs G such that G → (H,r). In the first part of this paper we show that when H is a complete graph Kₖ on k vertices, then $m_{inf}(H,r) = (R-1)/2$, where R = R(k;r) is the classical Ramsey number. As a corollary we derive a new proof of the result credited to Chvatál that the size Ramsey number for Kₖ equals $\binom{R} {2}$. We also study an on-line version of the size Ramsey number, related to the following two-person game: Painter colors on-line the edges provided by Builder, and Painter's goal is to avoid a monochromatic copy of Kₖ. The on-line Ramsey number R̅(k;r) is the smallest number of moves (edges) in which Builder can force Painter to lose if r colors are available. We show that R̅(3;2) = 8 and $R̅(k;2) ≤ 2k\binom{2k-2} {k-1}$, but leave unanswered the question if R̅(k;2) = o(R²(k;2)).

3

Ramsey Properties of Random Graphs and Folkman Numbers

81%

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

Discussiones Mathematicae Graph Theory

|

2017

|

tom 37

|

nr 3

755-776

EN

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.

Ograniczanie wyników

3 Discussiones Mathematicae Graph Theory

3 Ruciński A.

2 Rödl V.

1 Kurek A.

1 Schacht M.

1 2017

1 2014

1 2005

Families of triples with high minimum degree are hamiltonian

Two variants of the size Ramsey number

Ramsey Properties of Random Graphs and Folkman Numbers