imported>Etone |
imported>Etone |
| Line 1: |
Line 1: |
| {{Infobox
| | == Problem 1 == |
| |name = Infobox
| | (Matching vs. Star) |
| |bodystyle =
| |
| |title = <font size=3>组合数学 <br>
| |
| Combinatorics</font>
| |
| |titlestyle =
| |
|
| |
|
| |image =
| | 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 = yitong.yin@gmail.com yinyt@nju.edu.cn
| |
| |header4 =
| |
| |label4= office
| |
| |data4= 计算机系 804
| |
| |header5 = Class
| |
| |label5 =
| |
| |data5 =
| |
| |header6 =
| |
| |label6 = Class meetings
| |
| |data6 = Wednesday, 2pm-4pm <br> 仙I-319
| |
| |header7 =
| |
| |label7 = Place
| |
| |data7 =
| |
| |header8 =
| |
| |label8 = Office hours
| |
| |data8 = Wednesday, 4pm-6pm <br>计算机系 804
| |
| |header9 = Textbook
| |
| |label9 =
| |
| |data9 =
| |
| |header10 =
| |
| |label10 =
| |
| |data10 = [[File:LW-combinatorics.jpeg|border|100px]]
| |
| |header11 =
| |
| |label11 =
| |
| |data11 = van Lint and Wilson. <br> ''A course in Combinatorics, 2nd ed.'', <br> Cambridge Univ Press, 2001.
| |
| |header12 =
| |
| |label12 =
| |
| |data12 = [[File:Jukna_book.jpg|border|100px]]
| |
| |header13 =
| |
| |label13 =
| |
| |data13 = Jukna. ''Extremal Combinatorics: <br> With Applications in Computer Science,<br>2nd ed.'', Springer, 2011.
| |
| |belowstyle = background:#ddf;
| |
| |below =
| |
| }}
| |
|
| |
|
| This is the webpage for the ''Combinatorics'' class of fall 2019. Students who take this class should check this page periodically for content updates and new announcements.
| | (Hint: Learn from the proof of Erdos-Rado's sunflower lemma.) |
|
| |
|
| = Announcement = | | == Problem 2 == |
| * (2019/9/6) 第一课的lecture notes和slides已经发布。
| | (Frankl 1986) |
| * (2019/10/21)外网数学符号显示已经正常。
| |
| * (2019/11/04)<font color=red size=4>11月6日按原定计划上习题课。教服系统中的“停课”指的是：正常新内容的授课暂停一次，原授课时间段改为上习题课。</font>
| |
|
| |
|
| = Course info =
| | 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>. |
| * '''Instructor ''': 尹一通 ([http://tcs.nju.edu.cn/yinyt/ homepage])
| | * 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. |
| :*email: yinyt@nju.edu.cn
| | * Show that <math>|\mathcal{F}|\le 1+{k\choose \lfloor k/2\rfloor}</math>. |
| :*office: 804
| |
| * '''Teaching assistant''': 陈海敏 ([mailto:ichenhm@gmail.com email], [http://tcs.nju.edu.cn/files/people/haimin/ homepage])，蒋圣翊 ([mailto:shengyi.jiang@outlook.com email], [http://www.lamda.nju.edu.cn/jiangsy/ homepage])
| |
| * '''Class meeting''': Wednesday, 2pm-4pm, 仙I-319.
| |
| * '''Office hour''': Wednesday, 4pm-6pm, 计算机系 804.
| |
|
| |
|
| = Syllabus = | | ==Problem 3 == |
| | 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>. |
|
| |
|
| === 先修课程 Prerequisites ===
| | 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. |
| * 离散数学（Discrete Mathematics）
| |
| * 线性代数（Linear Algebra）
| |
| * 概率论（Probability Theory）
| |
|
| |
|
| === Course materials === | | ==Problem 4== |
| * [[组合数学 (Fall 2019)/Course materials|<font size=3>教材和参考书清单</font>]]
| | 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. |
| | |
| === 成绩 Grades ===
| |
| * 课程成绩：本课程将会有若干次作业和一次期末考试。最终成绩将由平时作业成绩 (≥ 60%) 和期末考试成绩 (≤ 40%) 综合得出。
| |
| * 迟交：如果有特殊的理由，无法按时完成作业，请提前联系授课老师，给出正当理由。否则迟交的作业将不被接受。
| |
| | |
| === <font color=red> 学术诚信 Academic Integrity </font>===
| |
| 学术诚信是所有从事学术活动的学生和学者最基本的职业道德底线，本课程将不遗余力的维护学术诚信规范，违反这一底线的行为将不会被容忍。
| |
| | |
| 作业完成的原则：署你名字的工作必须是你个人的贡献。在完成作业的过程中，允许讨论，前提是讨论的所有参与者均处于同等完成度。但关键想法的执行、以及作业文本的写作必须独立完成，并在作业中致谢（acknowledge）所有参与讨论的人。不允许其他任何形式的合作——尤其是与已经完成作业的同学“讨论”。
| |
| | |
| 本课程将对剽窃行为采取零容忍的态度。在完成作业过程中，对他人工作（出版物、互联网资料、其他人的作业等）直接的文本抄袭和对关键思想、关键元素的抄袭，按照 [http://www.acm.org/publications/policies/plagiarism_policy ACM Policy on Plagiarism]的解释，都将视为剽窃。剽窃者成绩将被取消。如果发现互相抄袭行为，<font color=red> 抄袭和被抄袭双方的成绩都将被取消</font>。因此请主动防止自己的作业被他人抄袭。
| |
| | |
| 学术诚信影响学生个人的品行，也关乎整个教育系统的正常运转。为了一点分数而做出学术不端的行为，不仅使自己沦为一个欺骗者，也使他人的诚实努力失去意义。让我们一起努力维护一个诚信的环境。
| |
| | |
| = Assignments =
| |
| *[[组合数学 (Fall 2019)/Problem Set 1|Problem Set 1]] due on Sept 25, in class. [[组合数学 (Fall 2019)/作业1已提交名单 | 当前作业1已提交名单]].
| |
| *[[组合数学 (Fall 2019)/Problem Set 2|Problem Set 2]] due on Oct 23, in class. [[组合数学 (Fall 2019)/作业2已提交名单 | 当前作业2已提交名单]].
| |
| *[[组合数学 (Fall 2019)/Problem Set 3|Problem Set 3]] due on Dec 4, in class.
| |
| | |
| = Lecture Notes =
| |
| # [[组合数学 (Fall 2019)/Basic enumeration|Basic enumeration | 基本计数]] （ [http://tcs.nju.edu.cn/slides/comb2019/BasicEnumeration.pdf slides]）
| |
| # [[组合数学 (Fall 2019)/Generating functions|Generating functions | 生成函数]] （ [http://tcs.nju.edu.cn/slides/comb2019/GeneratingFunction.pdf slides]）
| |
| # [[组合数学 (Fall 2019)/Sieve methods|Sieve methods | 筛法]] （ [http://tcs.nju.edu.cn/slides/comb2019/PIE.pdf slides]）
| |
| # [[组合数学 (Fall 2019)/Pólya's theory of counting|Pólya's theory of counting | Pólya计数法]] （ [http://tcs.nju.edu.cn/slides/comb2019/Polya.pdf slides]）
| |
| # [[组合数学 (Fall 2019)/Cayley's formula|Cayley's formula | Cayley公式]]（ [http://tcs.nju.edu.cn/slides/comb2019/Cayley.pdf slides]）
| |
| # [[组合数学 (Fall 2019)/Existence problems|Existence problems | 存在性问题]] （ [http://tcs.nju.edu.cn/slides/comb2019/Existence.pdf slides]）
| |
| # [[组合数学 (Fall 2019)/The probabilistic method|The probabilistic method | 概率法]]（ [http://tcs.nju.edu.cn/slides/comb2019/ProbMethod.pdf slides]）
| |
| # [[组合数学 (Fall 2019)/Extremal graph theory|Extremal graph theory | 极值图论]]（ [http://tcs.nju.edu.cn/slides/comb2019/ExtremalGraphs.pdf slides]）
| |
| # [[组合数学 (Fall 2019)/Extremal set theory|Extremal set theory | 极值集合论]]（ [http://tcs.nju.edu.cn/slides/comb2019/ExtremalSets.pdf slides]）
| |
| # Ramsey theory | Ramsey理论
| |
| # Matching theory | 匹配论
| |
| | |
| = Resources =
| |
| * [http://math.mit.edu/~fox/MAT307.html Combinatorics course] by Jacob Fox (now at Stanford) taught at MIT and Princeton.
| |
| * [https://www.math.ucla.edu/~pak/lectures/Math-Videos/comb-videos.htm Collection of Combinatorics Videos]
| |
| | |
| = Concepts =
| |
| * [http://en.wikipedia.org/wiki/Binomial_coefficient Binomial coefficient]
| |
| * [http://en.wikipedia.org/wiki/Twelvefold_way The twelvefold way]
| |
| * [http://en.wikipedia.org/wiki/Composition_(number_theory) Composition of a number]
| |
| * [http://en.wikipedia.org/wiki/Multiset#Formal_definition Multiset]
| |
| * [http://en.wikipedia.org/wiki/Combination#Number_of_combinations_with_repetition Combinations with repetition], [http://en.wikipedia.org/wiki/Multiset#Counting_multisets <math>k</math>-multisets on a set]
| |
| * [http://en.wikipedia.org/wiki/Multinomial_theorem#Multinomial_coefficients Multinomial coefficients]
| |
| * [http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind Stirling number of the second kind]
| |
| * [http://en.wikipedia.org/wiki/Partition_(number_theory) Partition of a number]
| |
| ** [http://en.wikipedia.org/wiki/Young_tableau Young tableau]
| |
| * [http://en.wikipedia.org/wiki/Fibonacci_number Fibonacci number]
| |
| * [http://en.wikipedia.org/wiki/Catalan_number Catalan number]
| |
| * [http://en.wikipedia.org/wiki/Generating_function Generating function] and [http://en.wikipedia.org/wiki/Formal_power_series formal power series]
| |
| * [http://en.wikipedia.org/wiki/Binomial_series Newton's formula]
| |
| * [https://en.wikipedia.org/wiki/Burnside%27s_lemma Burnside's lemma]
| |
| **[https://en.wikipedia.org/wiki/Group_action group action] and [https://en.wikipedia.org/wiki/Group_action#Orbits_and_stabilizers orbits]
| |
| * [https://en.wikipedia.org/wiki/Permutation#Cycle_notation Cycle decomposition] of permutation
| |
| * [https://en.wikipedia.org/wiki/Pólya_enumeration_theorem Pólya enumeration theorem]
| |
| * [http://en.wikipedia.org/wiki/Inclusion-exclusion_principle The principle of inclusion-exclusion] (and more generally the [http://en.wikipedia.org/wiki/Sieve_theory sieve method])
| |
| * [http://en.wikipedia.org/wiki/M%C3%B6bius_inversion_formula Möbius inversion formula]
| |
| * [http://en.wikipedia.org/wiki/Derangement Derangement], and [http://en.wikipedia.org/wiki/M%C3%A9nage_problem Problème des ménages]
| |
| * [http://en.wikipedia.org/wiki/Ryser%27s_formula#Ryser_formula Ryser's formula]
| |
| * [http://en.wikipedia.org/wiki/Euler_totient Euler totient function]
| |
| * [http://en.wikipedia.org/wiki/Cayley_formula Cayley's formula]
| |
| ** [http://en.wikipedia.org/wiki/Prüfer_sequence Prüfer code for trees]
| |
| ** [http://en.wikipedia.org/wiki/Kirchhoff%27s_matrix_tree_theorem Kirchhoff's matrix-tree theorem]
| |
| * [http://en.wikipedia.org/wiki/Double_counting_(proof_technique) Double counting] and the [http://en.wikipedia.org/wiki/Handshaking_lemma handshaking lemma]
| |
| * [http://en.wikipedia.org/wiki/Sperner's_lemma Sperner's lemma] and [http://en.wikipedia.org/wiki/Brouwer_fixed_point_theorem Brouwer fixed point theorem]
| |
| * [http://en.wikipedia.org/wiki/Pigeonhole_principle Pigeonhole principle]
| |
| :* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem Erdős–Szekeres theorem]
| |
| :* [http://en.wikipedia.org/wiki/Dirichlet's_approximation_theorem Dirichlet's approximation theorem]
| |
| * [http://en.wikipedia.org/wiki/Probabilistic_method The Probabilistic Method]
| |
| * [http://en.wikipedia.org/wiki/Lov%C3%A1sz_local_lemma Lovász local lemma]
| |
| * [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model Erdős–Rényi model for random graphs]
| |
| * [http://en.wikipedia.org/wiki/Extremal_graph_theory Extremal graph theory]
| |
| * [http://en.wikipedia.org/wiki/Turan_theorem Turán's theorem], [http://en.wikipedia.org/wiki/Tur%C3%A1n_graph Turán graph]
| |
| * Two analytic inequalities:
| |
| :*[http://en.wikipedia.org/wiki/Cauchy%E2%80%93Schwarz_inequality Cauchy–Schwarz inequality]
| |
| :* the [http://en.wikipedia.org/wiki/Inequality_of_arithmetic_and_geometric_means inequality of arithmetic and geometric means]
| |
| * [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Stone_theorem Erdős–Stone theorem] (fundamental theorem of extremal graph theory)
| |
| * [https://en.wikipedia.org/wiki/Sunflower_(mathematics) Sunflower lemma and conjecture]
| |
| * [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Ko%E2%80%93Rado_theorem Erdős–Ko–Rado theorem]
| |
| * [http://en.wikipedia.org/wiki/Sperner_family Sperner system]
| |
| * [https://en.wikipedia.org/wiki/Sauer–Shelah_lemma Sauer's lemma] and [https://en.wikipedia.org/wiki/VC_dimension VC dimension]
| |
| * [https://en.wikipedia.org/wiki/Kruskal–Katona_theorem Kruskal–Katona theorem]
| |
| * [http://en.wikipedia.org/wiki/Ramsey_theory Ramsey theory]
| |
| :*[http://en.wikipedia.org/wiki/Ramsey's_theorem Ramsey's theorem]
| |
| :*[http://en.wikipedia.org/wiki/Happy_Ending_problem Happy Ending problem]
| |
| * [https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem Hall's theorem ] (the marriage theorem)
| |
| :* [https://en.wikipedia.org/wiki/Doubly_stochastic_matrix Birkhoff–Von Neumann theorem]
| |
| * [http://en.wikipedia.org/wiki/K%C3%B6nig's_theorem_(graph_theory) König-Egerváry theorem]
| |
| * [http://en.wikipedia.org/wiki/Dilworth's_theorem Dilworth's theorem]
| |
| :* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem Erdős–Szekeres theorem]
| |
| * The [http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem Max-Flow Min-Cut Theorem]
| |
| :* [https://en.wikipedia.org/wiki/Menger%27s_theorem Menger's theorem]
| |
| :* [http://en.wikipedia.org/wiki/Maximum_flow_problem Maximum flow]
| |
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.