4 Assignment 4

4.1 Problem 1.

Proposition 1

if $T (n) = T (n / 3) + T (2 n / 3) + n$ then $T (n) = O (n \log n)$

Proof ▼

using induction, my induction hypothesis will be

T (n) \leq C n \log n, \forall n < N, 0 < C

Now we get that

\begin{aligned} T (n) & = T (\frac{n}{3}) + T (\frac{2 n}{3}) + n \\ \leq C \frac{n}{3} \log \frac{n}{3} + C \frac{2 n}{3} \log \frac{2 n}{3} + n \\ \leq C \frac{n}{3} \log n - C \frac{n}{3} \log 3 + C \frac{n}{3} \log n - C \frac{2 n}{3} \log \frac{3}{2} + n \\ \leq C n \log n - C \frac{n}{3} \log 3 - C \frac{2 n}{3} \log \frac{3}{2} + n \\ \leq^{(*)} C n \log n \end{aligned}

(31) imply the induction hypothesis, and (34) will hold by choosing $C$ s.t

n \leq C \frac{n}{3} \log 3 + C \frac{2 n}{3} \log \frac{3}{2}

Hence for any $n \geq 1$ we can choose $C$ such that

C \geq \frac{1}{\frac{1}{3} \log 3 + \frac{2}{3} \log \frac{3}{2}} \approx 1.578

We get that

T (n) = O (n \log n)

Proposition 2

if $T (n) = 2 T (n / 2) + n \log n$ then $T (n) = O (n \log^{2} n)$ .

Proof ▼

using induction, my induction hypothesis will be

T (n) \leq C n \log^{2} n, \forall n < N, 0 < C

for $n = 2$

\begin{aligned} T (2) & = 2 T (\frac{2}{2}) + 2 \log 2 \\ \leq 2 C + n \log n \\ = O (n \log^{2} n) \end{aligned}

Hence for any $n \geq 2$

\begin{aligned} T (n) & = 2 T (n) + n \log n \\ \leq 2 \log^{2} (\frac{n}{2}) \frac{n}{2} + n \log n \\ = O (n \log^{2} n) \end{aligned}

(39) holds since $n > \frac{n + 1}{2}$

Proposition 3

Let $c_{1}, \dots, c_{k}$ be k positive reals satisfying $\sum_{i = 1}^{k} c_{i} < 1$ . if $T (n) = \sum_{i = 1}^{k} T (c_{i} n) + n$ then $T (n) = O (n)$ .

Proof ▼

by induction, my induction hypothesis will be

T (n) \leq C n, \forall n < N, 0 < C

Its immediate that $T (0) \leq 0$ now lets

\begin{aligned} T (n) & = \sum_{i = 1}^{k} T (c_{i} n) + n \\ \leq \sum_{i = 1}^{k} C (c_{i} n) + n \\ \leq C n (\sum_{i = 1}^{k} c_{i} + \frac{1}{C}) \\ \leq^{(*)} C n \end{aligned}

(42) imply the induction hypothesis, and (44) will hold by choosing $C$ s.t

C \geq \frac{1}{1 - \sum_{i = 1}^{k} c_{i}}

Hence for any $n \geq 1$ (44) holds and we get that

T (n) = O (n)

4.2 Problem 2.

Theorem

Every tournament has a Hamilton path

Proof 1 ▼

Let $T = (V, E)$ be tournament graph where $| V | = n$ . using strong induction for $n \leq 2$ its immediate that hamiltonian path exists. now lets assume its hold for any $k < n$ . lets choose some $v \in V$ and define 2 sets such that

V_{i n} = {u : \vec{(u, v)} \in E}, V_{o u t} = {u : \vec{(v, u)} \in E}

Since $| V_{i n} | < n, | V_{o u t} | < n$ by the induction hypothesis exists paths
$P_{i n} \in V_{i n}, P_{o u t} \in V_{i n}$ such that $P_{i n}$ and $P_{o u t}$ are hamiltonian paths. now the path $P_{i n} \to v \to P_{o u t}$ is hamiltonian path for all vertices
$| V_{i n} | \cup | v | \cup | V_{o u t} | = n$

Proof 2 ▼

