TITLE: How to find the first-order approximation around a given point?
QUESTION [0 upvotes]: Lets pretend i have some function $f(x) = 2*x_1 + 3*x_2$, and says find first order approximation around some point [a b].
I know the formula $f_a (x) = f(x') + f(x)'*(x-x')$, but do not know how to plug in 2 dimensional point in place of x'
By the way x' is a  x hat, i do not know how to write here x hat :)
And $f_a ()$ is affine

REPLY [2 votes]: This does not answer the main question, since that takes no work at all. So we deal with the $f(x_1,x_2)=e^{x_1+x_2}+x_1^2+x_2^3$ of a comment by the OP, in a neighbourhood of $(0,1)$.
We have
$$\frac{\partial f}{\partial x_1}=e^{x_1+x_2}+2x_1.$$
At $(0,1)$ this is $e$.
Similarly,
$$\frac{\partial f}{\partial x_2}=e^{x_1+x_2}+3x_2^2.$$
At $(0,1)$ this is $e+3$.
So the linear approximation is
$$(x_1-0)(e)+(x_2-1)(e+3)+ (e+1).$$
The last term $e+1$ is just $f(0,1)$.
We can simplify the above expression a little.


TITLE: Are the borromean rings a torus link?
QUESTION [5 upvotes]: The $(3,3)$ torus link produces three unknots that are pairwise linked, which makes me suspect that the borromean rings ─ which are otherwise rather similar ─ cannot be produced through any $(p,q)$ torus link combination, and therefore that there is no deformation of the borromean rings that will make them lie on a torus. However, my knot theory isn't strong enough to make a harder case for this, and there's no mention of any connections in either wikipedia page.
So: can the borromean links be deformed so that they will lay on the surface of a torus? If so, how? If not, why not?

REPLY [1 votes]: No, the Borromean rings are not a torus link, which is what we call links that can lie on a torus.  To quote the wikipedia article on the Borromean rings:

The Borromean rings are a hyperbolic link: the complement of the Borromean rings in the 3-sphere admits a complete hyperbolic metric of finite volume.

Then we use the fact that every knot or link falls into one of three categories, this time using the wikipedia article on Hyperbolic links:

As a consequence of the work of William Thurston, it is known that every knot is precisely one of the following: hyperbolic, a torus knot, or a satellite knot. As a consequence, hyperbolic knots can be considered plentiful. A similar heuristic applies to hyperbolic links.

So, since the Borromean rings are hyperbolic, they cannot be a torus link. Hope this helps.


TITLE: Relation between Hajos number and chromatic number of a graph
QUESTION [0 upvotes]: So, I'm trying to solve the following exercise available in the book "The Probabilistic Method", by Alon and Spencer.
The Hajós number of a graph $G$ is the maximum number $k$ such that there are $k$ vertices in $G$ with a path between each pair so that all the $\binom{k}{2}$ paths are internally vertex disjoint (and no vertex is an internal vertex of a path and an endpoint of another). Is there a graph whose chromatic number exceeds twice its Hajós number?
My thoughts: I tried to follow this answer: Hajós Number vs. Chromatic Number
Following the hint, using the random graph $G(n, \frac{1}{2})$, it seems to me that there is a graph such that the Hajós number should be less or equal to $2 \sqrt{n}$, because for $k$ larger one would need more than $n$ vertices to construct $\binom{k}{2}$ such paths. My problem is how to get a lower bound for the chromatic number in this case. I'd appreciate any hint.

REPLY [1 votes]: The chromatic number of a random graph is well-known. If you are not happy simply citing Theorem 10.3.1 of Alon and Spencer for the result that with high probability
$$
   \chi(G_{n,1/2}) \sim \frac{n}{2\log_2 n}
$$
then we can get a lower bound of this order without too much difficulty. The probability that a set of $k$ vertices is independent is $2^{-k(k-1)/2}$, so the expected number of independent sets of size $k$ is
$$
   \binom nk 2^{-k(k-1)/2} \le \left(\frac{ne}{k} \cdot 2^{-(k-1)/2}\right)^k
$$
and when $k = 2 \log_2 n$, this becomes $\left(\frac{e\sqrt 2}{k}\right)^k = o(1)$. So with high probability there are no independent sets of this size, and therefore we need at least $\frac{n}{2\log_2 n}$ colors, since each color can be used on at most $2\log_2 n$ vertices.


TITLE: How was the 10's complement calculated for the signed numbers below?
QUESTION [0 upvotes]: In the image below, why is the given sum equal to +10, 627 ?
Why the 10's complement of +9286 is 990714 and not 000714 (10000-9286) ?
Why was there an overflow in part b) ?

REPLY [1 votes]: First of all, 10,627 is a mistake.  They probably changed the operands and forgot to update the result.
Ten's complement arithmetic works just like two's complement arithmetic.  I'll assume you are at least a bit familiar with that.
If you want to represent absolute values that require 5 digits, you need 6 digits, regardless of the base.  Complementation of $x$ is equivalent to computing $10^6-x$.  (In general, $b^n-x$ if $b$ is the base and $n$ is the number of digits.)
The arithmetic is done modulo $10^n$ (that is, $b^n$).  Hence everything in excess of $10^n-1$ is thrown away.  There's "overflow" also in case (d), even though it's not mentioned in the solutions.


TITLE: $(2,1+\sqrt{-5}), (1-\sqrt{-5},2)$ generate the $\mathbb Z[\sqrt{-5}]$-module $\langle 2,1+\sqrt{-5} \rangle \times \langle 2,1+\sqrt{-5} \rangle$
QUESTION [4 upvotes]: Ok, boring question here (I guess, at least). Let $R=\mathbb Z[\sqrt{-5}]$. Let $M=\langle 2,1+\sqrt{-5} \rangle$ the $R$-module generated by $2$ and $1+\sqrt{-5}$. I am asked to show that $M \times M = \langle (2,1+\sqrt{-5}), (1-\sqrt{-5},2) \rangle$, i.e. that $M \times M$ is generated by the two elements $(2,1+\sqrt{-5})$ and $(1-\sqrt{-5},2)$, and that $M \times M$ is free.
I was able to prove that $(2,1+\sqrt{-5})$ and $(1-\sqrt{-5},2)$ are linearly independent, but I can't find any way to show that they generate the whole $M \times M$ module.
I tried to proceed as follows: for any $a,b,c,d,e,f,g,h \in \mathbb Z$, I must find $\alpha, \beta, \gamma, \delta \in \mathbb Z$ such that
$$\big( 2(a+b\sqrt{-5})+(1-\sqrt{-5})(c+d\sqrt{-5}), 2(e+f\sqrt{-5})+(1-\sqrt{-5})(g+h\sqrt{-5}) \big)$$
$$=$$
$$\big( 2(\alpha+\beta\sqrt{-5})+(1-\sqrt{-5})(\gamma+\delta\sqrt{-5}), (1+\sqrt{-5})(\alpha+\beta\sqrt{-5})+2(\gamma+\delta\sqrt{-5}) \big).$$
After some computations, this lead me to
$$\big( 2a+c+5d+(2b+d-c)\sqrt{-5}, 2e+g+5h+(2f+h-g)\sqrt{-5} \big)$$
$$=$$
$$\big( 2\alpha + \gamma + 5\delta+(2\beta+\delta-\gamma)\sqrt{-5}, 2\gamma + \alpha - 5\beta + (2\delta+\beta+\alpha)\sqrt{-5}) \big),$$
which means that I have to solve the following system:
$$
\begin{cases}
2\alpha + \gamma + 5\delta= 2a+c+5d\\
2\beta+\delta-\gamma= 2b+d-c\\
2\gamma + \alpha - 5\beta= 2e+g+5h\\
2\delta+\beta+\alpha= 2f+h-g\\
\end{cases}
$$
and I don't know how to go on.
Any help is much appreciated! Thanks!

