Try Firefox if your web browser (e.g. Chrome, IE) does not support MathML, a part of HTML5.
Combinatorics: Problem Set 4
1 Problem 1
1.1
Recall the Turán theorem: if some graph $G(V,E)$ has no $r$clique, then $E\le \frac{r\u20132}{2(r\u20131)}{n}^{2}$. Here is the contrapositive theorem: if $E>\frac{r\u20132}{2(r\u20131)}{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({\scriptscriptstyle \begin{array}{c}n\\ 2\end{array}}\right)\u2013m$. Due to the contrapositive theorem, we have done if we can prove
$$\left(\begin{array}{c}n\\ 2\end{array}\right)\u2013m>\frac{r\u20132}{2(r\u20131)}{n}^{2}.$$ 
Since $m,n>0$,
$4{m}^{2}+4mn+{n}^{2}>0$  
$\iff $  ${({n}^{2}\u20132m\u2013n)}^{2}\u2013{n}^{2}({n}^{2}\u20134m\u20132n)>0$  
$\iff $  ${({n}^{2}\u20132m\u2013n)}^{2}>{n}^{2}({n}^{2}\u20134m\u20132n)$  
$\iff $  $n(n\u20131)\u20132m>{\displaystyle \frac{{n}^{2}\u20134m\u20132n}{{n}^{2}\u20132m\u2013n}}{n}^{2}$  $(2\left({\displaystyle \begin{array}{c}n\\ 2\end{array}}\right)>m)$  
$\iff $  $\left({\displaystyle \begin{array}{c}n\\ 2\end{array}}\right)\u2013m>{\displaystyle \frac{r\u20132}{2(r\u20131)}}{n}^{2}.$  $(r={\displaystyle \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.
$$\mathrm{Pr}[u\in S]=\frac{d!}{(d+1)!}=\frac{1}{d+1}.$$ 
By the linearity of expectation,
$$?[S]=\sum _{i\in V}\mathrm{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.
$$?[S]\ge \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\ge k$, we have done. Otherwise we can safely assume $M\le k\u20131$. Let $Y=\{v\in V\exists e\in M(e\text{is incident to}v)\}$. Then $Y=2M\le 2(k\u20131)$. 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\u20131)}^{2}}{2(k\u20131)}=k\u20131.$$ 
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)\le 2N(k\u20131).$$ 
Suppose we have an $n$player tournament where $n=2N(k\u20131)$. Take an arbitrary vertex $v$, and split $V\setminus \{v\}$ into two subset $S$ and $T$, where
$$  
$T=\{u\in V\setminus \{v\}u>v\}.$ 
Since $S+T+1=n=2N(k\u20131)$, we have either $S\ge N(k\u20131)$ or $T\ge N(k\u20131)$.
If $S\ge N(k\u20131)$. By induction hypothesis, there exists transitive tournament of size $(k\u20131)$ in $S$. Plusing the $v$ such that $$, there exists transitive tournament of size $k$ in $S\cup \{v\}$.
If $T\ge N(k\u20131)$. By induction hypothesis, there exists transitive tournament of size $(k\u20131)$ 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 twocolorings of ${K}_{n}$ and the universe of tournaments.
Given a twocoloring 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 twocoloring, then let $$, otherwise let $v>u$.
Obviously the mapping is injective. For all tournament, we can easily find the twocoloring 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)\ge {\delta}_{U}$, $\forall v\in V,d(v)\le {\mathrm{\Delta}}_{V}$, we have
${\delta}_{U}{U}^{\prime}\le {\mathrm{\Delta}}_{V}{V}^{\prime}$  
$\iff $  ${U}^{\prime}\le {\displaystyle \frac{{\mathrm{\Delta}}_{V}}{{\delta}_{U}}}{V}^{\prime}.$ 
Recall that ${\delta}_{U}\ge {\mathrm{\Delta}}_{V}$, we have ${U}^{\prime}\le {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},\mathrm{\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\ne 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\ne 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.
Combin.PS4 by himemeizhi is licensed under a Creative Commons AttributionShareAlike 4.0 International License.