MY-ASSIGNMENTEXPERT™可以为您提供 sydney MATH2069 Graph Theory图论的代写代考和辅导服务！
这是悉尼大学图论课程的代写成功案例。
MATH2069课程简介
This unit introduces students to several related areas of discrete mathematics, which serve their interests for further study in pure and applied mathematics, computer science and engineering. Topics to be covered in the first part of the unit include recursion and induction, generating functions and recurrences, combinatorics. Topics covered in the second part of the unit include Eulerian and Hamiltonian graphs, the theory of trees (used in the study of data structures), planar graphs, the study of chromatic polynomials (important in scheduling problems).
Prerequisites
At the completion of this unit, you should be able to:
- LO1. identify and use combinatorial objects involved in counting problems to solve them
- LO2. solve linear recurrence relations by using generating functions and characteristic equations
- LO3. identify Eulerian and Hamiltonian graphs
- LO4. apply special algorithms to find minimal walks in weighted graphs
- LO5. apply special algorithms to find spanning trees in graphs
- LO6. find chromatic numbers and chromatic polynomials of graphs.
MATH2069 Graph Theory HELP（EXAM HELP， ONLINE TUTOR）
page 195, #9 Show that deleting at most $(m-s)(n-t) / s$ edges from a $K_{m, n}$ will never destroy all its $K_{s, t}$ subgraphs.
Solution: Let $M \cup N$ be the partition of the graph $G$ obtained from $K_{m, n}$ by deleting these vertices. On the average, a vertex in $M$ is losing $(m-s)(n-t) /(s m)$ edges. Picking a set $S$ of $s$ vertices with most degrees from $M$. Consider the induced subgraph $G[S \cup N]$. We have
$$
|E(G[S \cup N])| \geq s(n-(m-s)(n-t) /(s m))=(s-1) n+t-\frac{s}{m}(n-t)>(s-1) n+t .
$$
Thus in $G[S \cup N]$, there are a set $T$ of $t$ vertices from $N$ with degree equal $s$. The induced subgraph $G[S \cup T]$ is a complete bipartite graph $K_{s, t}$.
page 195, #11 Let $1 \leq r \leq n$ be integers. Let $G$ be a bipartite graph with bipartition ${A, B}$, where $|A|=|B|=n$, and assume that $K_{r, r} \not \subset G$.
Show that
$$
\sum_{x \in A}\left(\begin{array}{c}
d(x) \
r
\end{array}\right) \leq(r-1)\left(\begin{array}{l}
n \
r
\end{array}\right)
$$
Use it to deduce $e x\left(n, K_{r, r}\right) \leq c n^{2-1 / r}$.
Solution: Let $1 \leq r \leq n$ be integers. Let $G$ be a bipartite graph with bipartition ${A, B}$, where $|A|=|B|=n$. Assume $K_{r, r} \not \subset G$. Let $d(x)$ denote the degree of vertex $x \in A$, and let $N(x)$ denote the neighborhood of $x$. Note that $N(x)$ contains $\left(\begin{array}{c}d(x) \ r\end{array}\right) r$-tuples of vertices. If we take the sum of all such $r$-tuples over the neighborhoods of all $x \in A$, we get $\sum_{x \in A}\left(\begin{array}{c}d(x) \ r\end{array}\right)$. Note that any $r$-tuple can be counted at most $r-1$ times. Otherwise, we would get a $K_{r, r}$ subgraph. Thus,
$$
\sum_{x \in A}\left(\begin{array}{c}
d(x) \
r
\end{array}\right) \leq(r-1)\left(\begin{array}{l}
n \
r
\end{array}\right)
$$
Due to the convexity of $\left(\begin{array}{c}d(x) \ r\end{array}\right)$ (for $\left.d(x)>r-1\right), \sum_{x \in A}\left(\begin{array}{c}d(x) \ r\end{array}\right)$ is minimized if the degrees of $x \in A$ are as even as possible. Thus,
$$
\sum_{x \in A}\left(\begin{array}{c}
d(x) \
r
\end{array}\right) \geq n \cdot\left(\begin{array}{c}
|E(G)| / n \
r
\end{array}\right) \geq n \cdot \frac{(|E(G)| / n-r)^r}{r !}
$$
Also,
$$
(r-1)\left(\begin{array}{l}
n \
r
\end{array}\right) \leq(r-1) \frac{n^r}{r !}
$$
Therefore,
$$
n \cdot \frac{(|E(G)| / n-r)^r}{r !} \leq(r-1) \frac{n^r}{r !}
$$
If we solve this for $|E(G)|$, we conclude that $\operatorname{ex}\left(n, K_{r, r}\right) \leq c n^{2-1 / r}$.
page 196, #11 Given a graph $G$ with $\epsilon(G) \geq k \in \mathbb{N}$, find a minor $H \prec G$ such that $\delta(H) \geq k \geq|H| / 2$.
Solution: Let $k=1$. Let $G$ be a graph with $\epsilon(G) \geq 1=k$. That means $G$ has at least one edge. If we let $H$ be a path $P_1, H$ is certainly a minor of $G$, and $\delta(H)=k=|H| / 2=1$.
We proceed by induction. Let $n \in \mathbb{N}$. Suppose for all $k \leq n-1$, for every graph $G$ with $\epsilon(G) \geq k$, we can find a minor $H \prec G$ such that $\delta(H) \geq k \geq|H| / 2$. Let $G$ be a graph with $\epsilon(G) \geq n$. Pick the minimal minor $H \prec G$ such that $\delta(H) \geq k$, and let $x \in H$. Let us create a new graph $H^{\prime}$ from $H$ by removing $x$. Since $\delta(H) \geq k, x$ is not isolated, and the neighbors of $x$ will have degree at least $k-1$ when $x$ is removed. Since $\epsilon\left(H^{\prime}\right) \geq k-1$, by the inductive hypothesis, we can find a minor $H^{\prime \prime}$ of $H^{\prime}$ that satisfies $\delta\left(H^{\prime \prime}\right) \geq k-1 \geq\left|H^{\prime \prime}\right| / 2$. When we add $x$ back in, we still get $\delta(H) \geq k$. Since we are adding only one vertex, $\left|H^{\prime \prime}\right|$ goes up by at $\operatorname{most} \frac{1}{2}$, so $k \geq|H| / 2$
If a graph $G_n$ contains no $K_4$ and only contains $o(n)$ independent vertices, then $\left|G_n\right|<\left(\frac{1}{8}+o(1)\right) n^2$. (Hint: apply Szemerédi’s Regularity Lemma.)
Solution: For any $\epsilon>0$, we apply Szemerédi’s Regularity Lemma to $G$ to get a regularity partition $V=V_0 \cup V_1 \cup \cdots \cup V_k$. We define an auxiliary graph $R$ with the vertex set $\left{V_1, \ldots, V_k\right}$. A pair $\left(V_i, V_j\right)$ forms an edge of $R$ if it is a regular pair with edge density at least $3 \epsilon$. We claim:
Claim a: No regularity pair has density $d>\frac{1}{2}+2 \epsilon$.
Claim b: $R$ is triangle-free.
Proof of Claim a: If a regular pair $\left(V_i, V_j\right)$ has density $d>\frac{1}{2}+2 \epsilon$. We claim that we can find a $K_4$ in $G$. Call a vertex $v \in V_i$ is good if for any $B \subset V_j$ with $|B|>\epsilon\left|V_j\right|, v$ has at least $(d-\epsilon)$ neighbors in $B$. All vertices in $V_i$ but a $\epsilon$-fraction are good. Since the independent number of $G$ is $o(n)$, there is an edge $x y$ in $V_i$ so that both $x$ and $y$ are good. This implies $\left|N(x) \cap N(y) \cap V_j\right|>(d-\epsilon)^2\left|V_j\right|$. Thus inside $N(x) \cap N(y) \cap V_j$ contains an edge st. The induced graph on ${x, y, s, t}$ is a $K_4$. Contradiction.
Proof of Claim b: Suppose that $R$ contains a triangle $V_i V_j V_s$. We can define a vertex $v \in V_i$ is good in a similarly way. At least $(1-2 \epsilon) V_i$ vertices are good. Pick an edge $x y$ so that both $x$ and $y$ are good in $V_i$. Consider $N(x) \cap N(y) \cap V_j$ and $N(x) \cap N(y) \cap V_s$. Both sets have size at least $(d-\epsilon)^2\left|V_i\right|$. Thus we can select an edge $z w$ so that $z \in N(x) \cap N(y) \cap V_j$ and $w \in N(x) \cap N(y) \cap V_s$. Once again, we found a $K_4$. Contradiction.
Let $l=\left|V_i\right| \approx \frac{n}{k}$. Since $R$ is triangle-free, $R$ has at most $k^2 / 4$ edges. The total number of edge in $G$ can be bounded by
$$
\begin{aligned}
\left|G_n\right| & \leq|R|\left(\frac{1}{2}+2 \epsilon\right) l^2+\left(\left(\begin{array}{l}
k \
2
\end{array}\right)-|R|\right) 3 \epsilon l^2+\epsilon k^2 l^2+\epsilon k l^2 \
& \leq\left(\frac{1}{8}+20 \epsilon\right) n^2 .
\end{aligned}
$$
Now let $\epsilon \rightarrow 0$, we have $\left|G_n\right|<\left(\frac{1}{8}+o(1)\right) n^2$.
MY-ASSIGNMENTEXPERT™可以为您提供 SYDNEY MATH2069 GRAPH THEORY图论的代写代考和辅导服务！
