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

Problem 1

Solve the following two existence problems:

• You are given [math]\displaystyle{ n }[/math] integers [math]\displaystyle{ a_1,a_2,\dots,a_n }[/math], such that for each [math]\displaystyle{ 1\leq i\leq n }[/math] it holds that [math]\displaystyle{ i-n\leq a_i\leq i-1 }[/math]. Show that there exists a nonempty subsequence (not necessarily consecutive) of these integers, whose sum is equal to [math]\displaystyle{ 0 }[/math]. (Hint: Consider [math]\displaystyle{ b_i=a_i-i }[/math])

• You are given two multisets [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math], both with [math]\displaystyle{ n }[/math] integers from [math]\displaystyle{ 1 }[/math] to [math]\displaystyle{ n }[/math]. Show that there exist two nonempty subsets [math]\displaystyle{ A'\subseteq A }[/math] and [math]\displaystyle{ B'\subseteq B }[/math] with equal sum, i.e. [math]\displaystyle{ \sum\limits_{x\in A'}x=\sum\limits_{y\in B'}y }[/math] (Hint: Replace the term multiset by sequence, the term subset by consecutive subsequence, and the statement is still true. )

Problem 2

Prove that there is an absolute constant [math]\displaystyle{ c\gt 0 }[/math] with the following property: let [math]\displaystyle{ A }[/math] be an [math]\displaystyle{ n\times n }[/math] matrix with pairwise distinct entries. Then there is a permutation of the rows of [math]\displaystyle{ A }[/math] so that no column in the permuted matrix contains an increasing subsequence of length at least [math]\displaystyle{ c\sqrt{n} }[/math].

Problem 3

A [math]\displaystyle{ 3 }[/math]-uniform hypergraph [math]\displaystyle{ H=(V,E) }[/math] consists of a set of vertices [math]\displaystyle{ V }[/math] and a set of edges [math]\displaystyle{ E }[/math], where each edge [math]\displaystyle{ e\in E }[/math] is a set of exactly three vertices from [math]\displaystyle{ V }[/math]. Prove:

Every [math]\displaystyle{ 3 }[/math]-uniform hypergraph with [math]\displaystyle{ n }[/math] vertices and [math]\displaystyle{ m\geq n/3 }[/math] edges contains an independent set (i.e., a set of vertices containing no edges) of size at least [math]\displaystyle{ \frac{2n^{1.5}}{3\sqrt{3m}} }[/math].

Problem 4

Let [math]\displaystyle{ D=(V,E) }[/math] be a simple directed graph with minimum outdegree [math]\displaystyle{ \delta }[/math] and maximum indegree [math]\displaystyle{ \Delta }[/math]. Prove:

For any positive integer [math]\displaystyle{ k }[/math], if [math]\displaystyle{ \mathrm{e}(\Delta \delta+1)(1-\frac{1}{k})^{\delta}\lt 1 }[/math], then [math]\displaystyle{ D }[/math] contains a (directed,simple) cycle of length [math]\displaystyle{ 0\pmod k. }[/math]

Hint: Let [math]\displaystyle{ f:V\rightarrow \{0,1,\dots,k-1\} }[/math] be a random coloring of [math]\displaystyle{ V }[/math] obtained by choosing uniformly and independently at random for each [math]\displaystyle{ v\in V }[/math]. Try to use Lovász Local Lemma to show something interesting!

Problem 5

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