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
Line 95:		Line 95:
	# [[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')
	~~# [[Media:Computational Method 2026 Assignments 6.pdf\|Homework6]] 请在2026年06月03日23点59分之前提交到 nm_nju_2026@163.com (文件名为'学号_姓名_A6.pdf')~~

	=Lecture Notes=		=Lecture Notes=