组合数学 (Spring 2014)/Problem Set 3: Difference between revisions
Jump to navigation
Jump to search
imported>Etone (Created page with "==Problem 1 == (Erdős-Lovász) 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</m…") |
imported>Etone No edit summary |
||
| Line 1: | Line 1: | ||
==Problem 1 == | ==Problem 1 == | ||
(Erdős-Lovász) | (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>. | 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 two 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>. | Use the probabilistic method to prove: For <math>k\ge 10</math>, there is a two 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>. | ||
Revision as of 08:02, 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 two 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].