Combinatorics - Chapter 2 - Ideas of Proofs

Question 1

idea of proof for proposition 2.4. winning for breaker => drawing for strong

Answer 1

• Since S is a winning strategy for breaker it ensures maker will not claim all the elements of any winning set regardless of makers strategy.
• It follows that if player 2 follows S in the strong game (X,F) then player 1 will never claim all the elements of any winning set A∈F.
• Thus the strong game will end in a draw or player 2 will win thus S is a drawing strategy for player 2 in the strong game (X,F)

Question 2

idea of proof for theorem 2.6. no winning strategy for player 2 in strong game. (strategy stealing)

Answer 2

1. suppose the contrary: player 2 has a winning strategy S in the strong game (X,F).
2. Using S we will define a new strategy S’ for player 1:
   - in player 1s first move, they must claim an arbitrary element
   - in any other round player 1 follows player 2s strategy S pretending to be player 2, pretending x is still available
   - Whenever S informs player 1 to claim x (or any other already claimed element) player 1 claims another arbitrary unclaimed board element and then pretends this element is unclaimed
3. It remains to show this is a winning strategy for player 2. At some point player 1 will claim all the elements of some winning set before player 2.

Question 3

idea of proof for proposition 2.9. monochromatic A for all colourings => winning strategy for player 1 [strong game]

Answer 3

• suppose the contrary (player 1 does not have a winning strategy)
• By the corollary both players have drawing strategies
• colour X such that all elements claimed by player 1 are red and all elements claimed by player 2 are blue.
• since the game is a draw X cannot contain a monochromatic A∈F, contradicting our assumption.

Question 4

idea of proof for proposition 2.9. monochromatic A for all colourings => winning strategy for player 1 [maker-breaker game]

Answer 4

If breaker has a winning strategy in the maker-breaker game then we know player 2 has a drawing strategy in the strong game (X,F) a contradiction.

Question 5

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

Answer 5

1. divide board into 40x40 disjoint squares. Breaker will play each game in parallel.
2. show maker can’t win the 40x40 14-in-a-row game (breaker has a winning strategy, erdos selfridge)
3. check breaker can always claim an element in Sₓ,ᵧ if maker claims first (|Sₓ,ᵧ| is even).
4. By the pigeonhole principle notice that a win for maker in the unrestricted game corresponds to a 14-in-a-row in Sₓ,ᵧ which is impossible by point 2 => breakers win

Question 6

idea of proof for theorem 2.19. makers win => 2 spanning trees

Answer 6

Let S be a winning strategy for maker in the connectivity game on G.
By prop 2.7 maker also has a winning strategy S’ is they are player 1.
Now lets play the game where maker follows S and breaker follows S’.
Since S’ is a winning strategy for player 2 and S is a winning strategy for player 1 they both claim winning sets. Hence, they have both claimed separate trees.
These two trees are clearly edge disjoint.

Question 7

first step in proof of winning strategy for breaker => drawing strategy for player two

Answer 7

Since S is a winning strategy for breaker it ensures maker will not claim all the elements of any winning set regardless of makers strategy.

Question 8

first step in proof of no winning strategy for player 2 in the strong game

Answer 8

Assume for a contradiction player 2 has a winning strategy S.

Question 9

What type of proof is the proof of no winning strategy for player 2 in the strong game

Answer 9

Strategy Stealing Proof

Question 10

first step in proof of monochromatic A for all colourings => winning strategy for player 1

Answer 10

Assume for a contradiction that player 1 doesn’t have a winning strategy.

Question 11

Set up for Idea of proof for The unrestricted n-in-a-row maker-breaker game is breakers win for n≥40.

Answer 11

It suffices to show that the statement holds for n=40.
We split ℤ² into 40x40 disjoint squares. That is, ℤ²= union over (x,y)∈ℤ² of Sₓ,ᵧ. Where for every (x,y)∈ℤ² we have Sₓ,ᵧ = {(40x+i,40y+i): i,j∈[40]}.
Breaker will play the 40x40 14-in-a-row maker breaker game on Sₓ,ᵧ for each (x,y)∈ℤ² in parallel.

Question 12

How do we know the 40x40 14-in-a-row maker breaker game is breakers win

Answer 12

we can apply erdos selfride

Question 13

40 consecutive elements in ℤ² will intersect with how many Sₓ,ᵧ

Answer 13

• at most 2 Sₓ,ᵧ is the 40 in a row is horizontal/vertical.

- at most 3 Sₓ,ᵧ if the 40 in a row is diagonal.

Question 14

What game are we trying to show is makers win in proof of the unrestricted n-in-a-row maker-breaker game is breakers win for n≥40.

Answer 14

the unrestricted maker breaker game where a winning set in 40 consecutive grid elements in a row/column/diagonal.