Showing 2025 · cs.DMShow all
3 papers · 2 filters
cs.DM2025
4-uniform Maker-Breaker and Maker-Maker games are PSPACE-complete
Florian Galliot
We study two positional games played on hypergraphs, whose edges may be interpreted as winning sets. Two players take turns picking a previously unpicked vertex of the hypergraph.…
cs.DM2025
Maker-Maker games of rank 4 are PSPACE-complete
Florian Galliot, Jonas Sénizergues
The Maker-Maker convention of positional games is played on a hypergraph whose edges are interpreted as winning sets. Two players take turns picking a previously unpicked vertex, a…
cs.DM2025
A unified convention for achievement positional games
Florian Galliot, Jonas Sénizergues
We introduce achievement positional games, a convention for positional games which encompasses the Maker-Maker and Maker-Breaker conventions. We consider two hypergraphs, one red a…