组合数学 (Fall 2019)/Problem Set 4: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>Etone
No edit summary
imported>Etone
Line 21: Line 21:


==Problem 4==
==Problem 4==
We color each non-empty subset of <math>[n]=\{1,2,\ldots,n\}</math> with one of the <math>r</math> colors in <math>[r]</math>. Show that for any finite <math>r</math> there is a finite <math>N</math> such that for all <math>n\ge </math>$, for any <math>r</math>-coloring of all non-empty subsets of <math>[n]</math>, there always exist <math>1\le i<j<k\le n</math> such that the intervals <math>[i,j)=\{i,i+1,\ldots, j-1\}</math>, <math>[j,k)=\{j,j+1,\ldots, k-1\}</math> and <math>[i,k)=\{i,i+1,\ldots, k-1\}</math> are all assigned with the same color by the <math>r</math>-coloring.
We color each non-empty subset of <math>[n]=\{1,2,\ldots,n\}</math> with one of the <math>r</math> colors in <math>[r]</math>. Show that for any finite <math>r</math> there is a finite <math>N</math> such that for all <math>n\ge N</math>, for any <math>r</math>-coloring of all non-empty subsets of <math>[n]</math>, there always exist <math>1\le i<j<k\le n</math> such that the intervals <math>[i,j)=\{i,i+1,\ldots, j-1\}</math>, <math>[j,k)=\{j,j+1,\ldots, k-1\}</math> and <math>[i,k)=\{i,i+1,\ldots, k-1\}</math> are all assigned with the same color by the <math>r</math>-coloring.

Revision as of 05:39, 11 December 2019

Problem 1

(Matching vs. Star)

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].

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

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

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

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

Problem 4

We color each non-empty subset of [math]\displaystyle{ [n]=\{1,2,\ldots,n\} }[/math] with one of the [math]\displaystyle{ r }[/math] colors in [math]\displaystyle{ [r] }[/math]. Show that for any finite [math]\displaystyle{ r }[/math] there is a finite [math]\displaystyle{ N }[/math] such that for all [math]\displaystyle{ n\ge N }[/math], for any [math]\displaystyle{ r }[/math]-coloring of all non-empty subsets of [math]\displaystyle{ [n] }[/math], there always exist [math]\displaystyle{ 1\le i\lt j\lt k\le n }[/math] such that the intervals [math]\displaystyle{ [i,j)=\{i,i+1,\ldots, j-1\} }[/math], [math]\displaystyle{ [j,k)=\{j,j+1,\ldots, k-1\} }[/math] and [math]\displaystyle{ [i,k)=\{i,i+1,\ldots, k-1\} }[/math] are all assigned with the same color by the [math]\displaystyle{ r }[/math]-coloring.