组合数学 (Spring 2014)/Problem Set 3: Difference between revisions
imported>Etone No edit summary |
imported>Etone |
||
| (8 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
<font size=3 color=red>注意：这次作业时间只有一周。</font> | |||
==Problem 1 == | ==Problem 1 == | ||
(Erdős-Lovász 1975) | |||
Let <math>\mathcal{H}\subseteq{V\choose k}</math> be a <math>k</math>-uniform <math>k</math>-regular hypergraph, so that for each <math>v\in V</math> there are ''exact'' <math>k</math> many <math>S\in\mathcal{H}</math> having <math>v\in S</math>. | |||
Use the probabilistic method to prove: For <math>k\ge 10</math>, there is a 2-coloring <math>f:V\rightarrow\{0,1\}</math> such that <math>\mathcal{H}</math> does not contain any monochromatic hyperedge <math>S\in\mathcal{H}</math>. | |||
== Problem 2 == | |||
(Frankl 1986) | |||
Let <math>\mathcal{F}\subseteq {[n]\choose k}</math> be a <math>k</math>-uniform family, and suppose that it satisfies that <math>A\cap B \not\subset C</math> for any <math>A,B,C\in\mathcal{F}</math>. | |||
* Fix any <math>B\in\mathcal{F}</math>. Show that the family <math>\{A\cap B\mid A\in\mathcal{F}, A\neq B\}</math> is an anti chain. | |||
* | * Show that <math>|\mathcal{F}|\le 1+{k\choose \lfloor k/2\rfloor}</math>. | ||
==Problem | == Problem 3 == | ||
( | Given a graph <math>G(V,E)</math>, a ''matching'' is a subset <math>M\subseteq E</math> of edges such that there are no two edges in <math>M</math> sharing a vertex, and a ''star'' is a subset <math>S\subseteq E</math> of edges such that every pair <math>e_1,e_2\in S</math> of distinct edges in <math>S</math> share the same vertex <math>v</math>. | ||
Prove that any graph <math>G</math> containing more than <math>2(k-1)^2</math> edges either contains a matching of size <math>k</math> or a star of size <math>k</math>. | |||
== Problem 4 == | |||
Let <math>n\le 2k</math> and let <math>\mathcal{F}\subseteq{[n]\choose k}</math> be a <math>k</math>-uniform family such that <math>A\cup B\neq [n]</math> for all <math>A,B\in\mathcal{F}</math>. Show that <math>|\mathcal{F}|\le\left(1-\frac{k}{n}\right){n\choose k}</math>. | |||
Latest revision as of 23:58, 14 May 2014
注意：这次作业时间只有一周。
Problem 1
(Erdős-Lovász 1975)
Let [math]\displaystyle{ \mathcal{H}\subseteq{V\choose k} }[/math] be a [math]\displaystyle{ k }[/math]-uniform [math]\displaystyle{ k }[/math]-regular hypergraph, so that for each [math]\displaystyle{ v\in V }[/math] there are exact [math]\displaystyle{ k }[/math] many [math]\displaystyle{ S\in\mathcal{H} }[/math] having [math]\displaystyle{ v\in S }[/math].
Use the probabilistic method to prove: For [math]\displaystyle{ k\ge 10 }[/math], there is a 2-coloring [math]\displaystyle{ f:V\rightarrow\{0,1\} }[/math] such that [math]\displaystyle{ \mathcal{H} }[/math] does not contain any monochromatic hyperedge [math]\displaystyle{ S\in\mathcal{H} }[/math].
Problem 2
(Frankl 1986)
Let [math]\displaystyle{ \mathcal{F}\subseteq {[n]\choose k} }[/math] be a [math]\displaystyle{ k }[/math]-uniform family, and suppose that it satisfies that [math]\displaystyle{ A\cap B \not\subset C }[/math] for any [math]\displaystyle{ A,B,C\in\mathcal{F} }[/math].
- Fix any [math]\displaystyle{ B\in\mathcal{F} }[/math]. Show that the family [math]\displaystyle{ \{A\cap B\mid A\in\mathcal{F}, A\neq B\} }[/math] is an anti chain.
- Show that [math]\displaystyle{ |\mathcal{F}|\le 1+{k\choose \lfloor k/2\rfloor} }[/math].
Problem 3
Given a graph [math]\displaystyle{ G(V,E) }[/math], a matching is a subset [math]\displaystyle{ M\subseteq E }[/math] of edges such that there are no two edges in [math]\displaystyle{ M }[/math] sharing a vertex, and a star is a subset [math]\displaystyle{ S\subseteq E }[/math] of edges such that every pair [math]\displaystyle{ e_1,e_2\in S }[/math] of distinct edges in [math]\displaystyle{ S }[/math] share the same vertex [math]\displaystyle{ v }[/math].
Prove that any graph [math]\displaystyle{ G }[/math] containing more than [math]\displaystyle{ 2(k-1)^2 }[/math] edges either contains a matching of size [math]\displaystyle{ k }[/math] or a star of size [math]\displaystyle{ k }[/math].
Problem 4
Let [math]\displaystyle{ n\le 2k }[/math] and let [math]\displaystyle{ \mathcal{F}\subseteq{[n]\choose k} }[/math] be a [math]\displaystyle{ k }[/math]-uniform family such that [math]\displaystyle{ A\cup B\neq [n] }[/math] for all [math]\displaystyle{ A,B\in\mathcal{F} }[/math]. Show that [math]\displaystyle{ |\mathcal{F}|\le\left(1-\frac{k}{n}\right){n\choose k} }[/math].