组合数学 (Fall 2023)/Problem Set 3

Problem 1

Solve the following two existence problems:

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

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

Problem 2

Suppose $n\ge 4$, and let $H$ be an $n$-uniform hypergraph with at most $\frac{4^{n-1}}{3^n}$ (hyper)edges. Prove that there is a coloring of the vertices of $H$ 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 $k\ge 3$, for $n$ sufficiently large there is a simple graph with $n$ vertices, at least $\frac{1}{4}{n}^{1+1/k}$ edges, and girth at least $k$. (Hint: Try to generate a random graph with $n$ vertices and then fix things up!)

Problem 4

Let $G=(V,E)$ be an undirected graph and suppose each $v\in V$ is associated with a set $S(v)$ of at least $2\mathrm{e}r$ colors, where $r\ge 1$. Suppose, in addition, that for each $v\in V$ and $c\in S(v)$ there are at most $r$ neighbors $u$ of $v$ such that $c$ lies in $S(u)$. Prove that there is a proper coloring of $G$ assigning to each vertex $v$ a color from its class $S(v)$ such that, for any edge $(u,v)\in E$, the colors assigned to $u$ and $v$ are different.

Problem 5

Prove the following theorem on extremal graph theory:

• (Graham–Kleitman 1973). If the edges of a complete graph on $n$ vertices are labeled arbitrarily with the integers $1,2,\dots ,\frac{n(n-1)}{2}$, each edge receiving its own integer, then there is a trail (i.e., a walk without repeated edges) of length at least $n-1$ with an increasing sequence of edge-labels. (Hint: To each vertex $v$, assign its weight $w_v$ equal to the length of the longest increasing trail ending at $v$. Can you show that $\sum _{i=1}^n{w}_i\ge n(n-1)$?)