组合数学 (Fall 2019)/Problem Set 1 and 组合数学 (Fall 2019)/Problem Set 4: Difference between pages

From TCS Wiki
(Difference between pages)
Jump to navigation Jump to search
VisualWikitext
imported>Etone
 
imported>Etone
No edit summary
 
Line 1: Line 1:
*每道题目的解答都要有<font color="red" size=5>完整的解题过程</font>。中英文不限。
== Problem 1 ==
(Matching vs. Star)


== Problem 1 ==
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>.
Suppose that we have <math>n</math> '''identical''' red balls and <math>m</math> '''distinct''' blue balls.
 
Find the number of ways to select <math>r</math> balls from these <math>n+m</math> balls, in each of the following cases:
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>.
#<math>r\leq m,\ r\leq n</math>;
 
#<math>n\leq r\leq m</math>;
(Hint: Learn from the proof of Erdos-Rado's sunflower lemma.)
#<math>m\leq r\leq n</math>.


== Problem 2 ==
== Problem 2 ==
李雷和韩梅梅竞选学生会主席，韩梅梅获得选票 <math>p</math> 张，李雷获得选票 <math>q</math> 张，<math>p>q</math>。我们将总共的 <math>p+q</math> 张选票一张一张的点数，有多少种选票的排序方式使得在整个点票过程中，韩梅梅的票数一直高于李雷的票数？等价地，假设选票均匀分布的随机排列，以多大概率在整个点票过程中，韩梅梅的票数一直高于李雷的票数。
(Frankl 1986)
 
== Problem 3 ==
In each of the following cases, first answer what the <math>a_n</math>'s are, and then try to give the closed forms for the generating functions <math>A(x)=\sum_{n\ge 0}a_n x^n</math>.
#<math>a_n</math> is the number of ways of distributing <math>n</math> identical objects into 4 distinct boxes;
#<math>a_n</math> is the number of ways of distributing <math>n</math> identical objects into 4 distinct boxes so that no box is empty;
#<math>a_n</math> is the number of ways of distributing <math>n</math> identical objects into 4 identical boxes so that no box is empty;
#<math>a_n</math> is the number of ways of distributing <math>n</math> identical objects into 4 identical boxes.


== Problem 4 ==
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>.
Let <math>(a_n)</math> be a sequence of numbers satisfying the recurrence relation:
* 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.
:<math> a_n-p \cdot a_{n-1}+(p-q)\cdot q \cdot a_{n-2}=0</math>  
* Show that <math>|\mathcal{F}|\le 1+{k\choose \lfloor k/2\rfloor}</math>.
with initial condition <math>a_0=1</math> and <math>a_1=p</math>, where <math>p</math> and <math>q</math> are distinct nonzero constants. Solve the recurrence relation.


== Problem 5 ==
==Problem 3 ==
Consider the decimal expansion <math>1/9899=0.0001010203050813213455\cdots</math>
An <math>n</math>-player tournament (竞赛图) <math>T([n],E)</math> is said to be '''transitive''', if there exists a permutation <math>\pi</math> of <math>[n]</math> such that <math>\pi_i<\pi_j</math> for every <math>(i,j)\in E</math>.


Why do the Fibonacci numbers 1,1,2,3,5,8,13,21,34,55 appear?
Show that for any <math>k\ge 3</math>, there exists a finite <math>N(k)</math> such that every tournament of <math>n\ge N(k)</math> players contains a transitive sub-tournament of <math>k</math> players. Express <math>N(k)</math> in terms of Ramsey number.


== Problem 6 ==
==Problem 4==
Let <math>f(n,r,s)</math> denote the number of subsets <math>S</math> of <math>\{0,1,2,\ldots,2n-1\}</math> consisting of <math>r</math> odd and <math>s</math> even integers, with no two elements of <math>S</math> differing by <math>1</math>. Give a combinatorial proof that <math>f(n,r,s)=\binom{n-r}{s}\binom{n-s}{r}</math>.
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.

Revision as of 05:38, 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 }[/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.

Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=组合数学_(Fall_2019)/Problem_Set_1&oldid=9086"