TCS Wiki - Recent changes [en]

概率论与数理统计 (Spring 2026)

Liuexp — Mon, 25 May 2026 07:48:49 GMT

Assignments

← Older revision		Revision as of 07:48, 25 May 2026
(2 intermediate revisions by the same user not shown)
Line 127:		Line 127:
	** [[概率论与数理统计 (Spring 2026)/第三次作业提交名单\|第三次作业提交名单]]		** [[概率论与数理统计 (Spring 2026)/第三次作业提交名单\|第三次作业提交名单]]

	*[[概率论与数理统计 (Spring 2026)/Problem Set 4\|Problem Set 4]] 请在 ~~<font color=red>TBA<~~/~~font>~~ 上课之前(9am UTC+8)提交到 [mailto:pr2026_nju@163.com pr2026_nju@163.com] (文件名为'<font color=red >学号_姓名_A4.pdf</font>').		*[[概率论与数理统计 (Spring 2026)/Problem Set 4\|Problem Set 4]] 请在 2026/6/3 上课之前(9am UTC+8)提交到 [mailto:pr2026_nju@163.com pr2026_nju@163.com] (文件名为'<font color=red >学号_姓名_A4.pdf</font>').

	= Lectures =		= Lectures =

计算复杂性 (Spring 2026)

Roundgod — Sun, 24 May 2026 02:23:32 GMT

第三次作业

← Older revision		Revision as of 02:23, 24 May 2026
Line 78:		Line 78:
	每次作业请将作业的电子版本(pdf、扫描或拍照)发送到助教邮箱		每次作业请将作业的电子版本(pdf、扫描或拍照)发送到助教邮箱

	第一次作业（ddl：4月6日）：Chapter 2, 3 Exercise 2.14, 2.16, 2.33, 3.3, 3.6, 3.8, 3.9(bonus)		第一次作业（ddl：4月6日）：Chapter 2, 3 Exercise 2.14, 2.16, 2.33, 3.3, 3.6, 3.8 (bonus), 3.9 (bonus)

	第二次作业（ddl：5月4日）：Chapter 6. Exercise 5.9, 5.12, 6.3, 6.12		第二次作业（ddl：5月4日）：Chapter 6. Exercise 5.9, 5.12, 6.3, 6.12

			第三次作业（ddl：6月8日）：Chapter 8. Exercise 8.1, 8.3, 8.5, 8.6, 8.11

组合数学 (Spring 2026)

652024330006 — Fri, 22 May 2026 14:56:14 GMT

Announcement

← Older revision		Revision as of 14:56, 22 May 2026
(One intermediate revision by the same user not shown)
Line 62:		Line 62:
	* '''(2026/03/25)'''<font color=red size=4> 第一次作业已发布</font>，请在 2026/04/08 上课之前提交到 [mailto:njucomb26@163.com njucomb26@163.com] (文件名为'学号_姓名_A1.pdf')		* '''(2026/03/25)'''<font color=red size=4> 第一次作业已发布</font>，请在 2026/04/08 上课之前提交到 [mailto:njucomb26@163.com njucomb26@163.com] (文件名为'学号_姓名_A1.pdf')
	* '''(2026/04/21)'''<font color=red size=4> 第二次作业已发布</font>，请在 2026/05/13 上课之前提交到 [mailto:njucomb26@163.com njucomb26@163.com] (文件名为'学号_姓名_A2.pdf')		* '''(2026/04/21)'''<font color=red size=4> 第二次作业已发布</font>，请在 2026/05/13 上课之前提交到 [mailto:njucomb26@163.com njucomb26@163.com] (文件名为'学号_姓名_A2.pdf')
			* '''(2026/05/22)'''<font color=red size=4> 第三次作业已发布</font>，请在 2026/06/03 上课之前提交到 [mailto:njucomb26@163.com njucomb26@163.com] (文件名为'学号_姓名_A3.pdf')

	= Course info =		= Course info =
Line 101:		Line 102:
	* [[组合数学 (Spring 2026)/Problem Set 1\|Problem Set 1]]		* [[组合数学 (Spring 2026)/Problem Set 1\|Problem Set 1]]
	* [[组合数学 (Spring 2026)/Problem Set 2\|Problem Set 2]]		* [[组合数学 (Spring 2026)/Problem Set 2\|Problem Set 2]]
			* [[组合数学 (Spring 2026)/Problem Set 3\|Problem Set 3]]

	= Lecture Notes =		= Lecture Notes =

组合数学 (Spring 2026)/Problem Set 3

652024330006 — Fri, 22 May 2026 14:54:47 GMT

Problem 4

← Older revision		Revision as of 14:54, 22 May 2026
(7 intermediate revisions by the same user not shown)
Line 1:		Line 1:
	==Problem 1==		==Problem 1==
	We color each non-empty subset of <math>[n]=\{1,2,\ldots,n\}</math> with one of the <math>r</math> colors in <math>[r]</math>. Show that for any finite <math>r</math> there is a finite <math>N</math> such that for all <math>n\ge N</math>, for any <math>r</math>-coloring of non-empty subsets of <math>[n]</math>, there always exist <math>1\le i<j<k\le n</math> such that the intervals <math>[i,j)=\{i,i+1,\ldots, j-1\}</math>, <math>[j,k)=\{j,j+1,\ldots, k-1\}</math> and <math>[i,k)=\{i,i+1,\ldots, k-1\}</math> are all assigned ~~with~~ the same color.		We color each non-empty subset of <math>[n]=\{1,2,\ldots,n\}</math> with one of the <math>r</math> colors in <math>[r]</math>. Show that for any finite <math>r</math> there is a finite <math>N</math> such that for all <math>n\ge N</math>, for any <math>r</math>-coloring of non-empty subsets of <math>[n]</math>, there always exist <math>1\le i<j<k\le n</math> such that the intervals <math>[i,j)=\{i,i+1,\ldots, j-1\}</math>, <math>[j,k)=\{j,j+1,\ldots, k-1\}</math> and <math>[i,k)=\{i,i+1,\ldots, k-1\}</math> are all assigned the same color.

	== Problem 2 ==		== Problem 2 ==
Line 11:		Line 11:


	'''Hint''': For an edge <math> e=(u,v)\in E </math>, let <math> t(e) </math> be the number of triangles containing <math> e </math>. Try to obtain that <math> t(e) \geq d(u)+d(v)-n </math> and use Cauchy–Schwarz inequality to ~~esitimate~~ the sum <math> \sum_{e=(u,v)\in E} (d(u)+d(v))</math>.		'''Hint''': For an edge <math> e=(u,v)\in E </math>, let <math> t(e) </math> be the number of triangles containing <math> e </math>. Try to obtain that <math> t(e) \geq d(u)+d(v)-n </math> and use Cauchy–Schwarz inequality to estimate the sum <math> \sum_{e=(u,v)\in E} (d(u)+d(v))</math>.

	== Problem 4 ==		== Problem 4 ==
	(Frankl 1986)		(Frankl 1986)

	Let <math>\mathcal{F}\subseteq {[n]\choose k}</math> be a <math>k</math>-uniform family, and suppose that it satisfies that <math>A\cap B \~~not\subset~~ C</math> for any <math>A,B,C\in\mathcal{F}</math>.		Let <math>\mathcal{F}\subseteq {[n]\choose k}</math> be a <math>k</math>-uniform family, and suppose that it satisfies that <math>A\cap B \nsubseteq C</math> for any pairwise distinct <math>A,B,C\in\mathcal{F}</math>.
	* Fix any <math>B\in\mathcal{F}</math>. Show that the family <math>\{A\cap B\mid A\in\mathcal{F}, A\neq B\}</math> is an ~~anti chain~~.		* Fix any <math>B\in\mathcal{F}</math>. Show that the family <math>\{A\cap B\mid A\in\mathcal{F}, A\neq B\}</math> is an antichain.
	* Show that <math>\|\mathcal{F}\|\le 1+{k\choose \lfloor k/2\rfloor}</math>.		* Show that <math>\|\mathcal{F}\|\le 1+{k\choose \lfloor k/2\rfloor}</math>.

			== Problem 5 ==
	== Problem 3 ==
	(Goodman 1959)		(Goodman 1959)

	Let <math> G=(V,E) </math> be a graph on <math> n </math> vertices and <math> t(G) </math> denote the number of triangles contained in the graph <math> G </math> or in its complement. Prove that <math> t(G)\geq \binom{n}{3}+\frac{2m^2}{n}-m(n-1)</math>.		Let <math> G=(V,E) </math> be a graph on <math> n </math> vertices, let <math> m=\|E\| </math>, and let <math> t(G) </math> denote the number of triangles contained in the graph <math> G </math> or in its complement. Prove that <math> t(G)\geq \binom{n}{3}+\frac{2m^2}{n}-m(n-1)</math>.

	'''Hint''': Let <math>t_i</math> be the number of ~~triples~~ of vertices <math>~~(i,~~j,k)</math> such that the vertex <math>i</math> is adjacent to precisely one of <math>j</math> or <math>k</math>.		'''Hint''': Let <math>t_i</math> be the number of unordered pairs of vertices <math>{j,k}</math> such that the vertex <math>i</math> is adjacent to precisely one of <math>j</math> or <math>k</math>.
	Note that <math>t_i = d_i(n-1-d_i)</math> where <math>d_i</math> is the degree of the vertex <math>i</math>.		Note that <math>t_i = d_i(n-1-d_i)</math> where <math>d_i</math> is the degree of the vertex <math>i</math>.
	Show that <math>t(G) \geq \binom{n}{3}-\frac{1}{2}\sum_i t_i</math> and use the Cauchy–Schwarz to bound <math> \sum_i t_i </math>.		Show that <math>t(G) \geq \binom{n}{3}-\frac{1}{2}\sum_i t_i</math> and use the Cauchy–Schwarz to bound <math> \sum_i t_i </math>.

组合数学 (Spring 2026)/Problem Set 3

652024330006 — Fri, 22 May 2026 13:31:21 GMT

Created page with "==Problem 1== We color each non-empty subset of <math>[n]=\{1,2,\ldots,n\}</math> with one of the <math>r</math> colors in <math>[r]</math>. Show that for any finite <math>r</math> there is a finite <math>N</math> such that for all <math>n\ge N</math>, for any <math>r</math>-coloring of non-empty subsets of <math>[n]</math>, there always exist <math>1\le i<j<k\le n</math> such that the intervals <math>[i,j)=\{i,i+1,\ldots, j-1\}</math>, <math>[j,k)=\{j,j+1,\ldots, k-1\}<..."

New page

==Problem 1==
We color each non-empty subset of <math>[n]=\{1,2,\ldots,n\}</math> with one of the <math>r</math> colors in <math>[r]</math>. Show that for any finite <math>r</math> there is a finite <math>N</math> such that for all <math>n\ge N</math>, for any <math>r</math>-coloring of non-empty subsets of <math>[n]</math>, there always exist <math>1\le i<j<k\le n</math> such that the intervals <math>[i,j)=\{i,i+1,\ldots, j-1\}</math>, <math>[j,k)=\{j,j+1,\ldots, k-1\}</math> and <math>[i,k)=\{i,i+1,\ldots, k-1\}</math> are all assigned with the same color.

== Problem 2 ==
An <math>n</math>-player tournament (竞赛图) <math>T([n],E)</math> is said to be '''transitive''', if there exists a permutation <math>\pi</math> of <math>[n]</math> such that <math>\pi_i<\pi_j</math> for every <math>(i,j)\in E</math>.

Show that for any <math>k\ge 3</math>, there exists a finite <math>N(k)</math> such that every tournament of <math>n\ge N(k)</math> players contains a transitive sub-tournament of <math>k</math> players. Express <math>N(k)</math> in terms of Ramsey number.

== Problem 3 ==
Let <math>G=(V,E)</math> be a graph on <math> n </math> vertices and <math> t(G) </math> the number of triangles in it. Show that <math> t(G)\geq \frac{|E|}{3n}\left(4|E|-n^2\right) </math>.

'''Hint''': For an edge <math> e=(u,v)\in E </math>, let <math> t(e) </math> be the number of triangles containing <math> e </math>. Try to obtain that <math> t(e) \geq d(u)+d(v)-n </math> and use Cauchy–Schwarz inequality to esitimate the sum <math> \sum_{e=(u,v)\in E} (d(u)+d(v))</math>.

