组合数学 (Spring 2026)/Problem Set 3

Problem 1

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 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 the same color.

Problem 2

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 3

Let [math]\displaystyle{ G=(V,E) }[/math] be a graph on [math]\displaystyle{ n }[/math] vertices and [math]\displaystyle{ t(G) }[/math] the number of triangles in it. Show that [math]\displaystyle{ t(G)\geq \frac{|E|}{3n}\left(4|E|-n^2\right) }[/math].

Hint: For an edge [math]\displaystyle{ e=(u,v)\in E }[/math], let [math]\displaystyle{ t(e) }[/math] be the number of triangles containing [math]\displaystyle{ e }[/math]. Try to obtain that [math]\displaystyle{ t(e) \geq d(u)+d(v)-n }[/math] and use Cauchy–Schwarz inequality to esitimate the sum [math]\displaystyle{ \sum_{e=(u,v)\in E} (d(u)+d(v)) }[/math].

Problem 4

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

(Goodman 1959)

Let [math]\displaystyle{ G=(V,E) }[/math] be a graph on [math]\displaystyle{ n }[/math] vertices and [math]\displaystyle{ t(G) }[/math] denote the number of triangles contained in the graph [math]\displaystyle{ G }[/math] or in its complement. Prove that [math]\displaystyle{ t(G)\geq \binom{n}{3}+\frac{2m^2}{n}-m(n-1) }[/math].

Hint: Let [math]\displaystyle{ t_i }[/math] be the number of triples of vertices [math]\displaystyle{ (i,j,k) }[/math] such that the vertex [math]\displaystyle{ i }[/math] is adjacent to precisely one of [math]\displaystyle{ j }[/math] or [math]\displaystyle{ k }[/math]. Note that [math]\displaystyle{ t_i = d_i(n-1-d_i) }[/math] where [math]\displaystyle{ d_i }[/math] is the degree of the vertex [math]\displaystyle{ i }[/math]. Show that [math]\displaystyle{ t(G) \geq \binom{n}{3}-\frac{1}{2}\sum_i t_i }[/math] and use the Cauchy–Schwarz to bound [math]\displaystyle{ \sum_i t_i }[/math].