First we can notice that $χ (T) =$ ¹ $n$ since any 2 vertex connected with an edge . Since $χ (T) \leq | P |$ where $P$ is the longest simple path in $T$ . on the other hand its can be at most $n$ since $T$ have $n$ vertex . we get that $| P | = n$ .

Hence since $P$ is simple path i.e its visit any vertex of the $T$ exactly once, and $P$ visit all the vertex or in other worlds $P$ is Hamilton path in $T$

4.3 Problem 3.

claim

Any set X of $s t + 1$ integers contains one of the following:

•: A subset $T = {x_{1}, \dots, x_{t + 1}} \subseteq X$ of size $t + 1$ such that $x_{k}$ divides $x_{k + 1}$ for every $1 \leq k \leq t$ .
•: A subset $S = {x_{1}, \dots, x_{s + 1}} \subseteq X$ of $s + 1$ integers such that $x_{i}$ does not divides $x_{j}$ for every $x_{i}, x_{j} \in S$ .

Proof ▼

Consider the following Poset define by

P = \footnote b y i n c u l d i n g $ ⟨ 0, 0 ⟩ $ a s w e l l {X, ⟨ x_{1}, x_{2} ⟩ : x_{1} | x_{2}}

Now lets look at $P$ over $X$ , first notice that when its have chain size $| t + 1 | \Rightarrow$ exists sequence of $x_{1} ⪯ \dots ⪯ x_{t + 1}$ such that $x_{1} | x_{2} \dots | x_{t + 1} \Rightarrow$ exist $T \subseteq X$ .
on the other hand if $P$ over $X$ , have anti-chain size $| s + 1 | \Rightarrow$ exist sequence of $x_{1} ⋠ \dots ⋠ x_{s + 1}$ such that $x_{1} ∤ x_{2} ∤ \dots ∤ x_{s + 1} \Rightarrow$ exist $S \subseteq X$ . Since

ω (X) α (X) \geq ω (X) \frac{| X |}{X (X)} \geq \footnote M i r s k y | X |

its following that splinting $X$ into $X (X)$ anti-chains, one of them will be at size $\frac{| X |}{X (X)}$ . if $α (X) \geq s + 1$ then $S \subseteq X$ , else $α (X) \leq s$ and

ω (X) \geq \frac{| X |}{α (X)} \leq \frac{s t + 1}{s} = t + \frac{1}{s}

and we get that $ω (X) \geq t + 1 \Rightarrow T \subseteq X$

4.4 Problem 4.

Consider the following Poset define by

P = {F, ⟨ S_{1}, S_{2} ⟩ : S_{1} \subseteq S_{2}}

where $F$ is collection $F = {S_{1}, \dots, S_{n}}$ of n sets.

Proposition 4

both chain and anti-chain of $P$ are union-free sets

Proof ▼

first by noticing that when its have chain $\Rightarrow$ exists sequence of $S_{1} ⪯ \dots ⪯ S_{k}$ such that $S_{1} \subseteq S_{2} \dots \subseteq S_{k}$ let mark this set of element as $S_{c h a i n}$ . lets assume that exsit some $S_{i}, S_{j}, S_{k} \in S_{c h a i n}$ s.t $S_{i} \cup S_{j} = S_{k}$ ,we can that hold only when $| S_{i} |, | S_{j} | \leq | S_{k} |$ but the Poset yield $S_{i} ⪯ S_{k}$ and $S_{j} ⪯ S_{k}$ hence $S_{i} = S_{k}$ or $S_{j} = S_{k}$ which lead to contradiction since $S_{c h a i n}$ is set.

Define $S_{a n t i - c h a i n}$ such that

S_{a n t i - c h a i n} = {S_{i}, S_{j} : S_{i} ⊈ S_{j} \land S_{j} ⊈ S_{i} s.t S_{i}, S_{j} \in F \forall i, j}

By assuming that exsit some $S_{i}, S_{j}, S_{k} \in S_{a n t i - c h a i n}$ s.t $S_{i} \cup S_{j} = S_{k}$ . its followed that $S_{i} \subseteq S_{k}$ but $S_{i} ⊈ S_{j}$ and we get an contradiction.

claim

every collection $F = {S_{1}, \dots, S_{n}}$ of n sets contains a sub-collection $S \subseteq F$ of at least $\sqrt{n}$ sets which is union-free

