text:
\section{Introduction}
The past few years have witnessed a tremendous increase in the use of unmanned aerial vehicles (UAVs) in civilian applications, such as for aerial surveillance, traffic control, photography, package  delivery, and communication platforms. In June 2016, the Federal Aviation Administration (FAA) finalized the operational rules for routine commercial use of small unmanned aircraft systems (UAS). It is anticipated that the new rules will generate more than 82 billion Dollars for the U.S. economy alone and create more than 100,000 new jobs over the next decade.\footnote{https://www.inc.com/yoram-solomon/with-one-rule-the-faa-just-created-an-82-billion-market-and-100000-new-jobs.html}
 However, before the wide usage of UAVs can be practically realized, there are still many technical challenges that remain unsolved. In particular, it is of paramount importance to ensure high-capacity, low-latency and ultra-reliable two-way wireless communications between UAVs and their associated ground entities, not only for supporting their safe operation, but also for enabling mission-specific rate-demanding payload communications. However, existing UAS mainly rely on the simple point-to-point communication over the unlicensed band (e.g., ISM 2.4 GHz), which is of low data rate, unreliable, insecure, vulnerable to interference, difficult to legitimately monitor and manage, and can only operate over very limited range. As the number of UAVs and their applications are anticipated to further grow in the  coming years, it is imperative to develop new wireless technologies to enable significantly enhanced UAV-ground communications.

{\it Cellular-connected UAV} is a promising technology to achieve the above goal, whereby UAVs for various applications are integrated into the existing and future cellular networks as new aerial user equipments (UEs), as illustrated in Fig.~\ref{F:Archiecture}. Compared to the traditional  ground-to-UAV communications via point-to-point links, cellular-connected UAV has several appealing advantages, discussed as follows.

\begin{itemize}
\item {\it Ubiquitous accessibility:} {Thanks to the almost ubiquitous accessibility of cellular networks worldwide, cellular-connected UAV makes it possible for the ground pilot to remotely command and control (C\&C) the UAV with essentially unlimited operation range. Besides, it provides an effective solution to maintain wireless connectivity between UAVs and various other stakeholders, such as the end users and the air traffic controllers, regardless of their locations. For example, by leveraging cellular network, live videos can be directly sent from the UAV to distant audiences worldwide.}

\item {\it Enhanced performance:} { With the advanced cellular technologies and authentication mechanisms, cellular-connected UAV has the potential to achieve significant performance improvement over the simple direct ground-to-UAV communications,} in terms of reliability, security, and communication throughput.

\item {\it Ease of monitoring and management:} Cellular-connected UAV offers an effective means to achieve large-scale air traffic monitoring and management. {  For example, with appropriate regulations and legislations, whenever necessary, the authorized party such as the air traffic controller could legitimately take over the UAV's remote control to timely avoid any safety threat foreseen.}

\item {\it Robust navigation:} Traditional UAV navigation mainly relies on satellite such as the Global Position System (GPS), which is however vulnerable to disruption of satellite signals due to, e.g., blockage by high buildings or bad weather conditions. {  Cellular-connected UAV offers one effective method, among others such as differential GPS (D-GPS), to achieve more robust UAV navigation by utilizing cellular signals as a complementary for GPS navigation.}

\item {\it Cost-effectiveness:} {  Last but not least, cellular-connected UAV is also cost-effective. On one hand, it can reuse the millions of cellular base stations (BSs) already deployed worldwide, without the need of building new infrastructures dedicated for UAS alone, thus significantly saving the network deployment cost. On the other hand, it may also help saving the operational cost, via bundling UAV C\&C and other numerous types of payload communications into cellular systems, which will create new business opportunities for both cellular and UAV operators. Thus, cellular-connected UAV is conceived to be a win-win technology for both cellular and UAV industries, which may help facilitate the integration of UAS into the National Airspace System (NAS) cost-effectively.}
\end{itemize}

\begin{figure}
\centering
\includegraphics[scale=0.5]{Archiecture2.pdf}
\caption{A schematic of cellular-connected UAVs for three use cases: drone camera, drone delivery and drone wireless relaying.}\label{F:Archiecture}
\end{figure}

{  The attempt for supporting UAV with cellular networks can be traced back to 2000's via Global System for Mobile Communications (GSM) \cite{976}, while it has received an upsurge of interest in both academia (see, e.g., \cite{949,950,945,978,979}) and industry recently.} For instance, AT\&T and Intel demonstrated the world's first long term evolution (LTE)-connected drone at the 2016 Mobile World Congress. In August 2016, Ericsson and China Mobile conducted what they called the world's first 5G-enabled drone prototype field trial in WuXi of China. In September 2016, Qualcomm tested the drone operation over commercial LTE networks, and a trial report on LTE UAS was released in May 2017.\footnote{Qualcomm, ``LTE unmanned aircraft systems'', Trial Report, May, 2017.} In early 2017, 3GPP approved a new work item for the study on enhanced support for aerial vehicles using LTE, and a series of proposals on technical innovations have been released since then.

Note that among the numerous UAV applications, UAV-enabled airborne communication has attracted extensive research attention recently \cite{649}, \cite{913}. Under this paradigm, dedicated UAVs are employed as aerial BSs, access points (APs), or relays, to assist the wireless communications of ground nodes, which we refer to as {\it UAV-assisted wireless communication}. The two paradigms of cellular-connected UAV communication and UAV-assisted terrestrial communication share both similarities (e.g., in terms of ground-UAV channel characteristics and interference) as well as essential differences. In particular, the roles of UAVs in these two paradigms are swapped: as BSs/APs/relays in UAV-assisted wireless communication versus  as cellular UEs in cellular-enabled UAV communication.  The main objective of this article is to give a new and state-of-the-art overview on the promising technology of cellular-connected UAV communication. The unique communication and spectrum requirements of such systems will be  discussed first, followed by the new design considerations and key promising technologies to enable our envisioned future generation of  heterogeneous wireless networks with coexisting terrestrial and aerial users in the three-dimensional (3D) space. We will further provide numerical results to corroborate our discussions and finally outline promising directions for further research.

\section{Unique Communication and Spectrum Requirement}
With UAVs as new aerial UEs, cellular-connected UAV has significantly different communication and spectrum requirements as compared to the traditional cellular communication with terrestrial users only.

\subsection{Basic Communication Requirement}
The basic communication requirements of UAS can be broadly classified into two categories: {\it control and non-payload communication} (CNPC) and {\it payload communication}.

CNPC refers to the two-way communications between unmanned aircraft and ground control station (or remote pilot) to ensure safe, reliable, and effective flight operation. Typical CNPC messages include:

\begin{itemize}
 \item Telemetry report (such as the flight altitude and velocity) from the UAV to the ground;

 \item Real-time remote C\&C for non-autonomous UAVs and regular flight command update (such as waypoint update) for (semi-)autonomous UAVs;

 \item Navigation aids as well as sense-and-avoid (S\&A) related information;

 \item Air traffic control (ATC) information relaying.
  \end{itemize}
 CNPC is usually of low data rate requirement (say, hundreds of Kbps), but has rather stringent requirement on ultra-reliability, high security, and low latency.

On the other hand, payload communication refers to all mission-related information transmission between UAV and ground users, such as the real-time video, image, and relaying data transmission. For instance, for the particular aerial videography application, the UAV needs to timely transmit the captured video to the end users via payload communications. Compared to CNPC, UAV payload communication usually has much higher data rate requirement. For instance, to support the  transmission of full high-definition (FHD) video from the UAV to the ground user, the transmission rate is about several Mbps, while for 4K video, it is higher than 30 Mbps. The rate requirement in the UAV-enabled  airborne communication can be even higher, e.g., up to dozens of Gbps for wireless backhauling.

\subsection{Spectrum for Cellular-Connected UAV}
The lost of CNPC link has potentially catastrophic consequences. Therefore, the International Civil Aviation Organization (ICAO) has determined that CNPC links of UAV must operate over protected aviation spectrum \cite{943}. However, this was not achieved by most existing UAS with the simple direct UAV-to-ground communication over unlicensed spectrum. Furthermore, International Telecommunication Union (ITU) studies have revealed that to support CNPC for the forecasted number of UAVs in the coming years, a maximum of 34 MHz terrestrial spectrum and 56 MHz satellite spectrum is needed for supporting both LoS and beyond LoS (BLoS) UAV operations.\footnote{ITU, ``Characteristics of unmanned aircraft systems and spectrum requirements to support their safe operation in nonsegregated airspace,'' Tech. Rep. M.2171, DEC., 2009.} To meet such requirement, the C-band spectrum at 5030-5091 MHz has been made available for UAV CNPC at WRC-12 (World Radiocommunication Conference). More recently, the WRC-15 decided that ``assignments to stations of geostationary Fixed Satellite Service (FSS) networks may be used for UAS CNPC links''.\footnote{``Resolution 155 (WRC-15),'' available online at https://www.itu.int/en/ITU-R/space/snl/Documents/RES-155.pdf.}

Cellular-connected UAV has the potential to enable both LoS and BLoS UAV operations without relying on satellite. {  To meet the spectrum regulation and bandwidth requirement for CNPC, one viable approach is to license the C-band spectrum to cellular operators exclusively for CNPC links, which, together with the cellular core network, can enable BLoS C\&C for UAVs.  On the other hand, UAVs may share the common cellular spectrum pool, such as the LTE spectrum and the forthcoming 5G spectrum, with the conventional ground UEs for payload communications, as long as the interference between aerial and ground UEs is properly controlled.}

\section{New Design Considerations}\label{sec:newConsideration}
{  Cellular-connected UAV calls for a paradigm shift on the design of cellular and UAV communication systems, to enable the efficient coexistence between conventional ground UEs and the new aerial UEs. Specifically, the following new considerations need to be taken into account.}

 {\bf 3D Coverage:}
  Compared to conventional ground UEs,  UAVs typically have much higher altitude, which may even significantly exceed the BS antenna height. As a result, BSs need to be able to offer a new 3D communication coverage, as opposed to the conventional two dimensional (2D) ground coverage. However, existing BS antennas are usually tilted downwards, either mechanically or electronically, to cater for the ground coverage with reduced inter-cell interference. Despite of this, preliminary field measurement results by Qualcomm have demonstrated satisfactory aerial coverage by BS antenna sidelobes for UAVs below 120 meters (m). However, as the altitude further increases, new solutions are needed to reshape the cellular BSs to seamlessly cover the sky. For scenarios where ubiquitous 3D coverage is not attainable or simply unnecessary, e.g., for aerial pipe inspection, the concept of ``UAV highway'' may be utilized by ensuring coverage at high altitude only along certain fixed aerial corridors. {  Besides, to further improve coverage beyond sidelobes, UAV relaying via air-to-air communications will be useful.}

{\bf Unique Channel Characteristics:}
 Different from the conventional terrestrial systems, the high UAV altitude leads to unique UAV-BS channels, which usually constitute strong LoS links. For urban environment with high-rise buildings, the LoS link may be occasionally blocked, while the LoS probability typically increases with the UAV altitude.
  Such  unique channel characteristics bring both new opportunities and challenges for the design of cellular-connected UAV communication. On one hand, the presence of LoS links usually results in strong communication channel between UAV and the associated serving BS. On the other hand, the dominance of LoS links makes the inter-cell interference a more critical issue for cellular systems with hybrid aerial and terrestrial UEs, as further discussed next.

{\bf Severe Aerial-Ground Interference:}
  {  One major challenge to ensure the efficient coexistence between  ground  and aerial UEs lies in the severe aerial-ground interference, which is illustrated in  Fig.~\ref{F:AerialInterference}. Compared to that in conventional terrestrial systems, the interference in cellular-connected UAV systems is aggravated by the LoS-dominated UAV-BS channels at high UAV altitude.} For downlink communication from BS to UAV,\footnote{We follow the convention to use ``downlink'' to refer to the communication from BSs to UEs and ``uplink'' to that in the reverse direction, although UEs may have higher altitude than BSs in cellular-connected UAV systems.} each UAV may receive severe interference from a large number of neighboring BSs that are not associated with it, due to strong LoS-dominated channels. As a result, it is expected that an aerial UE in general would have poorer downlink performance than a ground UE, as will be verified by simulations in Section~\ref{sec:simulation}.  On the other hand, in the uplink communication from UAV to BS, the UAV could also pose strong interference to many adjacent but non-associated BSs and result in a new ``exposed BS'' interference issue. Thus, devising effective interference mitigation techniques by taking into account the unique UAV-BS channel and interference characteristics is crucial to cellular-connected UAV systems.

\begin{figure}
\centering
\includegraphics[scale=0.4]{AerialInterference}
\caption{Severe uplink UAV-to-BS and downlink BS-to-UAV interferences due to the LoS-dominated UAV-BS channels at high UAV altitude.}\label{F:AerialInterference}
\end{figure}

 {\bf Asymmetric Uplink/Downlink Traffic Requirement:}
 Different from the current cellular network, which is mainly designed for supporting the more dominant downlink (as opposed to uplink) traffic, cellular-connected UAV communications in general need to support much higher data rate in the uplink transmission from the UAV to BSs, especially for certain rate demanding applications such as video streaming and aerial imaging. {  Therefore, additional study is needed to evaluate the feasibility of supporting such asymmetric traffic requirements with existing LTE systems, with potentially dense UAV deployment. Furthermore, for future 5G-and-beyond cellular systems, new technologies can be developed to address the unique UAV traffic requirement more efficiently. One possible solution is to use drastically different bands for uplink and downlink communications, such as the conventional sub-6 GHz for UAV downlink whereas the largely under-utilized millimeter wave (mmWave) spectrum for UAV uplink.}

\section{Promising Technologies}
In this section, we discuss several promising technologies to efficiently enable future wireless systems with hybrid terrestrial and aerial users.

{\bf Sub-Sector in Elevation Domain:}
Cell sectorization is an effective technique to increase the cellular capacity by reducing inter-cell interference using directional antennas with properly designed patterns. Current cellular BSs mostly consist of three sectors along the horizontal plane, using sectorized antenna with $120^\circ$ opening. The sectorization technique can be extended to construct sub-sectors in the elevation domain for aerial users. Specifically, for each horizontal sector in current cellular systems, the intended 3D coverage volume is further partitioned into several regions (or sub-sectors) based on the elevation angles. Each sub-sector is then covered by a 3D directional antenna with appropriately designed azimuth and elevation beamwidths.
 The sub-sector partition needs to be carefully designed by taking into account the required  coverage altitude range and the affordable UAV handoff frequency due to high mobility.

{\bf 3D Beamforming:} Compared to cell sectorization using directional antennas with fixed antenna patterns, 3D beamforming is a more flexible technique that adaptively designs the antenna beamforming based on the UAV location or even instantaneous channel state information (CSI). In this case, the BS needs to be equipped with full dimensional (FD) antenna array, such as uniform planar array (UPA), with active array elements.
 Different from the conventional 2D beamforming with fan-shaped beam, which can be realized by 1D array such as uniform linear array (ULA), 3D beamforming offers more refined angle resolutions in both azimuth and elevation dimensions and results in pencil-shaped beam. This thus helps significantly enhance the interference mitigation capability by exploiting the elevation angle separations of UAVs. Note that 3D beamforming has also received notable interest in conventional cellular networks \cite{946}. However, the large variation range of the elevation angles of UAVs and the dominance of the LoS UAV-BS channels make 3D beamforming especially appealing for cellular-connected UAV systems. Specifically, compared to conventional cellular networks with terrestrial UEs only, it is more likely to find two UEs with sufficiently separated elevation angles in systems with both aerial and ground UEs, thus making 3D beamforming more effective.

{\bf Multi-Cell Cooperation:} The LoS-dominating characteristic of UAV-BS channels brings new opportunities for multi-cell cooperation. Specifically, as the UAV at higher altitude is likely to have strong LoS links with more neighboring BSs, cellular-connected UAVs potentially can enjoy larger macro-diversity gain brought by multi-cell cooperation than conventional terrestrial users. There are in general two forms of multi-cell cooperation: {\it coordinated resource allocation} and {\it coordinated multi-point (CoMP) transmission/reception}. With coordinated resource allocation, the communication resources such as channel assignment, power allocation, beamforming weights and UE-BS association, are jointly optimized across different cells by taking into account the co-channel interference. {  One viable coordination technique is interference alignment, which could be particularly useful to cancel out the LoS interference for UAV systems.} On the other hand, with CoMP transmission/reception, the signals for each UE are jointly transmitted/received by multiple cooperating BSs that form a virtual distributed antenna array.

 While multi-cell cooperation has been extensively studied in conventional cellular systems, its implementation for cellular systems with hybrid aerial and terrestrial users faces new design challenges. In particular, the set of cooperating BSs need to be carefully chosen to achieve a desired trade-off between performance and backhaul overhead, by taking into account the flying status such as UAV speed and altitude, as well as the unique UAV-BS channel characteristics. One appealing approach is to apply the ``UAV-centric'' cell cooperation, where larger-scale multi-cell cooperation is applied for those UAVs with low speed (or relatively slow channel variations) and/or at high altitude (with potentially large macro-diversity gains).

{\bf Ground-Aerial NOMA:} Non-orthogonal multiple access (NOMA) is a promising technology to increase the spectrum efficiency in 5G cellular systems \cite{947}.
 Studies have revealed that compared to conventional orthogonal multiple access (OMA), NOMA yields the highest performance gain when the channel conditions of the users are most different \cite{947}. This makes NOMA a very attractive technology for simultaneously serving the payload communications of UAVs and ground UEs, referred to as {\it ground-aerial NOMA}, thanks to the generally asymmetric channel conditions for these two types of UEs. Consider the power-domain uplink ground-aerial NOMA as an example. As UAVs at high altitude typically have much stronger LoS communication links with the BS than ground UEs given the similar distance, the BSs could first decode the signal from the UAVs while treating that from the ground UEs as noise, and then subtract the decoded UAV signals before decoding the weaker signals for the ground UEs.

\section{Simulation Results and Discussions}\label{sec:simulation}
 As shown in Fig.~\ref{F:setup}(a), we consider a cellular system with 19 sites, each constituting 3 sectors/cells so that a total of 57 cells are considered. The cell indices are labeled in the figure. The 3GPP urban macro (UMa) scenario is considered, where the inter-site distance (ISD) is 500 m and the corresponding cell radius is 166.7 m. We consider two different array configurations at each cell: {\it fixed pattern} versus {\it 3D beamforming}. With fixed pattern, a ULA of size  $(M,N)=(8,1)$ is employed at each sector, where $M$ and $N$ denote the number of antenna elements along the vertical and horizontal dimension, respectively. For this configuration, the steering magnitude and phase of each antenna element is fixed to achieve a $10^\circ$ electrical downtilt. On the other hand, with 3D beamforming, each sector is equipped with a UPA of size $(M,N)=(8,4)$, and the signal magnitude and phase by each antenna element can be flexibly designed to enable 3D beamforming.  For both array configurations, adjacent antenna elements are separated by half wavelength, and the antenna element pattern follows from the 3GPP technical specification\footnote{3GPP TR38.901, ``Study on channel model for frequencies from 0.5 to 100 GHz'', V14.0.0.}, with half-power beamwidth given by $65^\circ$ both along the azimuth and elevation dimensions.  All relevant system parameters are summarized in Fig.~\ref{F:setup}(b).

\begin{figure}
\centering
\begin{subfigure}{0.45\textwidth}
\centering
\includegraphics[width=\textwidth]{CellLayout.pdf}
\caption{Cell layout. Arrows denote boresight of each cell.}
\end{subfigure}
\hspace{0.02\textwidth}
\begin{subfigure}{0.5\textwidth}
\centering
{\footnotesize \setstretch{1} \begin{tabular}{p{0.32\textwidth}|p{0.68\textwidth}}
\hline
BS antenna height & 25 m \\
\hline
Carrier frequency & 5 GHz for UAV C\&C and 2 GHz for others \\
\hline
Channel bandwidth & 1 MHz \\
\hline
Transmit power by each cell& 20 dBm, equally allocated among associated UEs \\
\hline
BS antenna element pattern & 3GPP TR38.901 V14.0.0 \\
\hline
 Array configuration at each cell & {\it Fixed pattern:} $8 \times 1$ ULA, $10^\circ$ downtilt; \newline {\it 3D beamforming:} $8\times 4$ UPA\\
\hline
Channel modeling & LoS probability, pathloss and shadowing: 3GPP R1-1714856; \newline  Small-scale fading: 3GPP TR38.901 V14.0.0 with $K=15$ dB\\
\hline
Cell association & {\it Fixed pattern:} Maximum RSRP based on large-scale channel gain; \newline {\it 3D beamforming:} Maximum RSRP with MRT beamforming based on instantaneous CSI \\
\hline
Noise power spectral density & $-174$ dBm/Hz, with 9 dB noise figure \\
\hline
\end{tabular}}
\caption{System parameters.}
\end{subfigure}
\caption{Simulation setup.}\label{F:setup}
\end{figure}

\subsection{UAV C\&C with Dedicated Channel}
First, we consider the downlink C\&C communication from the BS to the UAV. As marked by the red triangle in Fig.~\ref{F:setup}(a), we focus on one particular UAV with horizontal coordinate (250 m, 100 m), i.e., a UE near the edge of cells 1, 5 and 9. {  We assume that one dedicated channel at C-band with carrier frequency 5 GHz is exclusively assigned for this UAV. Therefore, interference issue is not present in this example.} Three UAV altitude values are considered: $H_{\mathrm{ue}}=$ 1.5 m, 90~m, and 200 m. Note that the UE altitude of 1.5 m may correspond to either a benchmark ground UE or a UAV in take-off/landing status.

\begin{figure}
\centering
\begin{subfigure}{0.48\textwidth}
\includegraphics[width=\linewidth]{AssoProbFixedPattern.pdf}
\caption{Fixed BS pattern}
\end{subfigure}
\hspace{0.02\textwidth}
\begin{subfigure}{0.48\textwidth}
\centering
\includegraphics[width=\linewidth]{AssoProb3DBF.pdf}\\
\caption{3D Beamforming}
\end{subfigure}
\caption{Association probability at different UAV altitude.}\label{F:AssoProb}
\end{figure}

Fig.~\ref{F:AssoProb} shows the cell association probability at different UAV altitude, where the maximum reference signal received power (RSRP) association rule is assumed. For fixed BS pattern, the RSRP is calculated based on the large-scale channel gain (pathloss and shadowing), whereas for 3D beamforming,  it is obtained via the maximal-ratio transmission (MRT) beamforming based on instantaneous CSI. It is observed from Fig.~\ref{F:AssoProb}(a) that with fixed BS pattern, the UAV is most likely to be associated with the nearby cells when the altitude is low (e.g., cells 1, 5 and 9 for $H_{\mathrm{ue}}=$ 1.5 m and 90 m). However, as the altitude increases, it is more likely that the associated cell is far away from the UAV, e.g., cells 13, 30 and 56 for $H_{\mathrm{ue}}=$ 200 m. This is expected since for UAV at higher altitude, the elevation angle-of-departures (AoDs) with respect to those nearby BSs are larger, and hence the UAV may more easily fall into the antenna nulls of those nearby BSs due to the downtilted antenna pattern. As a result, the UAV has to be associated with those distant cells via their antenna side lobes. {  Note that similar association results exist for UAV-assisted wireless communications with UAVs acting as aerial platform to serve ground UEs \cite{977}.} In contrast, with 3D beamforming, it is observed from Fig.~\ref{F:AssoProb}(b) that the UAV is almost surely associated with the nearby cells even for high altitude at $H_{\mathrm{ue}}=$ 200 m, thanks to the flexible beam adjustment to focus signals to the UAV with 3D beamforming.

Fig.~\ref{F:SNRCDF} plots the empirical cumulative distribution function (CDF) of the received signal-to-noise ratio (SNR) at the UAV. It is observed that for both fixed pattern and 3D beamforming, higher UAV altitude leads to less SNR variations, which is expected due to the higher LoS probability as the altitude increases. Besides, it is observed that compared to UE at the ground level (i.e., $H_{\mathrm{ue}}=1.5$ m), the worst-case SNRs are significantly improved at high altitude. For example, even with fixed BS pattern, the 5th percentile SNR (below which $5\%$ of the observations are found)  with $H_{\mathrm{ue}}=$ 200 m is about $10$dB higher than that at $1.5$ m, though in the former case, the UAV has to be associated with the more distant cells via their sidelobes as shown in Fig.~\ref{F:AssoProb}(a). This result demonstrates that the benefit of LoS communication link at high UAV altitude well compensates the small antenna gain of the sidelobe, thus validating the feasibility of leveraging existing cellular systems for UAV C\&C at moderate UAV altitude. Furthermore, for $H_{\mathrm{ue}}=$200 m, the SNR is lower than that for $H_{\mathrm{ue}}=90$ m, due to the increased link distance as well as the reduced side lobe gain with increasing $H_{\mathrm{ue}}$. Moreover, by comparing Fig.~\ref{F:SNRCDF}(a) and Fig.~\ref{F:SNRCDF}(b), it is observed that 3D beamforming is able to significantly improve the SNR performance for all UAV altitude, and the performance improvement is more significant for $H_{\mathrm{ue}}=200$ m due to the more dominant LoS communication link.

\begin{figure}
\centering
\begin{subfigure}{0.48\textwidth}
\centering
\includegraphics[width=\linewidth]{SNRCDFFixedPattern.pdf}
\caption{Fixed BS pattern}
\end{subfigure}
\hspace{0.02\textwidth}
\begin{subfigure}{0.48\textwidth}
\includegraphics[width=\linewidth]{SNRCDF3DBF.pdf}
\caption{3D beamforming}
\end{subfigure}
\caption{Empirical CDF of SNR at different UAV altitude.}\label{F:SNRCDF}
\end{figure}

\subsection{Shared Channel by UAV and Ground UE}
{  Next, we consider the multi-user downlink payload communication from BSs to UAVs. We assume that the UAVs reuse the same set of channels with the conventional ground UEs.} We focus on one particular channel that is reused by a total of 20 UEs, out of which $N_{\mathrm{UAV}}$ are aerial UEs. Three values for $N_{\mathrm{UAV}}$  are considered: $N_{\mathrm{UAV}}$= 0, 5 and 10. The horizontal locations of all UEs are uniformly distributed in a circular disk with radius 1000 m. For ground UEs, the altitude is fixed to 1.5 m, whereas for aerial UEs, it is uniformly distributed between 1.5 m and 300 m.

Fig.~\ref{F:SumRateCDF} plots the empirical CDF of the UEs' achievable sum rate for different number of UAVs with fixed BS antenna pattern versus 3D beamforming. First, it is observed that for both array configurations, the overall system spectral efficiency degrades as the number of aerial UEs increases. This is expected since compared to ground UEs, aerial UEs suffer from more severe interference due to the higher LoS probability with the non-associated BSs, and the interference effect overwhelms the benefit of stronger direct link with its associated BS. Therefore, an aerial UE typically has poorer downlink rate performance than a ground UE, as discussed in Section~\ref{sec:newConsideration}. Thus, as the number of aerial UEs increases, the overall spectral efficiency degrades. On the other hand, Fig.~\ref{F:SumRateCDF} shows that by employing 3D beamforming even with the low-complexity MRT scheme, the system spectral efficiency can be significantly improved for all the UAV numbers. For example, for $N_{\mathrm{UAV}}=10$, the 5th percentile UEs' sum rate with fixed pattern is about 30 Mbps, while it significantly increases to more than 68 Mbps with 3D beamforming. This demonstrates the great potential of 3D beamforming for cellular systems with hybrid aerial and ground UEs \cite{978}.

\begin{figure}
\centering
\includegraphics[width=0.6\linewidth]{SumRateCDFCombined.pdf}
\caption{Empirical CDF of UEs' achievable sum rate for different number of UAVs.}\label{F:SumRateCDF}
\end{figure}

\section{Conclusions and Future Directions}

In this article, we provide an overview of UAV/drone communications enabled by cellular networks, for embracing the forthcoming era of  ``Internet of Drones (IoD)''. The potential benefits of cellular-connected UAV communication as well as its unique communication and spectrum requirements are first discussed, as compared with conventional cellular communication with terrestrial users. Then, we focus on elaborating the new design considerations and promising technologies to enable future 3D heterogeneous wireless networks with both aerial and ground users. Simulation results are also provided to corroborate our discussions. Some promising directions for future research are outlined as follows.

{\bf Quality of Service-Aware Trajectory Design:}
Different from the conventional terrestrial UEs, the high and controllable mobility of UAVs offers an additional design degree of freedom via trajectory optimization for cellular-connected UAV systems. For example, for areas where ubiquitous aerial coverage by cellular BSs has not been achieved yet, the UAV trajectory should be properly  planned to avoid entering such coverage holes.
 In general, the UAV trajectories could be jointly optimized with communication resource allocation for various performance metrics, such as spectral efficiency, or energy efficiency by taking into account the UAV's propulsion energy consumption. Another interesting direction is to develop autonomous UAVs, where the positions are self-optimized based on real-time radio measurement \cite{914}.

{\bf Millimeter Wave Cellular-Connected UAV:}
MmWave communication that utilizes the wide available bandwidth above 28 GHz is a promising technology to achieve high-rate UAV communications \cite{948}. While mmWave communication has been extensively investigated for 5G-and-beyond cellular systems, its application in cellular-connected UAV systems faces both new opportunities and challenges. On one hand, as mmWave signals are vulnerable to blockage, the LoS-dominating UAV-BS channels offer the most favorable channel conditions for mmWave communications to be practically applied. On the other hand, the high UAV altitude and mobility requires efficient mmWave beamforming to be developed for 3D mmWave UAV-BS channels.

{\bf Cellular-Connected UAV Swarm:} UAV swarm is an effective UAV operation mode with a group of highly coordinated UAVs to complete a common mission cooperatively.  Due to the large number of UAVs and their close separations, it would be quite challenging and inefficient to connect each individual UAV directly with the cellular BSs. Instead, one promising approach is cellular-assisted U2U (UAV-to-UAV) communications, where the cellular BSs offer the backbone connectivity between the aerial network formed by the UAVs and the cellular core network. Besides, the use of massive MIMO technology for communications with UAV swarms has been recently studied in \cite{951}. More research efforts are needed to investigate the most effective aerial network topologies and the seamless integration of the aerial and cellular networks.

\bibliographystyle{IEEEtran}


text:
\section*{Introduction}
Let $S = K[x_{1}, \ldots, x_{n}]$ denote the polynomial ring in $n$ variables over a field $K$ with each $\deg x_{i} = 1$.  Let $I \subset S$ be a homogeneous ideal of $S$ and
\[
0 \to \bigoplus_{j \geq 1} S(-j)^{\beta_{h, j}} \to \cdots \to \bigoplus_{j \geq 1} S(-j)^{\beta_{1, j}} \to S \to S/I \to 0
\]
a (unique) graded minimal free $S$-resolution of $S/I$.  The ({\em Castelnuovo-Mumford}\,) {\em regularity} of $S/I$ is
\[
\reg (S/I) = \max\{ j - i : \beta_{i, j} \neq 0 \}.
\]
We say that $S/I$ has a {\em $q$-linear resolution} if $\beta_{i, j} = 0$ for each $1 \leq i \leq h$ and for each $j \neq q + i - 1$.  If $S/I$ has a $q$-linear resolution, then $\reg(S/I) = q - 1$ and $I$ is generated by homogeneous polynomials of degree $q$.  We refer the reader to, e.g., \cite{BH} and \cite{HHO} for the detailed information about regularity and linear resolutions.

The edge ring and the edge polytope of a finite connected simple graph together with its toric ideal has been studied by many articles.  Their foundation was established in \cite{OH, 2linear}. Moreover, several papers on the minimal free resolutions of edge rings are published, see e.g. \cite{BOV,GM,HKO,HMT,Koszulbipartite,2linear}. In particular, in \cite[Theorem 4.6]{2linear} it is shown that the edge ring $K[G]$, where $K$ is a field, of a finite connected simple graph $G$ on $[N] = \{ 1, \ldots, N \}$ has a $2$-linear resolution if and only if $K[G]$ is isomorphic to the polynomial ring in $N - \delta$ variables over the Segre product $K[x_1, x_2] \sharp K[y_1, \ldots, y_\delta]$ of two polynomial rings $K[x_1, x_2]$ and $K[y_1, \ldots, y_\delta]$, where $\delta$ is the normalized volume (\cite[p.~36]{Stu}) of the edge polytope ${\mathcal P}_G$ of $G$.  On the other hand, in \cite[Theorem 0.1]{HMT} it is shown that if the edge ring $K[G]$ of a finite connected simple graph $G$ has a $3$-linear resolution, then $K[G]$ is a hypersurface. Moreover, the following conjecture is given.
\begin{Conjecture}[{\cite[Conjecture 0.2]{HMT}}]
	\label{conj}
The edge ring of a finite connected simple graph with a $q$-linear resolution, where $q \geq 3$, is a hypersurface.
\end{Conjecture}

In the present paper, we solve Conjecture \ref{conj} for the case of bipartite graphs. In fact,
\begin{Theorem}
	\label{thm:main}
	The edge ring of a finite connected simple bipartite graph with a $q$-linear resolution, where $q \geq 3$, is a hypersurface.
\end{Theorem}
The edge rings of bipartite graphs and the associated lattice polytopes, which are called the edge polytopes (or root polytopes) play particularly important roles in commutative algebra and combinatorics, e.g., see \cite{KalPos,Koszulbipartite}.

In the present paper, after preparing necessary materials on edge polytopes and edge rings (Section \ref{sec:edge}), Theorem \ref{thm:main} will be proved in Section \ref{sec:proof}.

\subsection*{Acknowledgment}
The author was partially supported by JSPS KAKENHI 19K14505 and 19J00312.

\section{Edge polytopes and Edge rings}
\label{sec:edge}
A {\em lattice polytope} is a convex polytope all of whose coordinates have integer coordinates.  Let ${\mathcal P} \subset {\NZQ R}^N$ be a lattice polytope of dimension $d$ and ${\mathcal P} \cap {\NZQ Z}^N=\{{\bold a}_1,\ldots,{\bold a}_n \}$.  Let $K$ be a field and $K[{\bold t}^{\pm1}, s]=K[t_1^{\pm1},\ldots,t_N^{\pm 1},s]$ the Laurent polynomial ring in $N + 1$ variables over $K$.  Given a lattice point  ${\bold a}=(a_1,\ldots,a_N) \in {\NZQ Z}^N$, we write ${\bold t}^{{\bold a}}$ for the Laurent monomial $t_1^{a_1}\cdots t_N^{a_N} \in K[{\bold t}^{\pm 1}, s]$.  The \textit{toric ring} $K[{\mathcal P}]$ of ${\mathcal P}$ is the subalgebra of $K[{\bold t}^{\pm 1},s]$ which is generated by those monomials ${\bold t}^{{\bold a}_1}s,\ldots,{\bold t}^{{\bold a}_n}s$ over $K$.  Let $K[{\bold x}]=K[x_1,\ldots,x_n]$ denote the polynomial ring in $n$ variables over $K$ with each $\deg x_i=1$, and define the surjective ring homomorphism $\pi:K[{\bold x}] \to K[{\mathcal P}]$ by setting $\pi(x_i)={\bold t}^{{\bold a}_i}s$ for $1 \leq i \leq n$.  The kernel $I_{{\mathcal P}}$ of $\pi$ is called the \textit{toric ideal} of ${\mathcal P}$.

Let $G$ be a finite simple graph on the vertex set $V(G)=[N]$ with the edge set $E(G)=\{e_1,\ldots,e_n\}$.  (A finite graph $G$ is called simple if $G$ possesses no loop and no multiple edge.) Let ${\bold e}_1,\ldots,{\bold e}_N$ denote the canonical unit coordinate vectors of ${\NZQ R}^N$.  Given an edge $e=\{i,j\}$ of $G$, we set $\rho(e)={\bold e}_i+{\bold e}_j \in {\NZQ R}^{N}$.  The \textit{edge polytope}  ${\mathcal P}_G$ of $G$ is the lattice polytope which is the convex hull of $\{\rho(e_1),\ldots,\rho(e_n)\}$ in ${\NZQ R}^N$.
The edge polytope ${\mathcal P}_G$ of a finite simple bipartite graph $G$ is also called the \textit{root polytope} of $G$.
One has $\dim {\mathcal P}_G = N - c_0(G)-1$, where $c_0(G)$ is the number of connected bipartite components of $G$ (\cite[p. 57]{VV}). In particular, if $G$ is connected and bipartite, then $\dim {\mathcal P}_G = N - 2$.
The \textit{edge ring} $K[G]$ of $G$ is the toric ring of ${\mathcal P}_G$, that is, $K[G]=K[{\mathcal P}_G]$ and the toric ideal $I_G$ of $K[G]$ is the toric ideal of ${\mathcal P}_{G}$, that is, $I_{G} = I_{{\mathcal P}_{G}}$.
When the edge ring $K[G]$ of a finite simple graph $G$ is studied, we follow the convention of assuming that $G$ is connected.  Let $G$ be a finite disconnected simple graph with the connected components $G_1, G_2, \ldots, G_s$ and suppose that each $G_i$ has at least one edge.  Then the edge ring of $G$ is
$
K[G] = K[G_{1}] \otimes_{K} \cdots \otimes_{K} K[{G_{s}}]
$ and its toric ideal is
\[
(I_{G_1}, I_{G_2}, \ldots, I_{G_s})
\subset K[x_1^{(1)}, \ldots, x_{n_1}^{(1)}, x_1^{(2)}, \ldots, x_{n_2}^{(2)}, \ldots, x_1^{(s)}, \ldots, x_{n_s}^{(s)}].
\]
Let, say, $I_{G_1} \neq (0)$ and $I_{G_2} \neq (0)$.  Then $K[G]$ cannot have a linear resolution.  Hence $K[G]$ has a $q$-linear resolution if and only if there is $1 \leq i \leq s$ for which $K[G_i]$ has a $q$-linear resolution and each $K[G_j]$ with $i \neq j$ is the polynomial ring.

Recall from \cite{2linear} what a system of generators of the toric ideal $I_G$ of a finite connected simple bipartite graph is.
Let $C$ be an even cycle of $G$ with the edge set
\[
E(C)=\{e_{i_1},\ldots,e_{i_{2n}}\},
\]
where for $1 \leq j \leq 2n-1$, $e_{i_j}=\{v_{j},v_{j+1}\}$ and $e_{i_{2n}}=\{v_{2n},v_{1}\}$.
We write $f_C$ for the binomial
\[
f_C=\prod_{j=1}^{n}x_{i_{2j-1}}-\prod_{j=1}^{n}x_{i_{2j}}
\]
belonging to $I_G$, where $\pi(x_i)={\bold t}^{\rho(e_i)}s$.
\begin{Lemma}[{\cite[Corollary 5.12]{HHO}}]
	The toric ideal $I_G$ of a finite connected simple bipartite graph $G$ is generated by those binomials $f_{C}$, where $C$ is an even cycle of $G$.
\end{Lemma}

As a result, it follows that

\begin{Lemma}\label{lem:gen}

Let $G$ be a finite connected simple bipartite graph. Assume that $I_G$ is generated by homogeneous polynomials of degree $n$. Then $G$ has no even cycles of length $< 2n$. In particular, $I_G$ is generated by $\{f_{C} : C \mbox{ is an even cycle of length } 2n\}$.
\end{Lemma}

Next, we recall Ehrhart theory of lattice polytopes. Let ${\mathcal P} \subset {\NZQ R}^N$ be a lattice polytope of dimension $d$.  The {\em $h^*$-polynomial} (or {\em $\delta$-polynomial}) of ${\mathcal P}$ is the polynomial
\[
h^*({\mathcal P},\lambda)=(1-\lambda)^{d+1} \left[ 1+ \sum_{t=1}^{\infty} |t{\mathcal P} \cap {\NZQ Z}^N | \lambda^t \right]
\]
in $\lambda$, where $t{\mathcal P}=\{t {\bold a} : {\bold a} \in {\mathcal P} \}$.  Each coefficient of $h^*({\mathcal P}, \lambda)$ is a nonnegative integer and the degree of $h^*({\mathcal P}, \lambda)$ is at most $d$. Let $\deg({\mathcal P})$ denote the degree of $h^*({\mathcal P},\lambda)$ and set $\codeg({\mathcal P})=d+1-\deg({\mathcal P})$.
It then follows that
\[
\codeg({\mathcal P})= \min \{r \in {\NZQ Z}_{\geq 1} : \text{int}(r{\mathcal P})\cap {\NZQ Z}^{N} \neq \emptyset \},
\]
where $\text{int}({\mathcal P})$ is the relative interior of ${\mathcal P}$ in ${\NZQ R}^N$ and where ${\NZQ Z}_{\geq 1}$ stands for the set of positive integers.  We refer the reader to \cite[Part II]{HibiRedBook} for the detailed information about $\delta$-polynomials and their related topics.

From
\cite{S}  we obtain the following:
\begin{Lemma}[{\cite[Corollary 3.2]{HMT}}]
	\label{lem:deg}
	Let $G$ be a finite connected simple graph and let $G' \subset G$ be a  subgraph of $G$.  Then $\deg({\mathcal P}_{G'}) \leq \deg ({\mathcal P}_{G})$.
\end{Lemma}

On the other hand, from {\cite[p. 5952]{HKN}}
one has the following:
\begin{Lemma}[{\cite[Corollary 3.4]{HMT}}]
	\label{lem:reg}
	Let $G$ be a finite connected simple graph on $[N]$.
	Then
	\[
	\reg (K[{\mathcal P}_G]) \ge \deg ({\mathcal P}_G).
	\]
\end{Lemma}

\section{Proof of main theorem}
\label{sec:proof}
Let $G$ be a finite connected simple bipartite graph on $[N]$ such that $K[G]$ has a $q$-linear resolution with $q \geq 3$.
Then it follows that ${\rm reg}(K[G])=q-1$ and $I_G$ is generated by homogeneous polynomials of degree $q$. Hence in order to prove Theorem \ref{thm:main}, from Lemma \ref{lem:gen}, we should show that	 if $G$ has no even cycles of length $< 2q$ and has at least two even cycles of length $2q$,
	then we obtain ${\rm reg}(K[G]) \geq q$.

\begin{Lemma}
\label{lem:disjoint}
	If $G$ has disjoint two even cycles of length $2q$, then we obtain $\deg {\mathcal P}_G \geq q$.
\end{Lemma}

\begin{proof}
	Let $G'$ be a finite simple graph on $[4q]$ with the edge set
	$E(G')=\{ e_1,\ldots,e_{4q}\}$,
	where $e_i=\{i,i+1\}$ for $1 \leq i \leq 4q-1$ with $i \neq 2q$ and $e_{2q}=\{2q,1\}$ and $e_{4q}=\{4q,2q+1\}$.
	Namely, $G'$ is the disjoint union of two even cycles of length $2q$.
	Then one has $\dim {\mathcal P}_{G'}=4q-3$.
	Since
	\[
	\dfrac{1}{2}\sum_{i=1}^{4q} \rho (e_i)={\bold e}_1+\cdots+{\bold e}_{4q} \in {\rm int}(2q {\mathcal P}_{G'}) \cap {\NZQ Z}^{4q},
	\]
	we obtain  ${\rm codeg}({\mathcal P}_{G'}) \leq 2q$.
	Hence it follows that
	\[
	{\rm deg}({\mathcal P}_{G'})=\dim {\mathcal P}_{G'} + 1 - {\rm codeg}({\mathcal P}_{G'}) \geq 4q-3+1-2q=2q-2 \geq q.
	\]
	Therefore, from Lemma \ref{lem:deg}, one has $\deg ({\mathcal P}_G) \geq \deg({\mathcal P}_{G'}) \geq q$, as desired.
\end{proof}

\begin{Lemma}
\label{lem:twocycles}
If $G$ has two even cycles of length $2q$ which have precisely one common vertex, then we obtain $\deg {\mathcal P}_G \geq q$.
\end{Lemma}
\begin{proof}
 Let $G'$ be a connected finite simple graph on $[4q-1]$ with the edge set $E(G')=\{e_1,\ldots, e_{4q} \}$, where
	\[
	e_i=\begin{cases}
		\{i,i+1\} & 1 \leq i \leq 2q-1,\\
		\{2q,1 \} & i=2q,\\
		\{1,2q+1\} &i=2q+1,\\
		\{i-1,i\} & 2q+2 \leq i \leq 4q-1,\\
		\{4q-1,1\} & i=4q.
	\end{cases}
	\]

Since $G'$ is connected and bipartite, It follows that $\dim {\mathcal P}_{G_k}=4q-3$.
Since
\begin{displaymath}
	\begin{aligned}
		&	\sum_{i=1}^{2q} \left(\dfrac{1}{3} \rho(e_{2i-1}) + \dfrac{2}{3}\rho(e_{2i})\right)\\
		=&2{\bold e}_1+{\bold e}_2+\cdots+{\bold e}_{4q-1} \in {\rm int}(2q{\mathcal P}_{G'}) \cap {\NZQ Z}^{4q-1},
	\end{aligned}
\end{displaymath}
one has
	\[
	{\rm deg}({\mathcal P}_{G'}) \geq 4q-3+1 -2q=2q-2 \geq q.
	\]
Hence from Lemma \ref{lem:deg} we obtain $\deg {\mathcal P}_G \geq \deg {\mathcal P}_{G'} \geq q$, as desired.
	\end{proof}

	\begin{Lemma}
\label{lem:even}
Given positive integers $k$ and $m$ with $k+m \geq q$ and $k \leq m$,  let $G^{(e)}_{k,m}$ be a connected finite simple bipartite graph on $[2q+2m-1]$ with the edge set $E(G^{(e)}_{k,m})=\{e_1,\ldots,e_{2q+2m} \}$, where 	\[
	e_i=\begin{cases}
		\{i,i+1\} & 1 \leq i \leq 2q-1,\\
		\{2q,1 \} & i=2q,\\
		\{1,2q+1\} &i=2q+1,\\
		\{i-1,i\} & 2q+2 \leq i \leq 2q+2m-1,\\
		\{2q-2m-1,2k+1\} & i=2q+2m,
	\end{cases}
	\]
see {\rm FIGURE 1}.
Then we obtain $\deg {\mathcal P}_{G^{(e)}_{k,m}} \geq q$.
	\end{Lemma}
		\begin{figure}[h]
	\label{fig:even}
	\caption{$G^{(e)}_{k,m}$}
	\begin{tikzpicture}
	\coordinate (v1) at (90:3) node at (v1) [above] {$1$};
	\coordinate (v2) at (120:3) node at (v2) [above] {$2$};
	\coordinate (v3) at (150:3) node at (v3) [left] {$3$};
	\coordinate (v4) at (210:3) node at (v4) [left] {$2k-1$};
	\coordinate (v5) at (240:3) node at (v5) [below] {$2k$};
	\coordinate (v6) at (270:3) node at (v6) [below] {$2k+1$};
	\coordinate (v7) at (300:3) node at (v7) [right] {$2k+2$};
	\coordinate (v8) at (330:3) node at (v8) [right] {$2k+3$};
	\coordinate (v9) at (30:3) node at (v9) [right] {$2q-1$};
	\coordinate (v10) at (60:3) node at (v10) [above] {$2q$};
	\coordinate (v11) at (90:2) node at (v11) [right] {$2q+1$};
	\coordinate (v12) at (90:1) node at  (v12) [right] {$2q+2$};
	\coordinate (v13) at (270:1) node at (v13) [right] {$2q-2m-2$};
	\coordinate (v14) at (270:2) node at (v14) [right] {$2q-2m-1$};
	\coordinate (v15) at (90:0.75);
	\coordinate (v16) at (270:0.75);
	\coordinate (e1) at (105:3) node at (e1) [above] {$e_1$};
	\coordinate (e2) at (130:3) node at (e2) [left] {$e_2$};
	\coordinate (e3) at (230:3) node at (e3) [left] {$e_{2k-1}$};
	\coordinate (e4) at (254:3) node at (e4) [below] {$e_{2k}$};
	\coordinate (e5) at (290:3) node at (e5) [below] {$e_{2k+1}$};
	\coordinate (e6) at (314:3) node at (e6) [right] {$e_{2k+2}$};
	\coordinate (e7) at (45:3) node at (e7) [right] {$e_{2q-1}$};
	\coordinate (e8) at (75:3) node at (e8) [above] {$e_{2q}$};
	\coordinate (e9) at (90:2.5) node at (e9) {$e_{2q+1}$};
	\coordinate (e10) at (90:1.5) node at (e10)  {$e_{2q+2}$};
	\coordinate (e11) at (270:1.5) node at (e11)  {$e_{2q+2m-1}$};
	\coordinate (e12) at (270:2.5) node at (e12)  {$e_{2q+2m}$};
	\draw
	(20:3) arc (20:160:3cm)
	(200:3) arc (200:340:3cm)
	(v1)--(v15)
	(v6)--(v16)
	;
\fill
(v1) circle (2pt)
(v2) circle (2pt)
(v3) circle (2pt)
(v4) circle (2pt)
(v5) circle (2pt)
(v6) circle (2pt)
(v7) circle (2pt)
(v8) circle (2pt)
(v9) circle (2pt)
(v10) circle (2pt)
(v11) circle (2pt)
(v12) circle (2pt)
(v13) circle (2pt)
(v14) circle (2pt)
(180:3) circle (1pt)
(170:3) circle (1pt)
(190:3) circle (1pt)
(350:3) circle (1pt)
(0:3) circle (1pt)
(10:3) circle (1pt)
(0:0) circle (1pt)
(90:0.5) circle (1pt)
(270:0.5) circle (1pt)
;
    \end{tikzpicture}
	\end{figure}

	\begin{proof}
	Since ${\mathcal P}_{G^{(e)}_{k,m}}$ is bipartite and connected, one has $\dim {\mathcal P}_{G^{(e)}_{k,m}}=2q+2m-3$.
		Moreover, since
	\begin{displaymath}
	\begin{aligned}
		&	\sum_{i=1}^{k} \left(\dfrac{1}{3} \rho(e_{2i-1}) + \dfrac{2}{3}\rho(e_{2i}) \right)\\+&\sum_{i=k+1}^{q} \left(\dfrac{2}{3} \rho(e_{2i-1}) + \dfrac{1}{3}\rho(e_{2i})\right)
		\\+&\sum_{i=q+1}^{q+m} \left(\dfrac{1}{3} \rho(e_{2i-1}) + \dfrac{2}{3}\rho(e_{2i})\right)	\\=&{\bold e}_1+{\bold e}_2+\cdots+{\bold e}_{2q+2m-1}+{\bold e}_{2k+1} \in {\rm int}((q+m){\mathcal P}_{G^{(e)}_{k,m}}) \cap {\NZQ Z}^{2q+2m-1}
	\end{aligned}
\end{displaymath}
and since $m \geq q/2$,
we obtain $\deg {\mathcal P}_{G^{(e)}_{k,m}} \geq 2q+2m-3+1-q-m=q+m-2 \geq  3q/2 -2$.
If $q=3$, then $\deg {\mathcal P}_{G^{(e)}_{k,m}} \geq 3 > 5/2$. Moreover, if $q \geq 4$, then $\deg {\mathcal P}_{G^{(e)}_{k,m}} 3q/2 -2 \geq q$, as desired.
	\end{proof}

	\begin{Lemma}
		\label{lem:odd}
		Given positive integers $k$ and $m$ with $k+m-1 \geq q$ and $k \leq m$,  let $G^{(o)}_{k,m}$ be a connected finite simple bipartite graph on $[2q+2m-2]$ with the edge set $E(G^{(o)}_{k,m})=\{e_1,\ldots,e_{2q+2m-1} \}$, where 	\[
	e_i=\begin{cases}
		\{i,i+1\} & 1 \leq i \leq 2q-1,\\
		\{2q,1 \} & i=2q,\\
		\{1,2q+1\} &i=2q+1,\\
		\{i-1,i\} & 2q+2 \leq i \leq 2q+2m-2,\\
		\{2q-2m-2,2k\} & i=2q-2m-1,
	\end{cases}
	\]
see {\rm FIGURE 2}.
Then we obtain $\deg {\mathcal P}_{G^{(o)}_{k,m}} \geq q$.
	\end{Lemma}
	\begin{figure}[h]
	\label{fig:odd}
	\caption{$G^{(o)}_{k,m}$}
	\begin{tikzpicture}
	\coordinate (v1) at (90:3) node at (v1) [above] {$1$};
	\coordinate (v2) at (120:3) node at (v2) [above] {$2$};
	\coordinate (v3) at (150:3) node at (v3) [left] {$3$};
	\coordinate (v4) at (210:3) node at (v4) [left] {$2k-2$};
	\coordinate (v5) at (240:3) node at (v5) [below] {$2k-1$};
	\coordinate (v6) at (270:3) node at (v6) [below] {$2k$};
	\coordinate (v7) at (300:3) node at (v7) [right] {$2k+1$};
	\coordinate (v8) at (330:3) node at (v8) [right] {$2k+2$};
	\coordinate (v9) at (30:3) node at (v9) [right] {$2q-1$};
	\coordinate (v10) at (60:3) node at (v10) [above] {$2q$};
	\coordinate (v11) at (90:2) node at (v11) [right] {$2q+1$};
	\coordinate (v12) at (90:1) node at  (v12) [right] {$2q+2$};
	\coordinate (v13) at (270:1) node at (v13) [right] {$2q-2m-3$};
	\coordinate (v14) at (270:2) node at (v14) [right] {$2q-2m-2$};
	\coordinate (v15) at (90:0.75);
	\coordinate (v16) at (270:0.75);
	\coordinate (e1) at (105:3) node at (e1) [above] {$e_1$};
	\coordinate (e2) at (130:3) node at (e2) [left] {$e_2$};
	\coordinate (e3) at (230:3) node at (e3) [left] {$e_{2k-2}$};
	\coordinate (e4) at (255:3) node at (e4) [below] {$e_{2k-1}$};
	\coordinate (e5) at (290:3) node at (e5) [below] {$e_{2k}$};
	\coordinate (e6) at (315:3) node at (e6) [right] {$e_{2k+1}$};
	\coordinate (e7) at (45:3) node at (e7) [right] {$e_{2q-1}$};
	\coordinate (e8) at (75:3) node at (e8) [above] {$e_{2q}$};
	\coordinate (e9) at (90:2.5) node at (e9)  {$e_{2q+1}$};
	\coordinate (e10) at (90:1.5) node at (e10)  {$e_{2q+2}$};
	\coordinate (e11) at (270:1.5) node at (e11)  {$e_{2q+2m-2}$};
	\coordinate (e12) at (270:2.5) node at (e12)  {$e_{2q+2m-1}$};
	\draw
	(20:3) arc (20:160:3cm)
	(200:3) arc (200:340:3cm)
	(v1)--(v15)
	(v6)--(v16)
	;
\fill
(v1) circle (2pt)
(v2) circle (2pt)
(v3) circle (2pt)
(v4) circle (2pt)
(v5) circle (2pt)
(v6) circle (2pt)
(v7) circle (2pt)
(v8) circle (2pt)
(v9) circle (2pt)
(v10) circle (2pt)
(v11) circle (2pt)
(v12) circle (2pt)
(v13) circle (2pt)
(v14) circle (2pt)
(180:3) circle (1pt)
(170:3) circle (1pt)
(190:3) circle (1pt)
(350:3) circle (1pt)
(0:3) circle (1pt)
(10:3) circle (1pt)
(0:0) circle (1pt)
(90:0.5) circle (1pt)
(270:0.5) circle (1pt)
;
    \end{tikzpicture}
	\end{figure}

	\begin{proof}
			Since ${\mathcal P}_{G^{(o)}_{k,m}}$ is bipartite and connected, one has $\dim {\mathcal P}_{G^{(o)}_{k,m}}=2q+2m-4$.
		Moreover, since
	\begin{displaymath}
	\begin{aligned}
		&	\sum_{i=1}^{k-1} \left(\dfrac{1}{3} \rho(e_{2i-1}) + \dfrac{2}{3}\rho(e_{2i}) \right)+\dfrac{1}{3}\rho(e_{2k-1})
		\\+&\sum_{i=k}^{q-1} \left(\dfrac{1}{3} \rho(e_{2i}) + \dfrac{2}{3}\rho(e_{2i+1})\right)+\dfrac{1}{3}\rho(e_{2q})\\
		+&\sum_{i=q}^{q+m-2} \left(\dfrac{1}{3} \rho(e_{2i+1}) + \dfrac{2}{3}\rho(e_{2i+2})\right)+\dfrac{1}{3}\rho(e_{2q+2m-1})	\\=&{\bold e}_1+{\bold e}_2+\cdots+{\bold e}_{2q+2m-2}\in {\rm int}((q+m-1){\mathcal P}_{G^{(o)}_{k,m}}) \cap {\NZQ Z}^{2q+2m-2}
	\end{aligned}
\end{displaymath}
and since $m \geq (q+1)/2$,
we obtain $\deg {\mathcal P}_{G^{(o)}_{k,m}} \geq 2q+2m-4+1-q-m+1=q+m-2 \geq  3q/2 -3/2 \geq q$, as desired.
	\end{proof}

	Now, we prove Theorem \ref{thm:main}.
	\begin{proof}[Proof of Theorem \ref{thm:main}]
	Let $G$ be a connected finite simple bipartite graph such that $K[G]$ has a $q$-linear resolution, where $q \geq 3$.
	It then follows that $G$ has no even cycles of length $< 2q$ and has at least one even cycle of length $2q$, and $\deg {\mathcal P}_G \leq q-1$ from Lemma \ref{lem:reg}.
	Assume that $G$ has two even cycles of length $2q$.
	From Lemma \ref{lem:disjoint} each pair of even cycles of length $2q$ in $G$ has a common vertex. If two even cycles of length $2q$ in $G$ has precisely one common vertex. It then from Lemma \ref{lem:twocycles} that $\deg {\mathcal P}_G \geq q$, a contradiction.
	Hence each pair of even cycles of length $2q$ in $G$ has at least two common vertices.
	Let $C_1$ and $C_2 (C_1 \neq C_2)$ be even cycles of length $2q$ in $G$ with common vertices $v_1$ and $v_2 (v_1 \neq v_2)$.
Then each of $C_1$ and $C_2$ has two paths between $v_1$ and $v_2$.
Let $P_{i1}$ and $P_{i2}$ be two paths between $v_1$ and $v_2$ in $C_i$ for each $i=1,2$. Since $C_1 \neq C_2$, one has $\{P_{11},P_{12,}\} \neq \{P_{21}, P_{22} \}$.	Hence there are two vertices $w_1,w_2 \in C_1$ and a path $P$ of $G$ connecting $w_1$ and $w_2$ such that for each $w \in P$ with $w \neq w_1,w_2$, it holds $w \notin C_1$.
Let $G'$ be the connected bipartite graph on $C_1 \cup P$ with the edge set $E(G')=E(C_1) \cup E(P)$.
Since $G$ has no odd cycles and no even cycles of length $<2n$, so does $G'$.
Hence $G'$ is $G^{(e)}_{k,m}$ or $G^{(o)}_{k,m}$ which appear in Lemmas \ref{lem:even} and \ref{lem:odd}, and hence one has $\deg {\mathcal P}_G \geq \deg {\mathcal P}_{G'} \geq q$, a contradiction.
Therefore, $G$ has precisely one even cycle of length $2q$.
Thus, $K[G]$ is a hypersurface, as desired.
\end{proof}

redpajama_set_name: RedPajamaArXiv