== Problem 4 ==
(Frankl 1986)

Let <math>\mathcal{F}\subseteq {[n]\choose k}</math> be a <math>k</math>-uniform family, and suppose that it satisfies that <math>A\cap B \not\subset C</math> for any <math>A,B,C\in\mathcal{F}</math>.
* Fix any <math>B\in\mathcal{F}</math>. Show that the family <math>\{A\cap B\mid A\in\mathcal{F}, A\neq B\}</math> is an anti chain.
* Show that <math>|\mathcal{F}|\le 1+{k\choose \lfloor k/2\rfloor}</math>.

== Problem 3 ==
(Goodman 1959)

Let <math> G=(V,E) </math> be a graph on <math> n </math> vertices and <math> t(G) </math> denote the number of triangles contained in the graph <math> G </math> or in its complement. Prove that <math> t(G)\geq \binom{n}{3}+\frac{2m^2}{n}-m(n-1)</math>.

'''Hint''': Let <math>t_i</math> be the number of triples of vertices <math>(i,j,k)</math> such that the vertex <math>i</math> is adjacent to precisely one of <math>j</math> or <math>k</math>.
Note that <math>t_i = d_i(n-1-d_i)</math> where <math>d_i</math> is the degree of the vertex <math>i</math>.
Show that <math>t(G) \geq \binom{n}{3}-\frac{1}{2}\sum_i t_i</math> and use the Cauchy–Schwarz to bound <math> \sum_i t_i </math>.

计算方法 Numerical method (Spring 2026)/Homework5 提交名单

Houzhe — Thu, 21 May 2026 06:01:02 GMT

Created page with " 如有错漏请邮件联系助教. <center> {| class="wikitable" |- ! 学号 !! 姓名 |- | 211502017 || 董科苇 |- | 221220104 || 刘宇平 |- | 231250084 || 谢钦煌 |- | 231502006 || 潘虢奕 |- | 231502021 || 李思哲 |- | 231820107 || 张苏畅 |- | 241098018 || 吴皓 |- | 241220023 || 陈天骢 |- | 241220026 || 徐浩然 |- | 241220028 || 周方裕 |- | 241220043 || 张涛 |- | 241220058 || 陈星宇 |- | 241220073 || 王子墨 |- | 241220085 |..."

New page

如有错漏请邮件联系助教.
<center>
{| class="wikitable"
|-
! 学号 !! 姓名
|-
| 211502017 || 董科苇
|-
| 221220104 || 刘宇平
|-
| 231250084 || 谢钦煌
|-
| 231502006 || 潘虢奕
|-
| 231502021 || 李思哲
|-
| 231820107 || 张苏畅
|-
| 241098018 || 吴皓
|-
| 241220023 || 陈天骢
|-
| 241220026 || 徐浩然
|-
| 241220028 || 周方裕
|-
| 241220043 || 张涛
|-
| 241220058 || 陈星宇
|-
| 241220073 || 王子墨
|-
| 241220085 || 朱思成
|-
| 241220088 || 张淇博
|-
| 241220107 || 黄毅
|-
| 241220113 || 欧阳元
|-
| 241220119 || 陈奕如
|-
| 241220129 || 付云锋
|-
| 241220146 || 潘祖凯
|-
| 241220158 || 王能
|-
| 241220162 || 董嘉璇
|-
| 241220174 || 韩江恺
|-
| 241240001 || 董清扬
|-
| 241240007 || 杨煦天
|-
| 241240008 || 张恒畅
|-
| 241240010 || 仲骐禾
|-
| 241240017 || 江子林
|-
| 241240028 || 冯时
|-
| 241240029 || 谢骐泽
|-
| 241240030 || 邢子寒
|-
| 241240032 || 崔佳雪
|-
| 241240033 || 付雨彤
|-
| 241240035 || 周玟序
|-
| 241240049 || 罗嘉恒
|-
| 241240050 || 李柱锃
|-
| 241240051 || 何明航
|-
| 241240061 || 周泽钰
|-
| 241240068 || 郑飞阳
|-
| 241240069 || 陈姝婷
|-
| 241240070 || 刘梦溪
|-
| 241275040 || 蔡易航
|-
| 241276008 || 袁颀沣
|-
| 241502001 || 马修齐
|-
| 241502002 || 赵祥羽
|-
| 241502003 || 钱昱岐
|-
| 241502004 || 董牧之
|-
| 241502005 || 朱羽宽
|-
| 241502007 || 孔浩文
|-
| 241502008 || 程致远
|-
| 241502009 || 刘功泽
|-
| 241502010 || 鲍辰睿
|-
| 241502011 || 陈锦浩
|-
| 241502012 || 陈俊恒
|-
| 241502014 || 史善邦
|-
| 241502015 || 蒋豪
|-
| 241502016 || 李子珅
|-
| 241502017 || 魏思远
|-
| 241502018 || 陈俍宇
|-
| 241502019 || 钟磊
|-
| 241502020 || 王嘉诚
|-
| 241502021 || 金昕炜
|-
| 241502023 || 李睿星
|-
| 241502025 || 孙兴
|-
| 241502026 || 陈新
|-
| 241830144 || 黄佳
|-
| 241830199 || 朱江
|-
| 241830220 || 邹宇灏
|-
| 241840078 || 张惠泽
|-
| 241840080 || 朱爽爽
|-
| 241840087 || 朱枻
|-
| 241850002 || 张子腾
|-
| 241870076 || 李聿文
|-
| 241870148 || 赵彦杰
|}
</center>
共 74 人

计算方法 Numerical method (Spring 2026)

Houzhe — Thu, 21 May 2026 05:58:29 GMT

Assignments

← Older revision		Revision as of 05:58, 21 May 2026
(One intermediate revision by the same user not shown)
Line 94:		Line 94:
	# [[Media:Computational Method 2026 Assignments 3.pdf\|Homework3]] 请在2026年04月15日23点59分之前提交到 nm_nju_2026@163.com (文件名为'学号_姓名_A3.pdf') [[计算方法 Numerical method (Spring 2026)/Homework3 提交名单\|Homework3 提交名单]]		# [[Media:Computational Method 2026 Assignments 3.pdf\|Homework3]] 请在2026年04月15日23点59分之前提交到 nm_nju_2026@163.com (文件名为'学号_姓名_A3.pdf') [[计算方法 Numerical method (Spring 2026)/Homework3 提交名单\|Homework3 提交名单]]
	# [[Media:Computational Method 2026 Assignments 4.pdf\|Homework4]] 请在2026年05月06日23点59分之前提交到 nm_nju_2026@163.com (文件名为'学号_姓名_A4.pdf') [[计算方法 Numerical method (Spring 2026)/Homework4 提交名单\|Homework4 提交名单]]		# [[Media:Computational Method 2026 Assignments 4.pdf\|Homework4]] 请在2026年05月06日23点59分之前提交到 nm_nju_2026@163.com (文件名为'学号_姓名_A4.pdf') [[计算方法 Numerical method (Spring 2026)/Homework4 提交名单\|Homework4 提交名单]]
	# [[Media:Computational Method 2026 Assignments 5.pdf\|Homework5]] 请在2026年05月20日23点59分之前提交到 nm_nju_2026@163.com (文件名为'学号_姓名_A5.pdf')		# [[Media:Computational Method 2026 Assignments 5.pdf\|Homework5]] 请在2026年05月20日23点59分之前提交到 nm_nju_2026@163.com (文件名为'学号_姓名_A5.pdf') [[计算方法 Numerical method (Spring 2026)/Homework5 提交名单\|Homework5 提交名单]]
			# [[Media:Computational Method 2026 Assignments 6.pdf\|Homework6]] 请在2026年06月03日23点59分之前提交到 nm_nju_2026@163.com (文件名为'学号_姓名_A6.pdf')

	=Lecture Notes=		=Lecture Notes=

File:Computational Method 2026 Assignments 6.pdf

Houzhe — Wed, 20 May 2026 13:39:47 GMT

Houzhe uploaded a new version of File:Computational Method 2026 Assignments 6.pdf

New page

Computational Method 2026 Assignments 6

组合数学 (Fall 2026)/Ramsey theory

Etone — Wed, 20 May 2026 13:33:09 GMT

Created page with "== Ramsey's Theorem == === Ramsey's theorem for graph === {{Theorem|Ramsey's Theorem| :Let <math>k,\ell</math> be positive integers. Then there exists an integer <math>R(k,\ell)</math> satisfying: :If <math>n\ge R(k,\ell)</math>, for any coloring of edges of <math>K_n</math> with two colors red and blue, there exists a red <math>K_k</math> or a blue <math>K_\ell</math>. }} {{Proof| We show that <math>R(k,\ell)</math> is finite by induction on <math>k+\ell</math>. For the..."

New page

== Ramsey's Theorem ==
=== Ramsey's theorem for graph ===
{{Theorem|Ramsey's Theorem|
:Let <math>k,\ell</math> be positive integers. Then there exists an integer <math>R(k,\ell)</math> satisfying:
:If <math>n\ge R(k,\ell)</math>, for any coloring of edges of <math>K_n</math> with two colors red and blue, there exists a red <math>K_k</math> or a blue <math>K_\ell</math>.
}}
{{Proof|
We show that <math>R(k,\ell)</math> is finite by induction on <math>k+\ell</math>. For the base case, it is easy to verify that
:<math>R(k,1)=R(1,\ell)=1</math>.
For general <math>k</math> and <math>\ell</math>, we will show that
:<math>R(k,\ell)\le R(k,\ell-1)+R(k-1,\ell)</math>.
Suppose we have a two coloring of <math>K_n</math>, where <math>n=R(k,\ell-1)+R(k-1,\ell)</math>. Take an arbitrary vertex <math>v</math>, and split <math>V\setminus\{v\}</math> into two subsets <math>S</math> and <math>T</math>, where
:<math>\begin{align}
S&=\{u\in V\setminus\{v\}\mid uv \text{ is blue }\}\\
T&=\{u\in V\setminus\{v\}\mid uv \text{ is red }\}
\end{align}</math>
Since
:<math>|S|+|T|+1=n=R(k,\ell-1)+R(k-1,\ell)</math>,
we have either <math>|S|\ge R(k,\ell-1)</math> or <math>|T|\ge R(k-1,\ell)</math>. By symmetry, suppose <math>|S|\ge R(k,\ell-1)</math>. By induction hypothesis, the complete subgraph defined on <math>S</math> has either a red <math>K_k</math>, in which case we are done; or a blue <math>K_{\ell-1}</math>, in which case the complete subgraph defined on <math>S\cup{v}</math> must have a blue <math>K_\ell</math> since all edges from <math>v</math> to vertices in <math>S</math> are blue.
}}

{{Theorem|Ramsey's Theorem (graph, multicolor)|
:Let <math>r, k_1,k_2,\ldots,k_r</math> be positive integers. Then there exists an integer <math>R(r;k_1,k_2,\ldots,k_r)</math> satisfying:
:For any <math>r</math>-coloring of a complete graph of <math>n\ge R(r;k_1,k_2,\ldots,k_r)</math> vertices, there exists a monochromatic <math>k_i</math>-clique with the <math>i</math>th color for some <math>i\in\{1,2,\ldots,r\}</math>.
}}

{{Theorem|Lemma (the "mixing color" trick)|
:<math>R(r;k_1,k_2,\ldots,k_r)\le R(r-1;k_1,k_2,\ldots,k_{r-2},R(2;k_{r-1},k_r))</math>
}}
{{Proof|
We transfer the <math>r</math>-coloring to <math>(r-1)</math>-coloring by identifying the <math>(r-1)</math>th and the <math>r</math>th colors.

If <math>n\ge R(r-1;k_1,k_2,\ldots,k_{r-2},R(2;k_{r-1},k_r))</math>, then for any <math>r</math>-coloring of <math>K_n</math>, there either exist an <math>i\in\{1,2,\ldots,r-2\}</math> and a <math>k_i</math>-clique which is monochromatically colored with the <math>i</math>th color; or exists clique of <math>R(2;k_{r-1},k_r)</math> vertices which is monochromatically colored with the mixed color of the original <math>(r-1)</math>th and <math>r</math>th colors, which again implies that there exists either a <math>k</math>-clique which is monochromatically colored with the original <math>(r-1)</math>th color, or a <math>\ell</math>-clique which is monochromatically colored with the original <math>r</math>th color. This implies the recursion.
}}

