组合数学 (Fall 2017)/Problem Set 4

Problem 1

Prove the following independent set version of the Turan theorem:

• Let ${\displaystyle G(V,E)}$ be a graph of ${\displaystyle n=|V|}$ vertices and ${\displaystyle m=|E|}$ edges. ${\displaystyle G}$ must have an independent set ${\displaystyle S}$ of size ${\displaystyle |S|\geq {\frac {n^{2}}{2m+n}}}$.
1. Show that this theorem is a corollary to the Turan theorem for cliques.
2. Prove the theorem directly for the independent sets by the probabilistic method along with the Cauchy-Schwartz theorem, without using the Turan theorem.

Problem 2

(Matching vs. Star)

Given a graph ${\displaystyle G(V,E)}$, a matching is a subset ${\displaystyle M\subseteq E}$ of edges such that there are no two edges in ${\displaystyle M}$ sharing a vertex, and a star is a subset ${\displaystyle S\subseteq E}$ of edges such that every pair ${\displaystyle e_{1},e_{2}\in S}$ of distinct edges in ${\displaystyle S}$ share the same vertex ${\displaystyle v}$.

Prove that any graph ${\displaystyle G}$ containing more than ${\displaystyle 2(k-1)^{2}}$ edges either contains a matching of size ${\displaystyle k}$ or a star of size ${\displaystyle k}$.

(Hint: Learn from the proof of Erdos-Rado's sunflower lemma.)

Problem 3

(Frankl 1986)

Let ${\displaystyle {\mathcal {F}}\subseteq {[n] \choose k}}$ be a ${\displaystyle k}$-uniform family, and suppose that it satisfies that ${\displaystyle A\cap B\not \subset C}$ for any ${\displaystyle A,B,C\in {\mathcal {F}}}$.

• Fix any ${\displaystyle B\in {\mathcal {F}}}$. Show that the family ${\displaystyle \{A\cap B\mid A\in {\mathcal {F}},A\neq B\}}$ is an anti chain.
• Show that ${\displaystyle |{\mathcal {F}}|\leq 1+{k \choose \lfloor k/2\rfloor }}$.

Problem 4

Let ${\displaystyle n\leq 2k}$ and let ${\displaystyle {\mathcal {F}}\subseteq {[n] \choose k}}$ be a ${\displaystyle k}$-uniform family such that ${\displaystyle A\cup B\neq [n]}$ for all ${\displaystyle A,B\in {\mathcal {F}}}$. Show that ${\displaystyle |{\mathcal {F}}|\leq \left(1-{\frac {k}{n}}\right){n \choose k}}$.

Problem 5

An ${\displaystyle n}$-player tournament (竞赛图) ${\displaystyle T([n],E)}$ is said to be transitive, if there exists a permutation ${\displaystyle \pi }$ of ${\displaystyle [n]}$ such that ${\displaystyle \pi _{i}<\pi _{j}}$ for every ${\displaystyle (i,j)\in E}$.

Show that for any ${\displaystyle k\geq 3}$, there exists a finite ${\displaystyle N(k)}$ such that every tournament of ${\displaystyle n\geq N(k)}$ players contains a transitive sub-tournament of ${\displaystyle k}$ players. Express ${\displaystyle N(k)}$ in terms of Ramsey number.