Combinatorics Chapter 2 - defns or theorems Flashcards
Positional Game
A Positional Game (X,F) is a perfect information two player game in which
- X is a (usually finite) set called the board.
- F is a family of finite subsets of X called the winning set
- the two players take turns to claim previously unclaimed elements
Strong Game (X,F)
In a strong (X,F) the player who first claims all the elements of a winning set A∈F is the winner.
If neither player succeeds the game is a draw.
Maker-Breaker Game (X,F)
In a maker-breaker game (X,F) player 1 wins if they claim all the elements of a winning set A∈F is the winner. Otherwise player 2 wins. It is not possible to draw.
Breaker-Maker Game (X,F)
In a Breaker-Maker Game (X,F) player 2 wins if they claim all the elements of a winning set A∈F. Otherwise player 1 wins. It is not possible to draw.
Strategy for player 1
For player 1 in a positional game (X,F) is a function which, given any
- move number t≥1
- set R⊆X of size t-1 consisting of all board elements claimed so far by player 1
- set B⊆X|R of size t-1 consisting of all the board elements claimed so far by player 2
returns a free board element S(R,B)∈X(RUB) whichever player 1 should choose next.
Strategy for player 2
A strategy for player 2 in a positional game (X,F) is a function which given any
- t∈ℕ
- set R⊆X of size t claimed by player 1
- set B⊆X\R of size t-1 claimed by player 2
returns an unclaimed element S(R,B)∈X(RUB) which player 2 should claim next.
winning strategy
A strategy S is a winning strategy if the player following the strategy wins independent of the other player strategy.
drawing strategy
A strategy S is a drawing strategy if for some player following S then they will draw/win the game independent of the other players strategy.
proposition 2.4. winning strategy for breaker => for strong games
if s is a winning strategy for breaker in the maker breaker game (X,F) then S is a drawing strategy for player 2 in the strong game (X,F).
Zermelos Theorem
Let G be finite, perfect information two player game with no chance then exactly one of the following holds
(1) player 1 has a winning strategy for G. (G is a player 1 win)
(2) player 2 has a winning strategy for G. (G is a player 2 win)
(3) Both players have a drawing strategy for G. (G is a draw)
Theorem 2.6. (impossible to win in strong games)
For any finite set X and any family F of subsets of X there is no winning strategy for player 2 in the strong game (X,F).
proposition 2.7. winning strategy in breaker-maker and maker-breaker.
Let X be a finite set and F a family of subsets of X. If maker has a winning strategy in the breaker-maker game (X,F) the maker also has a winning strategy in the maker-breaker game.
corollary 2.8. results of strong games.
If X is a finite set and F is a family of subsets of X, then exactly one of the following holds
(1) player 1 has a winning strategy in the strong game (X,F)
(2) both players have drawing strategies in the strong game (X,F)
proposition 2.9. colouring for winning strategies.
Let X be a finite set and F a family of subsets of X. Suppose that every red/blue-colouring of X yields a monochromatic A∈F.
Then player 1 has a winning strategy in the strong game (X,F) and moreover maker has a winning strategy for the maker-breaker game (X,F).
Erdos-Selfridge Theorem
Let X be a set and let F be a family of subsets of X. If the sum of all A∈F of 2⁻|ᴬ| <1/2 then breaker has a wining strategy in a maker-breaker game (X,F)
n uniform
We say that F is n uniform if |A|=n for all A∈F
pairing strategy
Let X be a set and F be a family of subsets of X. Then, the pairing strategy for player 2 in the strong game (X,F) proceeds as follows:
preparation: Find distinct elements x₁,x₂,..,xₖ,y₁,y₂,…,yₖ with the property that each winning set A∈F there exits some i∈[k] such that xᵢ,yᵢ∈A
playing: Suppose that player 1 claims an element z and it is now player 2s turn. If z∈{xᵢ,yᵢ} for some i and {xᵢ,yᵢ}\z is unclaimed then player 2 claims the element {xᵢ,yᵢ}\z. Otherwise player 2 claims an arbitrary element.
By player in the described manner player 2 will always claim at least one element in each pair {xᵢ,yᵢ} for all i. Since each A∈F contains some pair {xᵢ,yᵢ}, player 2 claims at least one element in A∈F. Therefore player 1 cannot claim all the elements in some A∈F so so player 1 cannot win.
mxm n-in-a-row maker breaker game
An mxm n-in-a-row maker breaker game is the maker-breaker game (X,F) where
X=mxm square grid
F= all sets of n consecutive grid squares in a vertical, horizontal or diagonal line.
unrestricted mxm n-in-a-row maker breaker game
The unrestricted mxm n-in-a-row maker breaker game is the maker breaker game (X,F) where
X* = ℤ²
F* = {n consecutive grid elements in a horizontal, vertical or diagonal line}
proposition 2.18. unrestricted mxm n-in-a-row maker breaker game for n≥40
The unrestricted n-in-a-row maker-breaker game is breakers win for n≥40
Multigraph
A multigraph G is a graph G where each edge may appear multiple times. Loops are allowed.
connected
A graph is connected if every pair of vertices can be joined by a path.
spanning tree
A spanning tree is a minimal connected graph
connectivity game
Given a multigraph G, the connectivity game on G is the breaker-maker game (X,F) where
X= set of edges of G = E(G)
F = {edges that form a spanning tree in G}
Note: G is connected & there does not exists an edge in all the spanning trees (=> G has at least 2 spanning trees)
Theorem 2.19. Makers win => 2 spanning trees.
If maker has a winning strategy for the connectivity game on G, then G has 2 edge disjoint spanning trees.
Theorem 2.20. Lehmans. 2 spanning trees => makers win.
If a multigraph G has two edge disjoint spanning trees then maker has a winning strategy for the connectivity game on G.
