组合数学 (Fall 2023)/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 exists 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

Suppose [math]\displaystyle{ n \geq 4 }[/math], and let [math]\displaystyle{ H }[/math] be an [math]\displaystyle{ n }[/math]-uniform hypergraph with at most [math]\displaystyle{ \frac{4^{n−1}}{3^n} }[/math] (hyper)edges. Prove that there is a coloring of the vertices of [math]\displaystyle{ H }[/math] by four colors so that in every (hyper)edge all four colors are represented.

Problem 3

The girth of a graph is the length of its smallest cycle. Show that for any integer [math]\displaystyle{ k\geq 3 }[/math], for [math]\displaystyle{ n }[/math] sufficiently large there is a simple graph with [math]\displaystyle{ n }[/math] vertices, at least [math]\displaystyle{ \frac{1}{4}n^{1+1/k} }[/math] edges, and girth at least [math]\displaystyle{ k }[/math]. (Hint: Try to generate a random graph with [math]\displaystyle{ n }[/math] vertices and then fix things up!)