3 Assignment 3

3.1 Problem 1.

claim

There is an integer \(n_0\) such that for any \(n\ge n_0\), in every \(9\)-coloring of the integers \(\{ 1,2,3,\dots ,n\} \), one of the \(9\) color classes contains \(4\) integers \(a,b,c,d\) such that \(a+b+c=d\).

Proof ▼

based on Ramsay Theorem Let \(n_0=K(4,\dots ,4)\), where 4 appears \(k-1\) times. and lets \(c\) be \(r\)-colouring s.t:

\[ c:\{ 1,\dots ,n\} \to \{ 1,\dots , k\} \]

For graph \(K_n\) and labelling of its edge \(\{ 1,\dots ,n\} \). we can colour any edge \(e_{ij}\) with \(c(|i-j|)\). we got a \(k-1\)-colouring of \(K_n\). then for \(n_0\), we must have a \(K_4\) with all edges different. for vertices \(x\le y\le z \le w\) then

\[ a=y-x,b=z-y,c=w-z,d=w-x \]

Gives a solution

3.2 Problem 2.

claim

every tournament on n vertices, contains a transitive tournament on \(\lfloor \log _2 n \rfloor \) vertices.

Proof ▼

Using induction for \(n=0,1,2\) its holds on empty. W.L.O.G ¹ assume the claim holds for \(n\leq 2^k\) now lets look at some tournament on \(2^{k+1}\) vertices and we can pick any vertex \(v\), and define:

\[ v_{in}=\{ u : \text{ exsit edege } v\leftarrow u\} ,v_{out}=\{ u : \text{ exsit edege } v\rightarrow u\} \]

Hence \(|v_{in}|+|v_{out}|=2^{k+1}-1\) and one of them contain \(|2^k|\) edges, lets assume its \(v_{in}\) ² by our assumption its contains transitive tournament \(T_{in}\) size \(|k|\). now \(T_{in}\cup \{ v\} \) is sub tournament and any edge points to \(v\) hence its transitive tournament on \(|k+1|\) vertices.

claim

there exists a tournament on n vertices that does not contain a transitive tournament on \(2 \log _2 n + 2 \) vertices.

Proof ▼

The number of Tournament on \(n\) vertices is \(2^{\binom {n}{2}}\).The number of tournaments of size \(k\) is \(k!\), and there are \(\binom {n}{k}\) sets of size k, and the number of ways to choose the edges outside the transitive tournament is \({2^{\binom n2 - \binom k2}}\). hence if we show that

\[ k! \binom nk 2^{\binom n2 - \binom k2} {\lt} 2^{\binom n2} \]

its yield that for some \(k\) the number of n-vertex tournaments with a transitive subtournament on \(k\) vertices is smaller than the total number of tournaments.

\begin{eqnarray} 2^{\binom n2} & {\gt}& k! \binom nk 2^{\binom n2 - \binom k2} \\ 2^{\binom k2}& {\gt}& k! \binom nk \\ & {\gt}& k!\frac{n!}{k!(n-k)!} \\ & {\gt}& n(n-1)(n-2) \dotsm (n-k+1)\\ & {\gt}& n^k \end{eqnarray}

Taking \(\log _2\) from (3)(7)

\begin{eqnarray} {\binom k2} & {\gt}& k\log _2(n) \\ \frac{k!}{2(k-2)!}& {\gt}& k\log _2(n) \\ \frac{k!}{k(k-2)!}& {\gt}& 2\log _2(n)\\ k-1& {\gt}& 2\log _2(n)\\ k& {\gt}& 2\log _2(n)+1 \end{eqnarray}

3.3 Problem 3

claim

if an n-vertex graph \(G = (V, E)\) has no copy of \(K_{2,t}\) ³ then

\[ |E|\le {1\over 2}(\sqrt{t-1}n^{3\over 2}+n) \]

Proof ▼

W.L.O.G let \(t\ge 1\). we can distinguish that any \(e_1,e _2\in E\) have at most\(^3\) \(t\) neighbours. and each one of them can be part of pair. we can consider it as the number of path length 2 in \(G\). Let \(d(v_i)\) be the deg of \(v_i\in G\) and we get that:

\begin{eqnarray} t\binom n2\geq \sum _{v\in V} \binom {d(v)}{2}\geq n\binom {2|E|/n}{2} \end{eqnarray}

