Title: Daniel's Flashcards / Year 4 / Term 1 / Ramsey Theory

html: Theorem 1.1 (Ramsey’s Theorem for pairs). Assuming that:
- ℕ ( 2 ) are 2-coloured (i.e. c : ℕ ( 2 ) → { 1 , 2 }).
Then there exists M infinite monochromatic.
proof: Proof. Pick a 1 ∈ ℕ. Then there exists an infinite set A 1 such that c ( a 1 i ) = c 1 for all i ∈ A 1. Pick a 2 ∈ A 1 and find A 2 (infinite) such that c ( a 2 i ) = c 2 for all i ∈ A 2. Keep on doing this. We end up with a 1 < a 2 < a 3 < ⋯ < a k < ⋯ and A 1 ⊃ A 2 ⊃ ⋯ such that c ( a i j ) = c i for all j ∈ A i.
One colour appears infinitely many times c i 1 = c i 2 = ⋯ = c i k = ⋯ = e. Now note M = { a i 1 , a i 2 , a i 3 , … } is a monochromatic set. □
nothing: True

html: Theorem 1.2 (Ramsey’s Theorem for r-sets). Assuming that:
- ℕ ( r ) is finitely coloured.
Then there exists a monochromatic infinite set.
proof: Proof. r = 1 pigeonhole, r = 2 is Theorem 1.1. Prove this by induction.
Assume it is true for r − 1. Given c : ℕ ( r ) → [ k ], we must find M (infinite and monochromatic). Pick a 1 ∈ ℕ. Look at the r − 1 sets of ℕ ∖ { a 1 }. Define c ′ : ( ℕ ∖ { a 1 } ) ( r − 1 ) → [ k ] via c ′ ( F ) = c ( F ∪ { a 1 } ).
By induction there exists A 1 ⊆ ℕ ∖ { a 1 } such that c ′ is constant on it, say constantly equal to c 1.
Now pick a 2 ∈ A 1 and induce c ′ : ( A 1 ∖ { a 2 } ) ( r − 1 ) → [ k ] defined by c ′ ( F ) = c ( F ∪ { a 2 } ). By induction there exists A 2 ⊂ A 1 ∖ { a 2 } such that c ′ is constant on it, say equal to c 2.
Continuing this, we end up with a 1 , a 2 , … and sets A 1 , A 2 , … such that A i + 1 ⊂ A i ∖ { a i + 1 } with c ( F ∪ { a i } ) = c i for all F ⊂ A i + 1, | F | = r − 1.
Some colour must appear infinitely many times: say c i 1 = c i 2 = c i 3 = ⋯ = c. Check: M = { a i 1 , a i 2 , … } is monochromatic. □
nothing: True

html: Theorem 1.3 (Finite Ramsey). Assuming that:
- r ≥ 1, k ≥ 1, m ≥ 1
Then there exists n ∈ ℕ such that whenever [ n ] ( r ) is k-coloured, we can find a monochromatic set of size m.
proof: Proof. Suppose not. Then for each n we can find c n : [ n ] ( r ) → [ k ] with no monochromatic m-sets. Note that there are only finitely many ways to k-colour [ r ] ( r ). So infinitely many c n will agree on [ r ] ( r ). Pick A 1 such that for all n ∈ A 1,
c n | [ r ] ( r ) = d r : [ r ] ( r ) → [ k ] .
We can do the same on [ r + 1 ] ( r ) and produce some A 2 ⊂ A 1 such that c n | [ r + 1 ] ( r ) is constant on A 2.
Continuing this, we get ⋯ ⊂ A n ⊂ A n − 1 ⊂ ⋯ ⊂ A 1. They satisfy:
- (1) There is no monochromatic m-set for any d n : [ n ] ( r ) → [ k ] (because d n = c i | [ n ] ( r )).
- (2) These d n’s are nested: d j | [ i ] ( r ) = d i for j > i.
Finally: colour ℕ ( r ) via c ( F ) = d n ( F ), where n is any integer n ≥ max ⁡ F. One can see that this is well defined, and gives a contradiction to Theorem 1.2. □
nothing: True

