General Circulation(Fall 2019) and 组合数学 (Fall 2019)/Problem Set 4: Difference between pages

From TCS Wiki
(Difference between pages)
Jump to navigation Jump to search
VisualWikitext
imported>Etone
No edit summary
 
imported>Etone
No edit summary
 
Line 1: Line 1:
{{Infobox
== Problem 1 ==
|name        = Infobox
(Matching vs. Star)
|bodystyle    =  
|title        = 大气环流 <br>
General Circulation of the Atmosphere
|titlestyle  =


|image        = [[File:Yang_2014_3.jpg|border|150px]]
Given a graph <math>G(V,E)</math>, a ''matching'' is a subset <math>M\subseteq E</math> of edges such that there are no two edges in <math>M</math> sharing a vertex, and a ''star'' is a subset <math>S\subseteq E</math> of edges such that every pair <math>e_1,e_2\in S</math> of distinct edges in <math>S</math> share the same vertex <math>v</math>.
|imagestyle  =
|caption      =
|captionstyle =
|headerstyle  = background:#ccf;
|labelstyle  = background:#ddf;
|datastyle    =


|header1 =Instructor
Prove that any graph <math>G</math> containing more than <math>2(k-1)^2</math> edges either contains a matching of size <math>k</math> or a star of size <math>k</math>.
|label1  =
|data1  =
|header2 =
|label2  =
|data2  = 张洋
|header3 =
|label3  = Email
|data3  = yangzhang@nju.edu.cn
|header4 =
|label4= office
|data4= 仙林大气楼 B410
|header5 = Class
|label5  =
|data5  =
|header6 =
|label6  = Class meetings
|data6  = 周三 下午 2:00-4:00，仙 II-102
|header7 =
|label7  = Place
|data7  =
|header8 =
|label8  = Office hours
|data8  = 周二（双周）下午6:00-7:00 <br>仙林大气楼 B410
|header9 = Reference book
|label9  =
|data9  =
|header10 =
|label10  =
|data10  = {{Infobox
|name        =
|bodystyle  =
|title        =
|titlestyle  =
|image        = [[File:James-Circulating.jpg|border|100px]]
|imagestyle  =
|caption      = Introduction to Circulating Atmospheres, <br>''I. James'', Cambridge Press, 1995
|captionstyle = }}
|header11 =
|label11  =
|data11  = {{Infobox
|name        =
|bodystyle  =
|title        =
|titlestyle  =
|image        = [[File:Oort.jpg|border|100px]]
|imagestyle  =
|caption      =Physics of Climate, ''Peixoto, J. P.'' and ''A. H. Oort'',  Springer-Verlag New York, 1992
|captionstyle =
}}
|header12 =
|label12  =
|data12  = {{Infobox
|name        =
|bodystyle  =
|title        =
|titlestyle  =
|image        = [[File:geoff.jpg|border|100px]]
|imagestyle  =
|caption      =Atmospheric and Oceanic Fluid Dynamics: Fundamentals and Large-scale Circulation, ''Vallis, G. K.'', Cambridge University Press, 2006
|captionstyle =
}}
|belowstyle = background:#ddf;
|below =
}}


