# 组合数学 (Fall 2016)/Problem Set 4

Jump to navigation Jump to search

## 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|\ge \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}|\le 1+{k\choose \lfloor k/2\rfloor} }$.

## Problem 4

Let $\displaystyle{ n\le 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}|\le\left(1-\frac{k}{n}\right){n\choose k} }$.