html: Theorem 1.4 (Canonical Ramsey Theorem). Assuming that:
- ℕ ( 2 ) is coloured (possibly with an infinite number of colours)
Then there exists an infinite set M such that one of the following holds:
- (i) c is constant on M.
- (ii) c is injective on M.
- (iii) c ( { i , j } ) = c ( { k , l } ) if and only if i = k for i < j, k < l in M.
- (iv) c ( { i , j } ) = c ( { k , l } ) if and only if j = l, for all i < j, k < l.
proof: Proof. We colour an element { i < j < k < l } of ℕ ( 4 ) as follows: We say that it is red if c ( i j ) = c ( k l ), and blue otherwise.
By Ramsey’s Theorem for r-sets, there exists an infinite set M 1 that is monochromatic under this colouring.
- (1) Suppose M 1 is red. Then c is constant on M 1.
Let i < j, k < l. Pick m < n (in M 1) bigger than all 4. Then i < j < m < n hence c ( i j ) = c ( m n ). Also, k < l < m < n, so c ( k l ) = c ( m n ). So c is constant on M 1.
- (2) Now let’s assume M 1 is blue. So for i < j < k < l we have c ( i j ) ≠ c ( k l ). Next: colour M 1 ( 4 ) as follows: we will say that { i , j , k , l } is green if c ( i l ) = c ( j k ), and purple otherwise. By Ramsey’s Theorem for r-sets we can pick infinite M 2 ⊂ M 1 monochromatic.
We claim that M 2 cannot be green. This is because if M 2 is green, let i < j < k < l < m < n in M 2. Then:
  - { i < j < k < n } gives us that c ( i n ) = c ( j k )
  - { i < l < m < n } gives us that c ( i n ) = c ( l m )
But using these we get c ( j k ) = c ( l m ), which contradicts the fact that { i < j < k < l } is blue.
Therefore M 2 is purple: for i < j < k < l we have c ( i l ) ≠ c ( j k ).
Next we colour M 2 ( 4 ) as follows: { i < j < k < l } is orange if c ( i k ) = c ( j l ), and white otherwise. Again, by Ramsey’s Theorem for r-sets we can pick an infinite M 3 ⊂ M 2 such that it is monochromatic with respect to this colouring.
We claim that M 3 cannot be orange. If it is, then we again consider i < j < k < l < m < n:
  - { j < l < m < n } gives that c ( j m ) = c ( l n )
  - { i < j < k < m } gives that c ( j m ) = c ( i k )
Hence c ( i k ) = c ( l n ), which contradicts the fact that { i < j < l < n } is blue.
Therefore M 3 is white. This finally tells us (using earlier working) that given any pair disjoint edges, the colours must be different.
Now, we colour M 3 ( 3 ) via: { i < j < k } yellow if c ( i k ) = c ( j k ), and pink otherwise. By Ramsey’s Theorem for r-sets, there is an infinite M 4 ⊂ M 3 that is monochromatic.
We claim that M 4 is not yellow. If it is, then given i < j < k < l, we have c ( i j ) = c ( j k ) = c ( k l ), which contradicts blueness.
Thus for any i < j < k in M 4, we have c ( i j ) ≠ c ( j k ).
Finally: we colour M 4 ( 3 ) with 4 colours, with { i < j < k } coloured according to:
  - turquoise if c ( i j ) = c ( i k ) and c ( i k ) = c ( j k )
  - magenta if c ( i j ) = c ( i k ) and c ( i k ) ≠ c ( j k )
  - cyan if c ( i j ) ≠ c ( i k ) and c ( i k ) = c ( j k )
  - maroon if c ( i j ) ≠ c ( i k ) and c ( i k ) ≠ c ( j k )
By Ramsey’s Theorem for r-sets, there exists a monochromatic set M 5 ⊂ M 4. It cannot be turquoise because c ( i j ) = c ( j k ) contradicts M 4. Then:
  - magenta implies case (iii)
  - cyan implies case (iv)
  - maroon implies (ii), i.e. injective. □
nothing: True

html: Theorem 1.5. Assuming that:
- ℕ ( r ) abitrarily coloured
Then we can find an infinite set M and I ⊆ [ r ] such that for any x 1 < x 2 < ⋯ < x r in M, and y 1 < y 2 < ⋯ < y r in M we have c ( x 1 x 2 ⋯ x r ) = c ( y 1 y 2 ⋯ y r ) if and only if x i = y i for all i ∈ I.
proof: Proof. Exercise. Note that this proof is examinable (because the ideas are exactly the same as those in the previous theorem). □
cloze1: True

html: Definition 1.6 (Focused). Let A 1 , A 2 , … , A k be arithmetic progressions of length m. Say
A i = { a i , a i + d i , … , a i + ( m − 1 ) d i } .
We say that these arithmetic progressions are focused if a i + m d i = f for all i ∈ [ k ].
If we have a colouring of ℕ and A 1 , … , A k are focused arithmetic progressions if each A i is monochromatic but they all have different colours, then we call them colour-focused.
nothing: True

