Combinatorics Ideas of Proofs Flashcards
1
Q
idea of proof for the increasing/decreasing subsequence of length s+1/t+1 in a sequence of n distinct real numbers n>st (PROOF 1)[piles]
(erdos szekeres lemma)
A
- consider the following algorithm
(1) put a₁ onto pile 1
(2) Assume that we have already organised elements a₁, a₂, … , aᵢ₋₁ into piles 1,2,..,r
(3) add aᵢ to a correct pile: Let j∈[r] be smallest such that aᵢ is greater than the top element of pile j. Put aᵢ on top of pile j. Other we put aᵢ onoto a new pile r+1.
(4) repeat until out of aᵢs - Note that at any point during the algorithm the element in each pile forms an increasing subsequence. If there exists a pile with s+1 elements, then we have an increasing subsequence of length s+1 as required.
- Now assume all piles have atmost s (st, we must have atleast t+1 piles. Repeat the following. Let aᵢₜ₊₁ be the top element of pile t+1. When aᵢₜ₊₁ is added it is smaller than all the top elements in piles 1,2,…,t. Let aᵢₜ be the top element of pile t at this point in time. Note aᵢₜ₊₁ < aᵢₜ and iₜ < iₜ₊₁. Repeating this we get an increasing subsequence of length t+1 as required.
2
Q
idea of proof for Schurs theorem
A
- Let n = Rₖ(3,3,…,3) and let c be any k colouring of [n]
- define a k-edge-colouring c’ of Kₙ with vertex set [n] as follows c’(ij) = c(j-i)
- by our definition of n we have that there exists a monochromatic K₃ in c’ (let p,q,r be the verticies of this)
- Note, c’(pq)=c’(rq)=c’(pr)
- Let x = q-p, y=r-q and z=r-p. Now by the definition of c’ we have that c(x)=c(y)=c(z) moreover x+y=(q-p)+(r-p)=q-r=z as required
3
Q
Idea of proof for R(sK₂, tK₂)=2s+t-1 [upper bound]
A
- proceed by induction on t
- for t=1 use prop 1.4.
- Let n=2s+t-1.
- If Kₙ is monochromatic then we can find a red sK₂ or a blue tK₂ easily.
- if some red edge xy and blue edge xz from a vertex x then we delete x,y,z.
- Then n-3 = R((s-1)K₂,(t-1)K₂) (just sub in and manipulate). So by induction hypothesis and combining with either xy or xz we get a red sK₂ r a blue tK₂ respectively.
4
Q
Idea of proof for R(sK₂, tK₂)=2s+t-1 [lower bound]
A
Consider a K₂ₛ₊ₜ₋₂ with vertex set [2s+t-2]. Colour the edge ij red if i,j⩽2s-1 otherwise colour it blue.
- can’t make a red sK₂ because not enough vertices (only 2s-1 but need 2s)
- Each blue edge must contain a vertex in [2s,2s+t-2] so a blue matching has at most |[2s,2s+t-2]| = t-1 edges. so no blue tK₂
5
Q
Idea of proof for R(ℓK₂, Kₜ) = 2ℓ + t -2 [upper bound]
A
- proceed by induction on ℓ.
- ℓ=1 holds by prop 1.4.
- if edges all blue we are done.
- if edge xy is red remove it. By induction hyp there is a red (ℓ-1)K₂ or a blue Kₜ. Combine with the red edge xy and we are done.
6
Q
Idea of proof for R(ℓK₂, Kₜ) = 2ℓ + t -2 [lower bound]
A
Consider a K₂ℓ₊ₜ₋₃ with vertex set [2ℓ+t-2]. Colour the edge ij red if i,j⩽2ℓ-1 otherwise colour it blue.
- can’t make a red ℓK₂ because not enough vertices (only 2ℓ-1 but need 2ℓ)
- can’t make a blue Kₜ because we can have atmost one edge in the set [2ℓ-1] so total of 1 + (2ℓ+t-3)-(2ℓ-1)=t-1 vetices which isnt enough.
7
Q
Idea of proof to show ramsey number for graphs are well defined.
A
Let s = |V(G)| and t=|V(H)|. Let n=R(s,t). By definition in Kₙ there exists a red Kₛ or a blue Kₜ and G is a subgraph of Kₛ and H is a subgraph of Kₜ.
8
Q
Idea of proof for R(t)>⌊2^(t/2)⌋
A
- Let n=⌊2^(t/2)⌋ (floor makes n an integer)
- By Erdos Theorem it suffices to show that (n choose t)*2^(1-(t choose 2))<1.
On the LHS: use the fact n(n-1)…(n-t-1)⩽nᵗ, sub in value for n, replace 1+t/2 with t-1 since t≥4, put as a product which will be < 1.
9
Q
Idea of proof 1. for Erdos Theorem. [random colouring]
A
- colour Kₙ red/blue uniformly, ranomly and independently.
- Let X be the number of monochromatic copies of Kₜ in this random edge-colouring. We would like to bound the expectation of X from above 𝔼(X).
- Fix a set of T vertices note that the probability that T induced a monochromatic Kₜ = 2*(1/2)^(t choose 2).
- Note that there are n choose t ways of choosing t vertices in Kₙ
- Hence 𝔼(X) = sum of the probabilities T induced a monochromatic Kₜ = (n choose t)*2^(1 - t choose 2) <1.
- Since x is an integer which is greater than 0 we have that 1 > 𝔼(X) = sum of i * probability X=i ≥ sum of probability X =i = sum of probability X>0
- So we have that with a positive probability our random colouring does not contain a monochromatic Kₜ
10
Q
Idea of proof for R(3,4)=9 [lower bound]
A
- need to show a red/blue-edge-colouring of K₈ without a red K₃ or a blue K₄
- Let the vertices of K₈ be [8] colour the edge ij blue if i-j≡±1, ±2 mod 8 and red otherwise.
- assume a red K₃ containing vertex 3. The other vertices must lie in {4,5,6} however these are all adjacent and joined with blue edges. a contradiction.
- assume a blue K₄ containing vertex 1. grouping vertices in {7,8,1,2,3} diagonally we see that a blue K₄ contains at most one vertex in {2,7} and one vertex in {3,8}. 4 = |blue K₄| = |V(K₄)∩{1}|+|V(K₄)∩{2,7}|+|V(K₄)∩{3,8}| <= 3 a contradiction
11
Q
Idea of proof for R(3,4)=9 [upperbound] case 3
A
- consider any red/blue-edge colouring of K₉
- case 3: Every vertex is incident to exactly 3 red edges and 5 blue edges. Count the number of red edges (3*9)/2 not an integer so contradiction and case 3 never happens.
12
Q
Idea of proof for R(3,4)=9 [upperbound] case 2
A
- consider any red/blue-edge colouring of K₉
- case 2: a vertex of K₉ which is incident with at least 6 blue edges. the complete graph induced on these incident vertices contains a red K₃ or a blue K₃ (R(3,3)=6). In the former case we are done. In the latter case pairing this blue K₃ with the original vertex we get a blue K₄.
13
Q
Idea of proof for R(3,4)=9 [upperbound] case 1
A
- consider any red/blue-edge colouring of K₉
- case 1: a vertex of K₉ incident with at least 4 red edges. If any pair of these incident vertices are red then we have a red K₃. If none are red then all are blue so they form a blue K₄.
14
Q
Idea of proof for existence of Rₖ(s₁,s₂,…,sₖ)
A
- proceed induction on k (no. colours)
- we know true for k<3.
- Let m = Rₖ₋₁(s₁,s₂,…,sₖ) and n= R₂(m,sₖ) (these exist by induction hyp and base case)
- consider any edge colouring c of Kₙ with colours c₁,c₂,..,cₖ
- define a new red/blue edge colouring c* of Kₙ where c*(e) = red is c(e)∈{c₁,c₂,..,cₖ₋₁} and blue otherwise.
- By def from n there exists a red Kₘ or a blue Kₛₖ .
- In latter case we are done.
- In former case by definition of m there exists a monochromatic copy of Kₛᵢ with colour cᵢ for some i∈[k-1].
15
Q
Idea of proof for proposition 1.7. R(s,t)⩽2²ᵗ⁻¹.
A
- Let n = 2²ᵗ⁻¹
- let x₁ be a vertex note x₁ is joined to n-1 = 2²ᵗ⁻¹ = 2²ᵗ⁻²+2²ᵗ⁻²-1 edges coloured red or blue
- by the pigeonhole principle, there exists N₁=2²ᵗ⁻² of the same colour c₁ joined to x₁
- Let V1 of size N1 be a vertex set such that for every y∈V1 x1y is coloured c1.
- Now repeat the argument in V1
- repeat 2t-1 times
- for j>i the edge xixj is coloured ci (*)
- We obtain a sequence of vertices xᵢ such that xᵢxj is either red or blue.
- By the pigeonhole principle there exists a monochromatic subsequence of xᵢ. It follows these vertices form a monochromatic copy of Kt.
16
Q
Idea of proof for corollary R(s,t)⩽(s+t-2 choose s-1)
A
- proceed by induction on s+t
- when min{s,t}⩽2 then it holds by proposition 1.4.
- by erdos szekeres theorem we have R(s,t)⩽R(s-1,t)+R(s,t-1)
- by the induction hypothesis
R(s,t) ⩽ (s+t-3 s-2) + (s+t-3 s-1) = (s+t-2 s-1)
where the last equality holds by the binomial identity.
17
Q
Idea of proof for erdos and szekeves.
A
- proceed by induction on s+t
- base case if min{s,t}⩽2 then R(s,t) exists by proposition 1.4.
- assume the statement holds for s,t
- Let p=R(s-1,t) and q=(s,t-1). Let n=p+q.It suffices to show there always exists a red Kₛ of a blue Kₜ.
- Let x be a vertex of Kₙ. Note x is incident with n-1=p+q-1 edges.
- Apply pigeonhole principle (and assume w.l.g 3 red edges_
- by def of p there is a blue Kₜ or a red Kₛ₋₁
- If there is a blue Kₜ we are done
- if there is a red Kₛ₋₁ then together with the red edges to x it forms a red kₛ
18
Q
idea of proof for R(3,3)=6 (upper bound)
A
UPPER BOUND
- Need to show all red/blue-edge-colourings of K₆ contain a monochromatic K₃.
- Let x be a vertex in V(K₆). x is incident to 5 edges and each edge is coloured red or blue.
- By the pigeonhole principle x is joined to at least 3 edges of either red or blue. w.l.g. let y₁,y₂,y₃ be vertices s.t. the edge xyᵢ is red.
- If yᵢyⱼ is red then x,yᵢ,yⱼ is a red K₃.
- If yᵢyⱼ is blue for all i,j then y₁,y₂,y₃ forms a blue K₃
- Thus R(3)⩽6.
19
Q
idea of proof for R(3,3)=6 (lower bound)
A
LOWER BOUND show a red/blue-edge-colouring of K₅ without a red K₃ or a blue K₃. Let V(K₅)=[5]. For distinct i,j∈[5} colour the edge ij red if j-i≡±1mod5 and blue otherwise. Both the red and blue subgraphs are cycles of length 5 edges. Hence there is no monochromatic K₃. Thus R(3)>5
20
Q
idea of pigeonhole principle proof
A
- suppose the contrary for a contradiction (ie suppose for each i in 1 up to k there are at most sᵢ numbers of colour cᵢ)
- otherwise n = sum over i in 1 up to k of the number of numbers with colour cᵢ which is less than or equal to the sum over i in 1 up to k of sᵢ < n
21
Q
Set up for the lower bound of R(3,3,)=6
A
Let V(K₅) = [5] For distinct i,j∈[5] colour the edge ij red if j-i≡±1mod5 and blue otherwise.
22
Q
p in erdos szekeres theorem
A
p = R(s-1,t)
