Combinatorics Chapter 2 - defns or theorems

Question 1

Positional Game

Answer 1

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

Question 2

Strong Game (X,F)

Answer 2

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.

Question 3

Maker-Breaker Game (X,F)

Answer 3

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.

Question 4

Breaker-Maker Game (X,F)

Answer 4

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.

Question 5

Strategy for player 1

Answer 5

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.

Question 6

Strategy for player 2

Answer 6

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.

Question 7

winning strategy

Answer 7

A strategy S is a winning strategy if the player following the strategy wins independent of the other player strategy.

Question 8

drawing strategy

Answer 8

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.

Question 9

proposition 2.4. winning strategy for breaker => for strong games

Answer 9

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).

Question 10

Zermelos Theorem

Answer 10

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)

Question 11

Theorem 2.6. (impossible to win in strong games)

Answer 11

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).

Question 12

proposition 2.7. winning strategy in breaker-maker and maker-breaker.

Answer 12

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.

Question 13

corollary 2.8. results of strong games.

Answer 13

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)

Question 14

proposition 2.9. colouring for winning strategies.

Answer 14

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).

Question 15

Erdos-Selfridge Theorem

Answer 15

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)

Question 16

n uniform

Answer 16

We say that F is n uniform if |A|=n for all A∈F

Question 17

pairing strategy

Answer 17

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.

Question 18

mxm n-in-a-row maker breaker game

Answer 18

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.

Question 19

unrestricted mxm n-in-a-row maker breaker game

Answer 19

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}

Question 20

proposition 2.18. unrestricted mxm n-in-a-row maker breaker game for n≥40

Answer 20

The unrestricted n-in-a-row maker-breaker game is breakers win for n≥40

Question 21

Multigraph

Answer 21

A multigraph G is a graph G where each edge may appear multiple times. Loops are allowed.

Question 22

connected

Answer 22

A graph is connected if every pair of vertices can be joined by a path.

Question 23

spanning tree

Answer 23

A spanning tree is a minimal connected graph

Question 24

connectivity game

Answer 24

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)

Question 25

Theorem 2.19. Makers win => 2 spanning trees.

Answer 25

If maker has a winning strategy for the connectivity game on G, then G has 2 edge disjoint spanning trees.

Question 26

Theorem 2.20. Lehmans. 2 spanning trees => makers win.

Answer 26

If a multigraph G has two edge disjoint spanning trees then maker has a winning strategy for the connectivity game on G.