组合数学 (Fall 2019)/Problem Set 3: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>Haimin
No edit summary
imported>Haimin
No edit summary
 
(7 intermediate revisions by the same user not shown)
Line 1: Line 1:
<font color="red" size=5>Under Construction</font>
== Problem 1 ==
== Problem 1 ==
Let <math>L = L(K_{m,n})</math> be the laplacian matrix of the complete bipartite graph <math>K_{mn}</math>.
Consider a [http://en.wikipedia.org/wiki/Sequence ''sequence''] of numbers with the following properties: the sum of every <math>n</math> consecutive elements is negative, and the sum of every <math>m</math> consecutive elements is positive.
* Find a simple upper bound on rank<math>(L - nI)</math>. Deduce a lower bound on the number of eigenvalues of <math>L</math> equal to <math>n</math>.
Let <math>L(n,m)</math> be the maximum length of such sequence.
* Assume <math>m\neq n</math>, and do the same as (a) for <math>m</math> instead of <math>n</math>.
*(easy) Prove <math>L(n,m)<mn</math>.
* Find the remaining eigenvalues of <math>L</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.
* Compute <math>\kappa\left(K_{m,n}\right)</math>, the number of spanning trees of <math>K_{m,n}</math>.
# Prove <math>L(n,m)<m+n-1</math>.
* Give a combinatorial proof of the formula for <math>\kappa\left(K_{m,n}\right)</math>.
# Prove <math>L(n,m)\geq m+n-2</math>, for any <math>n,m</math> are relatively prime(the only positive integer factor that divides both of them is 1).


== Problem 2 ==
== Problem 2 ==
(Erdős-Spencer 1974)
Prove that if <math>n>srp</math>, then any sequence of <math>n</math> numbers must contain at least one of the following subsequence:
 
# a strictly increasing subsequence of length greater than <math>s</math>,
Let <math>n</math> coins of weights 0 and 1 be given. We are also given a scale with which we may weigh any subset of the coins. Our goal is to determine the weights of coins (that is, to known which coins are 0 and which are 1) with the minimal number of weighings.
# a strictly decreasing subsequence of length greater than <math>r</math>,
 
# a constant subsequence of length greater than <math>p</math>.  
This problem can be formalized as follows: A collection <math>S_1,S_1,\ldots,S_m\subseteq [n]</math> is called '''determining''' if an arbitrary subset <math>T\subseteq[n]</math> can be uniquely determined by the cardinalities <math>|S_i\cap T|, 1\le i\le m</math>.
 
* Prove that if there is a determining collection <math>S_1,S_1,\ldots,S_m\subseteq [n]</math>, then there is a way to determine the weights of <math>n</math> coins with <math>m</math> weighings.
* Use pigeonhole principle to show that if a collection <math>S_1,S_1,\ldots,S_m\subseteq [n]</math> is determining, then it must hold that <math>m\ge \frac{n}{\log_2(n+1)}</math>. (This gives a lower bound for the number of weighings required to determine the weights of <math>n</math> coins.)


== Problem 3 ==
== Problem 3 ==
A set of vertices <math>D\subseteq V</math> of graph <math>G(V,E)</math> is a [http://en.wikipedia.org/wiki/Dominating_set ''dominating set''] if for every <math>v\in V</math>, it holds that <math>v\in D</math> or <math>v</math> is adjacent to a vertex in <math>D</math>. The problem of computing minimum dominating set is NP-hard.  
A set of vertices <math>D\subseteq V</math> of graph <math>G(V,E)</math> is a [http://en.wikipedia.org/wiki/Dominating_set ''dominating set''] if for every <math>v\in V</math>, it holds that <math>v\in D</math> or <math>v</math> is adjacent to a vertex in <math>D</math>. The problem of computing minimum dominating set is NP-hard.  
* Prove that for every <math>d</math>-regular graph with <math>n</math> vertices, there exists a dominating set with size at most <math>\frac{n(1+\ln(d+1))}{d+1}</math>.
* Prove that for every <math>d</math>-regular graph with <math>n</math> vertices, there exists a dominating set with size at most <math>\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?
* 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 ==
== Problem 4 ==
"An <math>k</math>-edge-coloring for graph <math>G(V,E)</math>" is a mapping <math>f:E\to[k]</math>, where <math>E</math> is the edge set of graph <math>G</math>. Besides, <math>K_{n,m}</math> denotes the complete bipartite graph on <math>n</math> and <math>m</math> vertices.


* Prove there is a 2-coloring of edges of <math>K_n</math> with at most <math>\binom{n}{k}2^{1-\binom{a}{2}}</math> monochromatic <math>K_a</math>.
Prove that if <math>\binom{m}{a}\binom{n}{b}2^{1-ab}+\binom{n}{a}\binom{m}{b}2^{1-ab}<1</math> there is a 2-edge-coloring for <math>K_{m,n}</math> that there is no monochromatic <math>K_{a,b}</math> subgraph.
* Prove there is a 2-coloring of edges of the complete bipartite graph <math>K_{m,n}</math> with at most <math>\binom{m}{a}\binom{n}{b}2^{1-ab}+\binom{n}{a}\binom{m}{b}2^{1-ab}</math> monochromatic <math>K_{a,b}</math>.


== Problem 5 ==
== Problem 5 ==
Let <math>H(W,F)</math> be a graph and <math>n>|W|</math> be an integer. It is known that for some graph <math>G(V,E)</math> such that <math>|V|=n</math>, <math>|E|=m</math>, <math>G</math> does not contain <math>H</math> as a subgraph. Prove that for <math>k>\frac{n^2\ln n}{m}</math>, there is an edge <math>k</math>-coloring for <math>K_n</math> that <math>K_n</math> contains no monochromatic <math>H</math>.
Let <math>G(V,E)</math> be a cycle of length <math>k\cdot n</math> and let <math>V=V_1\cup V_2\cup\dots V_n</math> be a partition of its <math>k\cdot n</math> vertices into <math>n</math> pairwise disjoint subsets, each of cardinality <math>k</math>.
 
For <math>k\ge 11</math> show that there must be an independent set of <math>G</math> containing precisely one vertex from each <math>V_i</math>.
 
== Problem 6 ==
Consider the following independent set version of the Turan theorem:
: Let <math>G(V,E)</math> be a graph of <math>n=|V|</math> vertices and <math>m=|E|</math> edges. <math>G</math> must have an independent set <math>S</math> of size <math>|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>H(W,F)</math> be a graph and <math>n>|W|</math> be an integer. It is known that for some graph <math>G(V,E)</math> such that <math>|V|=n</math>, <math>|E|=m</math>, <math>G</math> does not contain <math>H</math> as a subgraph.  
 
Prove that for <math>k>\frac{n^2\ln n}{m}</math>, there is an <math>k</math>-edge-coloring for <math>K_n</math> that <math>K_n</math> contains no monochromatic <math>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>(A, B)</math> of disjoint <math>k</math> element subsets of <math>\{1,...,n\}</math>. A set <math>Y</math> separates the pair <math>(A, B)</math> if <math>A\subseteq Y</math> and <math>B\cap Y=\phi</math>.  


Remark: Let <math>E=\binom{V}{2}</math> be the edge set of <math>K_n</math>. "An edge <math>k</math>-coloring for <math>K_n</math>" is a mapping <math>f:E\to[k]</math>.
Prove that there exists <math>\ell=2k4^k\ln n</math> sets such that every pair <math>(A, B)</math> is separated by at least one of them.

Latest revision as of 08:28, 19 November 2019

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.