# Combin.PS4

My Solution for Combinatorics for the Fall 2015 semester, Problem Set 4. Keep your Academic Integrity plz.

# Combinatorics: Problem Set 4

Himemya

## 1 Problem 1

### 1.1

Recall the Turán theorem: if some graph $G(V,E)$ has no $r$-clique, then $|E|\leq\frac{r-2}{2(r-1)}n^{2}$. Here is the contrapositive theorem: if $|E|>\frac{r-2}{2(r-1)}n^{2}$, then the graph $G(V,E)$ has $r$-clique.

Now consider the complement graph $G^{\prime}(V,E^{\prime})$ of $G(V,E)$. Clearly, $G$ has an independent set of size $|S|$ if $G^{\prime}$ has a $|S|$-clique. Let $r=\frac{n^{2}}{2m+n}$, $|E^{\prime}|={\left({{n}\atop{2}}\right)}-m$. Due to the contrapositive theorem, we have done if we can prove

 ${\left({{n}\atop{2}}\right)}-m>\frac{r-2}{2(r-1)}n^{2}.$

Since $m,n>0$,

 $\displaystyle 4m^{2}+4mn+n^{2}>0$ $\displaystyle\iff$ $\displaystyle(n^{2}-2m-n)^{2}-n^{2}(n^{2}-4m-2n)>0$ $\displaystyle\iff$ $\displaystyle(n^{2}-2m-n)^{2}>n^{2}(n^{2}-4m-2n)$ $\displaystyle\iff$ $\displaystyle n(n-1)-2m>\frac{n^{2}-4m-2n}{n^{2}-2m-n}n^{2}$ $\displaystyle(2{\left({{n}\atop{2}}\right)}>m)$ $\displaystyle\iff$ $\displaystyle{\left({{n}\atop{2}}\right)}-m>\frac{r-2}{2(r-1)}n^{2}.$ $\displaystyle(r=\frac{n^{2}}{2m+n})$

### 1.2

We uniformly sample a permutation $\pi$ of $[n]$ at random. For each $v\in V$, if for all neighbor $v$ of $u\in V$ it holds that $\pi_{u}>\pi_{v}$, we include $v$ into the set $S$. Clearly $S$ will be an independent set.

Consider a vertex $u$ and its $d$ neighbors. There are $(d+1)!$ permutatoins for them, and only $d!$ permutatoin usch that $u$ is included into $S$, i.e.

 $\Pr[u\in S]=\frac{d!}{(d+1)!}=\frac{1}{d+1}.$

By the linearity of expectation,

 $\mathbf{E}[|S|]=\sum_{i\in V}\Pr[i\in S]=\sum_{i\in V}\frac{1}{d(i)+1}$

where $d(x)$ is the degree of the vertex $x$. Recall that $\sum_{i\in V}d(i)=2m$. The expectation will be minimized when $\forall v\in V,d(v)=2m/n$, i.e.

 $\mathbf{E}[|S|]\geq\sum_{i\in V}\frac{1}{\frac{2m}{n}+1}=\frac{n^{2}}{2m+n}.$

Therefore $G$ must have an independent set $S$ of size $\frac{n^{2}}{2m+n}$.
Thanks hint from Song Renjie.

### 1.3

The equality holds when the complement graph is Turán graph.

## 2 Problem 2