Proof ▼

let $α (P)$ be the longest $a n t i - c h a i n$ of $P$ over $F$ . If $α (P) \geq \sqrt{n}$ then exist such $S \in F$ . and if $α (P) < \sqrt{n}$

\frac{n}{ω (P)} = \frac{| F |}{ω (P)} \leq α (P) < \sqrt{n}

ω (P) \geq \sqrt{n}

And again by proposition 4 we get that exist such $S \in F$

4.5 Problem 5

claim

for a finite poset $P$ and let x, y be two elements of $P$ that are incomparable under $P$ . then $P$ has a linear extension in which $x < y$ .

Proof ▼

Let $P = (X, ⪯)$ be a finite partial order in which $x, y \in X$ are incomparable. now lets define new post $\hat{P} = (X, \hat{⪯})$

\hat{⪯} = {\begin{cases} w \hat{⪯} z & if w ⪯ z \\ w \hat{⪯} z & if z ⪯ y \land x ⪯ w \\ y \hat{⪯} x \end{cases}

•: $\hat{⪯}$ is reflexive since $⪯$ is reflexive
•: $\hat{⪯}$ is Transitive since $⪯$ is Transitive , and we apply apply only steps that respect the Transitive property of $⪯$
•: $\hat{⪯}$ is Anti-symmetric. consider $w \hat{⪯} z$ and $z \hat{⪯} w$ and let assume that $w \neq z$ . if $x = w$ or $y = w$ or $x = w, y = z$ its immediate lead to contradiction.
and when $w \hat{⪯} z \Rightarrow z ⪯ y \land x ⪯ w$ and $z \hat{⪯} w \Rightarrow w ⪯ y \land x ⪯ z$ then $x ⪯ z ⪯ y$ contradiction to the fact that $x, y$ are incomparable, hence $w \hat{⪯} z$ and $z \hat{⪯} w$ lead to $w = z$ ⁴

Hence $\hat{P}$ is poset where $x \hat{⪯} y$ and its contains less incomparable pairs than $⪯$ does. If $\hat{P}$ is linear then we done. otherwise exists some incomparable $w, z$ and we can extend $\hat{⪯}$ to ${\hat{⪯}}_{1}$ and follow the proses until we cover all the chains or get some ${\hat{⪯}}_{k}$ linear and respect $P$ where $x < y$

4.6 Problem 6

claim

in the setting of Arrow’s Theorem, if the individuals have only two options, then they can come up with a non-dictator social choice function.

Proof ▼

Lets proof that the democracy/majority voting system model satisfies the 3 condition of the Arrow’s Theorem when $N$ voters choose from $| {A, B} | = 2$ choices.

F : {S_{2}}^{N} \to \frac{\sum_{i}^{N} \mathds 1 [S_{i} choose A > B]}{N} i.e and indicator if S_{i} prefer A

if $F \geq \frac{1}{2}$ return $(A, B)$ else $(B, A)$
Monotonicity For two preference profiles $R = (R_{1}, \dots, R_{N})$ and $S = (S_{1}, \dots, S_{N})$ such that both profiles prefer $A > B$ but

0.5 < \frac{\sum_{i}^{N} \mathds 1 [S_{i} choose A > B]}{N} < \frac{\sum_{i}^{N} \mathds 1 [R_{i} choose A > B]}{N}

more people support $(A, B)$ and its yield that $F$ is monotone ⁵

Unanimity If alternative, $B < A$ for all orderings $R_{1}, \dots, R_{N},$ $R_{i} = (A, B) \forall i$ then $F (R_{1}, R_{2}, \dots, R_{N}) = (A, B)$ and $A$ is ranked strictly higher than $B$ by $F$ . its immediate from the way we construct $F$

0.5 < \frac{\sum_{i}^{N} \mathds 1 [R_{i} choose A > B]}{N}

Non-dictatorship There is no individual, i whose strict preferences always prevail consider the profile define

R = (R_{1}, R_{2}, \dots R_{N}) \forall i R_{i} = (A, B)

And

S = (S_{1}, S_{2}, \dots S_{N}) \forall i S_{i} = (B, A)

For the 2 given profiles there is no individual who can change the result. □