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

Problem 1

Consider a sequence of numbers with the following properties: the sum of every [math]\displaystyle{ n }[/math] consecutive elements is negative, and the sum of every [math]\displaystyle{ m }[/math] consecutive elements is positive. Let [math]\displaystyle{ L(n,m) }[/math] be the maximum length of such sequence.

• (easy) Prove [math]\displaystyle{ L(n,m)\lt mn }[/math].
• (nontrivial) You do not need to solve both (1.) and (2.), choose one among the two. But feel free to submit solutions for both.

1. Prove [math]\displaystyle{ L(n,m)\lt m+n-1 }[/math].
2. Prove [math]\displaystyle{ L(n,m)\geq m+n-2 }[/math], for any [math]\displaystyle{ n,m }[/math] are relatively prime(the only positive integer factor that divides both of them is 1).

Problem 2

Prove that if [math]\displaystyle{ n\gt srp }[/math], then any sequence of [math]\displaystyle{ n }[/math] numbers must contain at least one of the following subsequence:

1. a strictly increasing subsequence of length greater than [math]\displaystyle{ s }[/math],
2. a strictly decreasing subsequence of length greater than [math]\displaystyle{ r }[/math],
3. a constant subsequence of length greater than [math]\displaystyle{ p }[/math].

Problem 3

A set of vertices [math]\displaystyle{ D\subseteq V }[/math] of graph [math]\displaystyle{ G(V,E) }[/math] is a dominating set if for every [math]\displaystyle{ v\in V }[/math], it holds that [math]\displaystyle{ v\in D }[/math] or [math]\displaystyle{ v }[/math] is adjacent to a vertex in [math]\displaystyle{ D }[/math]. The problem of computing minimum dominating set is NP-hard.

• Prove that for every [math]\displaystyle{ d }[/math]-regular graph with [math]\displaystyle{ n }[/math] vertices, there exists a dominating set with size at most [math]\displaystyle{ \frac{n(1+\ln(d+1))}{d+1} }[/math].
• Try to obtain an upper bound for the size of dominating set using Lovász Local Lemma. Is it better or worse than previous one?

Problem 4

"An [math]\displaystyle{ k }[/math]-edge-coloring for graph [math]\displaystyle{ G(V,E) }[/math]" is a mapping [math]\displaystyle{ f:E\to[k] }[/math], where [math]\displaystyle{ E }[/math] is the edge set of graph [math]\displaystyle{ G }[/math]. Besides, [math]\displaystyle{ K_{n,m} }[/math] denotes the complete bipartite graph on [math]\displaystyle{ n }[/math] and [math]\displaystyle{ m }[/math] vertices.

Prove that if [math]\displaystyle{ \binom{m}{a}\binom{n}{b}2^{1-ab}+\binom{n}{a}\binom{m}{b}2^{1-ab}\lt 1 }[/math] there is a 2-edge-coloring for [math]\displaystyle{ K_{m,n} }[/math] that there is no monochromatic [math]\displaystyle{ K_{a,b} }[/math] subgraph.

Problem 5

Let [math]\displaystyle{ G(V,E) }[/math] be a cycle of length [math]\displaystyle{ k\cdot n }[/math] and let [math]\displaystyle{ V=V_1\cup V_2\cup\dots V_n }[/math] be a partition of its [math]\displaystyle{ k\cdot n }[/math] vertices into [math]\displaystyle{ n }[/math] pairwise disjoint subsets, each of cardinality [math]\displaystyle{ k }[/math].

For [math]\displaystyle{ k\ge 11 }[/math] show that there must be an independent set of [math]\displaystyle{ G }[/math] containing precisely one vertex from each [math]\displaystyle{ V_i }[/math].

Problem 6

Consider the following independent set version of the Turan theorem:

Let [math]\displaystyle{ G(V,E) }[/math] be a graph of [math]\displaystyle{ n=|V| }[/math] vertices and [math]\displaystyle{ m=|E| }[/math] edges. [math]\displaystyle{ G }[/math] must have an independent set [math]\displaystyle{ S }[/math] of size [math]\displaystyle{ |S|\ge \frac{n^2}{2m+n} }[/math].

• Show that this theorem is a corollary to the Turan theorem for cliques.
• Prove the theorem directly without using the Turan theorem for cliques.

Problem 7.1

You only need to solve one of (7.1) and (7.2). But feel free to submit solutions for both, and your score of problem 7 will be the maximum score.

Let [math]\displaystyle{ H(W,F) }[/math] be a graph and [math]\displaystyle{ n\gt |W| }[/math] be an integer. It is known that for some graph [math]\displaystyle{ G(V,E) }[/math] such that [math]\displaystyle{ |V|=n }[/math], [math]\displaystyle{ |E|=m }[/math], [math]\displaystyle{ G }[/math] does not contain [math]\displaystyle{ H }[/math] as a subgraph.

Prove that for [math]\displaystyle{ k\gt \frac{n^2\ln n}{m} }[/math], there is an [math]\displaystyle{ k }[/math]-edge-coloring for [math]\displaystyle{ K_n }[/math] that [math]\displaystyle{ K_n }[/math] contains no monochromatic [math]\displaystyle{ H }[/math].

Problem 7.2

You only need to solve one of (7.1) and (7.2). But feel free to submit solutions for both, and your score of problem 7 will be the maximum score.

Consider the family of all pairs [math]\displaystyle{ (A, B) }[/math] of disjoint [math]\displaystyle{ k }[/math] element subsets of [math]\displaystyle{ \{1,...,n\} }[/math]. A set [math]\displaystyle{ Y }[/math] separates the pair [math]\displaystyle{ (A, B) }[/math] if [math]\displaystyle{ A\subseteq Y }[/math] and [math]\displaystyle{ B\cap Y=\phi }[/math].

Prove that there exists [math]\displaystyle{ \ell=2k4^k\ln n }[/math] sets such that every pair [math]\displaystyle{ (A, B) }[/math] is separated by at least one of them.