(Hint: Learn from the proof of Erdos-Rado's sunflower lemma.)


This is the page for the class ''General Circulation of the Atmosphere (大气环流)'' for the Fall 2019 semester. Students who take this class should check this page periodically for content updates and new announcements.
== Problem 2 ==
(Frankl 1986)


= Announcement =
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>.
* 本学期大气环流课的答疑时间更改至  <font color="red" size="2>周二（双周）下午 5:00-6:00，大气楼 B410 </font>。【2019.9.24】
* 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.
* 本周三的大气环流课调至  <font color="red" size="2>周日（10.27）下午 6:00-8:00，大气楼 BC301</font>。【2019.10.21】
* Show that <math>|\mathcal{F}|\le 1+{k\choose \lfloor k/2\rfloor}</math>.
* 由于上周课程网站服务器故障，网页一直无法登陆。第二次作业的提交时间因此  <font color="red" size="2>延后至下周三（10.30）</font>。【2019.10.22】


= Course info =
==Problem 3 ==
* '''Instructor ''': 张洋，
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>.
:*office: 仙林气象楼 B410
:*email: yangzhang@nju.edu.cn
* '''Class meeting''': 周三 下午 2:00-4:00, 仙II-102
* '''Office hour''': 周二（双周）<font color="red" size="2>下午5:00-6:00</font>，仙林大气楼 B410
* '''Prerequisites''': 动力气象，天气学，气候学
* '''Grading''': 平时作业（50％）＋ 期末考试（50％）
本课程将大致布置4次作业，每次作业一二道题目左右。题目将选择每个课题最具有代表性、需要一定思维强度和动手能力的训练用题目,意在使学生通过顺利完成作业来建立环流系统的物理模型、以对课程内容得到深刻全面地理解和掌握。期末考试题目数量将会比平时作业多,覆盖面更广,但会比作业题目简单,只涉及对基本内容的掌握和对环流理论的直接应用。


= Course Slides =
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.
''Many figures in the course slides are adapted from the reference books, NOAA and other educational sources. These figures are <font color="red" size="2">for class use only.</font>''


*[2019.9.4]  [http://tcs.nju.edu.cn/yzhang/Course_intro_2019.pdf Course Introduction] and [http://tcs.nju.edu.cn/yzhang/Chap_1_1_2019.pdf Chapter 1_1]
==Problem 4==
*[2019.9.11] [http://tcs.nju.edu.cn/yzhang/Chap_1_2_2019.pdf Chapter 1_2] (reference reading: PO Chapter 5.1-5.2; James Chapter 2.2, 2.4)
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 </math>$, for any <math>r</math>-coloring of all 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 by the <math>r</math>-coloring.
*[2019.9.18] [http://tcs.nju.edu.cn/yzhang/Chap_2_1_2019.pdf Chapter2_1] (reference reading: PO Chapter 4.1, 6.3)
*[2019.9.25] [http://tcs.nju.edu.cn/yzhang/Chap_2_2_2019.pdf Chapter2_2] (reference reading: PO Chapter 6.7 - 6.8; Lindzen 2005, [http://tcs.nju.edu.cn/yzhang/lINDZEN_CHAP2.pdf Chapter 2]; Lindzen and Farrell 1977, [http://tcs.nju.edu.cn/yzhang/Lindzen_1977.pdf JAS])
*[2019.10.9] [http://tcs.nju.edu.cn/yzhang/Chap_3_1_2019.pdf Chapter 3_1] (reference reading: Vallis Chapter 11.1-11.2; Lindzen 2005, [http://tcs.nju.edu.cn/yzhang/Lindzen_chap7.pdf Chapter 7]; Held and Hou, 1980, [http://tcs.nju.edu.cn/yzhang/held_hou_1980.pdf JAS])
*[2019.10.16]  [http://tcs.nju.edu.cn/yzhang/Chap_3_2_2019.pdf Chapter 3_2]  (reference reading: Vallis Chapter 11.1-11.2, 11.4; Lindzen 2005, [http://tcs.nju.edu.cn/yzhang/Lindzen_chap7.pdf Chapter 7]; Held and Hou, 1980, [http://tcs.nju.edu.cn/yzhang/held_hou_1980.pdf JAS];Lindzen and Hou, 1988, [http://tcs.nju.edu.cn/yzhang/lindzen_hou_1988.pdf JAS])
 
= Assignments =
# [[Assignment 1, Fall 2019|Reanalysis data and the earth's climatology]] [Due:2019.10.09] <font color="red" size="1.5">请在本次作业的截止日期前将本次作业的图片部分和文字部分打包作为附件发送至邮箱 circulation_nju@126.com </font> [[Namelist_Assignment1_2019|上交作业人员名单]]
# [[Assignment 2, Fall 2019|Simple energy balance climate model]] [Due:2019.10.23]
 
= Course intro =
“大气环流”常指地球大气较大空间范围、较长时间尺度上的空气流动，及其对地球大气热量、动量、能量和水汽的全球输送。虽然从十七、十八世纪起人们就开始研究大尺度的大气运动(如Hadley在1735年提出的信风理论)，但大气环流真正发展成为一门较完备的学科方向却是近半个世纪的事情。随着四五十年代探空资料等高空气象要素的取得，以及六十年代卫星等覆盖全球的观测资料的加入，大气环流的空间结构和时间变化开始被系统、全面地揭示。与此同时，大气环流的数值模拟，也开始成为研究大气环流的一个主要方法，并发展至今成为了解和预估未来气候变化的主要手段。随着观测和模拟手段的进步，大气环流的理论研究也在近三十年开始快速地发展，人们对各种环流系统的维持和变化有了更全面、更深刻、也更为现代的理解。
 
现代的大气环流是大气动力学、天气学和气候学相结合的产物。大气环流，既是各种天气现象产生的背景流场，又是各种气候状态形成的动力机制。大气环流在低频、季节、年际、年代际等时间尺度的变化，不但会引起天气现象的变化，也影响着气候状态的形成。而在大气科学领域面临着诸如全球暖化、气候变化、环流异常等重大科学问题的今天，大气环流研究的重要性被推到了前所未有的高度,大气环流也成为活跃发展又充满挑战的学科方向。
 
本课程将讲述在过去几十年里大气环流在观测、理论和模拟上取得的进展。希望学生借此课程能熟悉大气环流的基本分布和形态，掌握各主要环流系统的维持和变化机制，建立各环流系统形成的物理模型，了解现阶段的大气环流模式，知道大气环流方向有待解决的科学问题。
 
作为一门课程，大气环流内容的讲述常可以有两条线索。一条是全球尺度上大气热量、动量、能量和水汽的分布与输送，Lorenz（1967）和 Peixoto and Oort（1992）是按此线索介绍大气环流的优秀教材；另一条线索，是各纬度、各区域内大气环流系统的形成、维持和变化机制，James（1995）和 Vallis（2006）是按此线索介绍大气环流的经典讲义。根据现阶段大气环流方向的研究特点，本课程的讲述将主要按照后一种方式来展开，并辅以介绍各环流系统对大气各要素场的输送。在介绍各环流系统时，本课程将以观测、理论和模拟为顺序，从各大气环流系统的观测事实入手，介绍大气环流系统的分布特征和时空变化特征；着重介绍关于环流系统的各种动力学模型和现阶段对环流系统的理解；辅以对环流系统模拟研究的介绍；最后通过三者的对比，讨论各环流系统有待研究的问题。
 
= Syllabus =
本课程具体的内容安排如下：第一章为大气环流的概述，介绍大气环流发展的历史、包含的内容以及大气环流研究的常用观测资料和分析方法。第二章介绍大气环流产生的外部强迫：辐射强迫和下界面过程。第三至六章介绍大气环流中的各个环流系统及它们的动力机制。第七章详细介绍各复杂度的大气环流模式。第八章介绍大气环流领域现阶段最大的一个开放课题：全球暖化背景下的大气环流。这一章既是对前几章所介绍的大气环流理论的应用与检验，又是对未来大气环流研究方向的探讨。借此让学生熟悉并理解大气环流领域亟需解决的课题。具体课程安排和参考书目如下。
== Course schedule ==
*大气环流概述 (Introduction) （4课时）
*大气环流的外部强迫（3课时）
**辐射强迫 (Radiative forcing)
**下界面过程 (Surface boundaries)
*经向环流系统 (Zonally-averaged circulations)
**Hadley 环流（4课时）
**Ferrel 环流，急流，中纬度的波流相互作用（8课时）
*纬向环流系统（Non-zonal circulations）（6课时）
**Storm tracks
**Monsoon
**ENSO and Walker circulation
*能量和水汽循环 (Angular momentum, energy and water vapor)（2课时）
*不同复杂度的大气环流模式 (General circulation in a hierarchy of models)（2课时）
*全球暖化背景下的大气环流 (General circulation in the global warming scenario)（2课时）
 
[[点击此处看详细课程安排 (click for more)]]
 
== References ==
*观测部分：Peixoto, J. P. and A. H. Oort, 1992: Physics of Climate. Springer-Verlag New York, Inc., 520 pp. 中文译本：气候物理学，1995，吴国雄、刘辉等译校，气象出版社。
*综合介绍：James, I., 1995: Introduction to circulating atmospheres. Cambridge University Press, 448 pp.
*理论部分：Vallis, G. K., 2006: Atmospheric and Oceanic Fluid Dynamics: Fundamentals and Large-scale Circulation. Cambridge University Press. 745 pp.
* [[其它参考书目（点击看详情）]]

Revision as of 05:38, 11 December 2019

Problem 1

(Matching vs. Star)

Given a graph [math]\displaystyle{ G(V,E) }[/math], a matching is a subset [math]\displaystyle{ M\subseteq E }[/math] of edges such that there are no two edges in [math]\displaystyle{ M }[/math] sharing a vertex, and a star is a subset [math]\displaystyle{ S\subseteq E }[/math] of edges such that every pair [math]\displaystyle{ e_1,e_2\in S }[/math] of distinct edges in [math]\displaystyle{ S }[/math] share the same vertex [math]\displaystyle{ v }[/math].

Prove that any graph [math]\displaystyle{ G }[/math] containing more than [math]\displaystyle{ 2(k-1)^2 }[/math] edges either contains a matching of size [math]\displaystyle{ k }[/math] or a star of size [math]\displaystyle{ k }[/math].

(Hint: Learn from the proof of Erdos-Rado's sunflower lemma.)

Problem 2

(Frankl 1986)

Let [math]\displaystyle{ \mathcal{F}\subseteq {[n]\choose k} }[/math] be a [math]\displaystyle{ k }[/math]-uniform family, and suppose that it satisfies that [math]\displaystyle{ A\cap B \not\subset C }[/math] for any [math]\displaystyle{ A,B,C\in\mathcal{F} }[/math].

  • Fix any [math]\displaystyle{ B\in\mathcal{F} }[/math]. Show that the family [math]\displaystyle{ \{A\cap B\mid A\in\mathcal{F}, A\neq B\} }[/math] is an anti chain.
  • Show that [math]\displaystyle{ |\mathcal{F}|\le 1+{k\choose \lfloor k/2\rfloor} }[/math].

Problem 3

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

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

Problem 4

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

Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=General_Circulation(Fall_2019)&oldid=9086"