# Two variants of the size Ramsey number

Andrzej Kurek; Andrzej Ruciński

Discussiones Mathematicae Graph Theory (2005)

- Volume: 25, Issue: 1-2, page 141-149
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topAndrzej Kurek, and Andrzej Ruciński. "Two variants of the size Ramsey number." Discussiones Mathematicae Graph Theory 25.1-2 (2005): 141-149. <http://eudml.org/doc/270499>.

@article{AndrzejKurek2005,

abstract = {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)).},

author = {Andrzej Kurek, Andrzej Ruciński},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {size Ramsey number; graph density; online Ramsey games},

language = {eng},

number = {1-2},

pages = {141-149},

title = {Two variants of the size Ramsey number},

url = {http://eudml.org/doc/270499},

volume = {25},

year = {2005},

}

TY - JOUR

AU - Andrzej Kurek

AU - Andrzej Ruciński

TI - Two variants of the size Ramsey number

JO - Discussiones Mathematicae Graph Theory

PY - 2005

VL - 25

IS - 1-2

SP - 141

EP - 149

AB - 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)).

LA - eng

KW - size Ramsey number; graph density; online Ramsey games

UR - http://eudml.org/doc/270499

ER -

## References

top- [1] N. Alon, C. McDiarmid and B. Reed, Star arboricity, Combinatorica 12 (1992) 375-380, doi: 10.1007/BF01305230.
- [2] N. Alon and V. Rödl, Sharp bounds for some multicolor Ramsey numbers, Combinatorica (2005), to appear, doi: 10.1007/s00493-005-0011-9. Zbl1090.05049
- [3] J. Beck, Achievements games and the probabilistic method, in: Combinatorics, Paul Erdős is Eighty, Bolyai Soc. Math. Stud. 1 (1993) 51-78.
- [4] R. Diestel, Graph Theory (Springer, 1996).
- [5] P. Erdős, R.J. Faudree, C.C. Rousseau and R.H. Schelp, The size Ramsey number, Period. Math. Hungar. 9 (1978) 145-161, doi: 10.1007/BF02018930. Zbl0331.05122
- [6] E. Friedgut, V. Rödl, A. Ruciński and P. Tetali, Random graphs with a monochromatic triangle in every edge coloring: a sharp threshold, Memoirs of the AMS, to appear. Zbl1087.05052
- [7] E. Friedgut, Y. Kohayakawa, V. Rödl, A. Ruciński and P. Tetali, Ramsey games against a one-armed bandit, Combinatorics, Probability and Computing 12 (2003) 515-545, doi: 10.1017/S0963548303005881. Zbl1059.05093
- [8] R.L. Graham, T. Łuczak, V. Rödl and A. Ruciński, Ramsey properties of families of graphs, J. Combin. Theory (B) 86 (2002) 413-419, doi: 10.1006/jctb.2002.2136. Zbl1031.05084
- [9] J.A. Grytczuk, M. Hałuszczak and H.A. Kierstead, On-line Ramsey Theory, Electr. J. Combin. (Sep 9, 2004), # R57. Zbl1057.05058
- [10] E. Györi, B. Rothschild and A. Ruciński, Every graph is contained in a sparsest possible balanced graph, Math. Proc. Cambr. Phil. Soc. 98 (1985) 397-401, doi: 10.1017/S030500410006360X. Zbl0582.05048
- [11] R.L. Graham, B. Rothschild and J.H. Spencer, Ramsey Theory (2nd ed., Wiley, 1990).
- [12] S. Janson, T. Łuczak and A. Ruciński, Random Graphs (Wiley, 2000), doi: 10.1002/9781118032718.
- [13] M. Krivelevich, Bounding Ramsey numbers through large deviation inequalities, Random Strutures Algorithms 7 (1995) 145-155, doi: 10.1002/rsa.3240070204. Zbl0835.05047
- [14] A. Kurek, Arboricity and star arboricity of graphs, in: Proc. of 4th Czechoslovak Symposium on Combinatorics, Graphs and Complexity (1992) 171-173, doi: 10.1016/S0167-5060(08)70624-1. Zbl0762.05036
- [15] A. Kurek, The density of Ramsey graphs (Ph.D. Thesis, AMU, 1997), in Polish.
- [16] A. Kurek and A. Ruciński, Globally sparse vertex-Ramsey graphs, J. Graph Theory 18 (1994) 73-81. Zbl0790.05027
- [17] R.D. Luce and H. Raiffa, Games and Decisions (Wiley, 1957). Zbl0084.15704
- [18] T. Łuczak, A. Ruciński and B. Voigt, Ramsey properties of random graphs, J. Combin. Theory (B) 56 (1992) 55-68, doi: 10.1016/0095-8956(92)90006-J. Zbl0711.05041
- [19] C. Payan, Graphes equilibres at arboricite rationalle, Europ. J. Combin. 7 (1986) 263-270.
- [20] S. Radziszowski, Small Ramsey Numbers, Electron. J. Combin. Dynamic Survey DS1 (38pp).
- [21] F.P. Ramsey, On a problem of formal logic, Proc. London Math. Soc. 30 264-286, doi: 10.1112/plms/s2-30.1.264. Zbl55.0032.04
- [22] V. Rödl and A. Ruciński, Lower bounds on probability thresholds for Ramsey properties, in: Combinatorics, Paul Erdős is Eighty (Vol. 1), Keszthely (Hungary), Bolyai Soc. Math. Studies (1993) 317-346. Zbl0790.05078
- [23] A. Ruciński, From random graphs to graph theory: Ramsey properties (extended abstract), Graph Theory Notes of New York XX (1991) 8-16.
- [24] A. Ruciński, From random graphs to graph theory (survey paper), in: Quo Vadis, Graph Theory?, Annals of Discrete Math. 55 (1993) 265-274.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.