组合数学 (Spring 2013)/Problem Set 3 and Carmichael number: Difference between pages

Latest revision as of 08:08, 11 March 2013

In number theory a Carmichael number is a composite positive integer [math]\displaystyle{ n }[/math], which satisfies the congruence [math]\displaystyle{ b^{n-1}\equiv 1\pmod{n} }[/math] for all integers [math]\displaystyle{ b }[/math] which are relatively prime to [math]\displaystyle{ n }[/math]. Being relatively prime means that they do not have common divisors, other than 1. Such numbers are named after Robert Carmichael.

All prime numbers [math]\displaystyle{ p }[/math] satisfy [math]\displaystyle{ b^{p-1}\equiv 1\pmod{p} }[/math] for all integers [math]\displaystyle{ b }[/math] which are relatively prime to [math]\displaystyle{ p }[/math]. This has been proven by the famous mathematician Pierre de Fermat. In most cases if a number [math]\displaystyle{ n }[/math] is composite, it does not satisfy this congruence equation. So, there exist not so many Carmichael numbers. We can say that Carmichael numbers are composite numbers that behave a little bit like they would be a prime number. Template:Math-stub

@@ Line 1: / Line 1: @@
-== Problem 1==
+In [[number theory]] a '''Carmichael number''' is a [[composite number|composite]] positive [[integer]] <math>n</math>, which satisfies the [[congruence]] <math>b^{n-1}\equiv 1\pmod{n}</math> for all integers <math>b</math> which are [[coprime|relatively prime]] to <math>n</math>. Being relatively prime means that they do not have common divisors, other than 1. Such numbers are named after [[Robert Daniel Carmichael|Robert Carmichael]].
-一个set family <math>\mathcal{F}\subset{[n]\choose k}</math> 的 '''blocking set''' 是这样一个集合 <math>T\subseteq[n]</math>，使每一个 member set <math>A\in\mathcal{F}</math> 都有 <math>T\cap A\neq\emptyset</math>。当 <math>k=2</math> 的时候，<math>\mathcal{F}</math> 就是一个图，而 blocking set <math>T</math> 就是这个图的顶点覆盖（vertex cover）。因此，blocking set 就是顶点覆盖在超图（hypergraph）上的推广。我们知道最小定点覆盖（minimum vertex cover）问题是 NP-hard 问题，因此求最小 blocking set 也是难的。
-证明：任何 <math>\mathcal{F}\subset{[n]\choose k}</math>, <math>|\mathcal{F}|=m</math>，都存在一个不大于 <math>\left\lceil\frac{n\ln m}{k}\right\rceil</math> 的 blocking set。
+All [[prime number]]s <math>p</math> satisfy <math>b^{p-1}\equiv 1\pmod{p}</math> for all integers <math>b</math> which are relatively prime to <math>p</math>. This has been proven by the famous mathematician [[Pierre de Fermat]]. In most cases if a number <math>n</math> is composite, it does '''not''' satisfy this congruence equation. So, there exist not so many Carmichael numbers. We can say that Carmichael numbers are composite numbers that behave a little bit like they would be a prime number.
+{{Math-stub}}
-== Problem 2==
+[[Category:Number theory]]
-一个图 <math>G(V,E)</math> 的'''支配集''' (dominating set) 是一个顶点集合 <math>D\subseteq V</math>，使得每个顶点 <math>v\in V</math> 要么属于 <math>D</math> 要么有邻居属于 <math>D</math>。最小支配集 (minimum dominating set) 是 NP-hard问题。
-证明：任何一个 <math>n</math> 个顶点的 <math>d</math>-regular 图（每个顶点恰好有 <math>d</math> 个邻居），必然存在一个不大于 <math>\frac{n(1+\ln(d+1))}{d+1}</math> 的支配集。
-== Problem 3 ==
-<math>H(W,F)\,</math> 为一个图，<math>n>|W|\,</math> 为一个整数。已知存在一个图 <math>G(V,E)\,</math> 有 <math>|V|=n, |E|=m\,</math> 且<font color=red>不包含</font> <math>H\,</math> 子图。
-证明：对于 <math>k>\frac{n^2\ln n}{m}</math>，存在一个对 <math>K_n\,</math>（<math>n</math>结点完全图）的<font color=red>边</font>的 <math>k</math> 着色，没有单色（monocharomatic）的<math>H\,</math>。
-注：令 <math>K_n</math> 的边集为 <math>E={V\choose 2}</math>，“对 <math>K_n</math> 的边的 <math>k</math> 着色"，就是一个映射 <math>f: E\rightarrow [k]</math>。
-即，每个边选择 <math>k</math> 种颜色之一进行着色，可以任意着色，无需考虑相邻的边是否同色。
-== Problem 4 ==
-一个图<math>G</math> 的 independence number <math>\alpha(G)</math> 为 <math>G</math> 中最大的独立集 (independent set) 的大小。证明Turán定理的对偶（dual）版本：
-{{Theorem|定理|
-:如果图 <math>G</math> 有 <math>n</math> 个结点，<math>\frac{nk}{2}</math> 条边，<math>k\ge 1</math>，则 <math>\alpha(G)\ge\frac{n}{k+1}</math>。
-}}
-要求至少给出两个版本的证明：
-#用概率法证明。
-#用Turán定理直接证明。
-==Problem 5 ==
-我们称一个[http://en.wikipedia.org/wiki/Tournament_(graph_theory) '''竞赛图'''] <math>T([n],E)</math> 是[http://en.wikipedia.org/wiki/Tournament_(graph_theory)#Transitivity 传递(transitive)]的，如果存在一个 <math>[n]</math> 的全排列 <math>\pi</math> 使得 <math>(i,j)\in E</math> 当且仅当 <math>\pi_i<\pi_j</math>，即该竞赛图 <math>T([n],E)</math> 的边的方向符合传递性。
-证明：对任何 <math>k\ge 3</math>，存在 <math>N(k)</math>，对任何的 <math>n\ge N(k)</math> 个点的竞赛图，都存在一个 <math>k</math> 个点的子竞赛图满足传递性。

组合数学 (Spring 2013)/Problem Set 3 and Carmichael number: Difference between pages

Latest revision as of 08:08, 11 March 2013

Navigation menu

Search