Game saturation of intersecting families

Balázs Patkós; Máté Vizer

Open Mathematics (2014)

  • Volume: 12, Issue: 9, page 1382-1389
  • ISSN: 2391-5455

Abstract

top
We consider the following combinatorial game: two players, Fast and Slow, claim k-element subsets of [n] = 1, 2, …, n alternately, one at each turn, so that both players are allowed to pick sets that intersect all previously claimed subsets. The game ends when there does not exist any unclaimed k-subset that meets all already claimed sets. The score of the game is the number of sets claimed by the two players, the aim of Fast is to keep the score as low as possible, while the aim of Slow is to postpone the game’s end as long as possible. The game saturation numbers, gsatF(IIn,k) and gsatS(IIn,k), are the score of the game when both players play according to an optimal strategy in the cases when the game starts with Fast’s or Slow’s move, respectively. We prove that Ω k ( n k / 3 - 5 ) ⩽ g s a t F ( 𝕀 n , k ) , g s a t S ( 𝕀 n , k ) ⩽ O k ( n k - k / 2 ) .

How to cite

top

Balázs Patkós, and Máté Vizer. "Game saturation of intersecting families." Open Mathematics 12.9 (2014): 1382-1389. <http://eudml.org/doc/269668>.

@article{BalázsPatkós2014,
abstract = {We consider the following combinatorial game: two players, Fast and Slow, claim k-element subsets of [n] = 1, 2, …, n alternately, one at each turn, so that both players are allowed to pick sets that intersect all previously claimed subsets. The game ends when there does not exist any unclaimed k-subset that meets all already claimed sets. The score of the game is the number of sets claimed by the two players, the aim of Fast is to keep the score as low as possible, while the aim of Slow is to postpone the game’s end as long as possible. The game saturation numbers, gsatF(IIn,k) and gsatS(IIn,k), are the score of the game when both players play according to an optimal strategy in the cases when the game starts with Fast’s or Slow’s move, respectively. We prove that $\Omega _k (n^\{k/3 - 5\} ) \leqslant gsat_F (\mathbb \{I\}_\{n,k\} ),gsat_S (\mathbb \{I\}_\{n,k\} ) \leqslant O_k (n^\{k - \sqrt\{k/2\} \} )$.},
author = {Balázs Patkós, Máté Vizer},
journal = {Open Mathematics},
keywords = {Intersecting families of sets; Saturated families; Positional games; intersecting families of sets; saturated families; positional games},
language = {eng},
number = {9},
pages = {1382-1389},
title = {Game saturation of intersecting families},
url = {http://eudml.org/doc/269668},
volume = {12},
year = {2014},
}

TY - JOUR
AU - Balázs Patkós
AU - Máté Vizer
TI - Game saturation of intersecting families
JO - Open Mathematics
PY - 2014
VL - 12
IS - 9
SP - 1382
EP - 1389
AB - We consider the following combinatorial game: two players, Fast and Slow, claim k-element subsets of [n] = 1, 2, …, n alternately, one at each turn, so that both players are allowed to pick sets that intersect all previously claimed subsets. The game ends when there does not exist any unclaimed k-subset that meets all already claimed sets. The score of the game is the number of sets claimed by the two players, the aim of Fast is to keep the score as low as possible, while the aim of Slow is to postpone the game’s end as long as possible. The game saturation numbers, gsatF(IIn,k) and gsatS(IIn,k), are the score of the game when both players play according to an optimal strategy in the cases when the game starts with Fast’s or Slow’s move, respectively. We prove that $\Omega _k (n^{k/3 - 5} ) \leqslant gsat_F (\mathbb {I}_{n,k} ),gsat_S (\mathbb {I}_{n,k} ) \leqslant O_k (n^{k - \sqrt{k/2} } )$.
LA - eng
KW - Intersecting families of sets; Saturated families; Positional games; intersecting families of sets; saturated families; positional games
UR - http://eudml.org/doc/269668
ER -

References

top
  1. [1] Beck J., Combinatorial Games, Encyclopedia of Mathematics and its Applications, 114, Cambridge University Press, Cambridge, 2008 http://dx.doi.org/10.1017/CBO9780511735202 
  2. [2] Boros E., Füredi Z., Kahn J., Maximal intersecting families and affine regular polygons in PG(2, q), J. Combin. Theory Ser. A, 1989, 52(1), 1–9 http://dx.doi.org/10.1016/0097-3165(89)90057-5 Zbl0737.05003
  3. [3] Cranston D.W., Kinnersley W.B., O S., West D.B., Game matching number of graphs, Discrete Appl. Math., 2013, 161(13–14), 1828–1836 http://dx.doi.org/10.1016/j.dam.2013.03.010 
  4. [4] Dow S.J., Drake D.A., Füredi Z., Larson J.A., A lower bound for the cardinality of a maximal family of mutually intersecting sets of equal size, Congr. Numer., 1985, 48, 47–48 Zbl0648.05001
  5. [5] Erdős P., Ko C., Rado R., Intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser., 1961, 12, 313–318 http://dx.doi.org/10.1093/qmath/12.1.313 Zbl0100.01902
  6. [6] Ferrara M., Jacobson M., Harris A., The game of F-saturator, Discrete Appl. Math., 2010, 158(3), 189–197 http://dx.doi.org/10.1016/j.dam.2009.09.014 Zbl1226.05179
  7. [7] Fraenkel A.S., Combinatorial games, Electron. J. Combin., 2012, #DS2 
  8. [8] Füredi Z., On maximal intersecting families of finite sets, J. Combin. Theory Ser. A, 1980, 28(3), 282–289 http://dx.doi.org/10.1016/0097-3165(80)90071-0 
  9. [9] Füredi Z., Reimer D., Seress Á., Hajnal’s triangle-free game and extremal graph problems, Congr. Numer., 1991, 82, 123–128 Zbl0764.05043
  10. [10] Hefetz D., Krivelevich M., Stojakovic M., personal communication 
  11. [11] Hefetz D., Krivelevich M., Stojakovic M., Szabó T., Positional Games, Oberwolfach Seminars, 44, Birkhäuser, Basel, 2014 Zbl1314.91003
  12. [12] Kahn J., On a problem of Erdős and Lovász. II: n(r) = O(r), J. Amer. Math. Soc., 1994, 7(1), 125–143 Zbl0792.05080
  13. [13] Mehta N., Seress Á., Connected, bounded degree, triangle avoidance games, Electron. J. Combin., 2012, 18(1), #193 Zbl1229.05210
  14. [14] Meyer J.C., 23rd unsolved problem, In: Hypergraph Seminar, Lecture Notes in Math., 411, Springer, Berlin, 1974, 285–286 http://dx.doi.org/10.1007/BFb0066187 
  15. [15] Seress Á., On Hajnal’s triangle-free game, Graphs Combin., 1992, 8(1), 75–79 http://dx.doi.org/10.1007/BF01271710 Zbl0757.90096

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.