Let $M\subseteq E$ be the largest matching of $G$. If $M\geq k$, we have done. Otherwise we can safely assume $|M|\leq k-1$. Let $Y=\{v\in V|\exists e\in M(e\text{ is incident to }v\}$. Then $|Y|=2|M|\leq 2(k-1)$. Clearly any edge is incident to at least one vertex in $Y$, otherwise $M$ will not be the largest matching of $G$.

By the Pigeonhole Principle, some vertex $y\in Y$ must has degree of at least

 $\frac{|E|}{|Y|}>\frac{2(k-1)^{2}}{2(k-1)}=k-1.$

In another word, there is a star of size $k$.

## 3 Problem 3

### 3.1

We show that $N(k)$ is finite by induction on $k$. For the base case, it is easy to verify that

 $N(2)=2.$

For general $k$, we will show that

 $N(k)\leq 2N(k-1).$

Suppose we have an $n$-player tournament where $n=2N(k-1)$. Take an arbitrary vertex $v$, and split $V\setminus\{v\}$ into two subset $S$ and $T$, where

 $\displaystyle S=\{u\in V\setminus\{v\}|u $\displaystyle T=\{u\in V\setminus\{v\}|u>v\}.$

Since $|S|+|T|+1=n=2N(k-1)$, we have either $|S|\geq N(k-1)$ or $|T|\geq N(k-1)$.

If $|S|\geq N(k-1)$. By induction hypothesis, there exists transitive tournament of size $(k-1)$ in $S$. Plusing the $v$ such that $\forall u\in S,v, there exists transitive tournament of size $k$ in $S\cup\{v\}$.

If $|T|\geq N(k-1)$. By induction hypothesis, there exists transitive tournament of size $(k-1)$ in $T$. Plusing the $v$ such that $\forall u\in T,v>u$, there exists transitive tournament of size $k$ in $T\cup\{v\}$.

### 3.2

 $N(k)=R(k,k).$

We construct a bijective mapping between the universe of two-colorings of $K_{n}$ and the universe of tournaments.

Given a two-coloring of $K_{n}$, we construct a unique tournament. For any $u,v\in V$ such that $u$’s label is smaller that $v$’s, if $(u,v)$ is red in the two-coloring, then let $u, otherwise let $v>u$.

Obviously the mapping is injective. For all tournament, we can easily find the two-coloring which will be mapped to it. Thus the mapping is surjective. In conclusion, the mapping is bijective.

## 4 Problem 4

Consider any subset $U^{\prime}\subseteq U$ and their neighbors $V^{\prime}=\{v\in V|\exists u\in U^{\prime}(\exists(u,v)\in E)\}$. By counting the edges between the two sets, we have

 $\sum_{u\in U^{\prime}}d(u)=\sum_{v\in V^{\prime}}d(v)$

where $d(x)$ is the degree of vertex $x$. Since $\forall u\in U,d(u)\geq\delta_{U}$, $\forall v\in V,d(v)\leq\Delta_{V}$, we have

 $\displaystyle\delta_{U}|U^{\prime}|\leq\Delta_{V}|V^{\prime}|$ $\displaystyle\iff$ $\displaystyle|U^{\prime}|\leq\frac{\Delta_{V}}{\delta_{U}}|V^{\prime}|.$

Recall that $\delta_{U}\geq\Delta_{V}$, we have $|U^{\prime}|\leq|V^{\prime}|$. Due to the Hall’s theorem, there must be a matching in $G$ such that all vertices in $U$ are matched.

## 5 Problem 5

Let $U=\{S_{1},S_{2},\cdots,S_{n}\}$ be poset about the relation $\subset$. We claim two obviously facts:

• Fact 1.

any subset $\mathcal{F}\subseteq U$ satisfies that for any different $A,B,C\in\mathcal{F}$ we have $A\cup B\neq C$, if $\mathcal{F}$ is an antichain.

• Fact 2.

any subset $\mathcal{F}\subseteq U$ satisfies that for any different $A,B,C\in\mathcal{F}$ we have $A\cup B\neq C$, if $\mathcal{F}$ is a chain.

If the largest antichain of $U$ is larger than $\lfloor\sqrt{n}\rfloor$, due to the fact 1, we have done. Otherwise, by the Dilworth theorem, $U$ can be partitioned into at most $\lfloor\sqrt{n}\rfloor$ chains. Due to the Pigeonhole Principle, there is a chain which contains at least $\lceil\sqrt{n}\rceil$ sets. Due to the fact 2, we have done.