The right-hand side hold from Jensen’s Inequality and since its minimized ⁴ the binomial when all the degrees are equal, \(d_i = 2|E|/|V|.\)

\begin{eqnarray} n\binom {2|E|/n}{2}= n\frac{(2|E|/n)(2|E|/n-1)}{2}\ge n\frac{(2|E|/n-1)^2}{2} \end{eqnarray}

And

\begin{eqnarray} t\binom n2 = t\frac{n^2-n}{2}\le t\frac{n^2}{2} \end{eqnarray}

.We conclude from (13)(14)(15) that

\begin{eqnarray} n\frac{(2|E|/n-1)^2}{2} & \leq & t\frac{n^2}{2} \\ {(2|E|/n-1)^2}& \leq & tn \\ 2|E|/n& \leq & \sqrt{tn}+1 \\ |E|& \leq ^{3} & {1\over 2}(\sqrt{t}n^{3\over 2}+n) \end{eqnarray}

3.4 Problem 4

claim

Let \(S_1, \dots , S_n \in [n]\) such that \(|S_i \cap S_j | \le 1\) for all \(1 \le i {\lt} j \le n\) then.

\[ \frac{1}{n}\sum ^n_{i=1}|S_i|=O(\sqrt{n}) \]

Proof ▼

Let define \(G=(V,E)\) such that

\[ S=\{ S_i:S_i\in [n]\} ,U=\{ i\in n\} \text{ and } E=\{ e_{S_k,m}:m\in S_k \} , V =S\cup U \]

Its immediate \(|V|=2n\) and \(G\) is Bipartite since we can dived \(V\) into 2 disjoint independent sets \(S\) and \(U\), that is any \(e\in E\) connects a vertex in \(S\) to one in \(U\). hence \(G\) has no copy of \(K_{2,2}\), using Problem 3 we can get that

\begin{eqnarray} |E|& \le & {1\over 2}(\sqrt{2-1}(2n)^{3\over 2}+2n)\\ \sum ^n_{i=1}|S_i|& \le & \sqrt{2}n^{3\over 2}+n\\ {1\over n} \sum ^n_{i=1}|S_i|& \le & \sqrt{2}\sqrt{n}+2\\ \frac{1}{n}\sum ^n_{i=1}|S_i|& =& O(\sqrt{n}) \end{eqnarray}

3.5 Problem 5

Theorem

if \(G = (V, E)\) has no copy of \(K_{t+1}\) then \(|E|\leq (1-\frac{1}{t})\frac{n^2}{2}.\)
(Turan’s Theorem)

Proof ▼

Let \(x = (x_1, . . . , x_n) \in \mathbb {R}^n\) and \(f\) to be vector and weight function satisfying

\[ \forall i\text{ } 0 {\lt}x_i\leq 1,\sum ^n_{i=1} x_i = 1,f(x)=\sum _{i,j\in E} x_ix_j \]

By taking \(x = (\frac{1}{n},\dots , \frac{1}{n})\) we get

\begin{eqnarray} f(x)\geq \sum _{i,j\in E}\frac{1}{n^2}\geq \frac{|E|}{n^2}\end{eqnarray}

The “weight shifting” method yield to shift the weight between any neighbours \(x_i,x_j\) if \(e_{i,j} \notin E\).
We can notice that the sum is maximized when all the weight is concentrated on a clique. Since any shift is does not decrease the value of \(f\) we can repeat the processes. since \(G = (V, E)\) has no copy of \(K_{t+1}\) we can have at most \(t\) size clique ,let name it \([T]\). we can get lower bound on \(f\) :

\begin{eqnarray} f(x)& \leq & \sum _{i,j\in [T]}x_ix_j=\sum _{i,j\in [T]}\frac{1}{t^2} \\ & \leq & \frac{t(t-1)}{2}\frac{1}{t^2}\\ & \leq & (1-\frac{1}{t})\frac{1}{2} \end{eqnarray}

Combining (27) and (24) to finish the proof

\begin{eqnarray} \frac{|E|}{n^2}& \leq & (1-\frac{1}{t})\frac{1}{2}\\ |E|& \leq & (1-\frac{1}{t})\frac{n^2}{2} \end{eqnarray}