text:
\begin{document}
	\title{When is the Achievable Rate Region Convex in Two-User Massive MIMO Systems?}
\author{Zheng~Chen, Emil~Bj\"{o}rnson, and~Erik~G.~Larsson
	\thanks{Z.~Chen, E.~Bj\"{o}rnson, and E.~G.~Larsson are with the Department of Electrical Engineering (ISY), Link\"{o}ping University,  58183 Link\"{o}ping, Sweden (email: \{zheng.chen, emil.bjornson, erik.g.larsson\}@liu.se).}
	\thanks{This work was supported in part by ELLIIT, CENIIT, and the Swedish Foundation for Strategic Research (SSF).} \vspace{-6mm}}
\maketitle

\begin{abstract}
This letter investigates the achievable rate region in Massive multiple-input-multiple-output (MIMO) systems with two users, with focus on the i.i.d.~Rayleigh fading and line-of-sight (LoS) scenarios. If the rate region is convex, spatial multiplexing is preferable to orthogonal scheduling, while the opposite is true for non-convex regions. We prove that the uplink and downlink rate regions with i.i.d.~Rayleigh fading are convex, while the convexity in LoS depends on  parameters such as angular user separation, number of antennas, and signal-to-noise ratio (SNR).
\end{abstract}
\vspace{-0.5cm}
\begin{keywords}
Rate region, convexity, Massive MIMO.
\end{keywords}

\vspace{-0.3cm}
\section{Introduction}

The achievable rate region of a multi-user multiple-input multiple-output (MIMO) system can be non-convex when using suboptimal transmission schemes that treat interference as noise or utilize imperfect channel state information (CSI) \cite{caire-achievable-mimo, ergodic-mimo-broadcast,bjornson2013optimal}. Yet, the capacity region is always convex \cite{capacity-mimo-broadcast}, since the capacity-achieving scheme may implicitly use time-sharing (scheduling) to convexify a region by operating on a line between two achievable points. In practice, it is important to know if a scheme for broadcast or multiple access channels must be accompanied with scheduling to maximize the rates.

Massive MIMO refers to a multi-user MIMO system with  a very large number of service antennas and this approach is a key enabler for the next generation of wireless networks \cite{zhang-overview}. Despite the vast research on Massive MIMO, prior works have not explicitly targeted the convexity of the rate region.
The common practice in Massive MIMO is to serve all users by spatial multiplexing \cite{massivemimobook}, although that is only preferable when the rate region is convex. In contrast, when the rate region is non-convex, higher sum throughput can be achieved by scheduling some at a time. In the basic two-user case, scheduling can be implemented by TDMA/FDMA/OFDMA.

In this letter, we characterize the achievable rate region of two-user Massive MIMO systems to gain fundamental insights into the convexity properties. A general form of rate expressions is considered and the Pareto boundaries in uplink (UL) and downlink (DL) are derived. By defining the boundary curve by parametric equations of the power-control coefficients, we derive necessary and sufficient conditions for convexity. In two specific cases, namely i.i.d.~Rayleigh fading and line-of-sight (LoS) channels, the exact convexity conditions are derived, discussed, and illustrated numerically.

 Note that the analysis in this letter is not limited to Massive MIMO systems. It can also capture other general cases when a single-antenna transmitter intends to send different signals to two receivers, such as a broadcast channel.

\vspace{-0.2cm}
\section{Two-user Rate Region in Massive MIMO}
\label{sec:general_downlink}
Consider a Massive MIMO system where a base station (BS) equipped with $M$ antennas serves two users. The achievable rates can be written in the general form
\vspace{-0.1cm}
\begin{equation}
R_1=\log_2\left(1+\frac{\alpha_1\eta_1}{\mu_{1,1} \eta_1+\mu_{1,2} \eta_2+1}\right),\label{rate_1}
\end{equation}
\begin{equation}
R_2=\log_2\left(1+\frac{\alpha_2 \eta_2}{\mu_{2,1} \eta_1+\mu_{2,2} \eta_2+1}\right), \label{rate_2}
\end{equation}
where $\eta_k$ is the power-control coefficient and $\alpha_k\geq0$ is the effective channel gain of user $k$, for $k=1,2$. The noise power is normalized to 1, $\mu_{1,1}\geq0$ and $\mu_{2,2}\geq0$ are the self-interference coefficients caused by having imperfect CSI, and $\mu_{1,2}\geq0$ and $\mu_{2,1}\geq0$ are the inter-user interference coefficients.
Note that $\eta_1$ and $\eta_2$ are design variables.
In the DL, the power constraint at the BS is $0\!\leq\! \eta_{1}+\eta_{2}\!\leq \!1$. In the UL, the power constraints of the two users are $0\leq\eta_1\leq 1$ and $0\leq\eta_2\leq1$. We keep the coefficients arbitrary in this section, while specific expressions are given in Sections~\ref{ergodic} and \ref{LoS}.

Using a similar definition of the Pareto boundary as in \cite{capacity-region},
in the following lemma, we state the general interpretation of convexity of the achievable rate region.
\begin{lemma}
	\label{lemma-convexity}
		Denote by $R_{1,\textnormal{bd}}$ and $R_{2,\textnormal{bd}}$ the achievable rates of user $1$ and user $2$ at the Pareto boundary. Both $R_{1,\textnormal{bd}}$ and $R_{2,\textnormal{bd}}$ are functions of the power-control coefficients $\eta_{1}$ and $\eta_{2}$. The achievable rate region is convex, if and only if $R_{1,\textnormal{bd}}$ is a concave function of $R_{2,\textnormal{bd}}$ for $R_{2,\textnormal{bd}}\in[0, R_{2,\max}]$, where $R_{2,\max}$ is the maximum rate of user $2$.
		If $R_{1,\textnormal{bd}}(R_{2,\textnormal{bd}})$  is continuous and twice differentiable for $R_{2,\textnormal{bd}}\in[0, R_{2,\max}]$, then $R_{1,\textnormal{bd}}(R_{2,\textnormal{bd}})$ is a concave function if and only if $\frac{d^2 R_{1,\textnormal{bd}}}{d R_{2,\textnormal{bd}}^2} \leq 0$.
\end{lemma}

\vspace{-0.4cm}
\subsection{Convexity of the DL Rate Region}
In the DL, the rates in \eqref{rate_1} and \eqref{rate_2} can be further simplified if we only consider the rates at the Pareto boundary.
\begin{fact}
	At the Pareto boundary $R_{1,\textnormal{bd}}(R_{2,\textnormal{bd}})$ of the DL rate region, we have $\eta_1+\eta_2=1$, $\eta_{1}\in[0,1]$ \cite[Theorem~1.9]{bjornson2013optimal}.
\end{fact}
\vspace{-0.1cm}
Based on this fact, the user rates at the Pareto boundary can be given as functions of a single variable $\eta_1$:
\vspace{-0.1cm}
\begin{align}
R_{1,\textnormal{bd}}(\eta_{1})&=\log_2\left(1+\frac{\alpha_1\eta_1}{(\mu_{1,1}-\mu_{1,2}) \eta_1+\mu_{1,2}+1}\right), \label{eq:rate1_general}\\
R_{2,\textnormal{bd}}(\eta_{1})&=\log_2\left(1+\frac{\alpha_2 (1-\eta_1)}{(\mu_{2,1} -\mu_{2,2} )\eta_1+\mu_{2,2}+1}\right). \label{eq:rate2_general}
\end{align}
Both $R_{1,\textnormal{bd}}$ and $R_{2,\textnormal{bd}}$ are continuous and twice-differentiable functions of $\eta_1$. The second-order derivative $\frac{d^2 R_{1,\textnormal{bd}}}{d R_{2,\textnormal{bd}}^2}$ is obtained by utilizing following fact.
\begin{fact}
	\label{def:chain_rule}
	Consider a two-dimensional curve with coordinates $(x,y)$ defined parametrically as $x=g(u)$ and $y=f(u)$, where $g$ and $f$ are continuous and twice-differentiable functions of $u$. The first-order derivative of $y$ with respect to $x$ is
		\vspace{-0.1cm}
	\begin{equation}
	\frac{d y}{d x}\mathop{=}\limits^{(a)}\frac{d y}{d u}\frac{d u}{d x}\mathop{=}\limits^{(b)}\frac{\frac{d y}{d u}}{\frac{d x}{d u}}=\frac{ f'(u)}{g'(u)},
	\label{eq:chain-rule-one}
		\vspace{-0.1cm}
	\end{equation}
	where $(a)$ is the chain rule in Leibniz's notation and $(b)$ follows from the inverse function rule.
	The second-order derivative of $y$ with respect to $x$ is
		\vspace{-0.2cm}
	\begin{align}
	\frac{d^2 y}{d x^2}&=\frac{d}{d u}\left(\frac{d y}{d x}\right)\cdot \frac{d u}{d x} = \frac{d \left(\frac{ f'(u)}{g'(u)}\right)}{d u}\cdot \frac{1}{g'(u)}   \nonumber \\
	&=\frac{f''(u)g'(u)-f'(u)g''(u)}{\left(g'(u)\right)^3}.
	\label{eq:chain-rule-second}
	\vspace{-0.3cm}
	\end{align}
	Note that $\frac{d^2 y}{d x^2}$ is obtained as a function of $u$.
\end{fact}

From \eqref{eq:rate1_general} and \eqref{eq:rate2_general}, using Lemma~\ref{lemma-convexity}, it is straightforward to obtain an exact convexity condition, but the expression is large and depends on six coefficients, thus it provides little insights.\footnote{The interested reader can find the exact condition in the supplementary document provided along with this paper.} However, for specific values of $\alpha_1, \alpha_2$ and $\mu_{1,1}, \mu_{1,2}, \mu_{2,1}, \mu_{2,2}$, that expression can be used to validate if $\frac{d^2 R_{1,\textnormal{bd}}}{d R_{2,\textnormal{bd}}^2} \leq 0$.

\begin{figure}[ht!]
	\vspace{-0.3cm}
	\centering
	\includegraphics[trim={1cm 2.5cm  1cm 3.2cm},clip, width=1.0\columnwidth]{rate_region_dl_ul.pdf}
	\vspace{-0.8cm}
	\caption{DL and UL Pareto boundaries with $\alpha_1=5$, $\alpha_2=10$, $\mu_{1,1}=\mu_{2,2}=1$. (a): The DL rate region is convex (marked with crosses) with $\mu_{1,2}=\mu_{2,1}=1$, and non-convex (marked with stars) with $\mu_{1,2}\!=\!\mu_{2,1}\!=\!10$; (b) The UL rate region is convex with $\mu_{1,2}\!=\!\mu_{2,1}\!=\!1$, and non-convex with $\mu_{1,2}\!=\!\mu_{2,1}\!=\!10$. }
	\label{fig:rate_downlink}
\end{figure}

Fig.~\ref{fig:rate_downlink}(a) shows examples of non-convex and convex DL rate regions. We see that when the inter-user interference coefficients are much larger than the self-interference coefficients, the achievable rate region has a non-convex shape.

\vspace{-0.3cm}
\subsection{Convexity of the UL Rate Region}

We now shift focus to the Pareto boundary in the UL.
\begin{fact}
	\label{fact:2}
	The Pareto boundary $R_{1,\textnormal{bd}}(R_{2,\textnormal{bd}})$ of the UL rate region consists of two segments: one with $\eta_1=1$ and any $\eta_2\in[0,1]$, the other one with $\eta_2=1$ and any $\eta_1\in[0,1]$.
\end{fact}
\begin{proof}
	For any $\eta_{1},\eta_{2}\in(0,1)$, by scaling both coefficients with $\delta>1$ such that either $\delta\eta_{1}=1$ or $\delta \eta_{2}=1$ is reached, a point at the Pareto boundary is achieved \cite[Theorem~1.9]{bjornson2013optimal}.
\end{proof}
At the first segment of the Pareto boundary with $\eta_1=1$, the rates can be simplified as functions of $\eta_2$:
\vspace{-0.15cm}
\begin{equation}
R_{1,\textnormal{bd1}}(\eta_{2})=\log_2\left(1+\frac{\alpha_1}{\mu_{1,2} \eta_2+\mu_{1,1} +1}\right),
\end{equation}
\vspace{-0.3cm}
\begin{equation}
R_{2,\textnormal{bd1}}(\eta_{2})=\log_2\left(1+\frac{\alpha_2 \eta_2}{\mu_{2,2} \eta_2+\mu_{2,1} +1}\right).
\end{equation}
Similarly, the second segment of the Pareto boundary is with $\eta_2=1$ and we can write the rates as functions of $\eta_1$:
\vspace{-0.15cm}
\begin{eqnarray}
R_{1,\textnormal{bd2}}(\eta_{1})&=&\log_2\left(1+\frac{\alpha_1\eta_1}{\mu_{1,1} \eta_1+\mu_{1,2} +1}\right),\\
R_{2,\textnormal{bd2}}(\eta_{1})&=&\log_2\left(1+\frac{\alpha_2 }{\mu_{2,1} \eta_1+\mu_{2,2} +1}\right).
\end{eqnarray}

Similar to the DL,  $R_{1,\textnormal{bd1}}(R_{2,\textnormal{bd1}})$ and $R_{1,\textnormal{bd2}}(R_{2,\textnormal{bd2}})$ need to be concave functions if the rate region is convex.
An additional condition at the interconnecting point of two segments of the boundary curve must also be satisfied.

\begin{lemma}
The two-user UL achievable rate region is convex if and only if (1) $\frac{d^2 R_{1,\textnormal{bd1}}}{d R_{2,\textnormal{bd1}}^2} \leq 0$; and (2) $\frac{d^2 R_{1,\textnormal{bd2}}}{d R_{2,\textnormal{bd2}}^2} \leq 0$; and (3) $\frac{R'_{1,\textnormal{bd1}}(\eta_{2})}{R'_{2,\textnormal{bd1}}(\eta_{2})}\Bigm|_{\eta_{2}=1}\geq \frac{R'_{1,\textnormal{bd2}}(\eta_{1})}{R'_{2,\textnormal{bd2}}(\eta_{1})}\Bigm|_{\eta_{1}=1}$.
\label{lemma-ul}
\end{lemma}
\begin{proof}
	The first two conditions follow directly from Lemma~\ref{lemma-convexity}. Since the Pareto boundary consists of two segments, at the interconnecting point with $\eta_{1}=\eta_{2}=1$, the boundary curve is not twice-differentiable. Thus, $\frac{d R_{1,\text{bd1}}}{d R_{2,\text{bd1}}}\Bigm|_{\eta_{2}=1}\geq\frac{d R_{1,\text{bd2}}}{d R_{2,\text{bd2}}}\Bigm|_{\eta_{1}=1}$ must be satisfied to assure the convexity of the region. From \eqref{eq:chain-rule-one}, we obtain the third condition in Lemma~\ref{lemma-ul}.
\end{proof}
\vspace{-0.1cm}
In Fig.~\ref{fig:rate_downlink}(b), we show examples of non-convex and convex UL rate regions.
We see that the UL Pareto boundary consists of two segments: $\small{\textsf{bd1}}$ with $\eta_1=1$ and $\small{\textsf{bd2}}$ with $\eta_2=1$. The combination of these segments completes the Pareto boundary.

\vspace{-0.2cm}
\section{Massive MIMO with i.i.d.~Rayleigh fading}
\label{ergodic}
As shown above, the convexity of the achievable rate region is strongly affected by the relations between the coefficients in the rate expressions. In this section, we analyze the rate region convexity for a Massive MIMO system with ergodic  i.i.d.~Rayleigh fading channels and single-antenna users.
\vspace{-0.2cm}
\subsection{Convexity of the DL Rate Region}
Denote by $\rho_{\textnormal{dl}}$ the total DL transmit power.
When using maximum ratio (MR) precoding based on imperfect channel knowledge as in \cite[Ch.~3]{marzetta2016fundamentals}, we have that a DL ergodic rate of user $k$ is  $R_k=\log_2\bigg(1+\frac{M\rho_{\textnormal{dl}} \gamma_k \eta_k}{1+\beta_k\rho_{\textnormal{dl}}(\eta_{1}+\eta_{2})}\bigg)$,
where $\eta_k$ is the power-control coefficient of user $k=1,2$ with $\eta_{1}+\eta_{2}\leq1$, $\beta_k$ is the channel gain of user $k$, and $\gamma_k$ is the mean square of the channel estimate.\footnote{With zero-forcing (ZF) precoding, the rate expressions are different but the same approach can be taken and the conclusions are the same.}

In terms of the general form in \eqref{rate_1} and \eqref{rate_2}, we have $\alpha_1=M\rho_{\textnormal{dl}} \gamma_1$, $\alpha_2=M\rho_{\textnormal{dl}} \gamma_2$, $\mu_{1,1}=\mu_{1,2}=\beta_1\rho_{\textnormal{dl}}$ and $\mu_{2,1}=\mu_{2,2}=\beta_2\rho_{\textnormal{dl}}$.
At the Pareto boundary, since $\eta_1+\eta_2=1$, we rewrite the ergodic achievable rates $R_{1,\textnormal{bd}}$ and $R_{2,\textnormal{bd}}$ as functions of $\eta_1$:
\vspace{-0.15cm}
\begin{equation}
R_{1,\textnormal{bd}}\!=\!\log_2\!\left(1+\frac{\alpha_1 \eta_1}{1+\mu_{1,1}}\right)\!, \,\,
R_{2,\textnormal{bd}}\!=\!\log_2\!\left(1+\frac{\alpha_2 (1-\eta_1)}{1+\mu_{2,2}}\right).
\end{equation}
Defining $\zeta = \frac{1}{\ln(2)}$, the first- and second-order derivatives are
\vspace{-0.1cm}
\begin{equation}
R'_{1,\textnormal{bd}}(\eta_1)=\frac{\zeta \alpha_1 }{1+\mu_{1,1}+\alpha_1 \eta_1}>0,
\vspace{-0.25cm}
\end{equation}
\begin{align}
R'_{2,\textnormal{bd}}(\eta_1)&=-\frac{\zeta \alpha_2}{1+\mu_{2,2}+\alpha_2-\alpha_2\eta_1}<0,\\
\vspace{-0.2cm}
R''_{1,\textnormal{bd}}(\eta_1)&=-\frac{\zeta \alpha_1^2}{(1+\mu_{1,1}+\alpha_1 \eta_1)^2}<0,  \\
\vspace{-0.2cm}
R''_{2,\textnormal{bd}}(\eta_1)&=-\frac{\zeta \alpha_2^2}{(1+\mu_{2,2}+\alpha_2-\alpha_2\eta_1)^2}<0.
\vspace{-0.2cm}
\end{align}
Then, using Lemma \ref{def:chain_rule}, it follows that
\vspace{-0.1cm}
\begin{equation}
\frac{d^2 R_{1,\textnormal{bd}} }{d R_{2,\textnormal{bd}}^2}=\frac{R''_{1,\textnormal{bd}}(\eta_1)R'_{2,\textnormal{bd}}(\eta_1)-R''_{2,\textnormal{bd}}(\eta_1)R'_{1,\textnormal{bd}}(\eta_1)}{\big(R'_{2,\textnormal{bd}}(\eta_1)\big)^3}<0.
\vspace{-0.15cm}
\end{equation}
This means that $R_{1,\textnormal{bd}}$ is a strictly concave function of $R_{2,\textnormal{bd}}$. From Lemma~\ref{lemma-convexity}, the achievable rate region is always convex.

\vspace{-0.2cm}
\subsection{Convexity of the UL Rate Region}
When using MR combining, an UL ergodic rate of user $k$ is $R_k=\log_2\bigg(1+\frac{M \rho_{\textnormal{ul}} \gamma_k \eta_k}{1+\sum_{k=1}^{2} \beta_k\rho_{\textnormal{ul}}\eta_{k}}\bigg)$ \cite[Ch.~3]{marzetta2016fundamentals}.
In terms of the general form in \eqref{rate_1} and \eqref{rate_2}, we have $\alpha_1=M\rho_{\textnormal{ul}}\gamma_1$, $\alpha_2=M\rho_{\textnormal{ul}}\gamma_2$, $\mu_{1,1}=\mu_{2,1}=\beta_1\rho_{\textnormal{ul}}$ and $\mu_{1,2}=\mu_{2,2}=\beta_2\rho_{\textnormal{ul}}$.
For the  Pareto boundary segment with $\eta_1=1$, we obtain
\begin{eqnarray}
\vspace{-0.2cm}
R_{1,\textnormal{bd1}}&=&\log_2\left(1+\frac{\alpha_1 }{\mu_{1,1}+\mu_{1,2}\eta_{2}+1 }\right), \\
R_{2,\textnormal{bd1}}&=&\log_2\left(1+\frac{\alpha_2\eta_{2} }{\mu_{1,1} +\mu_{1,2}\eta_{2} +1}\right).
\vspace{-0.2cm}
\end{eqnarray}
The first- and second-order derivatives of $R_{1,\textnormal{bd1}}$ and $R_{2,\textnormal{bd1}}$ are
\begin{equation}
\vspace{-0.15cm}
R'_{1,\textnormal{bd1}}(\eta_2)=-\frac{\zeta\alpha_1\mu_{1,2}}{\left(1+\mu_{1,1}+\mu_{1,2}\eta_{2}\right)\left(1+\mu_{1,1}+\alpha_1+\mu_{1,2} \eta_1\right)},
\end{equation}
\vspace{-0.3cm}
\begin{equation}
R'_{2,\textnormal{bd1}}(\eta_2)=\frac{\zeta\alpha_2 (\mu_{1,1}+1)}{\left(1+\mu_{1,1} +\mu_{1,2}\eta_{2} \right)\left(1+\mu_{1,1}+(\alpha_2+\mu_{1,2})\eta_2\right)},
\end{equation}
\vspace{-0.3cm}
\begin{equation}
R''_{1,\textnormal{bd1}}(\eta_2)=\frac{\zeta \alpha_1 \mu_{1,2}^2\left[\alpha_1+2(1+\mu_{1,1}+\mu_{1,2}\eta_{2})\right]}{\left(1+\mu_{1,1}+\mu_{1,2}\eta_{2}\right)^2\left(1+\mu_{1,1}+\alpha_1+\mu_{1,2} \eta_2\right)^2},
\end{equation}
\vspace{-0.3cm}
\begin{equation}
\begin{split}
&R''_{2,\textnormal{bd1}}(\eta_2)\!=\\&\!-\frac{\zeta\alpha_2 (\mu_{1,1}\!+\!1)\!\left[(1+\mu_{1,1})(2\mu_{1,2}+\alpha_2)+2\mu_{1,2}\eta_{2}(\mu_{1,2}+\alpha_2)\right]}{\left(1+\mu_{1,1} +\mu_{1,2}\eta_{2} \right)^2\left(1+\mu_{1,1}+(\alpha_2+\mu_{1,2})\eta_2 \right)^2}.
\end{split}
\end{equation}
\vspace{-0.1cm}
Using \eqref{eq:chain-rule-second} in Lemma \ref{def:chain_rule}, we can show that
\begin{equation}
\begin{split} \label{eq:UL_derivation_iid}
\frac{d^2 R_{1,\textnormal{bd1}}}{d R_{2,\textnormal{bd1}}^2}=&\frac{R''_{1,\textnormal{bd1}}(\eta_2)R'_{2,\textnormal{bd1}}(\eta_2)-R''_{2,\textnormal{bd1}}(\eta_2)R'_{1,\textnormal{bd1}}(\eta_2)}{\big(R'_{2,\textnormal{bd1}}(\eta_2)\big)^3}\\
=&-\frac{\alpha_1\mu_{1,2}\left[\alpha_2(1+\alpha_1+\mu_{1,1})+\alpha_1\mu_{1,2}\right]}{\zeta\alpha_2^2(1+\mu_{1,1})^2(1+\alpha_1+\mu_{1,1}+\mu_{1,2}\eta_{2})^2}\\
&\cdot (1\!+\!\mu_{1,1}\!+\!\mu_{1,2}\eta_{2})(1\!+\!\mu_{1,1}\!+\!\alpha_2\eta_{2}\!+\!\mu_{1,2}\eta_{2})\\
<&0,
\end{split}
\vspace{-0.5cm}
\end{equation}
where the intermediate steps are omitted due to lack of space.\footnote{The Mathematica scripts used by the authors to generate the results are included as supplementary documents to this paper.}
From \eqref{eq:UL_derivation_iid} it follows that
the function $R_{1,\textnormal{bd1}}(R_{2,\textnormal{bd1}})$ is always concave. Analogously, we can prove that at the second segment of the Pareto boundary with $\eta_2=1$,
 $R_{1,\textnormal{bd2}}(R_{2,\textnormal{bd2}})$ is also concave.
At the interconnecting point of the two segments,
in order to have $\frac{R'_{1,\textnormal{bd1}}(\eta_{2})}{R'_{2,\textnormal{bd1}}(\eta_{2})}\Bigm|_{\eta_{2}=1}\geq \frac{R'_{1,\textnormal{bd2}}(\eta_{1})}{R'_{2,\textnormal{bd2}}(\eta_{1})}\Bigm|_{\eta_{1}=1}$, after lengthy derivations, we obtain $
\frac{\mu_{1,2}}{1+\mu_{1,1}}\leq \frac{1+\mu_{1,2}}{\mu_{1,1}}$,
which always holds. Thus, all the convexity conditions in Lemma~\ref{lemma-ul} are satisfied, which means that the rate region is always convex.
\vspace{-0.2cm}
\begin{propi}
	\label{propo1}
 In a two-user Massive MIMO system with ergodic i.i.d.~Rayleigh fading channels and single-antenna users, both the UL and the DL rate regions are convex.
\end{propi}

\vspace{-0.3cm}
\section{Massive MIMO with LoS Propagation}
\label{LoS}
In Massive MIMO with LoS propagation, the channel is deterministic and can be estimated with a negligible overhead. We thus consider perfect CSI and no self-interference terms.
\vspace{-0.4cm}
\subsection{Convexity of the DL Rate Region}
We consider a BS equipped with a uniform linear array with $d_{\textnormal{H}}\leq1/2$ as antenna spacing (in wavelengths). Denote by $\theta_1$ and $\theta_2$ the angles of the two users as seen from the BS,
the achievable DL rates with MR precoding are
$R_{k}\!=\!\log_2\!\left(\!1+\!\frac{M\rho_{\textnormal{dl}}\beta_k\eta_k}{1+g(\theta_k, \theta_j)\rho_{\textnormal{dl}}\beta_k\eta_j}\right)$ for $k,j=\{1,2\}$, $j\neq k$ \cite{massivemimobook}, where
\begin{equation}
 g(\theta_k, \theta_j)=\begin{cases}
\frac{\sin^2\left[\pi d_{\textnormal{H}}M(\sin(\theta_k)-\sin(\theta_j))\right]}{M\sin^2\left[\pi d_{\textnormal{H}}(\sin(\theta_k)-\sin(\theta_j))\right]} &\text{if}~\sin(\theta_k)\neq\sin(\theta_j)\\
M & \text{if}~\sin(\theta_k)=\sin(\theta_j).
\end{cases}
\label{eq:gtheta}
\end{equation}
At the Pareto boundary, we have
\begin{equation}
R_{1,\textnormal{bd}}\!=\!\log_2\!\left(\!1+\!\frac{\alpha_1\eta_1}{1\!+\!\mu_{1,2}(1\!-\!\eta_{1})}\right),\,\, R_{2,\textnormal{bd}}\!=\!\log_2\!\left(\!1+\!\frac{\alpha_2(1-\eta_1)}{1\!+\!\mu_{2,1}\eta_{1}}\right)\!,\\
\end{equation}
where $\alpha_1=M\rho_{\textnormal{dl}}\beta_1$, $\alpha_2=M\rho_{\textnormal{dl}}\beta_2$, $\mu_{1,2}=g(\theta_1, \theta_2)\rho_{\textnormal{dl}}\beta_1$, $\mu_{2,1}=g(\theta_1, \theta_2)\rho_{\textnormal{dl}}\beta_2$.
From Lemma~\ref{lemma-convexity}, by calculating the second-order derivative, it is obvious that $\frac{d^2 R_{1,\textnormal{bd}} }{d R_{2,\textnormal{bd}}^2}$ is not always non-positive, thus the rate region is not always convex, but it depends on the specific values of $\beta_1$, $\beta_2$, $M$, and  $\rho_{\textnormal{dl}}$.

Consider the special case with $\beta_1=\beta_2$, where $\alpha_1=\alpha_2$ and $\mu_{1,2}=\mu_{2,1}$. The second derivative $\frac{d^2 R_{1,\textnormal{bd}} }{d R_{2,\textnormal{bd}}^2}$ can be simplified and it is non-positive for any $\eta_{1}\in[0,1]$ if and only if
\begin{equation}
\alpha_1\geq \mu_{1,2}(2+\mu_{1,2}).
\end{equation}
For equal per-antenna SNR, $\mathsf{SNR}\!=\!\rho_{\textnormal{dl}}\beta_1\!=\!\rho_{\textnormal{dl}}\beta_2$,  setting $\alpha_1=M \mathsf{SNR}$ and $\mu_{1,2}=g(\theta_1, \theta_2) \mathsf{SNR}$ gives the convexity condition
\begin{equation}
g(\theta_1,\theta_2)\leq\frac{\sqrt{M\cdot \mathsf{SNR}+1}-1}{\mathsf{SNR}}.
\label{eq:mimi-los-dl}
\end{equation}

Defining the threshold $g^*=\frac{\sqrt{M\cdot \mathsf{SNR}+1}-1}{\mathsf{SNR}}$, for a given pair of $(\theta_1, \theta_2)$, if $g(\theta_1,\theta_2)$ falls above this threshold, the DL achievable rate region is non-convex.
Thus, for a given SNR, there are certain ranges of angular separation between the two users that leads to a non-convex rate region.
\begin{figure}[ht]
	\vspace{-0.3cm}
	\centering
	\includegraphics[trim={0cm 0cm  0.5cm 0.2cm},clip, width=0.95\columnwidth]{Fig2_fraction_vs_SNR}
		\vspace{-0.3cm}
	\caption{Percentage of angles with non-convex rate region when fixing $\theta_1=0$ and varying $\theta_2\in[0, 90\degree]$. $\mathsf{SNR}=\rho_{\textnormal{dl}}\beta_1=\rho_{\textnormal{dl}}\beta_2$. $d_{\textnormal{H}}=0.5$ wavelength.}
	\label{fig:LoS-g-vs-SNR}
\end{figure}

\begin{figure}[ht]
	\vspace{-0.1cm}
	\centering
	\includegraphics[trim={0cm 0cm  0.5cm 0.5cm},clip, width=0.95\columnwidth]{Fig3_scheduling_gain}
	\vspace{-0.3cm}
	\caption{Sum rate comparison with $M=100$, same parameters as in Fig.~\ref{fig:LoS-g-vs-SNR}.}
	\label{fig:scheduling-gain}
	\vspace{-0.4cm}
\end{figure}

In Fig.~\ref{fig:LoS-g-vs-SNR}, we fix $\theta_1=0\degree$ and present the percentage of angles $\theta_2\in[0, 90\degree]$ resulting in non-convex rate regions for different SNR values.
From \eqref{eq:gtheta}, we know that $g(\theta_1,\theta_2)$ does not decrease monotonically with $|\theta_1-\theta_2|$, but it fluctuates when $|\theta_1-\theta_2|$ increases. The green part of the curves means that there is more than one interval of angles that gives non-convex rate regions.
In the low SNR regime, the fraction of angles with non-convex rate region reduces as $1/M$, since the array aperture increases with $M$ (this happens for any $d_{\textnormal{H}}$). In particular, note that $g^*\rightarrow M/2$ when $\mathsf{SNR}\rightarrow 0$ and $g(\theta_1,\theta_2)$ decreases almost linearly with $M$ when $|\theta_1-\theta_2|$ is small.

It is shown in \cite[Ch.~7]{marzetta2016fundamentals} that Massive MIMO with LoS offers nearly favorable propagation, but the channel can become unfavorable if $|\sin(\theta_1)-\sin(\theta_2)|\leq 1/M$. Our observation is that when $|\sin(\theta_1)-\sin(\theta_2)|$ is very small, the rate region becomes non-convex. Both observations suggest that in LoS, we should schedule users with very similar angles orthogonally (e.g., using TDMA, FDMA, or OFDMA). For example, Fig.~\ref{fig:scheduling-gain} shows the sum rate obtained with spatial multiplexing and orthogonal equal-resource scheduling for different $|\theta_1-\theta_2|$. In the extreme case of $\theta_1\simeq\theta_2$, the scheduling gain is $480\%$ when $\text{SNR}=15$\,dB, while for many other angles, spatial multiplexing gives 80\% higher sum rate.
\vspace{-0.3cm}
\subsection{Convexity of the UL Rate Region}
The achievable UL rates with MR combining are given by
$R_{k}\!=\!\log_2\!\left(\!1+\!\frac{M\rho_{\textnormal{ul}}\beta_k\eta_k}{1+g(\theta_k, \theta_j)\rho_{\textnormal{ul}}\beta_j\eta_j}\right)$ for $k,j=\{1,2\}$ and $j\neq k$ \cite{massivemimobook}.
At the first boundary segment with $\eta_{1}=1$, we have
\vspace{-0.1cm}
\begin{equation}
R_{1,\textnormal{bd1}}\!=\!\log_2\!\left(\!1+\!\frac{\alpha_1}{1+\mu_{1,2}\eta_{2}}\right),\,\, R_{2,\textnormal{bd1}}\!=\!\log_2\!\left(\!1+\!\frac{\alpha_2\eta_2}{1+\mu_{2,1}}\right),\\
\end{equation}
where $\alpha_1=M\rho_{\textnormal{ul}}\beta_1$, $\alpha_2=M\rho_{\textnormal{ul}}\beta_2$, $\mu_{1,2}=g(\theta_1, \theta_2)\rho_{\textnormal{ul}}\beta_2$, $\mu_{2,1}=g(\theta_1, \theta_2)\rho_{\textnormal{ul}}\beta_1$.
At the second segment of the boundary with $\eta_{2}=1$, we have
\vspace{-0.1cm}
\begin{equation}
R_{1,\textnormal{bd2}}\!=\!\log_2\!\left(\!1+\!\frac{\alpha_1\eta_{1}}{1+\mu_{1,2}}\right),\,\,R_{2,\textnormal{bd2}}\!=\!\log_2\!\left(\!1+\!\frac{\alpha_2}{1+\mu_{2,1}\eta_{1}}\right).\\
\end{equation}
The convexity conditions in Lemma~\ref{lemma-ul} are not always satisfied, thus the UL rate region is not always convex.

In the special case with $\beta_1=\beta_2$, we have $\alpha_1=\alpha_2$ and $\mu_{1,2}=\mu_{2,1}$.
From Lemma~\ref{def:chain_rule} and Lemma~\ref{lemma-ul}, in order to have $\frac{d^2 R_{1,\textnormal{bd1}}}{d R_{2,\textnormal{bd1}}^2} \leq 0$ for any $\eta_{2}\in[0,1]$, we obtain
\vspace{-0.2cm}
\begin{equation}
-\alpha_1^2+2\mu_{1,2}(1+\mu_{1,2})(1+\mu_{1,2}\eta_{2})+\alpha_1[-1+\mu_{1,2}+\mu_{1,2}^2(1+\eta_{2}^2)]\leq 0.
\label{eq:condition}
\end{equation}
The left-hand side of \eqref{eq:condition} is a quadratic function of $\eta_{2}$, which monotonically increases with $\eta_{2}$ within the range $0\leq \eta_{2}\leq 1$. Thus, its maximum value is reached at $\eta_{2}=1$. Plugging  $\eta_{2}=1$ into \eqref{eq:condition}, we have
\vspace{-0.2cm}
\begin{eqnarray}
&2\mu_{1,2}(1+\mu_{1,2})^2+\alpha_1(2\mu_{1,2}^2+\mu_{1,2}-1)-\alpha_1^2\leq 0 \nonumber\\
\Rightarrow& [\alpha_1-2\mu_{1,2}(1+\mu_{1,2})][\alpha_1+(1+\mu_{1,2})]\geq 0\nonumber\\
\Rightarrow& \alpha_1\geq 2\mu_{1,2}(1+\mu_{1,2}).
\end{eqnarray}
Plugging in $\alpha_1=M\cdot \mathsf{SNR}$ and $\mu_{1,2}=g(\theta_1, \theta_2)\cdot \mathsf{SNR}$ with $\mathsf{SNR}=\rho_{\textnormal{ul}}\beta_1=\rho_{\textnormal{ul}}\beta_2$, we obtain
\begin{equation}
\vspace{-0.2cm}
g(\theta_1, \theta_2)\leq \frac{\sqrt{2M\cdot \mathsf{SNR}+1}-1}{2 \mathsf{SNR}}.
\label{eq:first-two-condition}
\end{equation}
The third condition in Lemma~\ref{lemma-ul} gives $\frac{\mu_{1,2}}{1+\mu_{1,2}}\leq\frac{1+\mu_{1,2}}{\mu_{1,2}}$, which always holds.
Thus, we have that the UL rate region in Massive MIMO LoS is convex if and only if $g(\theta_1, \theta_2)\leq \frac{\sqrt{2M\cdot \mathsf{SNR}+1}-1}{2 \cdot \mathsf{SNR}}$.

Similar to the DL case, in the low SNR regime, when fixing $\theta_1=0\degree$ and varying $\theta_2\in[0,90\degree]$, the percentage of angles that gives non-convex rate region scales proportionally with $1/M$.

\vspace{-0.15cm}
\begin{propi}
	\label{propo2}
	In Massive MIMO with LoS channels, the convexity of the two-user rate region depends on the number of antennas $M$, SNRs, and user angles. In the low-SNR regime with $\beta_1=\beta_2$, the probability of having a non-convex region reduces as $1/M$ when the angles are uniformly distributed.
\end{propi}
\vspace{-0.15cm}
\section{Conclusions}
We studied the convexity of the achievable rate region in two-user Massive MIMO systems. We observed that with ergodic i.i.d.~Rayleigh fading, the rate region is always convex, thus it is always beneficial to serve the users by spatial multiplexing (Proposition~\ref{propo1}). With LoS channels, the convexity conditions depend on the number of antennas, the SNR values and the angles of the two users (Proposition~\ref{propo2}). When the angles are similar, the region is non-convex and  scheduling (time-sharing between the corner points) is preferable. The extension to more than two users is important future work.

\vspace{-0.1cm}

\bibliographystyle{IEEEtran}
\bibliography{ref}

\end{document}

config: arxiv


TITLE: Proving a set defined using the norm is compact
QUESTION [0 upvotes]: I'm currently stuck on the following question
Let be $ \|  \|$ be any norm on $\mathbb{R}^m$ and let $B = \{x \in \mathbb{R}^m : \| x \| \leq 1\}$. Prove that B is
compact.
I've shown that this set is bounded but I can't seem to show that it's closed. Can someone give me a hint to start off?

REPLY [2 votes]: If $y\notin B$, then the ball of positive(!) radius $|y|-1$ around $y$ is disjoint from $B$. Hence the complement of $B$ is open and $B$ itself closed.

REPLY [1 votes]: Assuming that your set is $B=\{x\in\Bbb R^m\mid\|x\|\leqslant1\}$, then it is closed because, if $n\colon\Bbb R^n\longrightarrow\Bbb R$ is the norm, then $n$ is continuous, $B=n^{-1}\bigl([0,1]\bigr)$, and $[0,1]$ is a closed subset of $\Bbb R$.


TITLE: If for every $x>0,P(|X_k|>x) \leq P(Y>x)$ then $\lim_k E[X_k|\mathcal{G}]=E[X|\mathcal{G}]$ a.s.?
QUESTION [5 upvotes]: Consider on a probability space $(\Omega,\mathcal{F},P),$ a sub-$\sigma$-algebra $\mathcal{G}$ and a sequence of random variables $(X_k)_k$ converging a.s. to $X$. Let $Y \in L^1.$

Prove that if $|X_k| \leq Y$ then $E[X_k|\mathcal{G}]$ converges a.s. to $E[X|\mathcal{G}]$.

Does it follow that $\lim_k E[X_k|\mathcal{G}]=E[X|\mathcal{G}]$ a.s.
a. if for every $x>0,P(|X_k|>x) \leq P(Y>x)?$
b. if for every $x>0,P(|X_k|>x|\mathcal{G}) \leq P(Y>x|\mathcal{G})$ a.s. ?

Attempt:

The result follows by applying Fatou's lemma: $E[\liminf_k(2Y-|X_k-X|)|\mathcal{G}] \leq \liminf_k E[2Y-|Y_k-Y||\mathcal{G}]$ a.s. which implies that $2E[Y|\mathcal{G}]\leq 2 E[Y|\mathcal{G}]-\limsup_kE[|X_k-X||\mathcal{G}]$ a.s. so that $\limsup_kE[|X_k-X||\mathcal{G}]=0$ a.s. concluding the proof.

Any ideas for part 2. are welcomed!

REPLY [3 votes]: Let $(X_n)_{n\geqslant 1}$ be a sequence of random variables on a probability space $(\Omega,\mathcal F,\mathbb P)$ that converges almost surely to a random variable $Y$. Let $\mathcal G$ be a sub-$\sigma$-algebra of $\mathcal F$. Consider the following four conditions:

$(C1)$: there exists an integrable random variable $Y$ such that $\lvert X_n\rvert\leqslant Y$ almost surely.
$(C2)$: there exists an integrable random variable $Y$ such that for each $x>0$, $\mathbb P\left(\lvert X_n\rvert>x\mid\mathcal G\right)\leqslant \mathbb P\left(Y>x\mid\mathcal G\right)$ almost surely.
$(C3)$: there exists an integrable random variable $Y$ such that for each $x>0$, $\mathbb P\left(\lvert X_n\rvert>x\right)\leqslant \mathbb P\left(Y>x\right)$.
$(C4)$: the sequence $\left(X_n\right)_{n\geqslant 1}$ is uniformly integrable.

The chain of implication $(C1)\Rightarrow (C2)\Rightarrow (C3) \Rightarrow (C4)$ takes places. Now the question is: which conditions among $(Ci)$, $1\leqslant i\leqslant 4$ guarantees that
$$
\tag{*}\mathbb E\left[X_n\mid\mathcal G\right]\to \mathbb E\left[X\mid\mathcal G\right].
$$
As it was shown in the opening post, $(C1)$ is sufficient and it was established in this thread  that $(C4)$ is not sufficient in general.
Interestingly, the example provided in this thread satisfies also the stochastic domination in $(C3)$. To this this, let write explicitly the counter-example. Let $\left(A_n\right)_{n\geqslant 1}$ and $\left(B_n\right)_{n\geqslant 1}$ be two mutually independent sequences of events, both sequences consisting of independent events, and such that $\mathbb P(A_n)=1/n$, $\mathbb P(B_n)=1/n^2$. Let $Y_n=\mathbf{1}_{A_n}$, $Z_n=n^2\mathbf{1}_{B_n}$ and $X_n=Y_nZ_n$. Let $\mathcal G:= \sigma(A_k,k\geqslant 1)$.

By the first Borel-Cantelli lemma, $\mathbb P(\limsup_n B_n)=0$ hence for almost every $\omega$, there exists an $n(\omega)$ such that $X_n(\omega)=0$ for $n\geqslant n(\omega)$. Therefore, $X_n\to X:=0$ almost surely.
For a positive $x$,  $\mathbb P(\lvert X_n\rvert>x)=\mathbf 1_{(0,n^2]}(x)\mathbb P(A_n\cap B_n)=\mathbf 1_{(0,n^2)}(x)n^{-3}$ hence
$$
\sup_{n\geqslant 1}\mathbb P(\lvert X_n\rvert>x)\leqslant \sup_{n\geqslant 1}\mathbf 1_{(0,n^2)}(x)n^{-3},
$$
which is reached at $n=\lfloor \sqrt{x}\rfloor+1$ hence any random variable $Y$ whose tail behaves as $(\lfloor \sqrt{x}\rfloor+1)^{-3}$ would do the job, as such a random variable would be integrable.
$\mathbb E\left[X_n\mid\mathcal G\right]=n^2\mathbf{1}_{A_n}\mathbb E\left[\mathbf{1}_{B_n}\mid\mathcal G\right]=\mathbf{1}_{A_n}$ and by the second Borel-Cantelli lemma, $\mathbb E\left[X_n\mid\mathcal G\right]$ does not converge to $0$ almost surely.

It remains to see whether $(C2)$ is sufficient. For $R>0$, let $\Phi_R\colon\mathbb R\to \mathbb R$ be the function defined by $\Phi_R(t)=-R$ if $t<-R$; $\Phi_R(t)=t$ if $-R\leqslant t\leqslant R$  and $ \Phi_R(t)=R$ if $t>R$. Since $\left( \Phi_R(X_n) \right)_{n\geqslant 1}$ converges almost surely to $\Phi_R(X)$ and $\lvert \Phi_R(X_n)\rvert\leqslant R$, we derive that
$\mathbb E\left[ \Phi_R(X_n)\mid \mathcal G\right]\to \mathbb E\left[ \Phi_R(X)\mid \mathcal G\right]$. Moreover, we can show that
$$
\tag{C5}
\sup_{n\geqslant 1} \mathbb E\left[\lvert X_n\rvert\mathbb{1}_{\{\lvert X_n\rvert>2^k\}}\mid\mathcal G\right]\to 0\mbox{ a.s. as }k\to \infty
$$
by applying the inequality in $(C2)$ with $x=2^j$ and sum over $j\geqslant k$. Since
$$
\left\lvert \mathbb E\left[X_n\mid\mathcal G\right]-\mathbb E\left[X\mid\mathcal G\right]\right\rvert\leqslant \left\lvert \mathbb E\left[\Phi_{2^k}(X_n)\mid\mathcal G\right]-\mathbb E\left[\Phi_{2^k}(X)\mid\mathcal G\right]\right\rvert+\left\lvert \mathbb E\left[X_n-\Phi_{2^k}(X_n)\mid\mathcal G\right]\right\rvert+\left\lvert \mathbb E\left[X-\Phi_{2^k}(X)\mid\mathcal G\right]\right\rvert
$$
and for a random variable $Z$, $\lvert Z-\Phi_{2^k}\rvert\leqslant \lvert Z \rvert\mathbf{1}_{\{\lvert Z \rvert>2^k\}}$, it follows that
$$
\left\lvert \mathbb E\left[X_n\mid\mathcal G\right]-\mathbb E\left[X\mid\mathcal G\right]\right\rvert\leqslant \left\lvert \mathbb E\left[\Phi_{2^k}(X_n)\mid\mathcal G\right]-\mathbb E\left[\Phi_{2^k}(X)\mid\mathcal G\right]\right\rvert+\left\lvert \mathbb E\left[\lvert X_n\rvert\mathbf{1}_{\{\lvert X_n \rvert>2^k\}}\mid\mathcal G\right]\right\rvert+\left\lvert \mathbb E\left[\lvert X \rvert\mathbf{1}_{\{\lvert X  \rvert>2^k\}}\mid\mathcal G\right]\right\rvert
$$
hence $(C2)$ is sufficient.
Actually, the proof shows that (C5) is sufficient. We have $(C1)\Rightarrow (C5)\Rightarrow (C2)$.


text:
\begin{document}

\title{\bf On the maximum Zagreb indices of bipartite graphs with given connectivity}

\author{Xiaocong He$^{a,}$\footnote{Corresponding author},\ \  Xiaobo He$^b$}
\date{}

\maketitle

\begin{center}
$^a$ School of Mathematics and Statistics, Central South University, New Campus, \\ Changsha, Hunan, 410083, P.R. China\\[5pt]
hexc2018@qq.com (X.C.~He)
\medskip

$^b$ School of Architectural Engineering, Huanggang Normal University, \\ Huanggang, Hubei, 438000, P.R. China\\
1459313778@qq.com (X.B. He)
\end{center}

\begin{abstract}
The first Zagreb index $M_{1}$ of a graph is defined as the sum of the square of every vertex degree, and the second Zagreb index $M_{2}$ of a graph is defined as the sum of the product of vertex degrees of each pair of adjacent vertices. In this paper, we study the Zagreb indices of bipartite graphs of order $n$ with $\kappa(G)=k$ (resp. $\kappa'(G)=s$) and sharp upper bounds are obtained for $M_1(G)$ and $M_2(G)$ for $G\in \mathcal{V}^k_n$ (resp. $\mathcal{E}^s_n$), where $\mathcal{V}^k_n$ is the set of bipartite graphs of order $n$ with $\kappa(G)=k$, and $\mathcal{E}^s_n$ is the set of bipartite graphs of order $n$ with $\kappa'(G)=s$.
\end{abstract}

\vspace{2mm} \noindent{\bf Keywords}: First Zagreb index; Second Zagreb index; Connectivity; Edge connectivity

\vspace{2mm}

\setcounter{section}{0}
\section{Introduction}\setcounter{equation}{0}
In this paper,  we only consider simple and undirected graphs. Let $G=(V, E)$ be a graph with the vertex set $V(G)$ and the edge set $E(G)$. Then $G-v,\, G-uv$ denote the graph obtained from $G$ by deleting vertex $v \in V$, or edge $uv \in E$, respectively. This notation is naturally extended if more than one vertex or edge is deleted. Similarly, $G+uv$ is obtained from $G$ by adding an edge $uv\notin E(G)$. Denote by $|U|$ the cardinality of the set $U$. For a vertex subset $S$ of $V(G)$, $G[S]$ consists of $S$ and all edges in $E(G)$ whose endvertices are contained in $S$. If $G$ is connected and for a set $W$ of vertices (edges), $G-W$ is disconnected, then we say $W$ is a \textit{vertex (edge) cut set} of $G$. In order to formulate our results, we need some graph-theoretical notations and terminologies. For other undefined ones, the reader is refereed to \cite{06}.

For $u\in V(G)$, we denote its neighborhood and the degree by $N_G(u)$ and $d_G(u)$, respectively. Let $\delta(G)=\max\{d_G(u): u\in V(G)\}$. Recall that $G$ is called \textit{k-connected} if $|G|>k$ and $G-X$ is connected for every set $X\subseteq V(G)$ with $|X|<k$. The greatest integer $k$ such that $G$ is $k$-connected is the connectivity $\kappa(G)$ of $G$. Thus, $\kappa(G)=0$ if and only if $G$ is disconnected or $K_1$, and $\kappa(K_n)=n-1$ for all $n\geq1$. Analogously, if $|G|>1$ and $G-E'$ is connected for every edge set $E'\subseteq E(G)$ of fewer than $s$ edges, then $G$ is called \textit{s-edge-connected}. The greatest integer $s$ such that $G$ is $s$-connected is the edge-connectivity $\kappa'(G)$ of $G$. In particular, $\kappa'(G)=0$ if $G$ is disconnected. If $G$ is a graph of order $n$, we may have the following fact.
\begin{kst}
\item[{\rm (1)}] $\kappa(G)\leq\kappa'(G)\leq \delta(G)\leq n-1$, and
\item[{\rm (2)}] $\kappa(G)=n-1$, $\kappa'(G)=n-1$ and $G\cong K_n$ are equivalent.
\end{kst}

A bipartite graph $G$ is a simple graph, whose vertex set $V(G)$ can be partitioned into two disjoint subsets $X$ and $Y$ such that every edge of $G$ joins a vertex of $X$ with a vertex of $Y$. A bipartite graph in which every two vertices from different partition classes are adjacent is called complete, which is denoted by $K_{p,q}$, where $p=|X|$, $q=|Y|$. In particular, let $K_{p,0}$, ($p\geq1$) denote $pK_1$.

Let $\mathcal{V}^k_n$ (resp. $\mathcal{E}^s_n$) be the class of all $n$-vertex bipartite graphs with connectivity $k$ (resp. edge-connectivity $s$). Let $n,k$ and $r$ be three positive integers such that $n\geq r\geq k$. We define a graph $O_k\vee_1(K_1\bigcup K_{n-r-1,r-k})$, where $\bigcup$ is the union of two graphs, $O_k$ ($k\geq1$) is an empty graph of order $k$ and $\vee_1$ is a graph operation that join all the vertices in $O_k$ to the vertex of $K_1$ and to the vertices belonging to the partition of cardinality $n-r-1$ in $K_{n-r-1,r-k}$ respectively.

The \textit{first Zagreb index} $M_1=M_1(G)$ and the \textit{second Zagreb index} $M_2=M_2(G)$ of the graph $G$ are defined, respectively, as:
\begin{align*}
M_{1}=M_{1}(G)=\sum_{u\in V(G)}d^2(u),\ \ \ M_{2}=M_{2}(G)=\sum_{uv\in E(G)}d(u)d(v).
\end{align*}
In 1972, Gutman and Trinajsti\'c \cite{1972-Gutman-Trinajstic} discovered the quantities $M_1$ and $M_2$ in certain approximate
expressions for the total $\pi$-electron energy. The name \textit{Zagreb index} (or, \textit{Zagreb group index}) seems to be first
used in the survey article \cite{1983-Balaban} and after that became standard. In fact, these graph invariants
were proposed in 1975 as measures of branching of the carbon atom skeleton (see \cite{2}). In the past ten years the researchers mainly focused on the bounds or mathematical properties of $M_1, M_2$, one may be referred to \cite{07,2010-FLH,2011-HL,2011-LZ,2011-LZ1,2010-LZH,6,2010-LZ,7} and the references with in. Especially, Liu and Gutman \cite{LG} determined the upper bounds for Zagreb indices of connected graphs; Feng and Ili\'{c} \cite{2010-F} determined sharp upper bounds for Zagreb indices $M_1$ and $M_2$ of graphs with a given matching number; Li and Zhou \cite{2010-LZH} determined the upper and lower bounds for Zagreb indices of graphs with connectivity at most $k$; Li and Zhang determined sharp upper bounds for Zagreb indices of bipartite graphs with a given diameter; see \cite{2011-LZ}. For a survey of chemical applications
and mathematical properties of the Zagreb indices, we refer the reader to \cite{2017-BDG,2004-IGD,2013-IGT,2003-NKMT,7}.

Motivated by \cite{2010-LZH}, in this paper we determine the maximum values on $M_1$ and $M_2$ in the case of $n$-vertex bipartite graphs, which is an important class of graphs in graph theory. Based on the structure of bipartite graphs, sharp upper bounds on $M_1$ and $M_2$ among $\mathcal{V}^k_n$ (resp. $\mathcal{E}^s_n$) are determined. The corresponding extremal graphs are identified, respectively.
\section{Lemmas and results}
In this section, we shall determine the sharp upper bounds for $M_1(G)$ and $M_2(G)$ of bipartite graph $G\in \mathcal{V}^k_n$ (resp. $\mathcal{E}^s_n$).

By the definition of Zagreb indices, we obtain the following lemma immediately.
\begin{lem}\label{lem2.1}
Let $u,v$ be two non-adjacent vertices of a connected graph $G$. We have
$$M_1(G+uv)>M_1(G), \ \ \ M_2(G+uv)>M_2(G).$$
\end{lem}

\begin{lem}[\cite{2010-LZH}]\label{lem2.2}
Let $G$ be a connected graph and $u, v$ be two vertices of $G$. Suppose $v_1, v_2, \ldots, v_s\in N(v)\backslash N(u)$, $1\leq s\leq d(v)$. Let $G^*=G-\{vv_1, vv_2, \ldots, vv_s\}+\{uv_1, uv_2, \ldots, uv_s\}$. If $d(u)\geq d(v)$ and $u$ is not adjacent to $v$, then
\begin{align*}
\text{$M_1(G^*)>M_1(G)$\ \ \ \ and \ \ \ \ $M_2(G^*)>M_2(G).$}
\end{align*}
\end{lem}
Let $\mathcal{A}^k_n=\{G$: $G=(X, Y)\in \mathcal{V}^k_n$ and there exists a vertex cut set $S$ of order $k$ in $G$ such that $S\bigcap X\neq\emptyset$ and $S\bigcap Y\neq\emptyset$\}.
\begin{lem}\label{lem2.3}
If $G\in\mathcal{A}^k_n$, then $G$ cannot be the graph with the maximum $M_1(G)$ and $M_2(G)$ in $\mathcal{V}^k_n$.
\end{lem}
\begin{proof}
Choose $G=(X,Y)\in\mathcal{A}^k_n$ such that $M_1(G)$ and $M_2(G)$ are as large as possible. By the definition of $\mathcal{A}^k_n$, suppose that $S=\{v_1,v_2,\ldots,v_k\}$ is a vertex cut set of order $k$ in $G$ such that $S\bigcap X\neq\emptyset$ and $S\bigcap Y\neq\emptyset$. We write $S_X=S\bigcap X$, $S_Y=S\bigcap Y$, $S^c_X=X-S_X$ and $S^c_Y=Y-S_Y$.

First we show the following facts.
\begin{fact}
$G[S_X\bigcup S_Y]$ is a complete bipartite graph with partitions $(S_X,S_Y)$.
\end{fact}
{\bf Proof of Fact 1.}~
Suppose that, on the contrary, there exist $v_i\in S_X$ and $v_j\in S_Y$ such that $v_iv_j\notin E(G)$. By Lemma \ref{lem2.1}, we have $M_1(G+v_iv_j)>M_1(G)$ and $M_2(G+v_iv_j)>M_2(G)$, a contradiction, since $G+v_iv_j$ is also a bipartite graph with connectivity $k$.

This completes the proof of Fact 1.\qed

With the similar argument as in the proof of Fact 1, we can showing the following fact.
\begin{fact}
For every component $H$ of $G-S$, $G[V(H)\bigcup S]$ is a complete bipartite graph.
\end{fact}
\begin{fact}
$G-S$ consists of two complete bipartite graphs.
\end{fact}
{\bf Proof of Fact 3.}~
Suppose that, on the contrary, $G-S$ contains three connected components, say $H_1, H_2, H_3$. Now we show that $S^c_X\neq \emptyset$ and $S^c_Y\neq \emptyset$. Otherwise, if $S^c_X=\emptyset$, then $S_X=X$ is a vertex cut set of $G$ with order $|S_X|<k=\kappa(G)$, a contradiction. Similarly, we have $S^c_Y\neq \emptyset$. Without loss of generality, assume that $V(H_1)\bigcap X\neq\emptyset$ and $V(H_2)\bigcap Y\neq\emptyset$. Let $x\in V(H_1)\bigcap X$ and $y\in V(H_2)\bigcap Y$. For $H_3$, if there exists $z\in V(H_3)\bigcap X$, then we have $G+zy\in \mathcal{V}^k_n$. By Lemma \ref{lem2.1}, $M_1(G+zy)>M_1(G)$ and $M_2(G+zy)>M_2(G)$, a contradiction. Hence, there exists $z\in V(H_3)\bigcap Y$. It is easy to see that $G+zx\in \mathcal{V}^k_n$. By Lemma \ref{lem2.1}, $M_1(G+zx)>M_1(G)$ and $M_2(G+zx)>M_2(G)$, a contradiction. Hence, $G-S$ consists of two complete bipartite graphs.\qed

By Fact 3, $G-S$ consists of two complete bipartite graphs, say $H_1$ and $H_2$. Since $G$ is $k$-connected, we have $H_i\bigcap X\neq\emptyset$ and $H_i\bigcap Y\neq\emptyset$ for $i=1,2$. Let $x_1\in H_1\bigcap X$ and $x_2\in H_2\bigcap X$. By Claim 2, we have $N_G(x_1)=(V(H_1)\bigcap Y)\bigcup S_Y$ and $N_G(x_2)=(V(H_2)\bigcap Y)\bigcup S_Y$. If $d_G(x_1)\geq d_G(x_2)$, set $G^*=G-\{x_2y| y\in V(H_2)\bigcap Y\}+\{x_1y| y\in V(H_2)\bigcap Y\}$. By Lemma \ref{lem2.2}, we have $M_1(G^*)>M_1(G)$ and $M_2(G^*)>M_2(G)$. Clearly, $G^*$ is a bipartite graph with $d_{G^*}(x_2)= |S_Y|<k$. Note that $|Y|\geq k$, then we choose an arbitrary $(k-|S_Y|)$ subset of $V(H_1)\bigcap Y$, say $A$. Let
$$G'=G^*+\{x_2y: y\in A\}+\{uv: u\in X\backslash\{x_2\}, y\in Y\}.$$
It is routine to check that $G'\in \mathcal{V}^k_n\backslash \mathcal{A}^k_n$. By Lemma \ref{lem2.1}, we have $M_1(G')>M_1(G^*)>M_1(G)$ and $M_2(G')>M_2(G^*)>M_2(G)$. If $d_G(x_1)< d_G(x_2)$, then the discussion is similar, we omit its procedure here.

This completes the proof.
\end{proof}

\begin{lem}\label{lem2.4}
Choose $G=(X,Y)\in\mathcal{V}^k_n$ such that its $M_1(G)$, $M_2(G)$ are as large as possible. If $S$ is a vertex cut set of order $k$ in $G$ such that $S\subseteq X$ and $|X|>k$, then $G-S$ consists of two components, one of which is an isolated vertex.
\end{lem}
\begin{proof}
Firstly, we show that $G-S$ consists of two components. Suppose that $G-S$ contains three components, say $G_1, G_2, G_3$. Since $|X|>k$, then $G-S$ contains a component with at least two vertices. Without loss of generality, assume that $|V(G_1)|\geq2$. Hence $V(G_1)\bigcap X\neq\emptyset$ and $V(G_1)\bigcap Y\neq\emptyset$. Since $G$ is connected, then $V(G_2)\bigcap Y\neq\emptyset$. Let $x\in V(G_1)\bigcap X$ and $y\in V(G_2)\bigcap Y$. It is easy to see that $G+xy\in\mathcal{V}^k_n$. By Lemma \ref{lem2.1}, we have $M_1(G+xy)>M_1(G)$ and $M_2(G+xy)>M_2(G)$, a contradiction. Now we can assume that $G-S$ contains two components, say $G_1$ and $G_2$, such that $|V(G_1)|\geq |V(G_2)|$. If $G_2$ is not an isolated vertex, then we have $V(G_2)\bigcap X\neq\emptyset$. Let $y_1\in V(G_1)\bigcap Y$ and $y_2\in V(G_2)\bigcap Y$. If $d_G(y_2)\geq d_G(y_1)$, set $$\widetilde{G}=G-\Big\{y_1x: x\in V(G_1)\bigcap X\Big\}+\Big\{y_2x: x\in V(G_1)\bigcap X\Big\}+\Big\{uv: u\in X, y\in Y\backslash\{y_1\}\Big\}.$$
It is routine to check that $\widetilde{G}\in \mathcal{V}^k_n$. By Lemmas \ref{lem2.1} and \ref{lem2.2}, $M_1(\widetilde{G})>M_1(G)$ and $M_2(\widetilde{G})>M_2(G)$, a contradiction.

This complete the proof.
\end{proof}
\begin{Obs}\label{o}
Choose $G=(X,Y)\in \mathcal{V}^k_n$ such that its $M_1(G)$, $M_2(G)$ are as large as possible. Since $G$ is $k$-connected, then $|X|\geq k$ and $|Y|\geq k$. If $S$ be a vertex cut set of order $k$ in $G$, by Lemma \ref{lem2.3}, without loss of generality, we have $S\subseteq X$. If $|X|=k$, i.e., $S=X$, then $G\cong K_{k,n-k}$. If $|X|>k$, by Lemma \ref{lem2.4}, we have $G\cong O_k\vee_1(K_1\bigcup K_{n-r-1,r-k})$ for some $r>k$. In both cases, we have $G\cong O_k\vee_1(K_1\bigcup K_{n-r-1,r-k})$ for some $r\geq k$. We partition $V(G)$ into $\{v\}\bigcup C\bigcup A\bigcup B\bigcup \{a_{n-r-1}\}$, where $C=\{c_1, c_2, \ldots,c_k\}$, $A=\{a_1, a_2, \ldots,a_{n-r-2}\}$ and $B=\{b_1, b_2, \ldots,b_{r-k}\}$, see Fig. 1.
\end{Obs}
\begin{figure}[h!]
\begin{center}
\psfrag{a}{$v$}\psfrag{b}{$c_1$}\psfrag{c}{$c_2$}\psfrag{d}{$c_k$}
\psfrag{e}{$b_1$}\psfrag{f}{$b_2$}\psfrag{g}{$b_{r-k}$}
\psfrag{h}{$a_1$}\psfrag{i}{$a_2$}\psfrag{j}{$a_{n-r-1}$}
\includegraphics[width=60mm]{fig-1.eps} \\
  \caption{$G\cong O_k\vee_1(K_1\bigcup K_{n-r-1,r-k})$, $r\geq k$.}
\end{center}
\end{figure}

\begin{lem}\label{2.5}
If $G\cong O_k\vee_1(K_1\bigcup K_{n-r-1,r-k})\in \mathcal{V}^k_n$ ($n\geq6$ and $k\leq\frac{n}{2}-1$) such that $r\leq \frac{n}{2}-2$ or $r>\frac{n}{2}$, then $G$ cannot be the graph with the maximum $M_1(G)$ and $M_2(G)$.
\end{lem}
\begin{proof}

We consider the following two cases.
\begin{Case}
$r\leq \frac{n}{2}-2$.
\end{Case}
In this case, let
$$G^*=G-\{a_{n-r-1}c_1, \ldots,a_{n-r-1}c_k, a_{n-r-1}b_1, \ldots, a_{n-r-1}b_{r-k}\}+\{a_{n-r-1}a_1, \ldots, a_{n-r-1}a_{n-r-2}\}.$$
It is rountine to check that $G^*\in \mathcal{V}^k_n$; see Fig. 2. And we have
\begin{figure}[h!]
\begin{center}
\psfrag{a}{$v$}\psfrag{b}{$c_1$}\psfrag{c}{$c_2$}\psfrag{d}{$c_k$}
\psfrag{e}{$b_1$}\psfrag{f}{$b_2$}\psfrag{g}{$b_{r-k}$}\psfrag{o}{$a_{n-r-1}$}
\psfrag{h}{$a_1$}\psfrag{i}{$a_2$}\psfrag{j}{$a_{n-r-2}$}
\psfrag{1}{$v$}\psfrag{2}{$c_1$}\psfrag{3}{$c_2$}\psfrag{4}{$c_k$}
\psfrag{5}{$b_1$}\psfrag{6}{$b_2$}\psfrag{7}{$b_{r-k}$}\psfrag{8}{$a_1$}
\psfrag{9}{$a_2$}\psfrag{k}{$a_k$}\psfrag{l}{$a_{n-r-1}$}
\psfrag{m}{$G^*$}\psfrag{n}{$G^{**}$}
\includegraphics[width=120mm]{fig-2.eps} \\
  \caption{Graphs $G^*$ and $G^{**}$ used in Case 1 of Lemma 2.5.}
\end{center}
\end{figure}
\begin{align*}
&M_1(G^*)-M_1(G)\\
=&\sum_{i=1}^{k}\Big[d^2_{G^*}(c_i)-d^2_{G}(c_i)\Big]+\sum_{i=1}^{r-k}\Big[d^2_{G^*}(b_i)-d^2_{G}(b_i)\Big]+\sum_{i=1}^{n-r-1}\Big[d^2_{G^*}(a_i)-d^2_{G}(a_i)\Big]\\
=&k[1-2(n-r)]+(r-k)[1-2(n-r-1)]+(n-r-2)(1+2r)+(n-r-2)^2-r^2\\
=&k[1-2(n-r)]+(r-k)[1-2(n-r)]+2(r-k)+(n-r-2)(1+2r)+(n-r-2)^2-r^2\\
=&r[1-2(n-r)]+2(r-k)+(n-r-2)(1+2r)+(n-r-2)^2-r^2\\
=&-3r+(n-r-2)+2(r-k)+(n-r-2)^2-r^2\\
=&[(n-r)-r-2]-2k+(n-r-2)^2-r^2\\
\geq&2-2k+(r+2)^2-r^2\\
=&-2k+4r+6\\
>&0,
\end{align*}
\begin{align*}
&M_2(G^*)-M_2(G)\\
=&\sum_{i=1}^{k}\Big[d_{G^*}(v)d_{G^*}(c_i)-d_{G}(v)d_{G}(c_i)\Big]+\sum_{i=1}^{k}\sum_{j=1}^{n-r-2}\Big[d_{G^*}(c_i)d_{G^*}(a_j)-d_{G}(c_i)d_{G}(a_j)\Big]\\
&+\sum_{i=1}^{r-k}\sum_{j=1}^{n-r-2}\Big[d_{G^*}(b_i)d_{G^*}(a_j)-d_{G}(b_i)d_{G}(a_j)\Big]+d_{G^*}(a_{n-r-1})\sum_{i=1}^{n-r-2}d_{G^*}(a_i)\\
&-d_{G}(a_{n-r-1})\Big[\sum_{i=1}^{k}d_{G}(c_i)+\sum_{i=1}^{r-k}d_G(b_i)\Big]\\
=&-k^2+(n-2r-1)(n-r-2)k+(n-2r-2)(r-k)(n-r-2)+(n-r-2)^2(r+1)\\
&-r^2(n-r)+r^2-rk\\
=&-k^2+(n-2r-1)(n-r-2)k+(n-2r-2)(r-k)(n-r-2)+\Big[(n-r)^2+4-4(n-r)\Big](r+1)\\
&-r^2(n-r)+r^2-rk\\
=&-k^2+(n-2r-1)(n-r-2)k+(n-2r-2)(r-k)(n-r-2)+\Big[(n-r)^2+4-4(n-r)\Big]\\
&+\Big[r(n-r)^2+4r-4(n-r)r\Big]-r^2(n-r)+r^2-rk\\
=&-k^2+(n-2r-1)(n-r-2)k+(n-2r-2)(r-k)(n-r-2)\\
&+\Big[(n-r)^2+4-4(n-r)+4r-4(n-r)r+r^2-rk\Big]+r(n-r)(n-r-r)\\
>&-k^2+\Big[(n-r)^2+4-4(n-r)+4r-4(n-r)r+r^2-rk\Big]+4r(n-r)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{(by $n-2r\geq4$)}\\
=&-k^2+\Big[(n-r)^2+4-4(n-r)+4r+r^2-rk\Big]\\
=&-k^2+(n-r-2)^2+4r+r^2-rk\\
>&0.
\end{align*}

\begin{Case}
$r>\frac{n}{2}$.
\end{Case}
In this case, let
$$G^{**}=G-\{vc_1, vc_2, \ldots, vc_k\}+\{va_1, va_2, \ldots, va_k\}.$$
It is routine to check that $G^{**}\in \mathcal{V}^k_n$; see Fig. 2. And we have
\begin{align*}
&M_1(G^{**})-M_1(G)\\
=&\sum_{i=1}^{k}\Big[d^2_{G^{**}}(c_i)-d^2_{G}(c_i)\Big]+\sum_{i=1}^{r-k}\Big[d^2_{G^{**}}(b_i)-d^2_{G}(b_i)\Big]+\sum_{i=1}^{k}\Big[d^2_{G^{**}}(a_i)-d^2_{G}(a_i)\Big]+\sum_{i=k+1}^{n-r-1}\Big[d^2_{G^{**}}(a_i)-d^2_{G}(a_i)\Big]\\
=&k\Big[1-2(n-r)\Big]+k(2r+1)\\
=&k(2+4r-2n)\\
>&0,
\end{align*}
\begin{align*}
&M_2(G^{**})-M_2(G)\\
=&\sum_{i=1}^{k}\Big[d_{G^{**}}(v)d_{G^{**}}(a_i)-d_{G}(v)d_{G}(c_i)\Big]+\sum_{i=1}^{k}\sum_{j=1}^{k}\Big[d_{G^{**}}(c_i)d_{G^{**}}(a_j)-d_{G}(c_i)d_{G}(a_j)\Big]\\
&+\sum_{i=1}^{k}\sum_{j=k+1}^{n-r-1-k}\Big[d_{G^{**}}(c_i)d_{G^{**}}(a_j)-d_{G}(c_i)d_{G}(a_j)\Big]+\sum_{i=1}^{r-k}\sum_{j=1}^{k}\Big[d_{G^{**}}(b_i)d_{G^{**}}(a_j)-d_{G}(b_i)d_{G}(a_j)\Big]\\
=&k^2\Big[r+1-(n-r)\Big]+k^2\Big[(r+1)(n-r-1)-r(n-r)\Big]-rk(n-r-1-k)+(n-r-1)(r-k)k\\
=&k^2\Big[r+1-(n-r)\Big]+k^2\Big[(n-r)-r-1\Big]-rk(n-r-1)+rk^2+rk(n-r)-rk-(n-r)k^2+k^2\\
=&rk^2-(n-r)k^2+k^2\\
=&(2r-n+1)k^2\\
>&0.
\end{align*}

This completes the proof.
\end{proof}

\begin{thm}\label{2.6}
Let $G$ be the graph in $\mathcal{V}^k_n$ ($n\geq6$) with the maximum $M_1(G)$ (resp. $M_2(G)$). Then we have the following results
\begin{wst}
\item[{\rm (i)}]$G\cong O_k\vee_1(K_1\bigcup K_{\frac{n-1}{2},\frac{n-1-2k}{2}})$ if $n$ is odd,
\item[{\rm (ii)}]$G\cong K_{\frac{n}{2}, \frac{n}{2}}$ if $n$ is even and $k=\frac{n}{2}$; $G\cong O_k\vee_1(K_1\bigcup K_{\frac{n}{2},\frac{n-2-2k}{2}})$ if $n$ is even and $k\leq\frac{n}{2}-1$.
\end{wst}
\end{thm}
\begin{proof}
Since $G$ is bipartite, by the definition of $k$-connected, we have $k\leq\frac{n}{2}$. If $k=\frac{n-1}{2}$ (resp. $k=\frac{n}{2}$), it is easy to see that $\mathcal{V}^k_n=\{K_{\frac{n-1}{2}, \frac{n+1}{2}}\}$ (resp. $\mathcal{V}^k_n=\{K_{\frac{n}{2}, \frac{n}{2}}\}$) and the result is clear. In what follows, assume that $k\leq\frac{n}{2}-1$. By Observation \ref{o} and Lemma \ref{2.5}, we have $G\in \Big\{O_k\vee_1(K_1\bigcup K_{n-r-1,r-k}): \frac{n-3}{2}\leq r\leq\frac{n}{2}\Big\}\subseteq \mathcal{V}^k_n$. We consider the following two cases.
\setcounter{Case}{0}
\begin{Case}
$n$ is odd.
\end{Case}
In this case, we have
$$
\Big\{O_k\vee_1(K_1\bigcup K_{n-r-1,r-k})| \frac{n-3}{2}\leq r\leq\frac{n}{2}\Big\}=\Big\{O_k\vee_1(K_1\bigcup K_{\frac{n+1}{2},\frac{n-3-2k}{2}}), O_k\vee_1(K_1\bigcup K_{\frac{n-1}{2},\frac{n-1-2k}{2}})\Big\}.
$$
Let $G\cong O_k\vee_1(K_1\bigcup K_{\frac{n-1}{2},\frac{n-1-2k}{2}})$ and $G'\cong O_k\vee_1(K_1\bigcup K_{\frac{n+1}{2},\frac{n-3-2k}{2}})$, see Fig. 3. Then we have
\begin{figure}[h!]
\begin{center}
\psfrag{a}{$v$}\psfrag{b}{$c_1$}\psfrag{c}{$c_2$}\psfrag{d}{$c_k$}
\psfrag{e}{$b_1$}\psfrag{f}{$b_2$}\psfrag{g}{$b_{\frac{n-1-2k}{2}}$}
\psfrag{h}{$a_1$}\psfrag{i}{$a_2$}\psfrag{j}{$a_{\frac{n-1}{2}}$}
\psfrag{1}{$v$}\psfrag{2}{$c_1$}\psfrag{3}{$c_2$}\psfrag{4}{$c_k$}
\psfrag{5}{$b_1$}\psfrag{6}{$b_2$}\psfrag{7}{$b_{\frac{n-3-2k}{2}}$}\psfrag{8}{$a_1$}
\psfrag{9}{$a_2$}\psfrag{k}{$a_{\frac{n-1}{2}}$}\psfrag{l}{$b_{\frac{n-1-2k}{2}}$}
\psfrag{m}{$G$}\psfrag{n}{$G'$}
\includegraphics[width=120mm]{fig-3.eps} \\
  \caption{Graphs $G$ and $G'$ used in Case 1 of Theorem 2.6.}
\end{center}
\end{figure}

\begin{align*}
&M_1(G)-M_1(G')\\
=&\sum_{i=1}^{k}\Big[d^2_{G}(c_i)-d^2_{G'}(c_i)\Big]+\sum_{i=1}^{\frac{n-1-2k}{2}}\Big[d^2_{G}(b_i)-d^2_{G'}(b_i)\Big]+\sum_{i=1}^{\frac{n-1}{2}}\Big[d^2_{G}(a_i)-d^2_{G'}(a_i)\Big]\\
=&k\Big[(\frac{n+1}{2})^2-(\frac{n+3}{2})^2\Big]+\frac{n-3-2k}{2}\Big[(\frac{n-1}{2})^2-(\frac{n+1}{2})^2\Big]+\frac{n-1}{2}\Big[(\frac{n-1}{2})^2-(\frac{n-3}{2})^2\Big]\\
&+(\frac{n-1}{2})^2-(\frac{n-3}{2})^2\\
=&\frac{k}{4}(-4n-8)-\frac{2n^2-6n-4nk}{4}+\frac{n-1}{4}(2n-4)+\frac{n^2+1-2n}{4}-\frac{n^2+9-6n}{4}\\
=&-2k+n-1\\
>&(-2)\times\frac{n-1}{2}+n-1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{(by $k\leq\frac{n}{2}-1$)}\\
=&0,
\end{align*}
\begin{align*}
&M_2(G)-M_2(G')\\
=&\sum_{i=1}^{k}\Big[d_{G}(v)d_{G}(c_i)-d_{G'}(v)d_{G'}(c_i)\Big]+\Big[\sum_{i=1}^{k}\sum_{j=1}^{\frac{n-1}{2}}d_{G}(c_i)d_{G}(a_j)-\sum_{i=1}^{k}\sum_{j=1}^{\frac{n-1}{2}}d_{G'}(c_i)d_{G'}(a_j)\\
&-d_{G'}(b_{\frac{n-1-2k}{2}})\sum^{k}_{i=1}d_{G'}(c_i)\Big]+\Big[\sum_{i=1}^{\frac{n-1-2k}{2}}\sum_{j=1}^{\frac{n-1}{2}}d_{G}(b_i)d_{G}(a_j)-\sum_{i=1}^{\frac{n-3-2k}{2}}\sum_{j=1}^{\frac{n-1}{2}}d_{G'}(b_i)d_{G'}(a_j)\Big]\\
=&-k^2+\Big[\frac{n+1}{2}\cdot\frac{n-1}{2}\cdot k\cdot\frac{n-1}{2}-\frac{n+3}{2}\cdot\frac{n-3}{2}\cdot k\cdot\frac{n+1}{2}\Big]+\Big[\frac{n-1}{2}\cdot\frac{n-1}{2}\cdot\frac{n-1-2k}{2}\cdot\frac{n-1}{2}\\
&-\frac{n+1}{2}\cdot\frac{n-3}{2}\cdot\frac{n-3-2k}{2}\cdot\frac{n+1}{2}\Big]\\
=&-k^2+\frac{k(n+1)}{8}\cdot(10-2n)+\frac{1}{8}\cdot(-8n+4n^2-4-8nk+2kn^2-2k)\\
=&\frac{1}{2}\Big[-2n+n^2-1+2k-2k^2\Big]\\
\geq&\frac{1}{2}\Big[-2n+n^2-1+2k-2(\frac{n}{2}-1)^2\Big]\\
=&\frac{1}{2}(\frac{n^2}{2}+2k-3)\\
>&0.
\end{align*}
Thus, we have (i) is true.

\begin{Case}
$n$ is even.
\end{Case}
In this case, we have
$$
\Big\{O_k\vee_1(K_1\bigcup K_{n-r-1,r-k})| \frac{n-3}{2}\leq r\leq\frac{n}{2}\Big\}=\Big\{O_k\vee_1(K_1\bigcup K_{\frac{n-2}{2},\frac{n-2k}{2}}), O_k\vee_1(K_1\bigcup K_{\frac{n}{2},\frac{n-2-2k}{2}})\Big\}.
$$
Let $G\cong O_k\vee_1(K_1\bigcup K_{\frac{n-2}{2},\frac{n-2k}{2}})$ and $G'\cong O_k\vee_1(K_1\bigcup K_{\frac{n}{2},\frac{n-2-2k}{2}})$, see Fig. 4. Then we have
\begin{figure}[h!]
\begin{center}
\psfrag{a}{$v$}\psfrag{b}{$c_1$}\psfrag{c}{$c_2$}\psfrag{d}{$c_k$}
\psfrag{e}{$b_1$}\psfrag{f}{$b_2$}\psfrag{g}{$b_{\frac{n-2-2k}{2}}$}
\psfrag{h}{$a_1$}\psfrag{i}{$a_2$}\psfrag{j}{$a_{\frac{n-2}{2}}$}
\psfrag{1}{$v$}\psfrag{2}{$c_1$}\psfrag{3}{$c_2$}\psfrag{4}{$c_k$}
\psfrag{5}{$b_1$}\psfrag{6}{$b_2$}\psfrag{7}{$b_{\frac{n-2-2k}{2}}$}\psfrag{8}{$a_1$}
\psfrag{9}{$a_2$}\psfrag{k}{$a_{\frac{n-2}{2}}$}\psfrag{l}{$a_{\frac{n}{2}}$}\psfrag{o}{$a_{\frac{n}{2}}$}
\psfrag{n}{$G$}\psfrag{m}{$G'$}
\includegraphics[width=120mm]{fig-4.eps} \\
  \caption{Graphs $G$ and $G'$ used in Case 2 of Theorem 2.6.}
\end{center}
\end{figure}
\begin{align*}
&M_1(G)-M_1(G')\\
=&\sum_{i=1}^{k}\Big[d^2_{G}(c_i)-d^2_{G'}(c_i)\Big]+\sum_{i=1}^{\frac{n-2-2k}{2}}\Big[d^2_{G}(b_i)-d^2_{G'}(b_i)\Big]+\sum_{i=1}^{\frac{n}{2}}\Big[d^2_{G}(a_i)-d^2_{G'}(a_i)\Big]\\
=&k\Big[(\frac{n+2}{2})^2-(\frac{n}{2})^2\Big]+\frac{n-2-2k}{2}\Big[(\frac{n}{2})^2-(\frac{n-2}{2})^2\Big]+\frac{n-2}{2}\Big[(\frac{n-2}{2})^2-(\frac{n}{2})^2\Big]\\
&++(\frac{n-2}{2})^2-(\frac{n-2}{2})^2\\
=&2k\\
>&0,
\end{align*}
\begin{align*}
&M_2(G)-M_2(G')\\
=&\sum_{i=1}^{k}\Big[d_{G}(v)d_{G}(c_i)-d_{G'}(v)d_{G'}(c_i)\Big]+\Big[\sum_{i=1}^{k}\sum_{j=1}^{\frac{n}{2}}d_{G}(c_i)d_{G}(a_j)-\sum_{i=1}^{k}\sum_{j=1}^{\frac{n}{2}}d_{G'}(c_i)d_{G'}(a_j)\Big]\\
&+\Big[\sum_{i=1}^{\frac{n-2-2k}{2}}\sum_{j=1}^{\frac{n}{2}}d_{G}(b_i)d_{G}(a_j)-\sum_{i=1}^{\frac{n-2-2k}{2}}\sum_{j=1}^{\frac{n-2}{2}}d_{G'}(b_i)d_{G'}(a_j)-d_{G'}(a_{\frac{n}{2}})\sum^{\frac{n-2}{2}}_{i=1}d_{G'}(a_i)\Big]\\
=&k^2+\Big[\frac{n+2}{2}\cdot\frac{n-2}{2}\cdot k\cdot\frac{n}{2}-\frac{n}{2}\cdot\frac{n}{2}\cdot k\cdot\frac{n-2}{2}\Big]+\Big[\frac{n-2-2k}{2}\cdot\frac{n}{2}\cdot\frac{n-2}{2}\cdot\frac{n}{2}\\
&-\frac{n-2k}{2}\cdot\frac{n-2}{2}\cdot\frac{n-2}{2}\cdot\frac{n}{2}\Big]\\
=&k^2+\frac{n-2}{2}\cdot\frac{n}{2}\cdot k-k\cdot\frac{n-2}{2}\cdot\frac{n}{2}\\
=&k^2\\
>&0.
\end{align*}
Thus, we have (ii) is true.

This completes the proof.
\end{proof}
\begin{thm}
Let $G$ be the graph in $\mathcal{E}^s_n$ ($n\geq6$) with the maximum $M_1(G)$ (resp. $M_2(G)$). Then we have the following results
\begin{wst}
\item[{\rm (i)}]$G\cong O_s\vee_1(K_1\bigcup K_{\frac{n-1}{2},\frac{n-1-2s}{2}})$ if $n$ is odd,
\item[{\rm (ii)}]$G\cong K_{\frac{n}{2}, \frac{n}{2}}$ if $n$ is even and $s=\frac{n}{2}$; $G\cong O_s\vee_1(K_1\bigcup K_{\frac{n}{2},\frac{n-2-2s}{2}})$ if $n$ is even and $s\leq\frac{n}{2}-1$.
\end{wst}
\end{thm}
\begin{proof}
By the inequality $\kappa(G)\leq\kappa'(G)\leq \delta(G)$, we have $G\in\bigcup_{k=1}^s\mathcal{V}^k_n$. Since $G$ is a bipartite graph, we have $\delta(G)\leq\frac{n}{2}$. Combining $\kappa(G)\leq\kappa'(G)\leq \delta(G)$, Lemma \ref{lem2.1} and Theorem \ref{2.6}, we have
\begin{wst}
\item[{\rm (i)}]$G\cong O_s\vee_1(K_1\bigcup K_{\frac{n-1}{2},\frac{n-1-2s}{2}})$ if $n$ is odd,
\item[{\rm (ii)}]$G\cong K_{\frac{n}{2}, \frac{n}{2}}$ if $n$ is even and $s=\frac{n}{2}$; $G\cong O_s\vee_1(K_1\bigcup K_{\frac{n}{2},\frac{n-2-2s}{2}})$ if $n$ is even and $s\leq\frac{n}{2}-1$.
\end{wst}
\end{proof}

This completes the proof.