3 Assignment 3

3.1 Problem 1.

claim

There is an integer $n_{0}$ such that for any $n \geq 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_{i j}$ 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 \leq y \leq z \leq 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 $⌊ \log_{2} n ⌋$ 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_{i n} = {u : exsit edege v \leftarrow u}, v_{o u t} = {u : exsit edege v \to u}

Hence $| v_{i n} | + | v_{o u t} | = 2^{k + 1} - 1$ and one of them contain $| 2^{k} |$ edges, lets assume its $v_{i n}$ ² by our assumption its contains transitive tournament $T_{i n}$ size $| k |$ . now $T_{i n} \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{n}{2}) - (\binom{k}{2})}$ . hence if we show that

k! (\binom{n}{k}) 2^{(\binom{n}{2}) - (\binom{k}{2})} < 2^{(\binom{n}{2})}

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{array}{rcl} 2^{(\binom{n}{2})} & > & k! (\binom{n}{k}) 2^{(\binom{n}{2}) - (\binom{k}{2})} \\ 2^{(\binom{k}{2})} & > & k! (\binom{n}{k}) \\ > & k! \frac{n!}{k! (n - k)!} \\ > & n (n - 1) (n - 2) \dots (n - k + 1) \\ > & n^{k} \end{array}

Taking $\log_{2}$ from (3)(7)

\begin{array}{rcl} (\binom{k}{2}) & > & k \log_{2} (n) \\ \frac{k!}{2 (k - 2)!} & > & k \log_{2} (n) \\ \frac{k!}{k (k - 2)!} & > & 2 \log_{2} (n) \\ k - 1 & > & 2 \log_{2} (n) \\ k & > & 2 \log_{2} (n) + 1 \end{array}

3.3 Problem 3

claim

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

| E | \leq \frac{1}{2} (\sqrt{t - 1} n^{\frac{3}{2}} + n)

Proof ▼

W.L.O.G let $t \geq 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{array}{r} t (\binom{n}{2}) \geq \sum_{v \in V} (\binom{d (v)}{2}) \geq n (\binom{2 | E | / n}{2}) \end{array}

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{array}{r} n (\binom{2 | E | / n}{2}) = n \frac{(2 | E | / n) (2 | E | / n - 1)}{2} \geq n \frac{(2 | E | / n - 1)^{2}}{2} \end{array}

And

\begin{array}{r} t (\binom{n}{2}) = t \frac{n^{2} - n}{2} \leq t \frac{n^{2}}{2} \end{array}

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

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

3.4 Problem 4

claim

Let $S_{1}, \dots, S_{n} \in [n]$ such that $| S_{i} \cap S_{j} | \leq 1$ for all $1 \leq i < j \leq n$ then.

\frac{1}{n} \sum_{i = 1}^{n} | S_{i} | = O (\sqrt{n})

Proof ▼

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

S = {S_{i} : S_{i} \in [n]}, U = {i \in n} and E = {e_{S_{k}, m} : m \in S_{k}}, V = S \cup U

Its immediate $| V | = 2 n$ 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{array}{rcl} | E | & \leq & \frac{1}{2} (\sqrt{2 - 1} (2 n)^{\frac{3}{2}} + 2 n) \\ \sum_{i = 1}^{n} | S_{i} | & \leq & \sqrt{2} n^{\frac{3}{2}} + n \\ \frac{1}{n} \sum_{i = 1}^{n} | S_{i} | & \leq & \sqrt{2} \sqrt{n} + 2 \\ \frac{1}{n} \sum_{i = 1}^{n} | S_{i} | & = & O (\sqrt{n}) \end{array}

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 R^{n}$ and $f$ to be vector and weight function satisfying

\forall i 0 < x_{i} \leq 1, \sum_{i = 1}^{n} x_{i} = 1, f (x) = \sum_{i, j \in E} x_{i} x_{j}

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

\begin{array}{r} f (x) \geq \sum_{i, j \in E} \frac{1}{n^{2}} \geq \frac{| E |}{n^{2}} \end{array}

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{array}{rcl} f (x) & \leq & \sum_{i, j \in [T]} x_{i} x_{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{array}

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

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