Posted on Categories:Graph Theory, 图论, 数学代写

# 数学代写|图论代考GRAPH THEORY代写|Minors

avatest™

## avatest™帮您通过考试

avatest™的各个学科专家已帮了学生顺利通过达上千场考试。我们保证您快速准时完成各时长和类型的考试，包括in class、take home、online、proctor。写手整理各样的资源来或按照您学校的资料教您，创造模拟试题，提供所有的问题例子，以保证您在真实考试中取得的通过率是85%以上。如果您有即将到来的每周、季考、期中或期末考试，我们都能帮助您！

•最快12小时交付

•200+ 英语母语导师

•70分以下全额退款

## 数学代写|图论代写GRAPH THEORY代考|Minors

In this section and the next, we ask how global assumptions about a graph – on its average degree, its chromatic number, or even its girthcan force it to contain a given graph as a minor or topological minor.
For example, consider the analogue of Turán’s theorem: how many edges on $n$ vertices force a $K^r$ minor or topological minor? We know already from Chapter 3.5 that topological $K^r$ minors can be forced in sparse graphs, i.e., that some linear number $c_r n$ of edges is enough. But what can we say about $c_r$ as a function of $r$ ? The upper bound $h(r)$ on $c_r$ that we found in the proof of Lemma 3.5 .1 was $2^{\left(\begin{array}{l}r \ 2\end{array}\right)}$; an easy lower bound is $\frac{1}{8} r^2$ (Exercise 25).

It was only in 1996 that this lower bound was shown to be of the right order of magnitude. With the help of Theorem 3.5.3, the proof is now just a few lines:

Theorem 7.2.1. There is a constant $c \in \mathbb{R}$ such that, for every $r \in \mathbb{N}$, every graph $G$ of average degree $d(G) \geqslant c r^2$ contains $K^r$ as a topological minor.

Proof. We prove the theorem with $c=10$. Let $G$ be a graph of average degree at least $10 r^2$. By Theorem 1.4 .3 with $k:=r^2, G$ has an $r^2$-connected subgraph $H$ with $\varepsilon(H)>\varepsilon(G)-r^2 \geqslant 4 r^2$. To find a $T K^r$ in $H$, we start by picking $r$ vertices as branch vertices, and $r-1$ neighbours of each of these as some initial subdividing vertices. These are $r^2$ vertices in total, so as $\delta(H) \geqslant \kappa(H) \geqslant r^2$ they can be chosen distinct. Now all that remains is to link up the subdividing vertices in pairs, by disjoint paths in $H$ corresponding to the edges of the $K^r$ of which we wish to find a subdivision. Such paths exist, because $H$ is $\frac{1}{2} r^2$-linked by Theorem 3.5.3.

For small $r$, one can try to determine the exact number of edges needed to force a $T K^r$ subgraph on $n$ vertices. For $r=4$, this number is $2 n-2$; see Corollary 7.3.2. For $r=5$, plane triangulations yield a lower bound of $3 n-5$ (Corollary 4.2.10). The converse, that $3 n-5$ edges do force a $T K^5$ – not just either a $T K^5$ or a $T K_{3,3}$, as they do by Corollary 4.2.10 and Kuratowski’s theorem-is already a difficult theorem (Mader 1998).

Let us now turn from topological minors to general minors. The average degree needed to force a $K^r$ minor is known almost precisely. Thomason (2001) determined, asymptotically, the smallest constant $c$ that makes the following theorem true as $\alpha+o(1)$, where $o(1)$ stands for a function of $r$ tending to zero as $r \rightarrow \infty$ and $\alpha=0.53131 \ldots$ is an explicit constant.

As we saw in Section 7.2, an average degree of $c r \sqrt{\log r}$ suffices to force an arbitrary graph to have a $K^r$ minor, and an average degree of $\mathrm{cr}^2$ forces it to have a topological $K^r$ minor. If we replace ‘average degree’ above with ‘chromatic number’ then, with almost the same constants $c$, the two assertions remain true: this is because every graph with chromatic number $k$ has a subgraph of average degree at least $k-1$ (Corollary 5.2 .3$)$.

Although both functions above, $c r \sqrt{\log r}$ and $c r^2$, are best possible (up to the constant $c$ ) for the said implications with ‘average degree’, the question arises whether they are still best possible with ‘chromatic number’ – or whether some slower-growing function would do in that case. What lies hidden behind this problem about growth rates is a fundamental question about the nature of the invariant $\chi$ : can this invariant have some direct structural effect on a graph in terms of forcing concrete substructures, or is its effect no greater than that of the ‘unstructural’ property of having lots of edges somewhere, which it implies trivially?
Neither for general nor for topological minors is the answer to this question known. For general minors, however, the following conjecture of Hadwiger suggests a positive answer:
The following implication holds for every integer $r>0$ and every graph $G$ :
$$\chi(G) \geqslant r \Rightarrow G \succcurlyeq K^r$$
Hadwiger’s conjecture is trivial for $r \leqslant 2$, easy for $r=3$ and $r=4$ (exercises), and equivalent to the four colour theorem for $r=5$ and $r=6$. For $r \geqslant 7$ the conjecture is open, but it is true for line graphs (Exercise 35) and for graphs of large girth (Exercise 33; see also Corollary 7.3.9). Rephrased as $G \succcurlyeq K^{\chi(G)}$, it is true for almost all graphs. ${ }^3$ In general, the conjecture for $r+1$ implies it for $r$ (exercise).

## 数学代写|图论代写GRAPH THEORY代考|Minors

$$\chi(G) \geqslant r \Rightarrow G \succcurlyeq K^r$$