imported>Haimin |
imported>TCSseminar |
Line 1: |
Line 1: |
| == Problem 1 ==
| |
| 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.
| |
| Let <math>L(n,m)</math> be the maximum length of such sequence.
| |
| *(easy) Prove <math>L(n,m)<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.
| |
| # Prove <math>L(n,m)<m+n-1</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 ==
| | {| class="wikitable" |
| Prove that if <math>n>srp</math>, then any sequence of <math>n</math> numbers must contain at least one of the following subsequence:
| | | 161140077 || 张昕渊 |
| # a strictly increasing subsequence of length greater than <math>s</math>,
| | |} |
| # a strictly decreasing subsequence of length greater than <math>r</math>,
| |
| # a constant subsequence of length greater than <math>p</math>.
| |
| | |
| == 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.
| |
| * 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?
| |
| | |
| == 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 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.
| |
| | |
| == Problem 5 ==
| |
| 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>.
| |
| | |
| 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.
| |