Biased positional games on hypergraphs

Citation
D. Duffus et al., Biased positional games on hypergraphs, ST SCI M H, 34(1-3), 1998, pp. 141-149
Citations number
6
Categorie Soggetti
Mathematics
Journal title
STUDIA SCIENTIARUM MATHEMATICARUM HUNGARICA
ISSN journal
00816906 → ACNP
Volume
34
Issue
1-3
Year of publication
1998
Pages
141 - 149
Database
ISI
SICI code
0081-6906(1998)34:1-3<141:BPGOH>2.0.ZU;2-H
Abstract
Let G(p, q, H) be the game played on a hypergraph H by two players, who alt ernately choose p and q vertices, respectively. The object of the first pla yer is to claim all vertices of a hyperedge of H, while the second player t ries to prevent him from doing so. We give a sufficient, condition for the first player to win G(p,q, H) played on an r-uniform hypergraph H and argue that this condition is close to optimal. Furthermore, we answer a question of Galvin by proving that, the first player has a winning strategy in G(1, q, H) for each 3-uniform hypergraph H with chromatic number large enough.