REPLY [2 votes]: Let $I = \langle(2,1+\sqrt{-5}),(1-\sqrt{-5},2)\rangle$.
As you've probably seen, $2 \times 2 - (1+\sqrt{-5})(1-\sqrt{-5}) = -2 \neq 0$ so $I$ is a free $R$-module of rank $2$, and we even have an $R$-basis of $I$.
More importantly this calculation also shows that $(0,2)$ and $(2,0)$ are in $I$ (just do the combination that cancels each component in the obvious way).
Then it's immediate to see that $(0,1+\sqrt{-5})$ and $(1-\sqrt{-5},0)$ are also in $I$, and finally that $M \times M \subset I$.
The other inclusion is obvious : since $2,1+\sqrt{-5},1-\sqrt{-5} \in M$, $I \subset M \times M$.
Hence $M \times M$ is the free $R$-module of rank $2$ generated by $(2,1+\sqrt{-5})$ and $(1-\sqrt{-5},2)$


text:
\begin{document}

\title{Minimum degree and size conditions for the proper connection number of graphs}

\author{ Xiaxia Guan$^a$, \quad Lina Xue$^a$, \quad Eddie Cheng$^b$, \quad Weihua Yang$^a$\footnote{Corresponding author. E-mail: ywh222@163.com,~yangweihua@tyut.edu.cn}\\
\\ \small $^a$Department of Mathematics, Taiyuan University of
Technology,\\
\small  Taiyuan Shanxi-030024,
China\\
\small $^b$Department of Mathematics and Statistics, Oakland University, Rochester, MI 48309, USA}
\date{}
\maketitle

