imported>Haimin |
imported>Etone |
| Line 1: |
Line 1: |
| == Problem 1 ==
| | 学号 姓名 |
| Let <math>L(n,m)</math> be the maximum length of [http://en.wikipedia.org/wiki/Sequence ''sequence''] with the following properties: the sum of every <math>n</math> consecutive elements is negative, the sum of every <math>m</math> consecutive elements is positive.
| | |
| *(easy) Prove <math>L(n,m)<mn</math>.
| | DZ1928004 刘尹成 |
| *(nontrivial) Prove <math>L(n,m)<m+n-1</math>.
| |
|
| |
|
| == Problem 2 ==
| | MG1928002 陈旭 |
| 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>,
| |
| # a strictly decreasing subsequence of length greater than <math>r</math>,
| |
| # a constant subsequence of length greater than <math>p</math>.
| |
|
| |
|
| == Problem 3 ==
| | MG1928003 邓煜恒 |
| 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 ==
| | MG1928005 龚丹毅 |
| "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 exist a 2-edge-coloring for <math>K_{m,n}</math> that there is no monochromatic <math>K_{a,b}</math> subgraph.
| | MG1928006 冀雅琴 |
|
| |
|
| == Problem 5 ==
| | MG1928007 康志杰 |
| 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 ==
| | MG1928008 李敏 |
| 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 ==
| | MG1928009 李同新 |
| 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.
| | |
| | MG1928012 蔺惠娟 |
| | |
| | MG1928013 令狐飘 |
|
| |
|
| 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.
| | MG1928016 刘姝君 |
|
| |
|
| 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>.
| | MG1928018 卢昱彤 |
|
| |
|
| == Problem 7.2 ==
| | MG1928019 陆晓娟 |
| 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>(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>.
| | MG1928020 马晨明 |
|
| |
|
| Prove that there exist <math>\ell=2k4^k\ln n</math> sets such that every pair <math>(A, B)</math> is separated by at least one of them.
| | MG1928026 石天润 |
| | |
| | MG1928027 谭洁 |
| | |
| | MG1928029 陶智 |
| | |
| | MG1928032 徐梓添 |
| | |
| | MG1928037 赵驿航 |
| | |
| | MG1928038 陈喆 |
| | |
| | MG1928039 都昊 |
| | |
| | MG1928045 彭蔚然 |
| | |
| | MG1928046 邱子键 |
| | |
| | MG1928053 姚靖心 |
| | |
| | MG1928054 战杨志豪 |
| | |
| | MG1928030 肖成龙 |
| | |
| | 161200070 赵志展 |
| | |
| | 161158085 张昱培 |
| | |
| | 161170043 王雅媛 |
| | |
| | 161170054 游振宇 |
| | |
| | 161158084 王译铭 |
| | |
| | 198354018 張沁全 |
| | |
| | 161158040 马梦楠 |
| | |
| | 161158029 栗卓 |
| | |
| | 161170026 刘世淦 |