# Game saturation of intersecting families

Open Mathematics (2014)

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

## Access Full Article

top## Abstract

top## How to cite

topBalá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] Beck J., Combinatorial Games, Encyclopedia of Mathematics and its Applications, 114, Cambridge University Press, Cambridge, 2008 http://dx.doi.org/10.1017/CBO9780511735202
- [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] 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] 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] 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] 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] Fraenkel A.S., Combinatorial games, Electron. J. Combin., 2012, #DS2
- [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] Füredi Z., Reimer D., Seress Á., Hajnal’s triangle-free game and extremal graph problems, Congr. Numer., 1991, 82, 123–128 Zbl0764.05043
- [10] Hefetz D., Krivelevich M., Stojakovic M., personal communication
- [11] Hefetz D., Krivelevich M., Stojakovic M., Szabó T., Positional Games, Oberwolfach Seminars, 44, Birkhäuser, Basel, 2014 Zbl1314.91003
- [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] Mehta N., Seress Á., Connected, bounded degree, triangle avoidance games, Electron. J. Combin., 2012, 18(1), #193 Zbl1229.05210
- [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] Seress Á., On Hajnal’s triangle-free game, Graphs Combin., 1992, 8(1), 75–79 http://dx.doi.org/10.1007/BF01271710 Zbl0757.90096