=== Ramsey number ===
The smallest number <math>R(k,\ell)</math> satisfying the condition in the Ramsey theory is called the '''Ramsey number'''.

Alternatively, we can define <math>R(k,\ell)</math> as the smallest <math>N</math> such that if <math>n\ge N</math>, for any 2-coloring of <math>K_n</math> in red and blue, there is either a red <math>K_k</math> or a blue <math>K_\ell</math>. The Ramsey theorem is stated as:
:"''<math>R(k,\ell)</math> is finite for any positive integers <math>k</math> and <math>\ell</math>.''"

The core of the inductive proof of the Ramsey theorem is the following recursion
:<math>\begin{align}
R(k,1) &=R(1,\ell)=1\\
R(k,\ell) &\le R(k,\ell-1)+R(k-1,\ell).
\end{align}</math>

From this recursion, we can deduce an upper bound for the Ramsey number.
{{Theorem|Theorem|
:<math>R(k,\ell)\le{k+\ell-2\choose k-1}</math>.
}}
{{Proof|It is easy to verify the bound by induction.
}}

------

The following theorem is due to Spencer in 1975, which is the best known lower bound for diagonal Ramsey number.

{{Theorem|Theorem (Spencer 1975)|
:<math>R(k,k)\ge Ck2^{k/2}</math> for some constant <math>C>0</math>.
}}

Its proof uses the Lovász local lemma in the probabilistic method.
{{Theorem
|Lovász Local Lemma (symmetric case)|
:Let <math>A_1,A_2,\ldots,A_n</math> be a set of events, and assume that the following hold:
:#for all <math>1\le i\le n</math>, <math>\Pr[A_i]\le p</math>;
:# each event <math>A_i</math> is independent of all but at most <math>d</math> other events, and
:::<math>ep(d+1)\le 1</math>.
:Then
::<math>\Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right]>0</math>.
}}

We can use the local lemma to prove a lower bound for the diagonal Ramsey number.
{{Proof|
To prove a lower bound <math>R(k,k)>n</math>, it is sufficient to show that there exists a 2-coloring of <math>K_n</math> without a monochromatic <math>K_k</math>. We prove this by the probabilistic method.

Pick a random 2-coloring of <math>K_n</math> by coloring each edge uniformly and independently with one of the two colors. For any set <math>S</math> of <math>k</math> vertices, let <math>A_S</math> denote the event that <math>S</math> forms a monochromatic <math>K_k</math>. It is easy to see that <math>\Pr[A_s]=2^{1-{k\choose 2}}=p</math>.

For any <math>k</math>-subset <math>T</math> of vertices, <math>A_S</math> and <math>A_T</math> are dependent if and only if <math>|S\cap T|\ge 2</math>. For each <math>S</math>, the number of <math>T</math> that <math>|S\cap T|\ge 2</math> is at most <math>{k\choose 2}{n\choose k-2}</math>, so the max degree of the dependency graph is <math>d\le{k\choose 2}{n\choose k-2}</math>.

Take <math>n=Ck2^{k/2}</math> for some appropriate constant <math>C>0</math>.
:<math>
\begin{align}
\mathrm{e}p(d+1)
&\le \mathrm{e}2^{1-{k\choose 2}}\left({k\choose 2}{n\choose k-2}+1\right)\\
&\le 2^{3-{k\choose 2}}{k\choose 2}{n\choose k-2}\\
&\le 1
\end{align}
</math>
Applying the local lemma, the probability that there is no monochromatic <math>K_k</math> is
:<math>\Pr\left[\bigwedge_{S\in{[n]\choose k}}\overline{A_S}\right]>0</math>.
Therefore, there exists a 2-coloring of <math>K_n</math> which has no monochromatic <math>K_k</math>, which means
:<math>R(k,k)>n=Ck2^{k/2}</math>.
}}

{{Theorem|Theorem|
:<math>\Omega\left(k2^{k/2}\right)\le R(k,k)\le{2k-2\choose k-1}=O\left(k^{-1/2}4^{k}\right)</math>.
}}

{| class="wikitable"
! ''<math>k</math>'',''<math>l</math>''
! 1
! 2
! 3
! 4
! 5
! 6
! 7
! 8
! 9
! 10
|-
! 1
| 1
| 1
| 1
| 1
| 1
| 1
| 1
| 1
| 1
| 1
|-
! 2
| 1
| 2
| 3
| 4
| 5
| 6
| 7
| 8
| 9
| 10
|-
! 3
| 1
| 3
| 6
| 9
| 14
| 18
| 23
| 28
| 36
| 40–43
|-
! 4
| 1
| 4
| 9
| 18
| 25
| 35–41
| 49–61
| 56–84
| 73–115
| 92–149
|-
! 5
| 1
| 5
| 14
| 25
| 43–49
| 58–87
| 80–143
| 101–216
| 125–316
| 143–442
|-
! 6
| 1
| 6
| 18
| 35–41
| 58–87
| 102–165
| 113–298
| 127–495
| 169–780
| 179–1171
|-
! 7
| 1
| 7
| 23
| 49–61
| 80–143
| 113–298
| 205–540
| 216–1031
| 233–1713
| 289–2826
|-
! 8
| 1
| 8
| 28
| 56–84
| 101–216
| 127–495
| 216–1031
| 282–1870
| 317–3583
| 317-6090
|-
! 9
| 1
| 9
| 36
| 73–115
| 125–316
| 169–780
| 233–1713
| 317–3583
| 565–6588
| 580–12677
|-
! 10
| 1
| 10
| 40–43
| 92–149
| 143–442
| 179–1171
| 289–2826
| 317-6090
| 580–12677
| 798–23556
|}

=== Ramsey's theorem for hypergraph ===
{{Theorem|Ramsey's Theorem (hypergraph, multicolor)|
:Let <math>r, t, k_1,k_2,\ldots,k_r</math> be positive integers. Then there exists an integer <math>R_t(r;k_1,k_2,\ldots,k_r)</math> satisfying:
:For any <math>r</math>-coloring of <math>{[n]\choose t}</math> with <math>n\ge R_t(r;k_1,k_2,\ldots,k_r)</math>, there exist an <math>i\in\{1,2,\ldots,r\}</math> and a subset <math>X\subseteq [n]</math> with <math>|X|\ge k_i</math> such that all members of <math>{X\choose t}</math> are colored with the <math>i</math>th color.
}}

<math>n\rightarrow(k_1,k_2,\ldots,k_r)^t</math>

{{Theorem|Lemma (the "mixing color" trick)|
:<math>R_t(r;k_1,k_2,\ldots,k_r)\le R_t(r-1;k_1,k_2,\ldots,k_{r-2},R_t(2;k_{r-1},k_r))</math>
}}

It is then sufficient to prove the Ramsey's theorem for the two-coloring of a hypergraph, that is, to prove <math>R_t(k,\ell)=R_t(2;k,\ell)</math> is finite.

{{Theorem|Lemma|
:<math>R_t(k,\ell)\le R_{t-1}(R_t(k-1,\ell),R_t(k,\ell-1))+1</math>
}}
{{Proof|
Let <math>n=R_{t-1}(R_t(k-1,\ell),R_t(k,\ell-1))+1</math>. Denote <math>[n]=\{1,2,\ldots,n\}</math>.

Let <math>f:{[n]\choose t}\rightarrow\{{\color{red}\text{red}},{\color{blue}\text{blue}}\}</math> be an arbitrary 2-coloring of <math>{[n]\choose t}</math>. It is then sufficient to show that there either exists an <math>X\subseteq[n]</math> with <math>|X|=k</math> such that all members of <math>{X\choose t}</math> are colored red by <math>f</math>; or exists an <math>X\subseteq[n]</math> with <math>|X|=\ell</math> such that all members of <math>{X\choose t}</math> are colored blue by <math>f</math>.

We remove <math>n</math> from <math>[n]</math> and define a new coloring <math>f'</math> of <math>{[n-1]\choose t-1}</math> by
:<math>f'(A)=f(A\cup\{n\})</math> for any <math>A\in{[n-1]\choose t-1}</math>.
By the choice of <math>n</math> and by symmetry, there exists a subset <math>S\subseteq[n-1]</math> with <math>|X|=R_t(k-1,\ell)</math> such that all members of <math>{S\choose t-1}</math> are colored with red by <math>f'</math>. Then there either exists an <math>X\subseteq S</math> with <math>|X|=\ell</math> such that <math>{X\choose t}</math> is colored all blue by <math>f</math>, in which case we are done; or exists an <math>X\subseteq S</math> with <math>|X|=k-1</math> such that <math>{X\choose t}</math> is colored all red by <math>f</math>. Next we prove that in the later case <math>{X\cup{n}\choose t}</math> is all red, which will close our proof. Since all <math>A\in{S\choose t-1}</math> are colored with red by <math>f'</math>, then by our definition of <math>f'</math>, <math>f(A\cup\{n\})={\color{red}\text{red}}</math> for all <math>A\in {X\choose t-1}\subseteq{S\choose t-1}</math>. Recalling that <math>{X\choose t}</math> is colored all red by <math>f</math>, <math>{X\cup\{n\}\choose t}</math> is colored all red by <math>f</math> and we are done.
}}

