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

Abstract

top
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 ) = m a x F ⊆ G | E ( F ) | / | V ( F ) | and define the Ramsey density m i n f ( 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 i n f ( 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 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 ) ≤ 2 k 2 k - 2 k - 1 , but leave unanswered the question if R̅(k;2) = o(R²(k;2)).

How to cite

top

Andrzej 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. [1] N. Alon, C. McDiarmid and B. Reed, Star arboricity, Combinatorica 12 (1992) 375-380, doi: 10.1007/BF01305230. 
  2. [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. [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. [4] R. Diestel, Graph Theory (Springer, 1996). 
  5. [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. [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. [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. [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. [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. [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. [11] R.L. Graham, B. Rothschild and J.H. Spencer, Ramsey Theory (2nd ed., Wiley, 1990). 
  12. [12] S. Janson, T. Łuczak and A. Ruciński, Random Graphs (Wiley, 2000), doi: 10.1002/9781118032718. 
  13. [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. [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. [15] A. Kurek, The density of Ramsey graphs (Ph.D. Thesis, AMU, 1997), in Polish. 
  16. [16] A. Kurek and A. Ruciński, Globally sparse vertex-Ramsey graphs, J. Graph Theory 18 (1994) 73-81. Zbl0790.05027
  17. [17] R.D. Luce and H. Raiffa, Games and Decisions (Wiley, 1957). Zbl0084.15704
  18. [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. [19] C. Payan, Graphes equilibres at arboricite rationalle, Europ. J. Combin. 7 (1986) 263-270. 
  20. [20] S. Radziszowski, Small Ramsey Numbers, Electron. J. Combin. Dynamic Survey DS1 (38pp). 
  21. [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. [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. [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. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.