# 组合数学 (Spring 2014)/Problem Set 3

## Problem 1

(Erdős-Lovász 1975)

Let ${\displaystyle {\mathcal {H}}\subseteq {V \choose k}}$ be a ${\displaystyle k}$-uniform ${\displaystyle k}$-regular hypergraph, so that for each ${\displaystyle v\in V}$ there are exact ${\displaystyle k}$ many ${\displaystyle S\in {\mathcal {H}}}$ having ${\displaystyle v\in S}$.

Use the probabilistic method to prove: For ${\displaystyle k\geq 10}$, there is a 2-coloring ${\displaystyle f:V\rightarrow \{0,1\}}$ such that ${\displaystyle {\mathcal {H}}}$ does not contain any monochromatic hyperedge ${\displaystyle S\in {\mathcal {H}}}$.

## Problem 2

(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 3

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}$.

## 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}}$.