html: Theorem 1.7. Assuming that:
- ℕ is k-coloured
Then we can find a monochromatic arithmetic progression of length 3 (equivalently, for any k we find an n that works).
proof: Proof. Claim: For any r ≤ k there exists an n such that if [ n ] is k-coloured then either:
- there exists a monochromatic arithmetic progression of length 3
- there exists r colour-focused arithmetic progressions of length 2
The proof is by induction on r.
Base case r = 1 we can take n = k + 1, since 2 numbers will have the same colour.
Suppose the result is true for r − 1 and let n be an n that satisfies the property in the claim.
We will show that N = ( k 2 n + 1 ) 2 n works for r. Let c : [ ( k 2 n + 1 ) 2 n ] → [ k ] be a colouring. We will split the ground set into k 2 n + 1 blocks of length 2 n. Call the blocks B i.
If there exists a monochromatic arithmetic progression of length 3 in this colouring, then we are done. So assume not.
By the induction hypothesis, the first half of each B i has r − 1 colour-focused arithmetic progressions of length 2. Because | B i | = 2 n, each block also contains their focus.
For a set | M | = 2 n, there are exactly k 2 n ways to k-colour it. So there exists two blocks B p and B p + t that are identically coloured.
Let { a i , a i + d i } be the r − 1 colour-focused arithmetic progressions in B p. Then { a i + 2 n t , a i + d i + 2 n t } are the corresponding ones in B p + t. Let f be the focus in B p, so therefore f + n t is the focus in B p + t.
Now take { a i , a i + d i + 2 n t } for i ∈ [ r − 1 ], and { f , f + 2 n t }. Since a i + 2 d i = f, we have a i + 2 d i + 4 n t = f + 4 n t. So all r of these sequences are focused at f + 4 n t.
We know that { a i , a i + d i + n t } and { f , f + 2 n t } are monochromatic by the choice of B p, B p + t. Why colour focused? { a i , a i + 2 n t } have different colours by induction hypothesis. Also, because c was assumed to have no monochromatic arithmetic progression of length 3, the colours of { f , f + 2 n t } must be different to all the colours of the above r − 1 arithmetic progressions of length 2. Thus we have r colour-focused arithmetic progressions of length 2 in [ ( k 2 n + 1 ) 2 n ]. □
cloze1: True

html: Theorem 1.8 (Van der Waerden). Assuming that:
- k , m ∈ ℕ
Then there exists an n ∈ ℕ such that whenever we k-colour [ n ] we can find a monochromatic arithmetic progression of length m.
proof: Proof. This will be by induction on m. For any k:
m = 1 is trivial.
m = 2 is pigeonhole.
m = 3 is Theorem 1.7.
Assume that this is true for some m − 1 fixed, but for any k. In other words, W ( k , m − 1 ) exists for all k ≥ 1.
Claim: For every r ≤ k there exists n such that we always have one of the following:
- have a monochromatic arithmetic progression of length m
- r colour-focused arithmetic progressions of length m − 1
When r = k we are done by looking at the focus. Now we prove the claim. We will prove it by induction on r.
For r = 1 we can take n = W ( k , m − 1 ).
Now assume that the result is true for r − 1 and that there does not exist a monochromatic arithmetic progression of length m. We will show that n works for r − 1, then W ( k 2 n , m − 1 ) 2 n will work for r.
Aim: whenever we k-colour [ W ( k 2 n , m − 1 ) 2 n ] we can find r colour-focused arithmetic progressions of length m − 1. Let B 1 = { 1 , 2 , … , 2 n }, B 2 = { 2 n + 1 , … , 4 n } etc, i.e. B i = [ 2 n ( i − 1 ) + 1 , 2 n i ] for i ∈ { 1 , … , W ( k 2 n , m − 1 ) }.
Let us look at the indices of these blocks. I colour i with k 2 n colours like so:
c ′ ( i ) = ( c ( 2 n ( i − 1 ) + 1 ) , c ( 2 n ( i − 1 ) + 2 ) , … , c ( 2 n i ) ) .
We therefore colour [ W ( k 2 n , m − 1 ) ] with k 2 n colours. By the definition of W, there exists a monochromatic arithmetic progression of length m − 1 (with respect to c ′). Say α , α + t , … , α + ( m − 2 ) t.
So the respective blocks B α , B α + 2 t , … , B α + ( m − 2 ) t are identically coloured. Look at B α. It has length 2 n, so by induction B α contains r − 1 colour-focused arithmetic progressions of length m − 1 together with their focus.
Let A i = { a i , a i + d i , … , a i + ( m − 2 ) d i } for i ∈ { 1 , … , r − 1 }. Let f be their focus. Look at B i = { a i , a i + d i + 2 n t , a i + 2 d i + 4 n t , … , a i + ( m − 2 ) d i + 2 ( m − 2 ) t }, i = 1 , … , r − 1.
They are monochromatic because the blocks are identically coloured and the B is are monochromatic. Since the colour of A i is the colour of B i and the A is are colour-focused, we must have that the B is have pairwise distinct colours.
Remember that the A is are are focused at f i and the colour of f i is different than the colour of all the A is. Note f i = a i + ( m − 1 ) d i.
Look at A = { f , f + 2 n t , 2 + 4 n t , … , f + 2 n ( m − 2 ) t }. This is an arithmetic progression of length m − 1 and monochromatic and of a different colour from all of the A is.
Enough to show a i + ( m − 1 ) ( d i + 2 n t ) = f + 2 n ( m − 1 ) t for all i, which is equivalent to a i + ( m − 1 ) d i = f, which is true as all the B is are focused at f. □
nothing: True

