On positional games |
| |
Authors: | József Beck |
| |
Institution: | Mathematical Institute of the Hungarian Academy of Sciences, Budapest, Realtanoda u.13–15, Hungary |
| |
Abstract: | Let {Ai} be a family of sets and let S = ∩iAi. By a positional game we shall mean a game played by two players on {Ai}. The players alternately pick elements of S and that player wins who fist has all the elements of one of the Ai. This paper deals with almost disjoint hypergraphs only, i.e., |Ai∪Aj| ? 1 if i ≠ j. Let be the smallest integer for which there is an almost disjoint n-uniform hypergraph , so that the first player has a winning strategy. It is shown that , which was conjectured by Erdös. The same method is applied to prove a conjecture of Hales and Jewett on r-dimensional tick-tack-toe if r is large enough. Finally we prove that for an arbitrary almost disjoint n-uniform hypergraph the second player has such a strategy that the first player unable to win in his mth move if m < (2 ? ?)n. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|