{\small{\bf Abstract:}
An edge-coloured graph $G$ is called $properly$ $connected$ if every two vertices are connected by a proper path. The $proper$ $connection$ $number$ of a connected graph $G$, denoted by $pc(G)$, is the smallest number of colours that are needed in order to make $G$ properly connected. Susan A. van Aardt et al.
gave a sufficient condition for the proper connection number to be at most $k$ in terms of the size of graphs. In this note,

our main result is the following, by adding a minimum degree condition: Let $G$ be a connected graph of order $n$, $k\geq3$. If $|E(G)|\geq \binom{n-m-(k+1-m)(\delta+1)}{2} +(k+1-m)\binom{\delta+1}{2}+k+2$, then $pc(G)\leq k$, where $m$ takes the value $t$ if $\delta=1$ and $\lfloor \frac{k}{\delta-1} \rfloor$ if $\delta\geq2$.  Furthermore, if $k=2$ and $\delta=2$,
$pc(G)\leq 2$, except $G\in \{G_{1}, G_{n}\}$ ($n\geq8$), where $G_{1}=K_{1}\vee 3K_{2}$ and  $G_{n}$ is obtained by taking a complete graph $K_{n-5}$  and $K_{1}\vee (2K_{2}$) with an arbitrary vertex of $K_{n-5}$ and a vertex with $d(v)=4$ in $K_{1}\vee (2K_{2}$) being joined. If  $k=2$, $\delta \geq 3$,
we conjecture $pc(G)\leq 2$, where $m$ takes the value $1$ if $\delta=3$ and $0$ if $\delta\geq4$ in the assumption.

\vskip 0.5cm  Keywords: Proper connection number; Minimum degree; Edge number

\section{Introduction}

All graphs in this work are simple, finite connected and undirected. We follow \cite{Boundy} for graph theoretical notations  not defined here. Let $G$ be a  connected graph, we denote by $c(G)$ the $circumference$ of $G$, i.e., the order of a longest cycle of $G$, and by $p(G)$ the $detour$ $number$ of $G$, i.e., the order of a longest path of $G$.

As the extension of proper colourings are motivated by rainbow connections of graphs, Andrews et al.\cite{Andrews} and, independently, Borozan et al.\cite{Borozan} introduced the concept of proper connections in graphs. An edge-coloured graph $G$ is called $rainbow$-$connected$\cite{Chartrand} if every two vertices are connected by a path whose edges have different colours.  The $rainbow$ $connection$ $number$ of a connected graph $G$, denoted by $rc(G)$, is the smallest number of colours that are needed in order to make $G$ rainbow connected. An easy observation is that if $G$ has $n$ vertices then $rc(G)\leq n-1$, since one may colour the edges of a given spanning tree of $G$ with different colours, and colour the remaining edges with one of the already used colours.

A path in an edge-coloured graph is called a $proper$ $path$ if no two adjacent edges of the path are colored with one same color. An edge-colored graph $G$ is called $properly$ $connected$ if every pair of distinct vertices of $G$ is connected by a path whose edges are properly coloured. For a connected graph $G$, the $proper$ $connection$ $number$ of $G$, denoted by $pc(G)$, is defined as the smallest number of colors that are needed in order to make $G$ properly connected.

The proper connection of graphs has the following application. When building a communication network of wireless signal towers, one fundamental requirement is that the network be connected. If there cannot be a direct connection between two towers $A$ and $B$, say for example if there is a mountain in between, there must be a route through other towers to get from $A$ to $B$. As a wireless transmission passes through a signal tower, to avoid interference, it would be helpful if the incoming signal and the outgoing signal do not share the same frequency. Suppose that we assign a vertex to each signal tower, an edge between two vertices if the corresponding signal towers are directly connected by a signal and assign a color to each edge based on the assigned frequency used for the communication, then, the number of frequencies needed to assign to the connections between towers so that there is always a path avoiding interference between each pair of towers is precisely the proper connection number of the corresponding graph \cite{Huang}.

For the proper connection number of $G$, the following results are known.

\begin{Proposition}\label {Proposition 1.}
Let $G$ be a  connected graph of order $n$ (number of vertices) and size $m$ (number of edges). Then

(1) $1\leq pc(G)\leq \min\{\chi^{\prime}(G), rc(G)\}\leq m$, where $\chi^{\prime}(G)$ is the edge chromatic number of $G$,

(2) $pc(G) = 1$ if and only if $G = K_{n}$,

(3) $pc(G) = m$ if and only if $G \cong K_{1,m}$ is a star of size $m$,

(4) If $G$ is a tree, then $pc(G) = \Delta(G)$,

(5) If $G$ is traceable, i.e., there exists Hamilton path in $G$, then $pc(G)\leq 2$.

\end{Proposition}

For each pair of positive integers $n$ and $k$, we define  $g(n,k)$ to be  the smallest integer such that every connected graph of order $n$ and size at least $g(n,k)$ has proper connection number at most $k$. Huang, Li, and wang \cite{Wang} showed that $g(n,k)=\binom{n-k-1}{2}+k+2$ for $k=2$, $n\geq14$, and for $k=3$, $n\geq14$. In this paper we consider the function $g(n,k)$ by adding a minimum degree condition.

The analogous problem for rainbow connections was introduced in \cite{Kemnitz} and results on that problem appeared in \cite{Przybylo,Kemnitz,Li 2,Li 3,I}.

\section{Auxiliary results}

We shall use the following result of Andrews et al. \cite{Andrews}.

\begin{lem}[\cite{Andrews}]\label{lem2.1}
If $G$ is a  connected graph and $H$ is a connected spanning subgraph of $G$, then $pc(G)\leq pc(H)$. In particular, $pc(G)\leq pc(T)$ for every spanning tree $T$ of $G$.
\end{lem}

In fact, Lemma~\ref{lem2.1} also states that the $proper$ $connection$ $number$ is monotonic under adding edges.

\begin{Proposition}[\cite{Borozan}]\label{Proposition3}
If a graph $G$ contains a vertex $v$ such that $d(v)\geq 2$ and $pc(G-v)\leq 2$, then $pc(G)\leq 2$.
\end{Proposition}

\begin{thm}[\cite{Borozan}]\label{thm1}
If $G$ is a $2$-connected graph, then $pc(G)\leq 3$.
\end{thm}

Huang et al. \cite{Wang} extended Theorem~\ref{thm1} as follows.

\begin{thm}[\cite{Wang}]\label{thm2}
If $G$ is a connected bridgeless graph, then $pc(G)\leq 3$.
\end{thm}

For a connected graph $G$ with bridges, Huang et al. \cite{Wang} described the following natural approach: Let $B \subseteq E(G)$ be the set of cut-edges of a graph $G$. Let $\mathcal{C}$ denoted the set of connected components of $G^{\prime}$ = $(V, E\backslash B)$. There are two types of elements in $\mathcal{C}$, singletons and connected bridgeless subgraphs of $G$. Let $\mathcal{S} \subseteq \mathcal{C}$ denoted the singletons and let $\mathcal{D}$ = $\mathcal{C} \setminus \mathcal{S}$. Each element of $\mathcal{S}$ is, therefore, a vertex, and each element of $\mathcal{D}$ is a connected bridgeless subgraph of $G$. Contracting each element of $\mathcal{D}$ to a vertex, we obtain a new graph $G^{*}$. It is easy to see that $G^{*}$ is a tree, and the edge set of $G^{*}$ is $B$. Using the above notations, we have the following result.

\begin{thm}[\cite{Wang}]\label{thm3}
If $G$ is a connected graph, then $pc(G) \leq \max \{3, \Delta(G^{*})\}$.
\end{thm}

\begin{thm}[\cite{Susan}]\label{thm3.1}
Let $G$ be a connected graph of order $n$ and $k\geq 2$. If $|E(G)|\geq \binom{n-k-1}{2} +k+2$, then $pc(G) \leq k$ except when $k=2$ and $G\in \{G^{\ast}_{1}, G^{\ast}_{2}\}$.
\end{thm}

The two attentional graphs in Theorem~\ref{thm3.1}. and the following.

Let $G^{\ast}_{1}=K_{1}\vee (2K_{1}+K_{2})$ and $G^{\ast}_{2}=K_{1}\vee (K_{1}+2K_{2})$ where $G+H=(V_{G}\cup V_{H},E_{G}\cup E_{H})$ is the disjoint union and $G\vee H=(V_{G}\cup V_{H},E_{G}\cup E_{H}\cup \{uv : u\in V_{G}, v\in V_{H}\})$ is the join of the graphs $G=(V_{G},E_{G})$ and $H=(V_{H},E_{H})$.

We shall repeatedly use the following identities.

\begin{Proposition}\label{Proposition2.5}
For every pair of positive integers $a$ and $b$,

$\binom{a}{2}+\binom{b}{2}$=$\binom{a+b}{2}-ab$ and
$\binom{a+1}{2}$=$\binom{a}{2}+a$.
\end{Proposition}

In addition, we need the following result.

\begin{thm}[\cite{Dirac}]\label{thm Dirac}
Let $G$ be a graph with $n$ vertices. If $\delta(G) \geq \frac{n-1}{2}$ then $G$ has a Hamiltonian path. Moreover, if $\delta(G)\geq\frac{n}{2}$, then $G$ has a Hamiltonian cycle. Also, if $\delta(G) \geq \frac{n+1}{2}$, then $G$ is Hamiltonian-connected.
\end{thm}

\begin{thm}[\cite{Susan}]\label{thm2.0}
Let $G$ be a connected graph of order $n$ and $t$ bridges, then  $|E(G)|\leq \binom{n-t}{2} +t$.
\end{thm}

The next lemma will be useful for the proof of our main result.

\begin{lem}\label{lem2.6}
Let $G$ be a connected graph of order $n$  with $t$ bridges and $\delta=\delta(G)$.
Then $|E(G)|\leq \binom{n-m-(t-m)(\delta+1)}{2} +(t-m)\binom{\delta+1}{2}+t,$
where if $t=0$, then $m=0$. If  $\delta=1$, then $m=t$. If $\delta \geq 2$ and $t\neq 0$, then $m=\lfloor \frac{t-1}{\delta-1} \rfloor$.
\end{lem}

\begin{proof}

It is easy to see that the result holds for $t=0$.
We assume $t\geq 1$, then $|\mathcal{C}|=t+1$. Let $C_{1}, \cdots, C_{t+1}$ be the $|\mathcal{C}|$ elements  and $n_{i}$ ($i=1, \cdots, t+1$) be the orders of $C_{i}$.  Then $|E(G)|=\sum\limits_{i=1}^{t+1}|E(C_{i})|+t\leq\sum\limits_{i=1}^{t+1}\binom{n_{i}}{2}+t$. We define a supergraph $\widetilde{G}$ of $G$ (that is, $G$ is subgraph of $\widetilde{G}$) by adding all the possible edges in each $C_i$ in $G-B$  (that is, each component of $\widetilde{G}-B$ is complete. If no confusion arises,  we also use $C_i$ in $\widetilde{G}$ to denote the complete subgraphs obtained from $C_i$ of $\mathcal{C}$).

Now we construct the graph $G^{\prime}$ from $\widetilde{G}$ if there are two components $C_k$ and $C_l$ satisfying  $1<n_{k} \leq n_{l}$. We move a vertex $v$ from $C_{k}$ to $C_{l}$, replace  $v$ with an arbitrary vertex in $V(C_k)\setminus v$ for the bridges incident to $v$,  add the edges between $v$ and the vertices in $C_{l}$, and delete the edges between $v$ and the vertices in $C_{k}$, where $v$ is not adjacent to the vertices of $C_{l}$ in  $\widetilde{G}$.
We claim that $|E(\widetilde{G})|\geq|E(G)|$, since
\begin{equation}\label{eq1}
\begin{split}
|E(G^{\prime})|&=
\sum_{\substack{i=1\\ \neq k,l }}^{t+1}\binom{n_{i}}{2}+\binom{n_{k}-1}{2}+\binom{n_{l}+1}{2}+t\\
&=\sum_{\substack{i=1\\ \neq k,l }}^{t+1}\binom{n_{i}}{2}+\binom{n_{k}}{2}-(n_{k}-1)+\binom{n_{l}}{2}+n_{l}+t\\
&=|E(\widetilde{G})|+n_{l}-n_{k}+1>|E(\widetilde{G})|\geq|E(G)|.
 \end{split}
 \end{equation}

It can be seen that if $\delta=1$, then we repeatedly  move vertices so that $\mathcal{D}$ has only one element, that is, $|E(G)|\leq \binom{n-t}{2}+t$ by (\ref{eq1}).

We next assume $\delta_{\widetilde{G}}\geq 2$. Without loss of generality, we let $C_{i},1\leq i\leq m$ be the elements of $\mathcal{S}$ and $C_{i}, m< i\leq t+1$ be the elements of $\mathcal{D}$, respectively. Note that, each $C_i, i\leq m$ has at least $\delta$ neighbors in $\mathcal{C}$, and there are at most $m-1$ edges between  $C_i$ in $\mathcal{S}$. Thus, we have $m\delta-(m-1)\leq t$, that is, $m\leq \frac{t-1}{\delta-1}$.

Suppose there exist $n_{a}$ in $\widetilde{G}$ so that $1<n_{a}<\delta+1$, $m< a\leq t+1$. Then every vertex is at least incident to $\delta+1-n_{a}$ bridges in $V(C_{a})$ as the minimum degree of $\widetilde{G}$ is at least $\delta$, that is, there is at least  $\delta$ bridges incident to $V(C_{a})$ due to $n_{a}(\delta+1-n_{a})>\delta$ for $1<n_{a}<\delta+1$. By (\ref{eq1}), the size of $\widetilde{G}$ is fewer than the size  of the graph obtained by  moving vertices of $C_{a}$ to $C_{b}$ ($n_{b}\geq \delta+1$) so that $n_{a}=1$. Thus, by (\ref{eq1}), if the size of $G$ is as large as possible, then $m=\lfloor \frac{t-1}{\delta-1} \rfloor$ and $n_{i}\geq \delta+1,m< i\leq t+1$.

Therefore, we conclude that $|E(G)|\leq \binom{n-m-(t-m)(\delta+1)}{2} +(t-m)\binom{\delta+1}{2}+t$.
\end{proof}

We end this section with some results on the existence of long cycles in graphs that will be used below. We first state a classic result of Erd\H{o}s and Gallai~\cite{Erdos}.

\begin{thm}[\cite{Erdos}]\label{thm4}
Let $G$ be a graph of order $n$ and circumference $c(G)$. If
$$|E(G)|> \frac{c}{2} (n-1),$$
then $c(G)> c$.
\end{thm}

We shall use Woodall's extension of the Erd\H{o}s-Gallai Theorem, which may be stated as follows.

\begin{thm}[\cite{Woodall}]\label{thm5}
Let $G$ be a graph of order $n=tm+r$, where $m\geq 1$, $t\geq 0$, and $1\leq r\leq m $. If
$$|E(G)|> t\binom{m+1}{2} +\binom{r}{2},$$
then $c(G)\geq m+2$ and $p(G)\geq m+3$.
\end{thm}

\begin{thm}[Ore's Theorem,\cite{Ore}]\label{thm5.1}
If $G$ is a graph of order $n\geq 3$ such that $d(u)+d(v)\geq n$ for any pair $u$, $v$ of nonadjacent vertices in $G$, then $G$ is Hamiltonian.
\end{thm}

We shall use the following corollary of Ore's Theorem.

\begin{cor}
Assume $G$ is a graph of order $n$ and
$$|E(G)|\geq \binom{n-1}{2}+2.$$
Then $G$ is Hamiltonian.
\end{cor}

\section{Minimum degree and size conditions for the proper connection number of graphs}

We first establish an upper bound for the function $g(n,k)$ defined in Section $1$.

\begin{thm}\label{thm7}
Let $G$ be a connected graph of order $n$, $k\geq 3$. If $|E(G)|\geq \binom{n-m-(k+1-m)(\delta+1)}{2} +(k+1-m)\binom{\delta+1}{2}+k+2$, then $pc(G)\leq k$. Where if $\delta=1$, then $m=k+1$. If $\delta \geq 2$, then $m=\lfloor \frac{k}{\delta-1} \rfloor$.
\end{thm}

\begin{proof}
We first note that the statement is true for $\delta=1$ by Theorem~\ref{thm3.1}. In the following, we show that it is true for $\delta \geq 2$.

If $G$ is a connected bridgeless graph, then $pc(G)\leq 3 \leq k$ by Theorem~\ref{thm2}. So we assume that $G$ is connected with $t\geq 1$ bridges. We consider two cases.

{\bf Case 1.}\quad $t\leq k$.

In this case, $pc(G) \leq \max \{3, \Delta(G^{*})\} \leq \max\{3, t\} \leq \max\{3, k\} = k$ by Theorem~\ref{thm3}.

{\bf Case 2.}\quad $t\geq k+1$.

By Lemma~\ref{lem2.6}, we have $|E(G)|\leq \binom{n-m-(t-m)(\delta+1)}{2} +(t-m)\binom{\delta+1}{2}+t$, where $m=\lfloor \frac{t-1}{\delta-1} \rfloor$.

Suppose $\frac{t-1}{\delta-1}$ is not a positive integer (i.e., $\frac{t-2}{\delta-1}=\frac{t-1}{\delta-1}$), then
\begin{equation*} \label{eq:1}
\begin{split}
|E(G)|& \leq
\binom{n-m-(t-m)(\delta+1)}{2} +(t-m)\binom{\delta+1}{2}+t\\
&=\binom{n-m-(t-1-m)(\delta+1)}{2}-(\delta+1)(n-m-(t-m)(\delta+1))\\
&-\binom{\delta+1}{2}+(t-1-m)\binom{\delta+1}{2}+\binom{\delta+1}{2}+(t-1)+1\\
&=\binom{n-m-(t-1-m)(\delta+1)}{2} +(t-1-m)\binom{\delta+1}{2}\\
&+(t-1)-(\delta+1)(n-m-(t-m)(\delta+1))+1\\
&\leq \binom{n-m-(t-1-m)(\delta+1)}{2} +(t-1-m)\binom{\delta+1}{2}+(t-1)
 \end{split}
 \end{equation*}

 Suppose $\frac{t-1}{\delta-1}$ is  a positive integer (i.e., $\frac{t-2}{\delta-1}=\frac{t-1}{\delta-1}-1$), then
\begin{equation*} \label{eq:1}
\begin{split}
|E(G)|&\leq
\binom{n-m-(t-m)(\delta+1)}{2} +(t-m)\binom{\delta+1}{2}+t\\
&=\binom{n-(m-1)-(t-m)(\delta+1)}{2}-(n-m-(t-m)(\delta+1))\\
&+(t-m)\binom{\delta+1}{2}+t\\
&\leq \binom{n-(m-1)-(t-1-(m-1))(\delta+1)}{2}-(n-(m-1)\\
&-(t-1-(m-1))+(t-1-(m-1))\binom{\delta+1}{2}+(t-1)+1\\
&\leq \binom{n-m-(t-1-m)(\delta+1)}{2} +(t-1-m)\binom{\delta+1}{2}+(t-1)
 \end{split}
 \end{equation*}
Hence,   $|E(G)|$ is monotonic  decreasing on the bridges $t$, then if $t=k+1$, $|E(G)|$ is maximum and $|E(G)|\leq \binom{n-m-(k+1-m)(\delta+1)}{2} +(k+1-m)\binom{\delta+1}{2}+k+1$, a contradiction.
\end{proof}

\begin{rem}If $\delta\geq t$ (i.e., $m=0$), then  we construct a graph $G_{k}$ as follows: Take a complete graph $K_{n-(k+1)(\delta+1)}$ and $k+1$ complete graph $K_{\delta+1}$. Now a vertex of $K_{n-(k+1)(\delta+1)}$ and an arbitrary vertex of $(k+1)$ complete graph $K_{\delta+1})$ are joined. The resulting graph $G_{k}$ has order $n$, size $|E(G_{k})|=\binom{n-(k+1)(\delta+1)}{2} +(k+1)\binom{\delta+1}{2}+k+1$, and proper connection number $pc(G_{k})\geq k+1-m+m>k$. Therefore, $g(n,k)=\binom{n-(k+1)(\delta+1)}{2}+(k+1)\binom{\delta+1}{2}+k+2$, $k\geq 3$.
\end{rem}

Finally, we consider the case $k=2$. When $n\leq 2n+1$, then  $pc(G)\leq 2$ by Theorem~\ref{thm Dirac}.

\begin{thm}[\cite{Huang3}]\label{thm11}
Let $G$ be a connected noncomplete graph of order $5\leq n\leq 8$, if $G\notin\{G_{1},G_{8}\}$ and $\delta(G)\geq2$, then $pc(G)=2$.
\end{thm}

The two attentional graphs in Theorem \ref{thm11} and the following.

$G_{1}=K_{1}\vee 3K_{2}$ and  $G_{8}$ is obtained by taking a complete graph $K_{3}$  and $K_{1}\vee (2K_{2}$) with an arbitrary vertex of $K_{3}$ and a vertex with $d(v)=4$ in $K_{1}\vee (2K_{2}$) being joined.

\begin{thm}\label{thm8}
Let $G$ be a simple connected graph of order $n$ ($n\geq6$), $k=2$, $\delta=2$. If $|E(G)|\geq \binom{n-5}{2} +7$, then $pc(G)\leq 2$ unless $G\in \{G_{1}, G_{n}\}$,  where $G_{1}=K_{1}\vee 3K_{2}$ and  $G_{n}$ is obtained by taking a complete graph $K_{n-5}$  and $K_{1}\vee (2K_{2}$) with an arbitrary vertex of $K_{n-5}$ and a vertex with $d(v)=4$ in $K_{1}\vee (2K_{2}$) being joined.
\end{thm}

\begin{proof}

If $k=2$, $\delta=2$, then $m=2$. We observe that the requirement $|E(G)|\geq \binom{n-5}{2} +7$ is equivalent to the requirement $|E(\bar{G})|\leq 5n-22$ where $\bar{G}$ is the complement of $G$.

Now we suppose $6 \leq n\leq 8$, the result holds by Theorem \ref{thm11}.

We now assume that $n\geq 9$ and proceed by induction on $n$. We consider five cases.

{\bf Case 1.}\quad $p(G)=n-1$.

Let $P=v_{1} v_{2} \ldots v_{n-1}$ be a path of order $n-1$ in $G$ and let $w$ be the vertex not contained in $P$. As $\delta=2$, then $d(w)\geq 2$. It follows from Proposition~\ref{Proposition3} that $pc(G)\leq 2$, a contradiction.

\textbf{Claim.} If $|E(G)|\geq \binom{n-6}{2} +7$ ($n\geq9$) with order $n-1$ of $G$, and $pc(G)\leq 2$ unless $G_{n-1}$. Let $G^{\prime}=G+v$ and $d_{G^{\prime}}(v)=n-6$, then $pc(G^{\prime})\leq 2$ or  $G^{\prime}=G_{n}$.

\begin{proof} We suppose $G^{\prime}\neq G_{n}$, there exist $v_{i}$ which does not belong to  $V(K_{n-5})$ such that $vv_{i}\in E(G)$, then
$p(G^{\prime})\geq n-1$. Hence $pc(G^{\prime})\leq 2$ according to Case 1 and Proposition~\ref{Proposition 1.}.
\end{proof}

{\bf Case 2.}\quad $p(G)=n-2$.

Let $P=v_{1} v_{2} \ldots v_{n-2}$ be a path of order $n-2$ in $G$ and let $w_{1}$, $w_{2}$ be the two vertices not contained in $P$. Since $\delta=2$, we have $d(w_{1})\geq 2$ and $d(w_{2})\geq 2$. Now assume $d_{p}(w_{2})\geq 2$ or $d_{p}(w_{2})\geq 2$,  without loss of generality, we assume $d_{p}(w_{2})\geq 2$. Since  $P$ is a longest path in $G$, then $w_{2}$ does not have consecutive neighbours on $P$ and  neither $v_{1}$ nor $v_{n-2}$ is a neighbour of $w_{2}$. And if $w_{1}v_{a}\in E(G)$, then $v_{1}v_{a+1}\in E(\bar{G})$. We have $d(w_{2})\leq \frac{n-5}{2}+1\leq n-6$ for $n\geq9$. Then $pc(G-w_{1})\leq2$  by our induction hypothesis. Thus, by applying Propositions~\ref{Proposition3}, we obtain that $pc(G)\leq2$.

Hence we may assume that $d_{p}(w_{1})=1$ and $d_{p}(w_{2})=1$, then $w_{1}$ and $w_{2}$ are adjacent. Let $w_{1}v_{a}, w_{2}v_{b}\in E(G)$, then $d(v_{1})\leq n-6$ and $d(v_{n-2})\leq n-6$, since $v_{1}v_{a+1}, v_{1}v_{a+2}, v_{1}v_{b+1}, v_{1}v_{b+2}$, $v_{1}w_{1}, v_{1}w_{2}, v_{n-2}v_{a-1}, v_{n-2}v_{a-2}, v_{n-2}v_{b-1}, v_{n-2}v_{b-2}, v_{n-2}w_{1}, v_{n-2}w_{2}, v_{1}v_{n-2}, v_{1}v_{n-3}, v_{2}v_{n-2}\in E(\bar{G})$. Then $|E(G-v)|\geq \binom{n-5}{2} +7-(n-6)=\binom{n-6}{2} +7$ ($v\in\{v_{1},v_{n-2}\}$) by Propositions~\ref{Proposition2.5}. If $\delta_{G-v}\geq 2$, then, by our induction hypothesis,  $pc(G-v)\leq 2$.  We obtain that $pc(G)=2$ by applying Propositions~\ref{Proposition3}. Thus we may assume $\delta_{G-v}=1$, then $d_{G}(v_{2})=d_{G}(v_{n-3})=d_{G}(w_{1})=d_{G}(w_{2})=2$ and $d_{G}(v_{1})> \frac{n}{2}$. There exist $v_{i}$ ($i$ is even) such that $v_{1}v_{i}\in E(G)$. Take a graph $G^{\prime}$ by adding  $v_{2}v_{i}$ in $G-v_{1}$. Note $\delta_{G^{\prime}}=2$, we have $G^{\prime}=G_{8}$ or $pc(G^{\prime})\leq 2$.  If  $pc(G^{\prime})\leq 2$, then $pc(G-v)\leq 2$ by our induction hypothesis and $pc(C)\leq2$, where $C=v_{1},\ldots,v_{i}$ is an even cycle. If $G^{\prime}=G_{8}$, then $p(G)\geq n-1$, a contradiction. Hence, $pc(G)\leq2$.

{\bf Case 3.}\quad $p(G)=n-3$.

Let $P=v_{1} v_{2} \ldots v_{n-3}$ be a path of order $n-3$ in $G$ and let $w_{1}$, $w_{2}$, $w_{3}$ be the three vertices not contained in $P$.
 First prove that exist $v$, where $v\in\{w_{1}, w_{2}, w_{3}, v_{1}, v_{n-3}\}$, such that $\delta_{G-v}\geq 2$. Suppose $\delta_{G-v}=1$, for all $v\in\{w_{1}, w_{2}, w_{3}, v_{1}, v_{n-3}\}$, then $d(v_{2})=d(v_{n-4})=2$ and exist two vertices such that $d(v)=2$ for $v\in\{w_{1},w_{2},w_{3}\}$, without loss of generality, we assume $d(w_{1})=d(w_{2})=2$. In fact, if $w_{3}v_{a}\in E(G)$, then $v_{1}v_{a+1}\in E(\bar{G})$. Hence $d(w_{3})+d(v_{1})\geq n$. then $|E(\bar{G})|\geq 4(n-3)-8+n=5n-20$, a contradiction. Since $d(w_{i})\leq \frac{n-7}{2}+2<n-6$ for $i=1,2,3$  and $d(v_{1})$($d(v_{n-3})$)$\leq n-6$. Then $|E(G-v)|\geq \binom{n-5}{2} +7-(n-6)=\binom{n-6}{2} +7$ by Propositions~\ref{Proposition2.5}. Hence, by our induction hypothesis,  $pc(G-v)\leq 2$.  We obtain that $pc(G)\leq2$ by applying Propositions~\ref{Proposition3}.

{\bf Case 4.}\quad $p(G)=n-4$.

Let $P=v_{1} v_{2} \ldots v_{n-4}$ be a path of order $n-4$ in $G$ and let $w_{1}$, $w_{2}$, $w_{3}$, $w_{4}$ be the four vertices not contained in $P$.  We obtain that $pc(G)=2$, similar to Case 3.

{\bf Case 5.}\quad $p(G)\leq n-5$.

If $n=9$, $|E(G)|\geq 13$, so $G$ contains a cycle of length at least $3$. Since $p(G)\leq 4$, this implies that $c(G)=3$. Hence $|E(G)|\leq 4\binom{3}{2}=12$, a contradiction.

If $n=10$, $|E(G)|\geq 17$. By Thorem~\ref{thm5} (by taking $t=4$, $m=2$, $r=2$), we obtain $c(G)\geq 4$. Since $p(G)\leq 5$, this implies that $c(G)=4$ and the longest cycle can only exist one. Then it is easily seen that $pc(G)\leq 2$, a contradiction.

If $n=11$, then $|E(G)|\geq 21$. By Thorem~\ref{thm5} (by taking $t=3$, $m=3$, $r=2$), we obtain $c(G)\geq 5$. Since $p(G)\leq 6$, this implies that $c(G)=5$ and the longest cycle can only exist one. Then $|E(G)|\leq \binom{5}{2} +3\cdot 3=19<21$, a contradiction.

If $12\leq n\leq 20$, by the arguments similar to that of $n=11$, we have the contradicting on $|E(G)|\geq \binom{n-5}{2} +7$.

If $n>20$, then $|E(G)|\geq \binom{n-5}{2} +7=\binom{n-6}{2} +(n-6)+7>\binom{n-6}{2} +\binom{7}{2}$ and then it follows from Theorem~\ref{thm5} (by taking $t=1$, $m=n-7$, $r=7$) that $p(G)\geq m+3=n-4$, contradicting our assumption on $p(G)$.
\end{proof}

\begin{rem}
The way is not applicable for $k=2$ and $\delta \geq 3$, since $\delta_{G-v}=\delta_{G}-1$ and the vertex belonging to $P$ with the degree being $\delta_{G-v}$ ($\delta_{G}-1$) in $G-v$ ($G$) is possible and $|E(G)|$ reduces  along with the bridges $\delta$  growth. We conjecture the following.
\end{rem}

\begin{Conjecture}\label{Conjecture3.4}
 Let $G$ be a connected graph of order $n$, $k=2$ and $\delta \geq 3$. If $|E(G)|\geq \binom{n-m-(3-m)(\delta+1)}{2}+(3-m)\binom{\delta+1}{2}+4$, then $pc(G)\leq 2$, where $m$ takes the value $1$ if $\delta=3$ and $0$ if $\delta\geq4$.
\end{Conjecture}

\begin{rem}
 We suggest a related (stronger) work for the conjecture above. Huang et al \cite{Huang3} showed  if $G$ is a connected noncomplete graph of order $n\geq 9$ and minimum degree $\delta(G)\geq n/4$, then $pc(G)=2$.
\end{rem}

\section{Acknowledgements}

The research is supported by NSFC (No.11671296) and NSF of Fujian Province (2015J05017), SRF for ROCS, SEM and Fund Program for the Scientific Activities of Selected
Returned Overseas Professionals in Shanxi Province.

config: arxiv


TITLE: how to compute $E(X^4)$ when $X$ follow the normal law $N(0,1)$
QUESTION [6 upvotes]: Suppose $X$ follow the normal law $N(0,1)$
We have the density $f= \frac{1}{\sqrt{\sigma^2 2\pi}} e^{- \frac{(x-m)^2}{2\sigma^2}}$
We want to compute $E(X^4)$
We have by definition that $\displaystyle E(X^4) = \frac{1}{\sqrt{2\pi}} \int_\infty^\infty{e^{-x^2/2}} x^4\,dx $
But i dont know how to continue
Thank you for helping me

REPLY [5 votes]: If you know about the moment-generating function for the standard normal, which is $M_X(t) = e^{t^2/2}$, then you have $E(X^4) = M_X^{(4)}(0)$ (i. e. the fourth derivative of $M_X$ evaluated at 0.)  But by the usual series expansion you have
$$M_X(t) = 1 + {t^2 \over 2} + {1 \over 2!} \left( {t^2 \over 2} \right)^2  + \cdots $$
and so the $t^4$ term of that series is $1/8$; thus the fourth derivative is $4!/8 = 3$.


TITLE: rearrange f(x) for easier integration
QUESTION [0 upvotes]: given a probability density function:
$$f(x)=\frac{10}{(\pi)(1+(x+2)^2)(1+(x-2)^2}$$
I've been ask to find the cumulative distribution function, I have also been given a hint :
Show the integrand can be rearranged as:
$$f(x) = (\frac{1}{4\pi})(\frac{x+2}{(1+(x+2)^2)}+\frac{2}{(1+(x+2)^2)}-\frac{x-2}{(1+(x-2)^2)}+\frac{2}{(1+(x-2)^2)})$$
I'm unable to show the original function can be rearranged to give the function in the hint, I have attempted using partial fractions but could not get the rearranged fuction.

REPLY [0 votes]: Hint
If you have no idea you can always go backward:
\begin{align}
&\frac{x+2}{(1+(x+2)^2)}+\frac{2}{(1+(x+2)^2)}-\frac{x-2}{(1+(x-2)^2)}+\frac{2}{(1+(x-2)^2)}=\cdots\\
&\cdots=\frac{(4+x)(1+(x-2)^2)+(4-x)(1+(x+2)^2)}{(1+(x+2)^2)(1+(x-2)^2)}=\frac{40}{(1+(x+2)^2)(1+(x-2)^2)}
\end{align}
as:
$$(4+x)(1+(x-2)^2)+(4-x)(1+(x+2)^2)=40$$


TITLE: limit of sequence $U_{n}=\sum_{j=1}^{n}\frac{an+1}{cn^{k}+j}$
QUESTION [1 upvotes]: How to find the limit of sequences of this general form:
$$
U_{n}=\sum_{j=1}^{n}\frac{an+1}{cn^{k}+j}
$$
$$
k\in\Bbb{N}-\{0, 1\}
$$
$$
(a, b)\in\Bbb{R}^{+}_*\times\Bbb{R}^{+}_*
$$

REPLY [1 votes]: Assuming $a,c >0$, the function $\displaystyle f_n(x) = \frac{an+1}{cn^k+x}$ is decreasing in $[0, \infty)$, so
\begin{equation}
U_n \leq \int_0^n \frac{an+1}{cn^k+x} \mathrm{d}x
\end{equation}
and
\begin{equation}
\lim_{n\to \infty} U_n \leq \lim_{n \to \infty} (an+1)\log\left(1+\frac{1}{cn^{k-1}}\right)
\end{equation}
So for $k>2$ we have that $U_n \to 0$ if $n \to \infty$. If $k=2$ we get the upper bound of $a/c$. Now use the fact that
\begin{equation}
U_n \geq \int_1^{n+1} f_n(x) \mathrm{d}x
\end{equation}
to conclude that the limit is equal to $a/c$ if $k=2$.


TITLE: Closed form for this incomplete gamma series?
QUESTION [2 upvotes]: The series I'm working with is
$$\sum_{k=0}^\infty \binom{z}{k}(-1)^k ( 1-\frac{\Gamma(k,-\log n)}{\Gamma(k)} )$$
with $z$ a complex variable and $\Gamma(k, -\log n)$ the upper incomplete gamma function.
Can this be expressed in a closed form (possibly involving special functions)?

As a bit of extra information, I already have a proof of the special case
$$\lim_{z \rightarrow 0}z^{-1}(-1+\sum_{k=0}^\infty \binom{z}{k}(-1)^k ( 1-\frac{\Gamma(k,-\log n))}{\Gamma(k)} ) = -\Gamma(0,-\log n)-\pi i -\log\log n - \gamma$$
and it seems empirically that for $z=-1$, the sum reduces to $1-\log n$.

REPLY [1 votes]: Alright, an answer, though without a rigorous proof. If anyone can fill in the details here, I'd be happy to accept their answer.
With a bit of manipulation in Mathematica, I ended up with the very tidy:
$$\sum_{k=0}^\infty \binom{z}{k}(-1)^k( 1 - \frac{\Gamma(k,-\log n)}{\Gamma(k)}) = L_{-z}(\log n),$$
where $L_z(n)$ is the Laguerre Polynomials (Mathworld link).
To end up here, I used an identity J.M. had shown in an answer to a previous question of mine (this one):
$$(-1)^k( 1 - \frac{\Gamma(k,-\log n)}{\Gamma(k)}) = \frac{(-1)^{k+1}}{\Gamma(k)}\int_{-\log n}^0 t^{k-1}e^{-t} dt$$
and then I swapped the order of the sum and the integral, and Mathematica immediately recognized the resulting terms as the Laguerre Polynomials.
Anyway, I know now from a bunch of tests that my sum does indeed seem to equal $L_{-z}(\log n).$  Can this be shown more tidily?


TITLE: The probability that the party $2$ will be in power after the next two elections,given that the party $1$ is in power,is
QUESTION [0 upvotes]: There are three main political parties namely $1,2,3$.If $p_{ij}$denote the probability that the party $j$ wins the general elections contested when party $i$ is in the power.The probability that the party $2$ will be in power after the next two elections,given that the party $1$ is in power,is
$(A)0.27\hspace{1cm}(B)0.24\hspace{1cm}(C)0.14\hspace{1cm}(D)0.06$
$p_{11}=0.7,p_{12}=0.2,p_{13}=0.1,p_{21}=0.5,p_{22}=0.3,p_{23}=0.2,p_{31}=0.3,p_{32}=0.4,p_{33}=0.3$
I suspect,Bayes should be applied here.But since this is asking probability after next two elections,i am confused how to handle this question.Please help me.

REPLY [3 votes]: Answer B is correct
If we assume that the chance winning the actual election depend only on the actual party in power and not on the previous results of elections then
we are talking about a Markov chain with the following state transition matrix:
$$
\mathbb P=\begin{bmatrix}
p_{11}&p_{12}&p_{13}\\
p_{21}&p_{22}&p_{23}\\
p_{31}&p_{32}&p_{33}
\end{bmatrix}
=\begin{bmatrix}
0.7&0.2&0.1\\
0.5&0.3&0.2\\
0.3&0.4&0.3
\end{bmatrix}.$$
Here $$p_{ij}=P(\text{ party } j \text{ wins } \mid \text{ party } i \text{ in power}).$$
If we don't assume this independence from the past then the problem cannot be solved based on the data given.
The state transition probabilities considering two elections is $\mathbb P^2$.
$$\mathbb P^2
=\begin{bmatrix}
0.7&0.2&0.1\\
0.5&0.3&0.2\\
0.3&0.4&0.3
\end{bmatrix}^2
=
\begin{bmatrix}
0.62&\color{red}{0.24}&0.14\\
0.56&0.27&0.17\\
0.5&0.3&0.2
\end{bmatrix}
.$$
The second element of the first row ($0.24$ / answer B) tells the probability that party $2$ will be in power after the second election from now assuming that party $1$ is in power today.

Elementary solution
Let $P_0^i, P_1^i, P_2^i$ denote that party $i$ is in power today, after the next election, and after the second election from now, respectively.
The question is the value of the following conditional probability:
$$P(P_2^2\mid P_0^1)=\frac{P(P_2^2\cap P_0^1)}{P(P_0^1)} \tag 1.$$
Obviously
$$P(P_2^2\cap P_0^1)=P(P_2^2\cap P_1^1\cap P_0^1)+P(P_2^2\cap P_1^2\cap P_0^1)+P(P_2^2\cap P_1^3\cap P_0^1)=$$
$$P(P_2^2\mid P_1^1\cap P_0^1)P(P_1^1\cap P_0^1)+P(P_2^2\mid P_1^2\cap P_0^1)P(P_1^2\cap P_0^1)+P(P_2^2\mid P_1^3\cap P_0^1)P(P_1^3\cap P_0^1)=$$
$$=P(P_2^2\mid P_1^1)P(P_1^1\cap P_0^1)+P(P_2^2\mid P_1^2)P(P_1^2\cap P_0^1)+P(P_2^2\mid P_1^3)P(P_1^3\cap P_0^1)=$$
$$=P(P_2^2\mid P_1^1)P(P_1^1\mid P_0^1)P(P_0^1)+P(P_2^2\mid P_1^2)P(P_1^1\mid P_0^1)P(P_0^1)+P(P_2^2\mid P_1^3)P(P_1^3\mid P_0^1)P(P_0^1).$$
We used the fact the the result of the election depends only on the current government (and perhaps on the abilities of the competing parties).
$P(P_0^1)$ cancels out in $(1)$, so we have now
$$P(P_2^2\mid P_0^1)=$$
$$=P(P_2^2\mid P_1^1)P(P_1^1\mid P_0^1)+P(P_2^2\mid P_1^2)P(P_1^1\mid P_0^1)+P(P_2^2\mid P_1^3)P(P_1^3\mid P_0^1)=$$
$$=p_{12}p_{11}+p_{22}p_{12}+p_{32}p_{13}=$$
$$=0.2\cdot0.7+0.3\cdot0.2+0.4\cdot0.1=\color{red}{0.24}.$$