html: Theorem 1.9 (Strengthened Van Waerden). Assuming that:
- m , k ∈ ℕ
Then there exists n such that whenever [ n ] is k-coloured, there exists a monochromatic arithmetic progression of length m together with their common differences, i.e. the set { d , a , a + d , … , a + ( m − 1 ) d } is monochromatic.
proof: Proof. By induction on the number of colours. k = 1 is trivial.
Assume that the case for k − 1 colours is true. So there exists n that works for m and k − 1.
We will show that W ( k , n ( m − 1 ) + 1 ) works for m and k. If [ W ( k , n ( m − 1 ) + 1 ) are k-coloured, then there exists a monochromatic arithmetic progression (say red) of length n ( m − 1 ) + 1, say a , a + d , … , a + d n ( m − 1 ).
If any of d , 2 d , … , n d is red, then we are done: e.g. a , a + r d , … , a + r ( m − 1 ) d for some r ∈ [ n ].
If not, the set { d , 2 d , … , n d } is k − 1-coloured.. This involves a ( k − 1 ) colouring on [ n ], therefore there exist b , b + r , … , b + ( m − 1 ) r and r the same colour. This translates to d b , d b + r , … , d b + d ( m − 1 ) r , d r monochromatic. □
nothing: True

html: Definition 1.10 (Combinatorial line). A combinatorial line in X n is a set of the following form:
{ ( x 1 , … , x n ) ∈ X n : ∃ ⁡ I ⊆ [ n ] , a i ∈ X , I ≠ ∅ , x i = a i ∀ ⁡ i ∉ I , x i = x j ∀ ⁡ i , j ∈ I } .
nothing: True

html: Theorem 1.11 (The Hales-Jewett Theorem). Assuming that:
- m , k ∈ ℕ
Then there exists n such that whenever we k-colour [ m ] n there exists a monochromatic combinatorial line.
proof: Proof of The Hales-Jewett Theorem . The proof is by induction on the size of the alphabet, i.e. m.
m = 1 is trivially true.
Assume m ≥ 1 and assume H J ( m − 1 , k ) exists for all k.
Claim: for every 1 ≤ r ≤ k there exists nsuch that in [ m ] n
- (1) either there exists monochromatic combinatorial lines
- (2) there exists r colour-focused combinatorial lines
Then we are done by r = k and looking at the focus.
Now we prove the claim:
r = 1: look in [ m − 1 ] n ′ ⊂ [ m ] n We can take H J ( m − 1 , k ).
Now assume r > 1 and that n is suitable for r − 1. We will show that n + H J ( m − 1 , k m n ) is suitable for r. Let N = H J ( m − 1 , k m n ) for convenience.
Need: given c a k-colouring of [ m ] n + N with no monochromatic combinatorial lines, we can find r colour-focused combinatorial lines. Look at [ m ] n + N as [ m ] n × [ m ] N, with [ m ] n = { a 1 , … , a m n }.
Let us colour [ m ] N as follows:
c ′ : [ m ] N → k m n c ′ ( b ) = ( c ( a 1 , b ) , c ( a 2 , b ) , … , c ( a m n , b ) ) .
By The Hales-Jewett Theorem there exists a combinatorial lines L with active coordinates I such that
c ( a , b ) = c ( a , b ′ ) ∀ ⁡ a ∈ [ m ] n , ∀ ⁡ b , b ′ ∈ L ∖ { L + } .
But now this induces c ″ : [ m ] n → k where c ″ ( a ) = c ( a , b ) for any b ∈ L ∖ { L + }. By the definition of n, there exist r − 1 colour-focused combinatorial lines (for c ″) L 1 , L 2 , … , L r − 1, focused at f, and with active coordinates I 1 , I 2 , … , I r − 1.
Finally: look at the combinatorial lines that start at L i − × L − and active coordinates I i ∪ I. These give r − 1 combinatorial lines, and the combinatorial lines that starts at f × L − with active coordinates I. All focused at f × L +. Then done. □
nothing: True

html: Definition 1.14 (d-dimensional space). A d-dimensional space S ⊆ X n or a d-point parameter set is a set such that there exists I 1 , I 2 , … , I d ⊆ [ n ] disjoint and a i ∈ X ∀ ⁡ i ∈ [ n ] ∖ ( I 1 ∪ ⋯ ∪ I d ), and x ∈ S if and only if:
- x i = a i for all i ∈ [ n ] ∖ ( I 1 ∪ ⋯ ∪ I d )
- x i = x i if i , j ∈ I d for some l ∈ [ d ]
nothing: True

html: Theorem 1.15 (The Extended Hales-Jewett Theorem). Assuming that:
- m , k , d positive integers
Then there exists n such that whenever [ m ] n is k-coloured, there exists a d-point parameter set monochromatic.
proof: Proof. In X n ′ d = ( X d ) n ′ = Y n ′ what does a combinatorial line in Y n ′ look like?
So a monochromatic line in Y n ′ is a monochromatic d-point parameter set in X n ′ d.
Letting n = d H J ( m d , d ) works. □
nothing: True

html: Definition 1.16 (Homothetic copy). Let S be a finite set of points in X n. A homothetic copy of S is a set of the form x + λ S.
nothing: True

html: Theorem 1.17 (Gallai’s Theorem). Assuming that:
- finite S ⊂ ℕ d
- k-colouring of ℕ d
Then there exists a monochromatic homothetic copy of S.
proof: Proof. S = { S 1 , … , S m }. Let c : ℕ d → k be a colouring.
We colour [ m ] n (for n large enough) as follows:
c ′ ( ( x 1 , … , x n ) ) = c ( S x 1 + S x 2 + ⋯ + S x m ) .
By The Hales-Jewett Theorem, there exists a monochromatic combinatorial line in [ m ] n with active coordinates I. Then
c ( ∑ inactive S i + | I | S j )
has the same colour for all j ∈ [ m ].
Done as this is a copy of S translate by ∑ ⁡ inactive S i, and dilation factor | I |. □
nothing: True

html: Lemma 2.3. Assuming that:
- λ ∈ ℚ
Then for any finite colouring of ℕ, there exists a monochromatic solution to x + λ y = z.
proof: Proof. If λ = 0 then nothing to show.
If λ < 0 then z − λ y = x, so these are equivalent.
Assume λ > 0, λ = r s, r , s ∈ ℕ.
Seek solution to x + r s = z. Let c : ℕ → [ k ] be a finite colouring. Prove this by induction on k.
k = 1 trivial.
Assume this is true for k − 1 and we want to show it for k. Assume n is suitable for k − 1. We show that W ( k , n r + 1 ) n s is suitable for k.
We now have [ W ( k , n r + 1 ) ] k-coloured. There exists a monochromatic arithmetic progression of length n r + 1, say a , a + d , … , a + d n r of colour red. Let us look at d i s, where i ∈ [ n ]. Note d i s ≤ W ( k , n r + 1 ) n s, so “it is in our set of coloured numbers”.
If d i s is also red, then a , a + i r d , d i s is a monochromatic solution.
If no such d i s exists, then { d s , 2 d s , … , n d s } is k − 1 coloured. So there exists i , j , k such that c ( i d s ) = c ( j d s ) = c ( k d s ) and i + λ j = k. Then d s i + λ d s j = d s k, i.e. d s i , d s j , d s k is a monochromatic solution. □
cloze1: True

html: Theorem 2.4 (Rado’s Theorem for single equation). Assuming that:
- ( a 1 , … , a n ) ∈ ℚ n
Then it is partition regular if and only if it has the column property.
proof: Proof. We saw in Proposition 2.2 that if it is partition regular then it has the column property.
For the other direction, we know that ∑ ⁡ i ∈ I a i = 0 and we need to show that given c : ℕ → [ k ] such that there exists monochromatic ( x 1 , … , x n ) such that ∑ ⁡ a i x i = 0.
Fix i 0 ∈ I and we “cook up” the following vector:
x i = { x if i = i 0 y if i ∉ I z if i ∈ I ∖ { i 0 }
Need x , y , z monochromatic such that ( ∑ ⁡ i ∉ I a i ) y + x a i 0 + ( ∑ i ∈ I ∖ { i 0 } a i ) z = 0, which is the same as requiring x a i 0 − z a i 0 + ( ∑ ⁡ i ∉ I a i ) y = 0.
Upon dividing by a i 0, we see that this is the same as
x + ( ∑ i ∉ I a i a i 0 ) y = z ,
which is true by Lemma 2.3. □
nothing: True

html: Proposition 2.5. Assuming that:
- A a matrix with entries in ℚ
- A is partition regular
Then A has the column property.
proof: Proof. Let C 1 , … , C n be its columns. Fix p prime.
Colour ℕ as we did before, by c ( x ) = e ( x ). By assumption there exists monochromatic x 1 such that ∑ ⁡ i x i C i = 0.
Let us partition C 1 , … , C n as B 1 ⊔ B 2 ⊔ ⋯ ⊔ B l where i , j ∈ B k if and only if t ( x i ) = t ( x j ), i ∈ B k 1, j ∈ B k 2 for k 1 < k 2 if and only if t ( x i ) < t ( x j ).
We do this for infinitely many p. Because there exist finitely many partitions, for infinitely many primes p we will have the same blocks.
- For B 1: ∑ ⁡ i x i C i = 0, say all have colour d, i.e. e ( x i ) = d ∈ [ 1 , … , p − 1 ]. Then ∑ ⁡ d C i ≡ 0 ( mod p ) (by collecting the right-most terms in base p). Since this holds for infinitely many p, we have that ∑ ⁡ i ∈ B i C i = 0 ( mod p ) for infinitely many primes (the large primes), and hence we have that ∑ ⁡ i ∈ B i C i = 0.
- ∑ ⁡ i ∈ B k ′ p t d C i + ∑ i ∈ B 1 , … B k ′ − 1 x i C i ≡ 0 ( mod p t + 1 ).
Then ∑ ⁡ i ∈ B k p t C i + ∑ i ∈ B 1 , … , B k ′ − 1 x i ( d ) − 1 C i ≡ 0 ( mod p t + 1 ) (∗).
Claim: ∑ ⁡ i ∈ B k C i ∈ span ⁡ i ∈ B 1 ∪ ⋯ ∪ B k − 1 ⟨ C i ⟩.
We will show that given U such that U ⋅ C i = 0 got sll i ∈ B 1 , … , B k − 1. Then
u ⋅ ( ∑ i ∈ B k C i ) = 0
which finishes the proof as this implies ∑ ⁡ i ∈ B k C i ∈ span ⁡ i ∈ B 1 ∪ ⋯ ∪ B k − 1 ⟨ C i ⟩. Take the inner product of (∗) with u. Get
p t ∑ i ∈ B k u ⋅ C i ≡ 0 ( mod p t + 1 ) ,
which is equivalent to ∑ ⁡ i ∈ B k u ⋅ C i ≡ 0 ( mod p ). Since this happens for infinitely many p, we get ∑ ⁡ i ∈ B k u ⋅ C i = 0. □
cloze1: True

html: Theorem 2.6. Assuming that:
- m , p , c in ℕ
- a finite colouring of ℕ
Then there exists a monochromatic ( m , p , c )-set.
proof: Proof. By the above remark, it is enough to find a ( k ( m − 1 ) + 1 , p , c )-set set such that each row is monochromatic.
Let n be large enough (enough in order to apply everything to follow). Let A 1 = { c , 2 c , … , c ⌊ n c ⌋ }. By Van der Waerden, there exists a monochromatic arithmetic progression of length 2 n 1 + 1, with n 1 is large enough.
R 1 = { c x 1 − n 1 d 1 , c x 1 − ( n 1 − 1 ) d 1 , … , c x 1 n 1 d 1 }
has colour k 1. Let M = m ( k − 1 ) + 1. Now we restrict attention to
B 1 = { d 1 , 2 d 1 , … , ⌊ n ( M − 1 ) p ⌋ d 1 } .
Observe that c x 1 + λ 1 b 1 + λ 2 b 2 + ⋯ + λ M − 1 b M − 1 where b i ∈ B i, λ i ∈ [ − p , p ] is in R 1 for any λ i ∈ [ − p , p ] and any b 1 , … , b M − 1. Thus has colour k 1.
Next: look inside B 1:
A 2 = { c d 1 , 2 c d 1 , … , ⌊ n 1 ( M − 1 ) p c ⌋ c d 1 } .
Apply Van der Waerden to find an arithmetic progression of length 2 n 2 + 1, of colour k 2. Let
R 2 = { c x 2 − n 2 d 2 , c x 2 − ( n 2 − 1 ) d 2 , … , c x 2 + n 2 d 2 } ,
of colour k 2, and let
B 2 = { d 2 , 2 d 2 , … , ⌊ n 2 ( M − 2 ) p 2 ⌋ d 2 } .
Note that for any b 1 , … , b M − 2 and λ 1 , … , λ M − 2 ∈ [ − p , p ]. Then
c x 2 + λ 1 b 1 + ⋯ + λ M − 2 b M − 2
is in R 2, thus has colour k 2.
Keep on doing this M times. Restrict to M generators (by setting some λ to 0). □
cloze1: True

html: Proposition 2.8. Assuming that:
- A has the column property
Then there exists m , p , c such that any ( m , p , c )-set contains a solution to A y = 0.
proof: Proof. Let C 1 , … , C n be the columns of A. Then there exists B 1 ⊔ B 2 ⊔ ⋯ ⊔ B r a partition of [ n ] such that
∑ i ∈ B k C i ∈ span ⁡ ℚ ( C i : i ∈ B 1 ∪ ⋯ ∪ B k − 1 ) .
For all k, we have
∑ i ∈ B k C i = ∑ i ∈ B 1 ∪ ⋯ ∪ B k − 1 q i k C i
with q i k ∈ ℚ.
For each k, let
d i k = { 0 if i ∉ B 1 ∪ ⋯ ∪ B k 1 if i ∈ B k − q i k if i ∈ B 1 ∪ ⋯ ∪ B k − 1
Rewriting the above we get
∑ i = 1 n d i k C i = 0
for all k. We will take m = r. Let x 1 , … , x r be some integers. Let y i = ∑ ⁡ k = 1 r d i k x k.
Claim ( y 1 , … , y n ) ⊤ ⁡ is a solution, i.e. ∑ ⁡ i = 1 n y i C i = 0. Indeed:
∑ i = 1 n y i C i = ∑ i − 1 n ∑ k = 1 r d i k x k C i = ∑ k = 1 r ∑ i = 1 n d i k x k C i = ∑ k = 1 r x k ( ∑ i = 1 n d i k C i ⏟ = 0 ) = 0
Look at y i = ∑ ⁡ k = 1 n d i k x k. Have d i k ∈ ℚ. Let c be the common denominator of all the q i ks. Then
c y i = ∑ k = 1 n c d i k ⏟ ∈ ℕ x k
Also have that c y is a solution. Our c (for the ( r , p , c )-set) is indeed the common denominator of the q i k, and p = c ⋅ max ⁡ | numerators |. □
cloze1: True

html: Theorem 2.9 (Consistency Theorem). Assuming that:
- A and B two matrices that are partition regular
Then
( A 0 0 B )
is partition regular.
proof: Proof. Trivial check of column property. □
nothing: True

html: Theorem 2.10. Assuming that:
- ℕ finitely coloured
Then a colour class contains solutions to all partition regular equations.
proof: Proof. ℕ = C 1 ⊔ C 2 ⊔ ⋯ ⊔ C k. Assume for all C i that there exists A i that is partition regular, but has no solution in C i. Look at
( A 1 0 ⋯ 0 0 A 2 ⋯ 0 ⋮ ⋮ ⋱ ⋮ 0 0 ⋯ A k ) .
This is partition regular too, hence it has a monochromatic solution of colour say C t. Then A t has a solution in C t, contradiction. □
cloze1: True

html: Theorem 2.11 (Hindman’s Theorem). Assuming that:
- ℕ is finitely coloured
Then there exists infinitely many ( x n ) n ≥ 1 such that
FS ⁡ ( X 1 ) : = { ∑ i ∈ I x i : ∅ ≠ I ⊆ ℕ , I finite }
is monochromatic.
proof: Proof.
- ⇐ If I try to extend U by adding in some A ∉ U, then since A c ∈ U, we would also have to have A ∩ A c ∈ U, which violated one of the properties of being a filter.
- ⇒ Suppose U is an ultrafilter and there exists A such that A , A c are not in U.
By maximality, if A is not in U then there exists B ∈ U such that A ∩ B = ∅. Indeed, suppose not. Then
F ′ = { S : S ⊇ A ∩ B for some B ∈ U }
extends it (the only way this can fail to be a filter is if ∅ ∈ F ′, which would require a B such that A ∩ B = ∅).
Then B ⊆ A c, so A c ∈ U, contradicting the initial assumption. □
nothing: True

html: Proposition 2.13. Assuming that:
- F a filter
Then there exists an ultrafilter U extending F ′.
proof: Proof. By Zorn’s lemma, it is enough to show that any chain of filters extending F has an upper bound.
Let ( F i ) i ∈ I be a chain of filters containing F, i.e. for all i ≠ j either F i ⊆ F j or F j ⊆ F i. Let F = ⋃ ⁡ i ∈ I F i. Need to show F is a filter:
- (1) ∅ ∉ F since ∅ ∉ F i for each i.
- (2) If A ∈ F and A ⊆ B then A ∈ F i for some i, and then we have B ∈ F i for this same i (as F i is a filter), so B ∈ F.
- (3) If A , B ∈ F then say A ∈ F i, B ∈ F j. Since ( F i ) is a chain, we can suppose without loss of generality that F i ⊆ F j. Then A , B ∈ F j, so A ∩ B ∈ F j ⊆ F, so A ∩ B ∈ F.
and also clearly F extends F. So F is an upper bound. □
cloze1: True

html: Proposition 2.15. Assuming that:
- U an ultrafilter
- p , q statements
Then
- (i) ∀ ⁡ U x , ( p ( x ) and q ( x ) ) if and only if ∀ ⁡ U x , p ( x ) and ∀ ⁡ U x , q ( x )
- (ii) ∀ ⁡ U x , ( p ( x ) or q ( x ) ) if and only if ∀ ⁡ U x , p ( x ) or ∀ ⁡ U x , q ( x )
- (iii) ∀ ⁡ U x , p ( x ) is false if and only if ∀ ⁡ U x , ¬ ⁡ p ( x )
proof: Proof. Let A = { x : p ( x ) }, B = { x : q ( x ) }.
- (i) A ∩ B ∈ U if and only if A ∈ U and B ∈ U
- (ii) A ∪ B ∈ U if and only if A ∈ U or B ∈ U
- (iii) A ∉ U if and only if A c ∈ U □
cloze1: True

html: Lemma 3.2. Assuming that:
- X ⊂ ℝ n Ramsey
- Y ⊂ ℝ m Ramsey
Then X × Y ⊂ ℝ n + m is also Ramsey.
proof: Proof. Let k be a colouring of S × T, where S is k-Ramsey for X and T is k | S |-Ramsey for T.
We k | S |-colour T as follows:
c ″ ( t ) = ( c ( s 1 , t ) , c ( s 2 , t ) , … , c ( s | S | , t ) ) .
By choice of T, there exists a monochromatic Y ′ (copy of Y) with respect to c ′, i.e. c ( s , y ) = c ( s , y ′ ) for all y , y ′ ∈ Y and any s ∈ S.
Now k-colour S via c ″ ( s ) = c ″ ( s , y ) for some y ∈ Y ′ (which is well-defined by the above). By the choice of X, there exists monochromatic X ′ with respect to c ″, and hence X ′ × Y ′ is monochromatic with respect to c. □
cloze1: True

html: Theorem 3.6. Assuming that:
- X is Ramsey
Then X is spherical.
proof: Proof. Suppose X is not spherical. Then there exists c i (not all 0) such that ∑ ⁡ i ∥ x i ∥ 2 = b and ∑ ⁡ i c i = 0.
Also true for any copy of X ′.
Going to split [ 0 , 1 ) into [ 0 , δ ) , [ δ , 2 δ ) , … for small δ. Then colour depending on where c i ∥ x ∥ 2 lies.
Let’s prove that there is a colouring of ℝ such that ∑ ⁡ i = 1 n c i y i = b does not have a monochromatic solution. Let ∑ ⁡ i = 1 n − 1 c i ( y i − y n ) = b. By rescaling, we may assume b = 1 2. Now we split [ 0 , 1 ) into intervals [ 0 , δ ) , [ δ , 2 δ ) , … where δ is very small. Let
c ( y ) = ( interval where { c 1 y } is , interval where { c 2 y } is , … ) .
A ( ⌊ 1 δ ⌋ ) n − 1-colouring.
Assume y 1 , … , y n − 1 monochromatic under c and such that ∑ ⁡ c i ( y i − y n ) = 1 2.
Hence the sum is within ( n − 1 ) δ of an integer, so not 1 2, if δ small enough. □
cloze1: True

html: Proposition 3.7 (Our product argument). Assuming that:
- X ⊆ ℝ d
- A ⊆ X
- ∀ ⁡ k , ∃ ⁡ a finite S ⊆ ℝ e such that whenever S is k-coloured, there exists a copy of X that is constant on A
Then for all n , k, there exists S ′ finite such that whenever S ′ is k-coloured there exists a copy of X n that is A-invariant.
proof: Proof. (Yawn, product argument…)
We will by induction on n (and all k at once).
n = 1 is just the assumption.
Suppose true for n − 1. Fix k. Let S be a finite set such that whenever S is k | X | coloured, there exists an A-invariant copy of X n − 1.
T a finite set such that whenever T is k | S |-coloured, there exists a copy of X with A monochromatic.
Claim: S × T works for X n.
By definition of T, if we look at c ′ ( s , t ) = ( c ( s 1 , t ) , c ( s 2 , t ) , … , c ( s | S | , t ) ), a k | S |-colouring. Thus there exists a copy of X with A monochromatic.
This induces a colouring of S as follows: c ″ ( s ) = ( c ( s , a ) , c ( s , x 1 ) , … , c ( s , x | X | − | A | ) ) for some a ∈ A (note c ( s , a ) is well-defined). This is a k | X | − | A | + 1-colouring.
Therefore by the choice of n, there exists a copy of X n − 1 that is A-invariant.
Then we are done as this copy of X in T is A-invariant. □
nothing: True