这是一次UCL伦敦大学学院图论与组合(MATH0029)课程的代写成功案例
这门课讲的内容其实不算特别多，大部分是图论的内容。比如说，它讲了极值图论(extremal graph theory)的内容。极值图论主要是研究在一个特定的约束条件下，哪些图可以达到极端的情况。这个领域有两个主要的分支，一个是研究是否存在哈密顿圈(Hamiltonian Cycle)的图，Dirac’s theorem 的这里着重讨论了Dirac’s theorem 和 Ore’s theorem；另外一个课程中讨论的定理是 Turán’s theorem。Turán’s theorem 本质上是一种 Ramsey 类型的定理，它给出了在没有某种特定子图的情况下，边数最多的图。之所以说它是一种 Ramsey 类型的定理，是因为它的逆命题是一种 Ramsey 类型的结果。
课程后续讨论了一些图论定理的应用，比如说去证明了费马大定理（Fermat’s Last Theorem）在$Z_p$下是不成立的，这其实通过染色可以转换成一个图论（Graph Theory）的问题。然后这个实际上是在MIT的一位研究加性组合的教授的课程note里也讨论过的问题，叫做schur定理，这个是比较简单应用。最后讲了范德瓦尔登定理（van der Waerden Theorem），这就比较困难一点，因为虽然它是拉姆赛形的定理，但是它有一定的难度，它需要在具有某种特定结构的集合里找到具有特定结构的子集。这应该是这个课程最难的部分，我估计考试的时候是不会考到的。图论里还有很多其他的内容，包括概率图论（Probabilistic Graph Theory）的内容，或者是一些代数图论（Algebraic Graph Theory）的内容等等，图论与组合MATH0029并没有覆盖到图论的全部内容。
我们来看图论与组合MATH0029这一课程中会出现的经典的考试题目
(a) State Dirac’s theorem.
(b) Prove that a connected graph $G$ has an Euler circuit if and only if every vertex has even degree.
(c) Give an example of a graph that contains an Euler circuit but does not contain a Hamilton cycle. Justify your answer.
(d) Let $G$ be a connected graph in which all vertices have even degree except two which have odd degree. Prove that there is a walk in $G$ that uses every edge exactly once.
像这个问题的前两个小问就是送分的。第1小问是陈述Dirac’s theorem，第2小问是证明一个连通图是否有欧拉回路，也就是每个顶点的度数都是偶数。这个可以用归纳法证明。然后第3个归纳需要证明存在一个图，它有欧拉回路但没有哈密顿回路。这个需要熟练掌握一个图存在欧拉回路和哈密顿回路的充分条件和必要条件，其中一个必要条件相当于将其约化为哈密顿回路的条件。目前还找不到一个图是否存在哈密顿回路的充要条件。而且还不确定这是否是一个NP完全问题，可能是一个NP问题。如果是NP问题，意味着这个问题很难解决。
(a) Define the Turán graph $T_r(n)$. How many edges are there in $T_3(11)$ ?
(b) Show that if $G=(V, E)$ is an $r$-partite graph of order $n$ then $|E| \leqslant\left|E\left(T_r(n)\right)\right|$.
(c) Define $\operatorname{ex}(n, H)$, where $H$ is a graph and $n \geqslant 1$ is an integer.
(d) Prove that
$$
\pi(H)=\lim _{n \rightarrow \infty} \frac{\operatorname{ex}(n, H)}{\left(\begin{array}{l}
n \
2
\end{array}\right)}
$$
is well-defined.
(e) Show that if $\Delta(H) \neq 0$ then $\pi(H) \leqslant 1-\frac{1}{\Delta(H)}$.
像第1题我们需要理解Turán graph的结构，特别是在边数和图的顶点比较小的情况下，它的形态是怎样的。第2个小问，实际上使用抽屉原理来解决。
UprivateTA™为您的留学生涯保驾护航。
MATH0029 Graph Theory and Combinatorics
| Year: | 2023-2024 |
| Code: | MATH0029 |
| Level: | 6 (UG)/7(PG) |
| Normal student group(s): | UG Year 3 Mathematics degrees |
| Value: | 15 credits (= 7.5 ECTS credits) |
| Term: | 1 |
| Assessment: | 90% examination 10% coursework |
| Normal Pre-requisites: | MATH0057 recommended |
| Lecturer: | Dr J Talbot |
Course Description and Objectives
The course aims to introduce students to discrete mathematics, a fundamental part of mathematics with many applications in computer science and related areas. The course provides an introduction to graph theory and combinatorics, the two cornerstones of discrete mathematics. The course will be offered to third or fourth year students taking Mathematics degrees, and might also be suitable for students from other departments. There will be an emphasis on extremal results and a variety of methods.
Recommended Texts
B Bollobás, Modern Graph Theory (Springer); B Bollobás, Combinatorics (Cambridge University Press).
Detailed Syllabus
- Binomial coefficients, convexity. Inequalities: Jensen’s, AM-GM, Cauchy-Schwarz. Graphs, subgraphs, connectedness, Euler circuits, cycles, trees, bipartite graphs and other basic concepts. Vertex colourings. Graphs with large girth and large chromatic number.
- Extremal graph theory: Dirac’s theorem. Ore’s theorem. Mantel’s theorem. Turán’s theorem (several proofs including probabilistic and analytic). Kövári-Sós-Turán theorem with applications to geometry. Erdős-Stone theorem. Stability. Andrásfai-Erdős-Sós theorem.
- Set Systems: Basic definitions; set systems and the discrete cube. Chains and antichains. Sperner’s lemma. The LYM inequality. Intersecting families; the Erdos-Ko-Rado theorem (probabilistic and compression proofs). Isoperimetric problems: local LYM inequality, Kruskal-Katona theorem. The linear algebra method: Fisher’s inequality, RayChaudhuri-Wilson theorem.
- Ramsey theory: Ramsey’s theorem. Upper and lower bounds including probabilistic ideas. Schur’s Theorem. Fermat’s Last Theorem is false in $\mathbb{Z}_p
Fourier analysis代写
微分几何代写
离散数学代写
Partial Differential Equations代写可以参考一份偏微分方程midterm答案解析
