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

Problem 1

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

• (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{ gcd(n,m)=1 }[/math].

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

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 exist 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 this problem 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 this problem 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 exist [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.