== Applications of Ramsey Theorem ==
=== The "Happy Ending" problem ===
{{Theorem|The happy ending problem|
:Any set of 5 points in the plane, no three on a line, has a subset of 4 points that form the vertices of a convex quadrilateral.
}}
See the article
[http://www.maa.org/mathland/mathtrek_10_3_00.html] for the proof.

We say a set of points in the plane in [http://en.wikipedia.org/wiki/General_position '''general positions'''] if no three of the points are on the same line.

{{Theorem|Theorem (Erdős-Szekeres 1935)|
:For any positive integer <math>m\ge 3</math>, there is an <math>N(m)</math> such that any set of at least <math>N(m)</math> points in general position in the plane (i.e., no three of the points are on a line) contains <math>m</math> points that are the vertices of a convex <math>m</math>-gon.
}}
{{Proof|
Let <math>N(m)=R_3(m,m)</math>. For <math>n\ge N(m)</math>, let <math>X</math> be an arbitrary set of <math>n</math> points in the plane, no three of which are on a line. Define a 2-coloring of the 3-subsets of points <math>f:{X\choose 3}\rightarrow\{0,1\}</math> as follows: for any <math>\{a,b,c\}\in{X\choose 3}</math>, let <math>\triangle_{abc}\subset X</math> be the set of points covered by the triangle <math>abc</math>; and <math>f(\{a,b,c\})=|\triangle_{abc}|\bmod 2</math>, that is, <math>f(\{a,b,c\})</math> indicates the oddness of the number of points covered by the triangle <math>abc</math>.

Since <math>|X|\ge R_3(m,m)</math>, there exists a <math>Y\subseteq X</math> such that <math>|Y|=m</math> and all members of <math>{Y\choose 3}</math> are colored with the same value by <math>f</math>.

We claim that the <math>m</math> points in <math>Y</math> are the vertices of a convex <math>m</math>-gon. If otherwise, by the definition of convexity, there exist <math>\{a,b,c,d\}\subseteq Y</math> such that <math>d\in\triangle_{abc}</math>. Since no three points are in the same line,
:<math>\triangle_{abc}=\triangle_{abd}\cup\triangle_{acd}\cup\triangle_{bcd}\cup\{d\}</math>,
where all unions are disjoint. Then <math>|\triangle_{abc}|=|\triangle_{abd}|+|\triangle_{acd}|+|\triangle_{bcd}|+1</math>, which implies that <math>f(\{a,b,c\}), f(\{a,b,d\}), f(\{a,c,d\}), f(\{b,c,d\})\,</math> cannot be equal, contradicting that all members of <math>{Y\choose 3}</math> have the same color.
}}

=== Yao's lower bound for implicit data structures ===
We consider the following fundamental problem of '''membership query'''.
{{Theorem|Membership Query|
:'''Input''': A data set <math>S\subset U</math> of size <math>n</math>, where <math>U</math> is a data universe of size <math>N</math>.
:'''Query''': a data item (also called a '''key''') <math>x\in U</math>.
:'''Answer''': Whether <math>x\in S</math>.
}}
This is a basic problem for data structures. People want to design efficient data structures to store the data set <math>S</math> so that the query "Is <math>x\in S</math>?" can be efficiently answered by accessing the data structure as little as possible in the worst case.

A '''sorted table''' for a data set <math>S\subset [N]</math> is a natural data structure in which the elements of <math>S=\{x_1,x_2,\ldots,x_n\}</math>, where <math>x_1<x_2<\cdots<x_n</math>, are stored in an array, one element <math>x_i</math> in each entry, in the increasing order.
For a sorted table, the membership query problem can be solved via '''binary search''' within <math>\Omega(\log_2 n)</math> memory accesses in the worst case. The following [https://dl.acm.org/doi/pdf/10.1145/322261.322274 fundamental result of Andrew Chi-Chih Yao (姚期智)] shows that this is the best possible for sorted tables. The proof is an elegant application of the '''adversarial argument'''(对手论证).

{{Theorem|Lemma (Yao 1981)|
:Suppose that <math>n\ge 2</math>, <math>N\ge 2n-1</math>, the data universe is <math>U=[N]</math>, and the size of the data set is <math>n</math>.
:If the data structure is a '''sorted table''', any search algorithm requires at least <math>\lceil\log_2 (n+1)\rceil</math> accesses to the data structure in the worst case.
}}
{{Proof|
We will show by an adversarial argument that <math>\lceil\log_2 (n+1)\rceil</math> accesses are required to search for the key value <math>x=n</math> in the universe <math>[N]=\{1,2,\ldots,N\}</math>. The construction of the adversarial data set <math>S</math> is by induction on <math>n</math>.

For <math>n=2</math> and <math>N\ge 2n-1=3</math> it is easy to see that 2 memory accesses are required to make sure whether the key value <math>n=2</math> presents in a sorted table containing 2 keys out of a data universe of size 3, in the worst case.

Let <math>n>2</math>. Assume the induction hypothesis for all smaller <math>n</math>. We will prove it for the size of data set <math>n</math>, size of universe <math>N\ge 2n-1</math> and the search key <math>x=n</math>.

Suppose that the first access position is <math>k</math>. The adversary chooses the table content <math>T[k]</math>. The adversary's strategy is:
:<math>
\begin{align}
T[k]=
\begin{cases}
k & k\le \frac{n}{2},\\
N-(n-k) & k> \frac{n}{2}.
\end{cases}
\end{align}
</math>
By symmetry, suppose it is the first case that <math>k\le \frac{n}{2}</math>. Then the key <math>x=n</math> may be in any position <math>i</math>, where <math>\frac{n}{2}+1\le i\le n</math>. In fact, <math>T\left[ \left\lceil \frac{n}{2}\right\rceil +1\right]</math> through <math>T[n]</math> is a sorted table of size <math>n'=\left\lfloor \frac{n}{2}\right\rfloor</math> which may contain any <math>n'</math>-subset of <math>\left\{\left\lceil \frac{n}{2}\right\rceil+1, \left\lceil \frac{n}{2}\right\rceil+2,\ldots,N\right\}</math>, and hence, in particular, any <math>n'</math>-subset of the new universe
:<math>U'=\left\{\left\lceil \frac{n}{2}\right\rceil+1, \left\lceil \frac{n}{2}\right\rceil+2,\ldots,N-\left\lceil \frac{n}{2}\right\rceil\right\}</math>.
The size <math>N'</math> of <math>U'</math> satisfies
:<math>N'=N-2\left\lceil \frac{n}{2}\right\rceil\ge 2(n-1)-2\left\lceil \frac{n}{2}\right\rceil \ge 2\left\lfloor \frac{n}{2}\right\rfloor-1= 2n'-1</math>,
and the desired key <math>n</math> has the relative value <math>x'=n- \left\lceil \frac{n}{2}\right\rceil=\left\lfloor \frac{n}{2}\right\rfloor=n'</math> in the new universe <math>U'</math>.

By the induction hypothesis, <math>\lceil\log_2 (n'+1)\rceil</math> more memory accesses will be required. Hence the total number of memory accesses is at least
:<math>1+\lceil\log_2 (n'+1)\rceil=1+\left\lceil\log_2 \left(\left\lfloor \frac{n}{2}\right\rfloor+1\right)\right\rceil\ge \lceil\log_2 (n+1)\rceil</math>.

If the first access is <math>k> \frac{n}{2}</math>, we symmetrically get that <math>T[1]</math> through <math>T\left[\left\lfloor \frac{n}{2}\right\rfloor\right]</math> is a sorted table of size <math>n'=\left\lfloor \frac{n}{2}\right\rfloor</math> which may contain any <math>n'</math>-subset of the universe
:<math>U'=\left\{\left\lceil \frac{n}{2}\right\rceil+1, \left\lceil \frac{n}{2}\right\rceil+2,\ldots,N-\left\lceil \frac{n}{2}\right\rceil\right\}</math>.
The rest is the same as before. This completes the induction.
}}

We have seen that on a sorted table, there is no search algorithm outperforming the binary search in the worst case.
Our question is:
:''Is there any other order than the increasing order, on which there is a better search algorithm?''

An '''implicit data structure''' use no extra space in addition to the original data set, thus a data structure can only be represented ''implicitly'' by the order of the data items in the table. That is, each data set is stored as a permutation of the set. Formally, an implicit data structure is described by a function
:<math>f:{U\choose n}\rightarrow[n!]</math>,
where each <math>\pi\in[n!]</math> specify a permutation of the sorted table, and a data set <math>S=\{x_1,x_2,\ldots,x_n\}</math> where <math>x_1<x_2<\cdots<x_n</math> is stored as an array <math>(x_{\pi(1)},x_{\pi(2)},\ldots,x_{\pi(n)}\}</math> where <math>\pi=f(S)</math>.

Thus, the sorted table is the simplest implicit data structure, in which <math>f(S)</math> always gives the identity permutation for all <math>S\in{U\choose n}</math>.
We observe that if <math>f</math> maps all data sets <math>S\in{U\choose n}</math> to the same permutation <math>\pi</math>, then the data structure is equivalent to the sorted table, under the bijection that the <math>i</math>th entry in the sorted table corresponds to the <math>\pi(i)</math>th entry of the actual array, where the same <math>\Omega(\log_2 n)</math> lower bound applies.

This observation can be generalized and made formal as follows.

{{Theorem|Observation|
:If there is a sub-universe <math>X\subseteq U</math> such that for every data set <math>S\in {X\choose n}</math>, the implicit data structure <math>f(S)=\pi</math> stores the data set using the the same permutation <math>\pi</math>, i.e.
::<math>f\left({X\choose n}\right)=\{\pi\}</math>
:then this implicit data structure is equivalent to the sorted table for all data sets from the new universe <math>X</math>, under the bijection that the <math>i</math>th entry in the sorted table corresponds to the <math>\pi(i)</math>th entry of the array.
:Therefore, if <math>|X|\ge 2n</math>, then the same <math>\Omega(\log_2 n)</math> lower bound for searching in a sorted table applies.
}}

Due to Ramsey theorem, for sufficiently large <math>N</math> which satisfies <math>N\ge R_{n}(n!;2n)</math>, for any <math>f:{U\choose n}\rightarrow[n!]</math>, there is an <math>X\subseteq U</math> of size <math>|X|\ge 2n</math>, such that <math>\left|f\left({X\choose n}\right)\right|=1</math>, which guarantees the existence of the sub-universe <math>X\subseteq U</math> required in the above observation for (wildly) large universe sizes <math>N</math>, which implies the following lower bound for implicit data structures.

{{Theorem|Theorem (Yao 1981)|
:Suppose that <math>n\ge 2</math>, and <math>N\ge 2n</math>, the data universe is <math>U=[N]</math>, and the size of the data set is <math>n</math>.
:For any '''implicit data structure''', if <math>N</math> is sufficiently large, then any search algorithm requires at least <math>\lfloor\log_2 n\rfloor</math> accesses to the data structure in the worst case.
}}

=== Linial's lower bound for local computation===
In the studies of '''local computation''' (initiated by [https://www.cs.huji.ac.il/~nati/PAPERS/locality_dist_graph_algs.pdf Linial] and [https://www.wisdom.weizmann.ac.il/~naor/PAPERS/lcl.pdf Naor and Stockmeyer]), people wants to answer questions like:
::''Can locally defined problems be computed locally?''
In general, the answer is no to the above question. A famous example is Linial's lower bound for '''maximal independent set''' ('''MIS''') in a ring.

Consider a very simple distributed network, a ring that contains <math>n</math> nodes, where each node is assigned a unique ID from <math>[n]=\{1,2,\ldots, n\}</math>. The labeled network is then described by a tuple <math>(a_1,a_2,\ldots,a_n)</math> of IDs, which is a permutation of <math>[n]</math>, where <math>a_i\in [n]</math> gives the ID of the <math>i</math>th node in the ring.

In a distributed algorithm, in each round, every node communicates with its 2 neighbors in the ring, and when the algorithm terminates, each node returns its local output. For example, in the MIS problem, the goal of the algorithm is to construct a maximal independent set: upon termination, each node returns a bit to indicate whether the node is in the constructed independent set. And the output gives a correct MIS as long as it satisfies both the followings:
* there are no two consecutive nodes in the ring both outputting 1;
* there are no three consecutive nodes in the ring all outputting 0.
This is clearly a locally defined problem. In fact, it is a constraint satisfaction problem (CSP) where each constraint only involves 1-local or 2-local neighborhood.

We are interested in the distributed algorithms that can always produce the correct answer, and want to prove a lower bound for the number of rounds required in the worst case by such distributed algorithms.

As a local distributed algorithm, each node <math>i</math> initially does not know anything beyond its local information, which is just its own ID <math>a_i\in [n]</math>.
And after <math>t</math> rounds, information-theoretically, each node <math>i</math> can at best know all information within its <math>t</math>-local neighborhood, which is represented by the <math>(2t-1)</math>-tuple <math>(a_{i-t},\ldots,a_{i-1},a_i,a_{i+1},\ldots a_{i+t})</math>, with the addition/subtraction modulo <math>n</math> along the ring.

This suggests us to define such a computational model for local distributed algorithms: any <math>t</math>-round local algorithm is described by a function
:<math>\mathcal{L}:[n]^{2t+1}\to\{0,1\}</math>.
For the <math>i</math>th node in the ring, its output is given by <math>\mathcal{L}(a_{i-t},\ldots,a_{i-1},a_i,a_{i+1},\ldots a_{i+t})</math>, where <math>a_j</math> represents the ID of the <math>j</math>th node in the ring, with the addition/subtraction modulo <math>n</math>.

As a correct algorithm for constructing MIS, it must hold that any three consecutive nodes can never output the same value. We then have the following lower bound for <math>t</math> for such algorithms.

{{Theorem|Theorem (Linial 1992)|
:For any <math>t</math>-round local algorithm for maximal independent set (MIS) on a ring of <math>n</math> nodes, it holds that
:: <math>t=\Omega(\log^*n)</math>
:where <math>\log^*n</math> represents the [https://en.wikipedia.org/wiki/Iterated_logarithm iterated logarithm], which is the number of times the logarithm function must be iteratively applied to <math>n</math> before the result is less than or equal to 1.
}}
This lower bound shows that even on very simple network like ring, some very basic locally defined problem (MIS) cannot be computed locally (within constant locality).

The original proof of Linial relies on chromatic number of so-called neighborhood graphs. Here we give an alternative proof based on Ramsey theorem found by Baruch Awerbuch.
{{Proof|
As we discussed earlier, any <math>t</math>-round local algorithm can be represented by a mapping
:<math>\mathcal{L}:[n]^{2t+1}\to\{0,1\}</math>.
It can naturally defines a 2-coloring:
:<math>f:{[n]\choose {2t+1}}\to\{0,1\}</math>
by the following construction: for any <math>\{a_1,a_2,\ldots,a_{2t+1}\}\subseteq [n]</math>, where <math>a_1<a_2<\cdots<a_{2t+1}</math>, we define
:<math>f(\{a_1,a_2,\ldots,a_{2t+1}\})=\mathcal{L}(a_1,a_2,\ldots,a_{2t+1})</math>.
By Ramsey theorem, for <math>n\ge R_{2t+1}(2;2t+3,2t+3)</math>, there exists a subset <math>\{a_1,a_2,\ldots,a_{2t+3}\}\subseteq [n]</math>, where <math>a_1<a_2<\cdots<a_{2t+3}</math>, such that
:<math>\left|f\left({S\choose {2t+1}}\right)\right|=1</math>.
By our construction of <math>f</math>, this means
:<math>\mathcal{L}(a_1,a_2,\ldots,a_{2t+1})=\mathcal{L}(a_2,a_3,\ldots,a_{2t+2})=\mathcal{L}(a_3,a_4,\ldots,a_{2t+3})</math>,
which contradicts to that the output of <math>\mathcal{L}</math> should indicate an MIS, on any ring with <math>2t+3</math> consecutive nodes labeled as <math>(a_1,a_2,\ldots,a_{2t+3})</math>, because on such rings, there would be 3 consecutive nodes with the same output bit.

Therefore, any <math>t</math>-round local algorithm that can always correctly produce an MIS on a ring, must satisfies that
:<math>n<R_{2t+1}(2;2t+3,2t+3)\le \underbrace{2^{2^{\unicode{x22F0}^{2}}}}_{ct}</math>,
for some constant <math>c>0</math>, whose inverse function gives the lower bound
:<math>t=\Omega(\log^*n)</math>.
}}

组合数学 (Spring 2026)

Etone — Wed, 20 May 2026 13:32:42 GMT

Lecture Notes

← Older revision		Revision as of 13:32, 20 May 2026
Line 114:		Line 114:
	#* [https://mathweb.ucsd.edu/~ronspubs/90_03_erdos_ko_rado.pdf Old and new proofs of the Erdős–Ko–Rado theorem] by Frankl and Graham		#* [https://mathweb.ucsd.edu/~ronspubs/90_03_erdos_ko_rado.pdf Old and new proofs of the Erdős–Ko–Rado theorem] by Frankl and Graham
	#* An [http://tcs.nju.edu.cn/slides/comb2026/sunflower-note.pdf LLM-generated lecture note] on Alweiss-Lovet-Wu-Zhang's improvement over the sunflower lemma, with simplified proofs by Rao-Tao		#* An [http://tcs.nju.edu.cn/slides/comb2026/sunflower-note.pdf LLM-generated lecture note] on Alweiss-Lovet-Wu-Zhang's improvement over the sunflower lemma, with simplified proofs by Rao-Tao
			# [[组合数学 (Fall 2026)/Ramsey theory\|Ramsey theory \| Ramsey理论]]（[http://tcs.nju.edu.cn/slides/comb2026/Ramsey.pdf slides]）

	= Resources =		= Resources =

计算方法 Numerical method (Spring 2026)

Liuexp — Wed, 20 May 2026 05:51:14 GMT

Lecture Notes

← Older revision		Revision as of 05:51, 20 May 2026
Line 109:		Line 109:
	# [[Media:计算方法9-2026.pdf\|迭代法解线性方程组：梯度下降方法与共轭梯度]]		# [[Media:计算方法9-2026.pdf\|迭代法解线性方程组：梯度下降方法与共轭梯度]]
	# [[Media:计算方法10-2026.pdf\|幂迭代的特例：随机游走与马尔可夫链]]		# [[Media:计算方法10-2026.pdf\|幂迭代的特例：随机游走与马尔可夫链]]
	# 谱图论		# [[Media:计算方法11-2026.pdf\|谱图论]]
	# 电阻电路网络，碰撞时间和遍历时间		# 电阻电路网络，碰撞时间和遍历时间
	# 线性规划入门		# 线性规划入门
	# LP顶点，对偶性和零和游戏		# LP顶点，对偶性和零和游戏

File:计算方法11-2026.pdf

Liuexp — Wed, 20 May 2026 05:49:37 GMT

Liuexp uploaded File:计算方法11-2026.pdf

New page

计算方法11

计算方法 Numerical method (Spring 2026)

Houzhe — Wed, 20 May 2026 03:31:02 GMT

Assignments

← Older revision		Revision as of 03:31, 20 May 2026
(One intermediate revision by the same user not shown)
(No difference)

File:Computational Method 2026 Assignments 6.pdf

Houzhe — Mon, 18 May 2026 12:46:36 GMT

Houzhe uploaded File:Computational Method 2026 Assignments 6.pdf

New page

Computational Method 2026 Assignments 6

计算方法 Numerical method (Spring 2026)/Homework4 提交名单

Houzhe — Mon, 18 May 2026 12:34:02 GMT

← Older revision		Revision as of 12:34, 18 May 2026
Line 112:		Line 112:
	\|-		\|-
	\| 241502015 \|\| 蒋豪		\| 241502015 \|\| 蒋豪
			\|-
			\| 241502016 \|\| 李子珅
	\|-		\|-
	\| 241502017 \|\| 魏思远		\| 241502017 \|\| 魏思远
Line 148:		Line 150:
	\|}		\|}
	</center>		</center>
	共 71 人		共 72 人

概率论与数理统计 (Spring 2026)/第二次作业提交名单

Zhe — Sat, 16 May 2026 10:06:26 GMT

← Older revision		Revision as of 10:06, 16 May 2026
(One intermediate revision by the same user not shown)
Line 4:		Line 4:
	\|-		\|-
	! 学号 !! 姓名		! 学号 !! 姓名
			\|-
			\| 211830049 \|\| 王杰
	\|-		\|-
	\| 221180155 \|\| 许云鹏		\| 221180155 \|\| 许云鹏
Line 130:		Line 132:
	\|}		\|}
	</center>		</center>
	共 62 人。		共 63 人。

概率论与数理统计 (Spring 2026)

Yqzhu — Sat, 16 May 2026 09:56:42 GMT

Assignments

← Older revision		Revision as of 09:56, 16 May 2026
Line 125:		Line 125:

	*[[概率论与数理统计 (Spring 2026)/Problem Set 3\|Problem Set 3]] 请在 2026/5/13 上课之前(9am UTC+8)提交到 [mailto:pr2026_nju@163.com pr2026_nju@163.com] (文件名为'<font color=red >学号_姓名_A3.pdf</font>').		*[[概率论与数理统计 (Spring 2026)/Problem Set 3\|Problem Set 3]] 请在 2026/5/13 上课之前(9am UTC+8)提交到 [mailto:pr2026_nju@163.com pr2026_nju@163.com] (文件名为'<font color=red >学号_姓名_A3.pdf</font>').
			** [[概率论与数理统计 (Spring 2026)/第三次作业提交名单\|第三次作业提交名单]]

	*[[概率论与数理统计 (Spring 2026)/Problem Set 4\|Problem Set 4]] 请在 <font color=red>TBA</font> 上课之前(9am UTC+8)提交到 [mailto:pr2026_nju@163.com pr2026_nju@163.com] (文件名为'<font color=red >学号_姓名_A4.pdf</font>').		*[[概率论与数理统计 (Spring 2026)/Problem Set 4\|Problem Set 4]] 请在 <font color=red>TBA</font> 上课之前(9am UTC+8)提交到 [mailto:pr2026_nju@163.com pr2026_nju@163.com] (文件名为'<font color=red >学号_姓名_A4.pdf</font>').

概率论与数理统计 (Spring 2026)/第三次作业提交名单

Yqzhu — Sat, 16 May 2026 09:54:20 GMT

Created page with "如有错漏邮件请及时联系助教。 <center> {| class="wikitable" |- ! 学号 !! 姓名 |- | 211830049 || 王杰 |- | 221180155 || 许云鹏 |- | 221830067 || 张笑 |- | 221840103 || 曹南 |- | 231250084 || 谢钦煌 |- | 241098114 || 于静涵 |- | 241180041 || 赵瀚清 |- | 241220002 || 张瑞珉 |- | 241220003 || 沈琪皓 |- | 241220004 || 张宸源 |- | 241220095 || 王天祥 |- | 241220136 || 祁书轩 |- | 241240001 || 董清扬 |- | 241240004 || 陈仝..."

New page

如有错漏邮件请及时联系助教。
<center>
{| class="wikitable"
|-
! 学号 !! 姓名
|-
| 211830049 || 王杰
|-
| 221180155 || 许云鹏
|-
| 221830067 || 张笑
|-
| 221840103 || 曹南
|-
| 231250084 || 谢钦煌
|-
| 241098114 || 于静涵
|-
| 241180041 || 赵瀚清
|-
| 241220002 || 张瑞珉
|-
| 241220003 || 沈琪皓
|-
| 241220004 || 张宸源
|-
| 241220095 || 王天祥
|-
| 241220136 || 祁书轩
|-
| 241240001 || 董清扬
|-
| 241240004 || 陈仝
|-
| 241240007 || 杨煦天
|-
| 241240008 || 张恒畅
|-
| 241240017 || 江子林
|-
| 241240019 || 王祎泽
|-
| 241240022 || 潘诚懿
|-
| 241240029 || 谢骐泽
|-
| 241240032 || 崔佳雪
|-
| 241240033 || 付雨彤
|-
| 241240035 || 周玟序
|-
| 241240036 || 唐愉兵
|-
| 241240038 || 胡彦腾
|-
| 241240041 || 李东泽
|-
| 241240046 || 黄嘉诚
|-
| 241240048 || 康子凯
|-
| 241240049 || 罗嘉恒
|-
| 241240050 || 李柱锃
|-
| 241240051 || 何明航
|-
| 241240053 || 张家奇
|-
| 241240061 || 周泽钰
|-
| 241240066 || 贺子铭
|-
| 241240068 || 郑飞阳
|-
| 241240069 || 陈姝婷
|-
| 241240070 || 刘梦溪
|-
| 241276007 || 胡博
|-
| 241276008 || 袁颀沣
|-
| 241820122 || 商世雄
|-
| 241840052 || 李彦均
|-
| 241840065 || 荣恒嬉
|-
| 241840067 || 赵思景
|-
| 241840078 || 张惠泽
|-
| 241840087 || 朱枻
|-
| 241840113 || 曾睿鸣
|-
| 241840173 || 刘明俊
|-
| 241840199 || 陈诣涵
|-
| 241840240 || 李味鸿
|-
| 241850002 || 张子腾
|-
| 241870025 || 张科杰
|-
| 241870032 || 赵益
|-
| 241870077 || 张辰曦
|-
| 241870097 || 丁瀚铭
|-
| 241870230 || 闵文楷
|-
| 241870240 || 杨学舟
|-
| 241880173 || 陆知渔
|-
| 241880325 || 刘孟阳
|-
| 241880488 || 扶嘉年
|-
| 241880503 || 郑一鸣
|-
| 251275003 || 翟悦凯
|}
</center>
共 61 人。

计算理论之美 (Summer 2026)

Liumingmou — Thu, 14 May 2026 03:27:53 GMT

Tentative Schedule

← Older revision		Revision as of 03:27, 14 May 2026
(4 intermediate revisions by the same user not shown)
Line 15:		Line 15:
	}}		}}

	由南京大学计算机学院和智能软件学院支持的第5届“计算理论之美”暑期讲习班将于2026年7月24日至7月27日在江苏省苏州市南京大学苏州校区开班。本次讲习班将围绕算法设计主题开展系列报告，包括TBA等板块，主要面向对理论计算机科学以及计算机科学中的数学感兴趣的国内外本科生，安排4天的高级课程。内容深入浅出，由国内外一线的优秀学者讲授，使学员初步了解理论计算机科学的一些研究前沿、初步掌握一些新理论与新方法，为有志于从事理论计算机科学研究的学者打下一定的基础，也让从事其他相关方向研究的学生与教师们领略计算理论的魅力。		由南京大学计算机学院和智能软件学院支持的第5届“计算理论之美”暑期讲习班将于2026年7月24日至7月27日在江苏省苏州市南京大学苏州校区开班。本次讲习班将围绕算法设计主题开展系列报告，包括组合最优化、哈希表、差分隐私、量子计算、数据结构复杂性、图计算等板块，主要面向对理论计算机科学以及计算机科学中的数学感兴趣的国内外本科生，安排4天的高级课程。内容深入浅出，由国内外一线的优秀学者讲授，使学员初步了解理论计算机科学的一些研究前沿、初步掌握一些新理论与新方法，为有志于从事理论计算机科学研究的学者打下一定的基础，也让从事其他相关方向研究的学生与教师们领略计算理论的魅力。

	联系邮箱：nju_tcs@163.com		联系邮箱：nju_tcs@163.com
Line 42:		Line 42:
	Group photo: 7月TBD日上午茶歇环节中安排参会者合影留念		Group photo: 7月TBD日上午茶歇环节中安排参会者合影留念

			Speakers (in lexicographic order): 陈林（浙江大学）、刘明谋（南京大学）、Pasin Manurangsi（Google Research）、王启圣（上海交通大学）、俞华程（普林斯顿大学）、张天翼（南京大学）、TBD

	== Take-home Exams ==		== Take-home Exams ==
Line 56:		Line 56:

	== About Our Summer School ==		== About Our Summer School ==
	Our summer school is supported by the School of Computer Science and the School of Intelligent Software and Engineering at Nanjing University and will be held from July 24th to July 27th, 2026, at the Suzhou Campus of Nanjing University in Suzhou, Jiangsu Province, China. The theme of this year's summer school will be the design and analysis of algorithms, with topics ranging from ~~TBA~~ etc.		Our summer school is supported by the School of Computer Science and the School of Intelligent Software and Engineering at Nanjing University and will be held from July 24th to July 27th, 2026, at the Suzhou Campus of Nanjing University in Suzhou, Jiangsu Province, China. The theme of this year's summer school will be the design and analysis of algorithms, with topics ranging from combinatorial optimization, hash table design, differential privacy, quantum computing, data structure compelxity, and graph algorithms etc.
	Target audience will include aspiring undergraduate and graduate students from China and overseas, and the program will feature 4 days of advanced courses. The courses will be presented by leading young scholars both from within China and overseas, covering both cutting-edge research and modern toolkits in theoretical computer science.		Target audience will include aspiring undergraduate and graduate students from China and overseas, and the program will feature 4 days of advanced courses. The courses will be presented by leading young scholars both from within China and overseas, covering both cutting-edge research and modern toolkits in theoretical computer science.
	The summer school will help connect aspiring young students with young scholars to engage research in theoretical computer science, and embark on a journey to appreciate the charm of computational theory.		The summer school will help connect aspiring young students with young scholars to engage research in theoretical computer science, and embark on a journey to appreciate the charm of computational theory.

计算理论之美 (Summer 2026)

Liumingmou — Thu, 14 May 2026 02:02:26 GMT

Created page with "{{Infobox |name = Infobox |headerstyle = background:#4D72BE; |labelstyle = background:#DAE1F0; |header1 = 计算理论之美 |label2 = {{Nowrap|负责人}} |data2 = 黄棱潇 ([mailto:huanglingxiao@nju.edu.cn huanglingxiao@nju.edu.cn]) |label4 = 时间 |data4 = 2026.7.24 — 2026.7.27 |label5 = 地点 |data5 = {{Nowrap|南京大学苏州校区 TBA}} |belowstyle = background:#DAE1F0; |below = }} 由南京大学计算..."

New page

{{Infobox
|name = Infobox
|headerstyle = background:#4D72BE;
|labelstyle = background:#DAE1F0;

|header1 = 计算理论之美
|label2 = {{Nowrap|负责人}}
|data2 = 黄棱潇 ([mailto:huanglingxiao@nju.edu.cn huanglingxiao@nju.edu.cn])
|label4 = 时间
|data4 = 2026.7.24 — 2026.7.27
|label5 = 地点
|data5 = {{Nowrap|南京大学苏州校区 TBA}}
|belowstyle = background:#DAE1F0;
|below =
}}

由南京大学计算机学院和智能软件学院支持的第5届“计算理论之美”暑期讲习班将于2026年7月24日至7月27日在江苏省苏州市南京大学苏州校区开班。本次讲习班将围绕算法设计主题开展系列报告，包括TBA等板块，主要面向对理论计算机科学以及计算机科学中的数学感兴趣的国内外本科生，安排4天的高级课程。内容深入浅出，由国内外一线的优秀学者讲授，使学员初步了解理论计算机科学的一些研究前沿、初步掌握一些新理论与新方法，为有志于从事理论计算机科学研究的学者打下一定的基础，也让从事其他相关方向研究的学生与教师们领略计算理论的魅力。

联系邮箱：nju_tcs@163.com

联系人：
* 黄棱潇： huanglingxiao@nju.edu.cn
* 刘明谋： lmm@nju.edu.cn
* 班吟： 175227530@qq.com

注册报名流程：由于前几届报名人数过多，本届将会采用问卷初筛形式进行报名。请同学们先填写以下[TBA 调查问卷]:

TBA

通过初筛后的同学将提前两周收到包含报名链接的邮件。
南大同学仅需填写问卷，讲习班期间直接到会场听报告即可。

费用：本科生包住宿，非本科生不包含住宿。餐费自理
问卷报名截止日期： TBD

== Tentative Schedule ==

Venue (地点)：南京大学苏州校区TBA

Group photo: 7月TBD日上午茶歇环节中安排参会者合影留念

== Take-home Exams ==
成绩优秀的同学可推荐参加南京大学计算机学院预推免保研面试，并在录取后可凭借此次暑期讲习班申请两个研究生学分。

作业提交方式：发送电子版到邮箱nju_tcs@163.com

== Links to Past Summer Schools ==
* [[计算理论之美 (Summer 2025)|计算理论之美暑期学校 (Summer 2025)]]
* [[计算理论之美 (Summer 2024)|计算理论之美暑期学校 (Summer 2024)]]
* [[计算理论之美 (Summer 2023)|计算理论之美暑期学校 (Summer 2023)]]
* [[计算理论之美 (Summer 2021)|计算理论之美暑期学校 (Summer 2021)]]

== About Our Summer School ==
Our summer school is supported by the School of Computer Science and the School of Intelligent Software and Engineering at Nanjing University and will be held from July 24th to July 27th, 2026, at the Suzhou Campus of Nanjing University in Suzhou, Jiangsu Province, China. The theme of this year's summer school will be the design and analysis of algorithms, with topics ranging from TBA etc.
Target audience will include aspiring undergraduate and graduate students from China and overseas, and the program will feature 4 days of advanced courses. The courses will be presented by leading young scholars both from within China and overseas, covering both cutting-edge research and modern toolkits in theoretical computer science.
The summer school will help connect aspiring young students with young scholars to engage research in theoretical computer science, and embark on a journey to appreciate the charm of computational theory.

Accommodation (shared room) will be provided to undergraduates only.

Due to capacity, we prioritize undergraduates seeking to join NJU TCS group for PhD or for a research intern. To register, please fill out the following form: TBA

If you are selected into our summer school, you will receive a confirmation email.

组合数学 (Fall 2026)/Extremal set theory

Etone — Wed, 13 May 2026 08:49:22 GMT

Created page with "== Sunflowers == An set system is a '''sunflower''' if all its member sets intersect at the same set of elements. {{Theorem|Definition (sunflower)| : A set family <math>\mathcal{F}\subseteq 2^X</math> is a '''sunflower''' of size <math>r</math> with a '''core''' <math>C\subseteq X</math> if ::<math>\forall S,T\in\mathcal{F}</math> that <math>S\neq T</math>, <math>S\cap T=C</math>. }} Note that we do not require the core to be nonempty, thus a family of disjoint sets is..."

Show changes

组合数学 (Spring 2026)

Etone — Wed, 13 May 2026 08:48:27 GMT

Lecture Notes

← Older revision		Revision as of 08:48, 13 May 2026
(2 intermediate revisions by the same user not shown)
Line 110:		Line 110:
	# [[组合数学 (Fall 2026)/Existence problems\|Existence problems \| 存在性问题]]		# [[组合数学 (Fall 2026)/Existence problems\|Existence problems \| 存在性问题]]
	# [[组合数学 (Fall 2026)/The probabilistic method\|The probabilistic method \| 概率法]] ([http://tcs.nju.edu.cn/slides/comb2026/ProbMethod.pdf slides])		# [[组合数学 (Fall 2026)/The probabilistic method\|The probabilistic method \| 概率法]] ([http://tcs.nju.edu.cn/slides/comb2026/ProbMethod.pdf slides])
	# [[组合数学 (Fall 2026)/Extremal graph theory\|Extremal graph theory \| 极值图论]] ([http://tcs.nju.edu.cn/slides/~~comb2025~~/ExtremalGraphs.pdf slides])		# [[组合数学 (Fall 2026)/Extremal graph theory\|Extremal graph theory \| 极值图论]] ([http://tcs.nju.edu.cn/slides/comb2026/ExtremalGraphs.pdf slides])
			# [[组合数学 (Fall 2026)/Extremal set theory\|Extremal set theory \| 极值集合论]]（[http://tcs.nju.edu.cn/slides/comb2026/ExtremalSets.pdf slides]）
			#* [https://mathweb.ucsd.edu/~ronspubs/90_03_erdos_ko_rado.pdf Old and new proofs of the Erdős–Ko–Rado theorem] by Frankl and Graham
			#* An [http://tcs.nju.edu.cn/slides/comb2026/sunflower-note.pdf LLM-generated lecture note] on Alweiss-Lovet-Wu-Zhang's improvement over the sunflower lemma, with simplified proofs by Rao-Tao

	= Resources =		= Resources =

概率论与数理统计 (Spring 2026)

Liuexp — Wed, 13 May 2026 05:21:44 GMT

Lectures

← Older revision		Revision as of 05:21, 13 May 2026
Line 148:		Line 148:
	#* [https://measure.axler.net/MIRA.pdf Measure, Integration & Real Analysis] by Sheldon Axler		#* [https://measure.axler.net/MIRA.pdf Measure, Integration & Real Analysis] by Sheldon Axler
	#* [[概率论与数理统计 (Spring 2025)/An exercise on induced distribution\|An exercise on induced distribution]]		#* [[概率论与数理统计 (Spring 2025)/An exercise on induced distribution\|An exercise on induced distribution]]
	# [http://tcs.nju.edu.cn/slides/~~prob2025~~/Convergence.pdf 极限定理]		# [http://tcs.nju.edu.cn/slides/prob2026/Convergence.pdf 极限定理]
	#* 阅读：'''[BT] 第5章'''		#* 阅读：'''[BT] 第5章'''
	#* 阅读：'''[GS] Sections 5.7~5.10, 7.1~7.5'''		#* 阅读：'''[GS] Sections 5.7~5.10, 7.1~7.5'''

概率论与数理统计 (Spring 2026)

Zhe — Wed, 13 May 2026 00:35:03 GMT

Assignments

← Older revision		Revision as of 00:35, 13 May 2026
Line 125:		Line 125:

	*[[概率论与数理统计 (Spring 2026)/Problem Set 3\|Problem Set 3]] 请在 2026/5/13 上课之前(9am UTC+8)提交到 [mailto:pr2026_nju@163.com pr2026_nju@163.com] (文件名为'<font color=red >学号_姓名_A3.pdf</font>').		*[[概率论与数理统计 (Spring 2026)/Problem Set 3\|Problem Set 3]] 请在 2026/5/13 上课之前(9am UTC+8)提交到 [mailto:pr2026_nju@163.com pr2026_nju@163.com] (文件名为'<font color=red >学号_姓名_A3.pdf</font>').

			*[[概率论与数理统计 (Spring 2026)/Problem Set 4\|Problem Set 4]] 请在 <font color=red>TBA</font> 上课之前(9am UTC+8)提交到 [mailto:pr2026_nju@163.com pr2026_nju@163.com] (文件名为'<font color=red >学号_姓名_A4.pdf</font>').

	= Lectures =		= Lectures =

概率论与数理统计 (Spring 2026)

Liuexp — Tue, 12 May 2026 10:59:22 GMT

Lectures

← Older revision		Revision as of 10:59, 12 May 2026
Line 146:		Line 146:
	#* [https://measure.axler.net/MIRA.pdf Measure, Integration & Real Analysis] by Sheldon Axler		#* [https://measure.axler.net/MIRA.pdf Measure, Integration & Real Analysis] by Sheldon Axler
	#* [[概率论与数理统计 (Spring 2025)/An exercise on induced distribution\|An exercise on induced distribution]]		#* [[概率论与数理统计 (Spring 2025)/An exercise on induced distribution\|An exercise on induced distribution]]
			# [http://tcs.nju.edu.cn/slides/prob2025/Convergence.pdf 极限定理]
			#* 阅读：'''[BT] 第5章'''
			#* 阅读：'''[GS] Sections 5.7~5.10, 7.1~7.5'''

	= Concepts =		= Concepts =

File:Convergence-Prob-2026.pdf

Liuexp — Tue, 12 May 2026 10:57:36 GMT

Liuexp uploaded File:Convergence-Prob-2026.pdf

New page

Convergence-Prob-2026

概率论与数理统计 (Spring 2026)/Problem Set 4

Zhe — Tue, 12 May 2026 10:53:10 GMT

Add problems

New page

*每道题目的解答都要有完整的解题过程，中英文不限。

*我们推荐大家使用LaTeX, markdown等对作业进行排版。

*Bonus problem为附加题（选做）。

*为督促大家认真完成平时作业、扎实掌握课程内容，本课程期末考试将从作业题目中随机抽取部分题目进行考查。请大家务必重视每一次作业，认真理解解题思路。

*若考试中被抽取到的作业题目答错、答不完整或无法作答，将按照相关标准对作业进行扣分处理。

== Assumption throughout Problem Set 4==
Without further notice, we are working on probability space <math>(\Omega,\mathcal{F},\mathbf{Pr})</math>.

Without further notice, we assume that the expectation of random variables are well-defined.

The term <math>\log</math> used in this context refers to the natural logarithm.

== Problem 1 (Continuous Random Variables, 30 points)==
<ul>
<li> [Density function]
Determine the value of <math>C</math> such that <math>f(x) = C\exp(-x-e^{-x}), x\in \mathbb{R}</math> is a probability density function (PDF) for a continuous random variable.
</li>

<li>
[Independence] Let <math>X</math> and <math>Y</math> be independent and identically distributed continuous random variables with cumulative distribution function (CDF) <math>F</math> and probability density function (PDF) <math>f</math>. Find out the density functions of <math>V = \max\{X,Y\}</math> and <math>U = \min\{X,Y\}</math>.
</li>

<li>
[Correlation] Let <math>X</math> be uniformly distributed on <math>(-1,1)</math> and <math>Y_k = \cos(k \pi X)</math> for <math>k=1,2,\ldots,n</math>. Are the random variables <math>Y_1, Y_2, \ldots, Y_n</math> correlated? independent? You should prove your claim rigorously.
</li>

<li> [Expectation of random variables (I)]
Let <math>X</math> be a continuous random variable with mean <math>\mu</math> and cumulative distribution function (CDF) <math>F</math>.
<ul>
<li>
Suppose <math>X \ge 0</math>. Show that <math>\int_{0}^a F(x) dx = \int_{a}^{\infty} [1-F(x)] dx</math> if and only if <math>a = \mu</math>.
</li>
<li>
Suppose <math>X</math> has finite variance. Show that <math>g(a) = \mathbb{E}((X-a)^2)</math> achieves the minimum when <math>a = \mu</math>.
</li>
</ul>
</li>

<li>
[Expectation of random variables (II)] Let <math>X, Y</math> be two independent and identically distributed continuous random variables with cumulative distribution function (CDF) <math>F</math>. Furthermore, assume <math>X,Y</math> are non-negative. Show that <math>\mathbb{E}[|X-Y|] = 2 \left(\mathbb{E}[X] - \int_{0}^{\infty} (1-F(x))^2 dx\right)</math>
</li>

<li>
[Conditional distribution] Let <math>X</math> and <math>Y</math> be two random variables. The joint density of <math>X</math> and <math>Y</math> is given by <math>f(x,y) = c(x^2 - y^2)e^{-x}</math>, where <math>0\leq x <\infty</math> and <math>-x\leq y \leq x</math>. Here, <math>c\in \mathbb{R}_+</math> is a constant. Find out the conditional distribution of <math>Y</math>, given <math>X = x</math>.
</li>

<li>
[Uniform Distribution (I)] Let <math>P_i = (X_i,Y_i), 1\leq i\leq n</math>, be independent, uniformly distributed points in the unit square <math>[0,1]^2</math>. A point <math>P_i</math> is called "peripheral" if, for all <math>r = 1,2,\cdots,n</math>, either <math>X_r \leq X_i</math> or <math>Y_r \leq Y_i</math>, or both. Find out the expected number of peripheral points.
</li>

<li>
[Uniform Distribution (II)] Derive the moment generating function of the standard uniform distribution, i.e., uniform distribution on <math>(0,1)</math>.
</li>

<li>
[Exponential distribution] Let <math>X</math> have an exponential distribution. Show that <math>\textbf{Pr}[X>s+x|X>s] = \textbf{Pr}[X>x]</math>, for <math>x,s\geq 0</math>. This is the memoryless property. Show that the exponential distribution is the only continuous distribution with this property.
</li>

<li>
[Normal distribution(I)] Let <math>X,Y\sim N(0,1)</math> be two independent and identically distributed normal random variables. Let <math>Z = X-Y</math>. Find the density function of <math>Z</math> and <math>|Z|</math> respectively.
</li>

<li>
[Normal distribution(II)] Let <math>X</math> have the <math>N(0,1)</math> distribution and let <math>a>0</math>. Show that the random variable <math>Y</math> given by
<math>\begin{equation*}
Y = \begin{cases}
X, & |X|< a \\
-X, & |X|\geq a
\end{cases}
\end{equation*}</math>
has the <math>N(0,1)</math> distribution, and find an expression for <math>\rho(a) = \textbf{Cov}(X,Y)</math> in terms of the density function <math>\phi</math> of <math>X</math>.
</li>

<li>
[Discrete hazard rate] Let <math>X</math> be a non-negative integer-valued random variable with <math>h(r) = \mathbf{Pr}[X = r \mid X \geq r]</math>. If <math>\{U_i : i \geq 0\}</math> are independent and uniform on <math>[0, 1]</math>, show that <math>Z = \min\{n : U_n \leq h(n)\}</math> has the same distribution as <math>X</math>.
</li>

<li>[Random process]
Given a fixed real number <math>U \in (0,1)</math> as input of the following process, find out the expected returning value.
{{Theorem|''Process''|
:'''Input:''' real number <math>U \in (0,1)</math>;
----
:initialize <math>x = 0</math> and <math>count = 0</math>;
:while <math> x do
:* choose <math>y \in (0,1)</math> uniformly at random;
:* update <math>x = x + y</math> and <math>count = count + 1</math>;
:return <math>count</math>;
}}
</li>
<li>
[Random semicircle] We sample <math>n</math> points within a circle <math>C=\{(x,y) \in \mathbb{R}^2 \mid x^2+y^2 \le 1\}</math> independently and uniformly at random (i.e., the density function <math>f(x,y) \propto 1_{(x,y) \in C}</math>). Find out the probability that they all lie within some semicircle of the original circle <math>C</math>. (Hint: you may apply the technique of change of variables, see [https://en.wikipedia.org/wiki/Random_variable#Functions_of_random_variables function of random variables] or Chapter 4.7 in [GS])
</li>
</ul>

== Problem 2 (Stochastic Domination and Coupling, 10 points)==
<ul>
<li>
[Stochastic domination] Let <math>X, Y</math> be continuous random variables. Show that <math>X</math> dominates <math>Y</math> stochastically if and only if <math>\mathbb{E}[f(X)]\geq \mathbb{E}[f(Y)]</math> for any non-decreasing function <math>f</math> for which the expectations exist.
</li>
<li>
[Poisson vs. Bernoulli] Let <math>X \sim \mathrm{Pois}(\lambda)</math> with <math>\lambda > 0</math>, and let <math>Y \sim \mathrm{Ber}(p)</math> be a Bernoulli random variable with success probability <math>p \in (0, 1)</math>. Determine the condition on <math>\lambda</math> and <math>p</math> under which <math>X</math> stochastically dominates <math>Y</math>.
</li>
<li>
[Coupling of Poisson variables] Let <math>X \sim \mathrm{Pois}(\lambda)</math> and <math>Y \sim \mathrm{Pois}(\mu)</math> be Poisson random variables. Use the coupling method to prove that <math>X</math> stochastically dominates <math>Y</math> whenever <math>\lambda \ge \mu</math>.
</li>
</ul>

== Problem 3 (LLN and CLT, 20 points + 5 points) ==
In this problem, you may apply the results of Laws of Large Numbers (LLN) and the Central Limit Theorem (CLT) to solve the problems.

<ul>
<li>[St. Petersburg paradox] Consider the well-known game involving a fair coin. In this game, if it takes <math>k</math> tosses to obtain a head, you will win <math>2^k</math> dollars as the reward. Despite the game's expected reward being infinite, people tend to offer relatively modest amounts to participate. The following provides a mathematical explanation for this phenomenon.
<ul>
<li>
For each <math>n \ge 1</math>, let <math>X_{n,1}, X_{n,2},\ldots, X_{n,k}</math> be independent random variables. Furthermore, let <math>b_n > 0</math> be real numbers with <math>b_n \to \infty</math> and <math>\widetilde{X}_{n,k} = X_{n,k} \mathbf{1}_{|X_{n,k}| \le b_n}</math> for all <math>1 \le k \le n</math>. If <math>\sum_{k=1}^n \mathbf{Pr}(|X_{n,k}| > b_n) \to 0</math> and <math>b_n^{-2} \sum_{k=1}^n \mathbf{E}[\widetilde{X}_{n,k}^2] \to 0</math> when <math>n \to \infty</math>, then <math>(S_n-a_n)/b_n \overset{P}{\to} 0 </math>, where <math>S_n = \sum_{k=1}^n X_{n,k}</math> and <math>a_n = \sum_{k=1}^n \mathbf{E}[\widetilde{X}_{n,k}]</math>.
</li>
<li>
Let <math>S_n</math> be the total winnings after playing <math>n</math> rounds of the game. Prove that <math>\frac{S_n}{n \log_2 n} \overset{P}{\to} 1</math>. (Therefore, a fair price to play this game <math>n</math> times is roughly <math>n \log_2 n</math> dollars)
</li>

<li> (Bonus problem, 5 points)
Let <math>S_n</math> be the total winnings after playing <math>n</math> rounds of the game. Prove that <math> \limsup_{n \to \infty} \frac{S_n}{n \log_2 n} = \infty</math> almost surely. (Hint: You may use Borel-Cantelli lemmas)
</li>

</ul>
</li>

<li>
[Monte Carlo integration] Let <math>f</math> be a continuous function on <math>[0,1]</math> and <math>U_1,U_2,\ldots,U_n \sim U(0,1)</math> be independent random variables. Show that <math>I = \frac{1}{n}\sum_{i=1}^n f(U_i) \to \int_0^1 f(x) \mathrm{d}x</math> in probability. (Remark: This holds so long as <math>f</math> is a measurable function on <math>[0,1]</math> with <math>\int_0^1 |f(x)| \mathrm{d}x < \infty</math>)
</li>

<li>[Stirling's formula]
By considering the central limit theorem for the sum of independent Poisson-distributed random variables, show that
<math>n! \sim \sqrt{2\pi n} \cdot \left(\frac{n}{\mathrm{e}}\right)^n</math>
</li>
</ul>

== Problem 4 (Strong Law of Large Numbers, 15 points, '''Bonus Problem''')==
<ul>
Throughout this problem, we assume <math>X_1,X_2,\ldots,</math> be jointly independent square-integrable real random variables of mean zero. We will prove the strong law of large numbers by Kolmogorov maximal inequality.
<li>[Kolmogorov maximal inequality]
Let <math>S_n = \sum_{i=1}^n X_i</math>. Prove that <math>\mathbf{Pr}\left(\max_{1 \le i \le n} |S_i| \ge t \right) \le \frac{\mathbf{Var}(S_n)}{t^2}</math>.
</li>
<li>[Convergence of random series]
Suppose <math>\sum_{i=1}^{+\infty} \mathbf{Var}(X_i) < \infty</math>. Prove that the series <math>\sum_{i=1}^{+\infty} X_i</math> is almost surely convergent.
</li>
<li>[Strong law of large numbers]
Prove the strong law of large numbers using previous propositions.
</li>
</ul>

高级算法 (Spring 2026)

Liumingmou — Mon, 11 May 2026 15:23:25 GMT

课件及相关阅读资料

← Older revision		Revision as of 15:23, 11 May 2026
(One intermediate revision by the same user not shown)
Line 142:		Line 142:
	#* Hashing in Practice: Chernoff Bound with limited independence, tabulation hashing		#* Hashing in Practice: Chernoff Bound with limited independence, tabulation hashing
	# [https://box.nju.edu.cn/f/c44c13910eff43ffaf7f/ Dimensionality reduction]		# [https://box.nju.edu.cn/f/c44c13910eff43ffaf7f/ Dimensionality reduction]
	#* Johnson-Lindenstrauss Transformation: independent Gaussian entries, projection onto uniform random subspace, i.i.d. -1/+1 entries		#* Johnson-Lindenstrauss Transformation:
			#** Intuition: In high-dimensional spaces, a uniformly random vector is almost certainly nearly orthogonal to any fixed vector
			#** Constructions: independent Gaussian entries, projection onto uniform random subspace, i.i.d. -1/+1 entries
			#** Modern applications: TurboQuant versus RaBitQ versus Quantized JL
	#** Fast Johnson-Lindenstrauss Transformation		#** Fast Johnson-Lindenstrauss Transformation
	#* Approximate Nearest Neighbor Search: by dimensionality reduction, by Locality Sensitive Hashing (LSH)		#* Approximate Nearest Neighbor Search: by dimensionality reduction, by Locality Sensitive Hashing (LSH)

概率论与数理统计 (Spring 2026)

Zhe — Mon, 11 May 2026 08:22:46 GMT

Concepts

← Older revision		Revision as of 08:22, 11 May 2026
Line 202:		Line 202:
	** [https://en.wikipedia.org/wiki/Conditional_expectation Conditional expectation]		** [https://en.wikipedia.org/wiki/Conditional_expectation Conditional expectation]
	** [https://en.wikipedia.org/wiki/Law_of_total_expectation Law of total expectation]		** [https://en.wikipedia.org/wiki/Law_of_total_expectation Law of total expectation]
			* [https://en.wikipedia.org/wiki/Markov%27s_inequality Markov's inequality]
			* [https://en.wikipedia.org/wiki/Chebyshev%27s_inequality Chebyshev's inequality]
			* [https://en.wikipedia.org/wiki/Moment_(mathematics) Moment] related
			** [https://en.wikipedia.org/wiki/Central_moment Central moment]
			** [https://en.wikipedia.org/wiki/Variance Variance]
			** [https://en.wikipedia.org/wiki/Standard_deviation Standard deviation]
			** [https://en.wikipedia.org/wiki/Covariance Covariance]
			** [https://en.wikipedia.org/wiki/Correlation Correlation]
			** [https://en.wikipedia.org/wiki/Correlation_does_not_imply_causation Correlation does not imply causation]
			** [https://en.wikipedia.org/wiki/Skewness Skewness]
			** [https://en.wikipedia.org/wiki/Kurtosis Kurtosis]
			** [https://en.wikipedia.org/wiki/Moment_problem Moment problem]
			* [https://en.wikipedia.org/wiki/Measure_(mathematics) Measure]
			** [https://en.wikipedia.org/wiki/Borel_set Borel set]
			** [https://en.wikipedia.org/wiki/Lebesgue_integration Lebesgue integration]
			** [https://en.wikipedia.org/wiki/Measurable_function Measurable function]
			** [https://en.wikipedia.org/wiki/Cantor_set Cantor set]
			** [https://en.wikipedia.org/wiki/Non-measurable_set Non-measurable set]
			*[https://en.wikipedia.org/wiki/Probability_density_function Probability density function]
			** [https://en.wikipedia.org/wiki/Probability_distribution#Absolutely_continuous_probability_distribution Continuous probability distribution]
			**[https://en.wikipedia.org/wiki/Conditional_probability_distribution#Conditional_continuous_distributions Conditional continuous distributions]
			**[https://en.wikipedia.org/wiki/Convolution_of_probability_distributions Convolution of probability distributions] and [https://en.wikipedia.org/wiki/List_of_convolutions_of_probability_distributions List of convolutions of probability distributions]
			* Some '''continuous''' probability distributions
			** [https://en.wikipedia.org/wiki/Continuous_uniform_distribution Continuous uniform distribution]
			** [https://en.wikipedia.org/wiki/Exponential_distribution Exponential distribution] and [https://en.wikipedia.org/wiki/Poisson_point_process Poisson point process]
			** [https://en.wikipedia.org/wiki/Normal_distribution Normal (Gaussion) distribution]
			*** [https://en.wikipedia.org/wiki/Gaussian_function Gaussian function] and [https://en.wikipedia.org/wiki/Gaussian_integral Gaussian integral]
			*** [https://en.wikipedia.org/wiki/Standard_normal_table Standard normal table]
			*** [https://en.wikipedia.org/wiki/68%E2%80%9395%E2%80%9399.7_rule 68–95–99.7 rule]
			*** [https://en.wikipedia.org/wiki/Sum_of_normally_distributed_random_variables Sum of normally distributed random variables]
			*** [https://en.wikipedia.org/wiki/Multivariate_normal_distribution Multivariate normal distribution]
			** [https://en.wikipedia.org/wiki/Chi-squared_distribution Chi-squared distribution]
			** [https://en.wikipedia.org/wiki/Gamma_distribution Gamma distribution] and [https://en.wikipedia.org/wiki/Gamma_function Gamma function]
			** [https://en.wikipedia.org/wiki/Beta_distribution Beta distribution] and [https://en.wikipedia.org/wiki/Beta_function Beta function]
			** [https://en.wikipedia.org/wiki/Cauchy_distribution Cauchy distribution]
			** and [https://en.wikipedia.org/wiki/List_of_probability_distributions#Absolutely_continuous_distributions others]
			* [https://en.wikipedia.org/wiki/Inverse_transform_sampling Inverse transform sampling]
			* [https://en.wikipedia.org/wiki/Stochastic_dominance Stochastic dominance] and [https://en.wikipedia.org/wiki/Coupling_(probability) Coupling]
			* [https://en.wikipedia.org/wiki/Moment-generating_function Moment-generating function]
			* [https://en.wikipedia.org/wiki/Convergence_of_random_variables Convergence of random variables]
			** [https://en.wikipedia.org/wiki/Pointwise_convergence Pointwise convergence]
			** [https://en.wikipedia.org/wiki/Convergence_of_measures#Weak_convergence_of_measures Weak convergence of measures]
			** [https://en.wikipedia.org/wiki/Convergence_in_measure Convergence in measure]
			** [https://en.wikipedia.org/wiki/Skorokhod%27s_representation_theorem Skorokhod's representation theorem]
			** [https://en.wikipedia.org/wiki/Continuous_mapping_theorem Continuous mapping theorem]
			* [https://en.wikipedia.org/wiki/Borel%E2%80%93Cantelli_lemma Borel–Cantelli lemma] and [https://en.wikipedia.org/wiki/Zero%E2%80%93one_law zero-one laws]
			* [https://en.wikipedia.org/wiki/Law_of_large_numbers Law of large numbers]
			* [https://en.wikipedia.org/wiki/Central_limit_theorem Central limit theorem]
			** [https://en.wikipedia.org/wiki/De_Moivre%E2%80%93Laplace_theorem De Moivre–Laplace theorem]
			** [https://en.wikipedia.org/wiki/Berry%E2%80%93Esseen_theorem Berry–Esseen theorem]
			* [https://en.wikipedia.org/wiki/Characteristic_function_(probability_theory) Characteristic function]
			** [https://en.wikipedia.org/wiki/Lévy%27s_continuity_theorem Lévy's continuity theorem]
			* Concentration of measures:
			** [https://en.wikipedia.org/wiki/Moment-generating_function Moment-generating function]
			** [https://en.wikipedia.org/wiki/Chernoff_bound Chernoff bound]
			** [https://en.wikipedia.org/wiki/Hoeffding%27s_inequality Hoeffding's bound]
			** [https://en.wikipedia.org/wiki/Doob_martingale#McDiarmid's_inequality McDiarmid's inequality]
			** [https://en.wikipedia.org/wiki/Doob_martingale Doob martingale] and [https://en.wikipedia.org/wiki/Azuma%27s_inequality Azuma's inequality]
			** [https://en.wikipedia.org/wiki/Sub-Gaussian_distribution Sub-Gaussian distribution]
			* [https://en.wikipedia.org/wiki/Stochastic_process Stochastic process]
			* [https://en.wikipedia.org/wiki/Stopping_time Stopping time]
			* [https://en.wikipedia.org/wiki/Martingale_(probability_theory) Martingale]
			** [https://en.wikipedia.org/wiki/Optional_stopping_theorem Optional stopping theorem]
			* [https://en.wikipedia.org/wiki/Wald%27s_equation Wald's equation]
			* [https://en.wikipedia.org/wiki/Markov_chain Markov chain]
			** [https://en.wikipedia.org/wiki/Markov_property Markov property] and [https://en.wikipedia.org/wiki/Memorylessness memorylessness]
			** [https://en.wikipedia.org/wiki/Stochastic_matrix Stochastic matrix]
			** [https://en.wikipedia.org/wiki/Stationary_distribution Stationary distribution]

高级算法 (Spring 2026)

Liumingmou — Sun, 10 May 2026 16:28:58 GMT

课件及相关阅读资料

← Older revision		Revision as of 16:28, 10 May 2026
Line 141:		Line 141:
	#* Modern Hash Table: Cuckoo hashing, succinct dictionaries		#* Modern Hash Table: Cuckoo hashing, succinct dictionaries
	#* Hashing in Practice: Chernoff Bound with limited independence, tabulation hashing		#* Hashing in Practice: Chernoff Bound with limited independence, tabulation hashing
			# [https://box.nju.edu.cn/f/c44c13910eff43ffaf7f/ Dimensionality reduction]
			#* Johnson-Lindenstrauss Transformation: independent Gaussian entries, projection onto uniform random subspace, i.i.d. -1/+1 entries
			#** Fast Johnson-Lindenstrauss Transformation
			#* Approximate Nearest Neighbor Search: by dimensionality reduction, by Locality Sensitive Hashing (LSH)
			#* Oblivious Subspace Embedding (OSE): net argument
			#** Application: linear regression by sketch-and-solve via OSE, linear regression by fast iteration with OSE
			#** Sparse Oblivious Subspace Embedding: count sketch

	= Related Online Courses=		= Related Online Courses=

← Older revision		Revision as of 09:56, 16 May 2026
Line 125:		Line 125:

	*[[概率论与数理统计 (Spring 2026)/Problem Set 3\|Problem Set 3]] 请在 2026/5/13 上课之前(9am UTC+8)提交到 [mailto:pr2026_nju@163.com pr2026_nju@163.com] (文件名为'<font color=red >学号_姓名_A3.pdf</font>').		*[[概率论与数理统计 (Spring 2026)/Problem Set 3\|Problem Set 3]] 请在 2026/5/13 上课之前(9am UTC+8)提交到 [mailto:pr2026_nju@163.com pr2026_nju@163.com] (文件名为'<font color=red >学号_姓名_A3.pdf</font>').
			** [[概率论与数理统计 (Spring 2026)/第三次作业提交名单\|第三次作业提交名单]]

	*[[概率论与数理统计 (Spring 2026)/Problem Set 4\|Problem Set 4]] 请在 <font color=red>TBA</font> 上课之前(9am UTC+8)提交到 [mailto:pr2026_nju@163.com pr2026_nju@163.com] (文件名为'<font color=red >学号_姓名_A4.pdf</font>').		*[[概率论与数理统计 (Spring 2026)/Problem Set 4\|Problem Set 4]] 请在 <font color=red>TBA</font> 上课之前(9am UTC+8)提交到 [mailto:pr2026_nju@163.com pr2026_nju@163.com] (文件名为'<font color=red >学号_姓名_A4.pdf</font>').