\section{Introduction}

Let $G$ be a simple graph (for basic terminology on graph theory, we refer the reader to~\cite{BM08}). A function $\psi \colon V(G)\to \mathbb{N}$ is a \emph{proper k-coloring of G} if $|\psi(V(G))| = k$ and $\psi(u)\neq \psi(v)$ whenever $uv \in E(G)$. Because we only deal with proper colorings in this text, from call them simply a coloring. We call the elements of $\psi(V(G))$ \emph{colors}. Given a color $i \in \psi(V(G))$, the set $\psi^{-1}(i)$ is called \emph{color class i}. The \emph{chromatic number of $G$} is the minimum value $\chi(G)$ for which $G$ admits a coloring. The problem of deciding~$\chi(G)\le k$ for given $G$ and $k$ is one of the most studied problems in Graph Theory. It is one of Karp's 21 $\textsc{NP}$-complete problems~\cite{K.72}, and it remains $\textsc{NP}$-complete even when restricted to many classes of graphs, as for instance, it is $\textsc{NP}$-complete when $k=3$ and $G$ is a 4-regular planar graph~\cite{D.80}, or a line graph~\cite{H.81}. There are many variations of the coloring problem, and in this article we investigate two of these variations, both of them based on existing coloring heuristics.

Given a coloring $\psi$ of $G$, we say that $u \in V(G)$ is a \emph{b-vertex in $\psi$} if $u$ is adjacent to every color class different from $\psi(u)$, i.e., if $N(u)\cap \psi^{-1}(i)\neq \emptyset$ for every $i\neq \psi(u)$. Note that if some color class $c$ does not contain b-vertices, we can obtain a $(k-1)$-coloring by changing the color of each vertex $v \in \psi^{-1}(c)$ to another color different from $c$ where $v$ has no neighbors. We say that this new coloring is obtained from the first one by \emph{cleaning  color $c$}. If a coloring cannot be cleaned, it means that all color classes have at least one b-vertex. Such a coloring is called  a \emph{b-coloring of $G$}. Observe that an optimal coloring cannot have the number of colors decreased by the described algorithm; therefore every optimal coloring is also a b-coloring. In~\cite{Irving.Manlove.99}, the authors define the \emph{b-chromatic number of $G$}, denoted by $b(G)$, as the largest natural $k$ for which $G$ has a b-coloring with $k$ colors. In the same article, the authors demonstrated that the problem of finding  $b(G)$ is $\textsc{NP}$-complete in general.

Another interesting aspect about b-colorings concerns its existence for every possible value between $\chi(G)$ and $b(G)$. In~\cite{Irving.Manlove.99}, the authors observe that the cube has a b-coloring using 2 colors and 4 colors, but has no b-coloring using 3 colors. Inspired by this result, in~\cite{KRATOCHVIL.etal.02} it is shown that for any integer $n\geq 4$ the graph obtained from the complete bipartite graph $K_{n,n}$ by deleting the edges from a perfect matching has a b-coloring using $2$ and $n$ colors, but has no b-coloring using a number of colors between $2$ and $n$. This motivates the definition of the \emph{b-spectrum of G}, that is the set $S_{b}(G)$ containing every integer $k$ such that $G$ has a b-coloring with $k$ colors. A graph $G$ is \emph{b-continous} if $S_{b}(G)= [\chi(G),b(G)] \cap \mathbb{Z}$. In~\cite{Barth.Cohen.Faik}, they prove that for each finite subset $S \subset \mathbb{N} - \{1\}$, there exists a graph $G$ such that $S_{b}(G)=S$, and also that deciding if a graph is b-continuous is $\textsc{NP}$-complete even if colorings with $\chi(G)$ and $b(G)$ colors are given.

Now, given a b-coloring with $k$ colors, since each b-vertex has at least $k-1$ neighbors, there exists $k$ vertices with degree at least $k-1$ (this would be a subset of $k$ b-vertices of the $k$ colors). So if we define $m(G)$ as the largest positive integer $k$ such that there exist at least $k$ vertices with degree at least $m(G)-1$ in $G$, we have that $b(G)\leq m(G)$.
This upper bound was introduced in~\cite{Irving.Manlove.99}, where the authors show that one can find $m(G)$ in polynomial time using the degree list of the graph.
Also, they prove that if $G$ is a tree, then $b(G)\geq m(G)-1$, and that one can decide if $b(G)=m(G)$ in polynomial time. Their result was later generalized for graphs with girth at least 7~\cite{CLS.15} (the \emph{girth of $G$} is the minimum lenght of a cycle in $G$). We also mention that there are many results that say that regular graphs with large girth have high b-chromatic number~\cite{BMZ.09,CJ.11,EK.09,BMZ.09}. Indeed, the following conjecture is still open.

\begin{conjecture}[Blidia, Maffray and Zemir~\cite{BMZ.09}]
If $G$ is a $d$-regular graph with girth at least~5 and $G$ is not the Petersen graph, then $b(G)= d+1$.
\end{conjecture}

Because of these results, it makes sense to investigate the b-continuity of graphs with large girth. Indeed, in~\cite{BK.12} the authors prove that regular graphs with girth at least~6 and without cycles of length~7 are b-continuous, and in~\cite{L-SS.17}, they prove that every graph with girth at least~10 are b-continuous.
Here, we improve their result to graphs with girth at least~8.

\begin{theorem}\label{th:main} If $G$ is a graph with girth at least 8, then $G$ is b-continuous.
\end{theorem}

In addition, we prove that graphs with girth at least~7 are, in a way, almost b-continuous.

\begin{theorem} \label{th:second}
If $G$ is a graph with girth at least 7, then $[2\chi(G),b(G)]\cap \mathbb{Z} \subseteq S_{b}(G)$.
\end{theorem}

Now, given a coloring $\psi:V(G)\rightarrow \{1,\ldots,k\}$, we say that $u\in V(G)$ is a \emph{Grundy vertex} if $u$ has a neighbor in color class $i$, for every color $i<f(u)$, and that $f$ is a \emph{partial Grundy coloring} if every color class contains at least one Grundy vertex. This concept was introduced in~\cite{EHLP.03}, where the authors relate the new concept with parsimonious colorings. We mention that a more largely studied concept is that of the Grundy colorings, where every vertex is a Grundy vertex. These are also called greedy colorings since they represent colorings that can be obtained by the greedy algorithm. In this context, a partial Grundy coloring can be thought of as a coloring that cannot have the number of colors decreased by moving vertices to smaller colors. Because a coloring with $\chi(G)$ colors cannot be improved like this, we get that it must be a partial Grundy coloring.
The \emph{partial Grundy number} is then defined as the worst case scenario for this heuristis, i.e., it is the maximum number of colors in any partial Grundy coloring; it is denoted by $\partial\Gamma(G)$.

Interestingly enough, these colorings are also easier on graphs with large girth. In~\cite{S.etal.05}, the authors introduce an upper bound for $\partial\Gamma(G)$, called the \emph{stair factor of $G$} and denoted here by $s(G)$, and they prove that if $G$ has girth at least~9, then $\partial\Gamma(G) = s(G)$. We improve their result in the theorem below.

\begin{theorem} \label{th:partialGrundy}
If $G$ is a graph with girth at least 7, then $\partial\Gamma(G)=s(G)$, and an optimal partial Grundy coloring can be obtained in polynomial time.
\end{theorem}

Observe that this and the result in~\cite{CLS.15} tell us that that if $G$ has girth at least~7, then both the b-chromatic number and the partial Grundy number of $G$ are high. However, we mention that these colorings are not similar when the continuity is concerned. In~\cite{BK.13}, the authors prove that every graph $G$ has a partial Grundy coloring with $k$ colors, for every $k\in\{\chi(G),\ldots,\partial\Gamma(G)\}$. This is a common trait with Grundy colorings~\cite{CS.79}.

Our article is organized as follows. In Section~\ref{sec:proofBcol}, we prove Theorems~\ref{th:main} and~\ref{th:second}; in Section~\ref{sec:proofPartialG}, we prove Theorem~\ref{th:partialGrundy}; and in Section~\ref{sec:conclusion}, we give our closing remarks. The definitions and notation are introduced as they are needed.

\section{b-continuity}\label{sec:proofBcol}

In~\cite{BK.12}, a vertex $u\in V(G)$ is called a \emph{$k$-iris} if there exists $S \subseteq N(u)$ such that $|S| \geq k-1$ and $d(v)\geq k-1$ for every $v \in S$. See Figure~\ref{fig:kiris}. This definition is important because of the following important lemma.
\input{kiris.tex}

\begin{lemma}[\cite{BK.12}]\label{lem:BK.12}
Let $G$ be a graph with girth at least 6 and without cycles of lengh 7. If $G$ has a $k$-iris with	 $k \geq \chi(G)$, then $G$ has a b-coloring with $k$ colors.
\end{lemma}

To prove Theorems~\ref{th:main} and~\ref{th:second}, given a b-coloring of $G$ with $k$ colors, $k>\chi(G)+1$, we try to obtain a b-coloring of $G$ with $k-1$ colors. However, this is not always possible, and when this happens, it is because we have a $k$-iris. Our theorem then follows from the lemma above. We mention that the constraint about not having cycles of length~7 appears only in the above lemma, but not on our proof. We now introduce the further needed definitions.

Let $G$ be a simple graph and $\psi$ be a b-coloring of $G$ with $k>\chi(G)+1$ colors. We say that $u$ \emph{realizes color $i$} if $\psi(u)=i$ and $u$ is a b-vertex. We also say that color $i$ is \emph{realized by $u$}. For $x \in V(G)$ and $i \in \{1,\ldots,k\}$, let $N^{\psi,i}(x)$ be the set of vertices of color $i$ in the neighborhood of $x$, i.e., $N^{\psi,i}(x) = N(x)\cap \psi^{-1}(i)$; in fact, we omit $\psi$ in the superscript since it is always clear from the context. This is also done in the next definitions. For a subset $X \subseteq V(G)$, let $N^{i}(X) = \bigcup_{x \in X} N^{i}(X)\setminus X$. Let $B(\psi)$ denote the set of b-vertices in $\psi$ and, for each $i\in \{1,\ldots,k\}$, let $B_{i} = B(\psi)\cap \psi^{-1}(i)$ be the set of b-vertices in color class $i$.

Given a set $K$ such that $K\subseteq \psi^{-1}(i)$ for some $i \in \{1,\ldots,k\}$, we say that a color $j \in \{1,\ldots,k\}\setminus\{i\}$ is \emph{dependent on K} if $N^{i}(B_{j}) \subseteq K$; denote by $U(K)$ the set of colors depending on $K$. If $K=\{x\}$, we write simply $U(x)$.
Given $x \in V(G)\setminus B(\psi)$, if $|U(x)|\geq 2$ we call $x$ a \emph{useful} vertex; otherwise, we say that $x$ is \emph{useless}.
For $j\in \{1,\ldots,k\}$, we say that $x \in V(G)$ is \emph{j-mutable} if $x$ is useless and there exists a color $c$ such that we can change the color of $x$ to $c$ without creating any b-vertex of color $j$; we also say that color $c$ is \emph{safe for $(x,j)$}. If there is no safe color for $(x,j)$, we say that $x$ is $j$-imutable.

The next lemma is the main ingredient in our proof. Combined with Lemma~\ref{lem:BK.12}, it immediatly implies Theorem~\ref{th:main}.

\begin{lemma}\label{lem:mainl}
Let $G=(V,E)$ be a graph with girth at least 7. If $G$ has a b-coloring with $k$ colors where $k\geq \chi(G)+1$, then either $G$ has a b-coloring with $k-1$ colors, or $G$ contains a $(k-1)$-iris.
\end{lemma}

\begin{proof}
Our proof is similar to that made in \cite{L-SS.17}, but we concentrate in one color that we want to eliminate.

Suppose that $G$ does not have a b-coloring with $k-1$ colors; we prove that $G$ has a $(k-1)$-iris.
For this, let $\psi$ be a b-coloring with $k$ colors that minimizes $|B_{1}|$ and then minimizes $|\psi^{-1}(1)|$ (i.e., it firstly minimizes the number of b-vertices of color~1, then it minimizes the number of vertices of color~1). First, we prove that every $x \in \psi^{-1}(1)\setminus B_1$ is useful. Suppose otherwise and let $x$ be a useless vertex in color class~1, i.e., $|U(x)|\le 1$. If $U(x)= \emptyset$, then we can recolor $x$ without losing any b-vertex, a contradiction since $\psi$ minimizes $|\psi^{-1}(1)|$. And if $U(x)=\{d\}$, then we can obtain a b-coloring with $k-1$ by recoloring $x$ and cleaning $d$, again a contradiction. Therefore, the following holds:

\begin{center}(i) Every $x\in \psi^{-1}(1)\setminus B_1$ is useful. \end{center}

Now, we choose any $u \in B_{1}$ and analyse its vicinity in order to obtain the desired $(k-1)$-iris. For this, the following two claims are essential.

\begin{claim}\label{claim1}
Let $j\in \{2,\ldots,k\}$. If every $x\in N^j(u)\setminus B_j$ is 1-mutable, then one of the following holds:
\begin{itemize}
	\item[(ii)] $N(u)\cap B_{j} \neq \emptyset$; or

	\item[(iii)] There exists a color $d \in \{2,\ldots,k\}\setminus \{j\}$ such that $d$ depends on $N^{j}(u)$, i.e.,
	\[N^j(B_d)\subseteq N^j(u).\]
\end{itemize}
\end{claim}
\emph{Proof of claim:}
Suppose that neither (ii) nor (iii) holds, and let $\psi'$ be obtained from $\psi$ by changing the color of each $x\in N^{j}(u)$ to a color $c$ safe for $(x,1)$. Because $(iii)$ does not hold, we get that $U(N^{j}(u))\subseteq \{1\}$. Therefore, at most one color loses all of its b-vertices, namely color~1, and since every $x\in N^j(u)$ is 1-mutable, no b-vertices of color~1 is created. But because $u$ is not a b-vertex in $\psi'$ (it is not adjacent to color $j$ anymore) and $\psi$ minimizes $|B_{1}|$, we get that $\psi'$ cannot be a b-coloring, which means that we can obtain a b-coloring with $k-1$ colors by cleaning color 1.$\diamondsuit$

\vspace{0.3cm}
The following claim tells us that (ii) or (iii) actually always hold.

\begin{claim}\label{claim2} (iv) Every $x \in N^{j}(u)\setminus B_j$ is 1-mutable, for every $j\in \{2,\ldots,k\}$.\end{claim}
\emph{Proof of claim:}
Suppose, without loss of generality, that $d\in\{2,\ldots,k\}$ is such that the colors in $\{d+1,\ldots,k\}$ are exactly the colors that contains some $1$-imutable vertex. We count the number of colors with b-vertices in the vicinity of $u$ to get that in fact $d\ge k$. So, for each $i\in \{d+1,\ldots,k\}$, let $w_i\in N^i(u)$ be a $1$-imutable vertex. By definition, this means that, for each $i\in \{d+1,\ldots,k\}$, there exists some neighbor of $w_i$ that would be turned into a b-vertex of color~1 in case we change the color of $w_i$; let $v_i$ be such a vertex. We then know that $v_i\in \psi^{-1}(1)\setminus B_1$, which by (i) gets us that $|U(v_{i})|\geq 2$. By the definition of $U(x)$ and the fact that every $x\in \{v_{d+1},\ldots,v_k\}$ is colored with color~1, we get:

\begin{equation}U(v_i)\cap U(v_\ell) = \emptyset\mbox{, for every }i,\ell\in\{d+1,\ldots,k\}, i\neq \ell.\label{eq1}\end{equation}

Now, we investigate the b-vertices around colors $\{2,\ldots,d\}$. By Claim~\ref{claim1}, suppose, without loss of generality, that $p\in \{2,\ldots,d\}$ is such that (ii) holds for colors  in $\{2,\ldots,p\}$, while (iii) holds for colors in $\{p+1,\ldots, d\}$. For each $i\in \{p+1,\ldots, d\}$, let $c_i\in\{2,\ldots,k\}\setminus \{i\}$ be a color depending on $N^i(u)$, which means that $B_{c_i}\subseteq N(N^i(u))$.  Observe that, since $G$ has no cycles of length~3, we get:

\begin{equation}\{2,\ldots,p\}\cap \{c_{p+1},\ldots,c_d\} = \emptyset\label{eq2}\end{equation}

Also, because $G$ has no cycles of length~4, we get $c_i\neq c_\ell$ for every $i\neq \ell$, i.e.:

\begin{equation}|\{c_{p+1},\ldots,c_d\}| = d-p\label{eq3}\end{equation}

Finally, because $G$ has no cycles of length smaller than~6, we get that:

\begin{equation}\{2,\ldots,p,c_{p+1},\ldots,c_d\} \cap \bigcup_{i={d+1}}^{k}U(v_i) = \emptyset.\label{eq4}\end{equation}

Now, recall that $\psi(v_i)=1$ for every $i\in\{d+1,\ldots,k\}$, and that $c_i\neq 1$ for every $i\in\{p+1,\ldots,d\}$. This means that $1\notin \{c_{p+1},\ldots,c_d\}\cup\bigcup_{i=d+1}^pU(v_i)$. By combining Equations~(\ref{eq1}) through~(\ref{eq4}), we get the following, which implies $d\ge k$ as desired:

\[\begin{array}{ll}
k-1  & \geq |\{2,\ldots,p\}\cup \{c_{p+1},\ldots,c_{d}\} \cup U(v_{d+1})\cup \ldots \cup U(v_{k})| \\
              & = d- 1+ \sum_{i=d+1}^{k}|U(v_{i})| \\
              & \geq d -1 + 2(k-d).
\end{array}\diamondsuit\]

Now, let $N = (N(u)\cup N(N(u)))\setminus \{u\}$. Observe that because (ii) or (iii) holds for every color $\ell\in \{2,\ldots,k\}$, we get that $B(\psi)\subseteq N$. Suppose that $N[u]$ does not contain a $(k-1)$-iris, otherwise the proof is done. This means that at least one color in $\{2,\ldots,k\}$, say $k$, is such that (ii) does not hold for $k$, which  by Claim~\ref{claim1} implies that (iii) holds, i.e., that there exists a color in $\{2,\ldots,k-1\}$, say 2, such that $N^2(B_k)\subseteq N^2(u)$ (Observe Figure~\ref{fig:theoremProof}). Now, let $w\in N^1(B_k)$; it exists since the vertices in $B_k$ are b-vertices. By (i), there exists at least two colors in $\{2,\ldots,k\}$ that depend on $w$. But because $B(\psi)\subseteq N$, we get a cycle of length at most~6, a contradiction.\hfill$\Box$

\input{theoremProof.tex}

\end{proof}

Now, to prove Theorem~\ref{th:second}, we apply Lemma~\ref{lem:mainl} and the next lemma. A \emph{star} is a tree that has at most one vertex with degree bigger than~1, and the \emph{diameter} of a graph $G$ is the maximum number of edges in a shortest path of $G$.

\begin{lemma}
If a graph $G$ has girth at least 7 and a $k$-iris where $k\geq 2\chi(G)$, then $G$ has a b-coloring with $k$ colors.
\end{lemma}

\begin{proof}
Let $u \in V(G)$ be a $k$-iris with $k\geq 2\chi(G)$. Let $u_{2},\ldots,u_{k}$ be neighbors of $u$ such that $d(u_{i})\geq k-1$ for every $i \in\{2,\ldots,k\}$; let $N_i$ be a subset of $k-2$ neighbors of $u_i$ different from $u$.  Start by coloring $u$ with 1 and, for each $i\in \{2,\ldots,k\}$, give color $i$ to $u_i$ and colors $\{2,\ldots,k\}\setminus \{i\}$ to $N_i$. Denote by $P$ the set $\bigcup_{i=2}^kN[u_i]$ (set of colored vertices), and observe that the coloring can be easily done since $G[T]-u$ is a forest formed by $k-1$ stars. Also, note that we already have $k$ b-vertices of distinct colors, and thus it only remains to extend the partial coloring to the rest of the graph. For this, let $B$ be the set of vertices adjacent to some color class in $\{1,\ldots,\chi(G)\}$. See Figure~\ref{fig:kirisG7}.

\input{kirisG7.tex}

We claim that $|N(w)\cap T|\le 1$ for every $w\in B$; indeed, because $T$ induces a tree of diameter~4,  if this was not true than we would get a cycle of length at most~6. By the definition of $B$, we then get that every $w\in B$ has no neighbors in color classes $\chi(G)+1,\ldots,k$. Thus, since $k\ge 2\chi(G)$, we can color $G[B]$ with colors $\chi(G)+1,\ldots,2\chi(G)$. Finally, by the definition of $B$, we know that every $w\in V(G)\setminus (B\cup T)$ has no neighbors of color $1$ through $\chi(G)$, which means that we can color $G-T-B$ with these colors.\hfill$\Box$
\end{proof}

\section{Partial Grundy Colorings}\label{sec:proofPartialG}

The next definitions were introduced in~\cite{S.etal.05}. Given $W = (w_1,\ldots,w_s)$, a sequence of vertices, we say that $W$ is a \emph{feasible sequence} if $d_{G_i}(w_i)\ge i-1$, for every $i\in \{1,\ldots,s\}$, where $G_i = G-\{w_{i+1},\ldots,w_s\}$. The \emph{stair factor of $G$} is the maximum size of a feasible sequence; we denote it here by $s(G)$. In~\cite{S.etal.05}, they prove that $s(G)$ is an upper bound for $\partial\Gamma(G)$, and that if $W$ is a feasible sequence of $G$ of size $s$, and $G$ has girth at least~9, then $G$ has a partial Grundy coloring with $s$ colors. This implies that $\partial\Gamma(G) = s(G)$ when $G$ has girth at least~9. We prove that it continues to hold when $G$ has girth at least~7 by also proving that the existence of a feasible sequence of size $s$ makes it possible to obtain a partial Grundy coloring of $G$ of size $s$. We mention that they also prove that computing a feasible sequence of maximum size can be done in polynomial time, which combined with our proof imply Theorem~\ref{th:partialGrundy}.

Now, consider a feasible sequence $(w_1,\ldots,w_s)$, $s\ge 2$, and for each $i\in \{2,\ldots,s\}$, let $N_i \subseteq N_{G_i}(w_i)$ be of cardinality $i-1$. Denote the set $\{w_2,\ldots,w_s\}$ by $W$. We say that a partial coloring $\psi$ of $G$ is \emph{non-redundant for $W$} if for every $i\in \{2,\ldots,s\}$, we get that $\psi(w_i) = i$ and all the colored vertices in $N_i$ have distinct colors in $\{1,\ldots,i-1\}$.

\begin{proof}[of Theorem~\ref{th:partialGrundy}]
Let $(w_1,\ldots,w_s)$ be a feasible sequence. Denote by $W$ the set $\{w_2,\ldots,w_s\}$ and let $N_i$ be defined as before; also let $N = \bigcup_{i=2}^s N_i$. First, note that if $\psi$ is a non-redundant partial coloring that colors $W\cup N$, then a partial Grundy coloring with at least~$s$ colors can be obtained from $\psi$ in a greedy way: this is true because $w_i\in W$ is a Grundy vertex in $\psi^{-1}(i)$, for each $i\in \{2,\ldots,s\}$, and any vertex $x\in \psi^{-1}(1)$, which exists since $N_2$ is colored with~1, is a Grundy vertex.

Start by coloring each $w_i\in W$ with $i$. For each $x\in N$, define:
\[m(x) = \min\{i\in\{2,\ldots,s\}\mid w_i\in N(x)\}.\]

Note that if $\psi$ is a non-redundant partial coloring and $x$ is colored in $\psi$, then $\psi(x)<m(x)$. We will then color $N$ in a non-decreasing order of $m(x)$. Suppose we are at the iteration of some $x\in N$, and observe that the colors that are forbidden for $x$ are the colors that appear in $N(x)$, and also the colors that appear in $N(w_i)$, where $w_i\in N(x)$. So, denote by $\ell$ the value $m(x)$ and by $F$ the set of vertices $N(x)\cup N(N_W(x))$. By what was said before, if there exists a color $c\in \{1,\ldots,\ell-1\}\setminus \psi(F)$, then we can give color $c$ to $x$ to obtain a non-redundant partial coloring that colors $x$, so suppose otherwise. For each $i\in \{1,\ldots,\ell-1\}$, let $y_i\in F$ be such that $\psi(y_i) = i$. First, note that, by the definition of $m(x)$ and the fact that $\psi(y_i)<m(x)$, we get that if $y_i\in N(x)$, then $y_i\in N$. Now, for each $i\in \{1,\ldots, \ell-1\}$, define:

\[
u_i = \left\{\begin{array}{ll}
y_i & \mbox{, if $y_i\in W$}\\
w_{m(y_i)} & \mbox{, otherwise}
\end{array}\right.\]

 Let $W^{<\ell}$ be the set $\{w_2,\ldots,w_{\ell-1}\}$.  Observe Figure~\ref{fig:partialG}.

 \input{partialG.tex}

 Consider $i\in \{1,\ldots,\ell-1\}$. If $u_i=y_i$, then, because $\psi(y_i)<m(x)$, we get $u_i\in W^{<\ell}$.  Otherwise, we get that $y_i\in N$ and, by the chosen order of coloring, we get that $m(y_i) < m(x)$, which again implies that $u_i\in W^{<\ell}$. We then get $\{u_1,\ldots,u_{\ell-1}\}\subseteq W^{<\ell} = \{w_2,\ldots,w_{\ell-1}\}$, which by the pigeonhole principle implies that there exist $i,j\in \{1,\ldots,\ell-1\}$ with $i\neq j$ such that $u_i=u_j$. But because $u_i$ and $u_j$ are at distance at most~3 from $x$, we get a cycle of length smaller than~7, a contradiction.\hfill$\Box$
\end{proof}

\section{Conclusion}\label{sec:conclusion}

We have proved that every graph with girth at least~8 is b-continuous, and that graphs with girth at least~7 are in a way almost b-continuous. This improves the result presented in~\cite{L-SS.17}, where they prove that graphs with girth at least~10 are b-continuous. There, the authors also pose the following questions:

\begin{question}\label{q:general}
What is the minimum $\hat{g}$ such that $G$ is b-continuous whenever $G$ is a graph with girth at least $\hat{g}$?
\end{question}

\begin{question}\label{q:bipartite}
What is the minimum $\tilde{g}$ such that $G$ is b-continuous whenever $G$ is a bipartite graph with girth at least $\tilde{g}$?
\end{question}

Recall that the graph obtained from the complete bipartite graph $K_{n,n}$ by removing a perfect matching is not b-continuous, for every $n\ge 4$~\cite{KRATOCHVIL.etal.02}. Hence, by our result we get:

\[5\le \hat{g}\le 8.\]

And because bipartite graphs have no odd cycles, we get:
\[\tilde{g}\in\{6,8\}.\]

We believe that the same techniques might improve this bound to~7, but not further. In particular, we mention that Lemma~\ref{lem:mainl} works for graphs with girth~7, and that Theorem~\ref{th:main} is restricted to girth at least~8 just because of Lemma~\ref{lem:BK.12}. Therefore, if the following question is answered ``yes'', then we get $\hat{g}\le 7$.

\begin{question}
Let $G$ be a graph with girth at least~7 such that $G$ has a $k$-iris, with $k \geq \chi(G)+1$. Does $G$ admit a b-coloring with $k$ colors?
\end{question}

We also mention that the coloring problem is $\textsc{NP}$-complete for graphs with girth at least $k$, for every fixed $k\geq 3$~\cite{LK.07}. This is why any proof of a result like Theorem~\ref{th:main} is expected to have a non-constructive part.

As for the case of bipartite graphs, we think it is worth mentioning a known conjecture about their b-chromatic number. Recall the upper bound $m(G)$ for the b-chromatic number $b(G)$, which is the maximum value $k$ for which there exist $k$ vertices with degree at least $k-1$. The set of all vertices with degree at least $m(G)-1$ is denoted by $D(G)$, and a graph is said to be \emph{tight} if $|D(G)| = m(G)$; this means that there is only one candidate set for the set of b-vertices of a b-coloring of $G$ with $m(G)$ colors. Deciding if $b(G)=m(G)$ is $\textsc{NP}$-complete even for bipartite tight graphs~\cite{KRATOCHVIL.etal.02}. In~\cite{HLS.12}, the authors define the class $\mathcal{B}_m$ that contains every bipartite graph $G = (A\cup B, E)$ such that $m(G)=m$, $D(G) = A$ and $G$ has girth at least~6. They conjecture the following:

\begin{conjecture}[Havet, Linhares-Sales and Sampaio~\cite{HLS.12}\label{ConjHSL.12}]
For every $m\ge 3$, and every $G\in \mathcal{B}_m$, we have that: \[b(G)\ge m(G)-1.\]
\end{conjecture}

We mention that, if $G$ is a bipartite graph with girth at least~6 and a b-coloring of $G$ with $k$ colors is given, with $k\ge \chi(G)+1$, then, with a little more work in the proof of Lemma~\ref{lem:mainl}, one can get that $G$ contains an induced subgraph $H$ that has a structure similar to the structure of a graph in $\mathcal{B}_k$. Trying to use this structure to obtain a b-coloring of $H$ with $k-1$ colors could translate into proving Conjecture~\ref{ConjHSL.12}. And on the other way around, we believe that a strategy to prove Conjecture~\ref{ConjHSL.12} could help coloring these graphs, which would imply that the answer to Question~\ref{q:bipartite} is ``yes''. This means that answering Question~\ref{q:bipartite} seems as hard as proving Conjecture~\ref{ConjHSL.12}. We also mention that in~\cite{LC.13}, it is proved that Conjecture~\ref{ConjHSL.12} is a consequence of the famous Erd\H{o}s-Faber-Lov\'asz Conjecture, which remains open since~1972 and which is largely believed to hold. This is strong evidence that Conjecture~\ref{ConjHSL.12} holds.

Now, concerning partial Grundy colorings, an obvious question also concerns the minimum girth for which $\partial\Gamma(G)=s(G)$ holds.

\begin{question}\label{q:general}
What is the minimum $\dot{g}$ such that $\partial\Gamma(G)=s(G)$ whenever $G$ is a graph with girth at least $\dot{g}$?
\end{question}

Oberve that if $G=(A\cup B,E)$ is the complete bipartite graph $K_{n,n}$, then $s(G) = n+1$: a feasible sequence is obtained by starting with any vertex in $A$, then ordering each $v\in B$. However, we argument that the only existing partial Grundy coloring of $G$ uses 2 colors. For this, suppose without loss of generality that color~1 appears in $A$. Then no vertex in $B$ is colored with 1, which means that no Grundy vertex of color bigger than~1 can appear in $A$. But now, if color $i>2$ has a Grundy vertex $u$ in $B$, then color~2 must appear in $A$ and, therefore, cannot appear in $B$. We get a contradiction since in this case color~2 has no Grundy vertices. We then get the following bounds
\[5\le \dot{g}\le 7.\]

\bibliographystyle{plain}


\section{Introduction}

   A critical aspect of millimeter-wave (mmWave) signals  is its sensitivity to blockage by the human hand \cite{Statistical_Raghavan18} which has to be accounted for while designing beamforming codebooks. Beamforming, which is required to combine the signals from different antennas, is a critical part of mmWave communications since it relies on high array gains \cite{Millimeter_Raghavan17}.

   Although digital beamforming is elegant theoretically and results in  excellent array gains, the commercial devices will most probably avoid using fully-digital beamforming due to its complexity, both in hardware and signal processing \cite{MIMO_Alkhateeb14, Automatic_Jianhua19}. Instead, analog beamforming, which is based on pre-designed codebooks, is proposed as an alternative and supported by the 3GPP 5G NR standard \cite{3GPP2018}.
   The idea is that a set of beamforming vectors (codewords) is predetermined, and the device switches between these codewords to select the one that maximizes the antenna gain in the direction of the received signal. A comparison between digital and analog codebook beamforming has been conducted recently in \cite{Antenna_Raghavan19}, where the authors showed that the codebook beamforming can balance the trade-off between the overhead complexity and array gain and can perform close to the digital beamforming. Another recent study was performed in \cite{Automatic_Jianhua19}, which proposes and compares different heuristic approaches to design the beam codebooks taking into account the antennas' radiation pattern.

	However, \cite{Automatic_Jianhua19} only considers the free space propagation without the possible hand blockage and \cite{Antenna_Raghavan19} focuses on comparing different antenna types and comparing the analog codebook beamforming and the digital one. Moreover, their model of the human hand is either based on a stochastic model \cite{3GPP2017}, which assumes a 30 dB flat loss in the antenna gain due to the hand blockage, or a statistical loss \cite{Statistical_Raghavan18}, which only differentiates between the blockage in landscape and portrait orientations. It is well-known that users hold their phones in different ways depending on the applications they are using, the environment,  and their habits. These different hand grips affect the radiation patterns in distinct ways even though the phone orientation is the same. For example, while in the landscape orientation, the user can hold the phone with both hands or a single hand. The effect of single hand blockage on the radiation patterns can be quite different from that of dual hand blockage because when the fingers are near the antenna, the radiation is influenced more by coupling, reflection, and attenuation caused by the finger \cite{mmWave_Zhao15,Efficiency_Khan18}.

	In this work, we focus on the problem of adapting the beam codebooks according to the available knowledge of the user hand grip. More specifically, we consider a practical placement of the antennas on the mobile device and a practical design algorithm of the beam codebooks. We also use high-frequency structure simulator (HFSS) to obtain the antenna radiation patterns, where we include our model of the human hand into the simulations to capture the irregularities in the radiation patterns caused by the hand and to avoid using oversimplified analytical models. To this end, we compare three codebook adaptation schemes: An idealistic {\it grip-aware} scheme, which assumes that the device can accurately detect the hand grip and use a codebook that is specifically designed for it; a more practical scheme we call the {\it semi-aware} scheme, which is based on the assumption that the device only knows the orientation of the device and the active application the user is using; and a benchmark {\it grip-agnostic} scheme, where the codebook is designed assuming no-blockage and does not accommodate the hand grip. We show that the {\it grip-aware} and the {\it semi-aware} schemes can achieve over $57\%$ gain in terms of the spherical coverage compared to the {\it grip-agnostic} scheme, where the gain depends on the activity. Overall, our results show that beamforming codebooks must be adapted to the hand grip. Otherwise, a significant loss of the spherical coverage is expected which might lead to a link failure.

	\section{System Model}\label{Sec:SysMod}

	\subsection{Antenna and Mobile Design}

	 A good design for the mobile device must have different antenna arrays with different orientations, such that each array is able to receive the signal from certain directions (coverage region). What's more, there must be overlap between the different coverage regions for the antenna arrays to account for possible hand blockage. To this end, different antenna designs were proposed in 3GPP meetings  \cite{Samsung_Consideration17,Qualcomm_Consideration17,Apple_Consideration17} and studied in the literature \cite{Antenna_Raghavan19} to ensure the previous requirements. We consider the design shown in Fig. \ref{fig:Designs}, where we have three $2\times 2$ patch antenna modules placed on top two corners and the right bottom corner of the back of the phone. Also, each is surrounded by two modules of dipole antennas on the edges.
	\begin{figure}[t]
		\centering
			\centerline{\includegraphics[width=  3in]{./D1_1.pdf}}
		\caption{\, The considered antenna placements.}
		\label{fig:Designs}
	\end{figure}
	Note that we consider a mix of edge (dipole) and face (patch) antenna arrays. This is because the $2\times2$ patch array provides good spherical coverage to the hemisphere on the back of the phone, but it cannot be used to receive (transmit) signals from (through) the front end of the phone because of the front-to-back ratio of the patch antenna as well as blockage by the screen \cite{Statistical_Raghavan18}. On the other hand, the dipole antenna arrays can be used to extend the coverage region to the sides of the device, but it also restricts us to linear antenna arrays due to size constraints. Note that there is also redundancy since some arrays point to the same direction. This is because we need to account for possible hand blockages which can severely reduce the gain of the blocked antenna as shown later in this work.

    To reduce the complexity of the management and design of the beam codebook, the mobile device is restricted to use one array at a time, referred to as an antenna module, which is either a $2 \times 2$ patch array or a $1 \times 2$ dipole array. This design will be studied in the following sections in terms of the spherical coverage in free space as well as in the presence of hand blockage.
	\subsection{Spherical Coverage and HFSS}\label{Sec:SCaH}

	The main performance metric considered in this work is {\it spherical coverage} which corresponds to the antennas' far field gain over all possible directions. To quantify it, we discretize the unit sphere uniformly, and then the antenna gain is found for each point on the sphere. More rigorously, let $\mathcal X=\left\{x_i=(\theta_i,\phi_i), \ \forall i \in \{1,2, \cdots, N_p\}\right\}$ be a set of points uniformly distributed on the surface of the unit sphere, where $N_p$ is the number of points
	and  $0^\circ \leq \theta_i \leq 180^\circ $, $0^\circ \leq \phi_i < 360^\circ$ are the spherical coordinates of the $i^{\rm th}$ point. Each point represents one possible direction for the signal to arrive from. In other words, we have discretized the possible angle of arrivals (AoAs). The handset has a set of beamforming vectors (codewords), referred to as a codebook $\mathcal W_c$, and chooses the codeword that maximizes the antenna gain given the AoA. Let the gain at point $x_i$ be denoted by $G_{i}({\mathbf w})\in \mathbb{R}_{+}$, given a codeword ${\mathbf{w}}\in \mathbb{C}^{N_t \times 1}$, where $N_t$ is the total number of antennas.  Then the spherical coverage is defined as follows
	 \begin{equation}\label{eq:SphericalCovMat}
	\mathcal{S}(\mathcal{W}_c)=\{\max_{{\mathbf w} \in {\mathcal W_c}} G_i({\mathbf w}), \ \forall i \in \{1,2, \cdots, N_p\}\}.
	\end{equation}

	Based on this, the mean spherical coverage across all points on the sphere given a codebook $\mathcal W_c$, denoted by $\bar{\mathcal{S}}(\mathcal W_c)$,  is given by
	\begin{equation}\label{Eq:AveSC}
	\bar{\mathcal{S}}({\mathcal W_c})=\frac{1}{N_p} \sum\limits_{i=1}^{N_p} \max_{\mathbf w \in {\mathcal W_c}} G_i(\mathbf w).
	\end{equation}

	To compute the antenna gain $G_{i}({\mathbf w})$ given a certain setup of antennas, we use an electromagnetic simulation software called HFSS, since the theoretical models fall short in capturing the irregularities in the antennas' radiation patterns. The design shown in Fig. \ref{fig:Designs} was built in HFSS, where the antennas were designed for 39 GHz carrier frequency with a half wavelength separation. In this design, we did not add the different components in the phone and only modeled the screen, since it is the main source of reflections and absorption.

	Using HFSS, we get the antenna response of each element in each array for each direction $x_i$. Hence, for a given direction $x_i$, we have an antenna response vector, which we denote by ${\mathbf{M}_{i}}\in \mathbb{C}^{1 \times N_t}$, and the antenna gain is given by
	\begin{equation}\label{Eq:Gain}
	G_{i}({\mathbf w})= {\mathbf{w}}^{H} {\mathbf{M}}_{ i}^{H} {\mathbf{M}}_{i} {\mathbf{w}},
	\end{equation}
	where ${\mathbf w}^{H}$ is the Hermitian (conjugate) transpose of the vector ${\mathbf w}$.

 \begin{figure*}
	\centering
	\begin{subfigure}{\columnwidth}
		\centerline{\includegraphics[width=  2.6in]{./RadWO2.png}}
		\caption{\, Without blockage.}
		\label{fig:RadWO}
	\end{subfigure}%
	\begin{subfigure}{\columnwidth}
		\centering
		\centerline{\includegraphics[width=  2.6in]{./RadW2.png}}
		\caption{\, With blockage.}
		\label{fig:RadW}
	\end{subfigure}
	\caption{The 3D antenna gain in dB of a patch antenna with and without blockage by a finger. }
	\label{fig:RadWOandW}\vspace{-0.4cm}
\end{figure*}

	At this point, we need to design the codebook  to maximize some function of the spherical coverage.
	In this work, we choose the codebook ${\mathcal W_c}$ that maximizes the mean spherical coverage out of a given large set of candidate codewords ${\mathcal W_d}$, where the set ${\mathcal W_d}$ satisfies all the required conditions on the maximum transmit power and the finite number of bits in the phase shifter. Hence, we have the following optimization problem
	\begin{equation}
	{\mathcal W_{c}}=\argmax_{ \left\{ {\mathbf w_1}, \cdots, {\mathbf w}_{N_c} \right\} \subset {\mathcal W_d}} \bar{\mathcal{S}}(\{{{\mathbf w}_1, \cdots, {\mathbf w}_{N_c}}\}),\label{Eq:OptiPro}
	\end{equation}
	which is a combinatorial problem and solving it using an exhaustive search is not feasible given a large set ${\mathcal W_d}$ and a large number of points $N_p$. Different heuristic approaches to solve this problem were discussed in detail in \cite{Automatic_Jianhua19}. In this work, we adopt the greedy approach which we now  describe. The greedy approach is an iterative one, where the first codeword is selected to maximize the mean spherical coverage given by \eqref{Eq:AveSC}. The second codeword is also chosen to maximize the mean spherical coverage, but given that we have already selected the first codeword. In other words, the second codeword is chosen such that the composite spherical coverage of the first and second codewords is maximized. Hence, the choice of second codeword is biased to select the one that points the beam in a different direction of the first codeword. Subsequently,  the $N^{\rm th}$ codeword is found by
	  \begin{align}
	{\mathbf w}_{N}=\argmax_{{\mathbf w}\in {\mathcal W_d} \setminus \{{\mathbf w}_1, \cdots,{\mathbf w}_{N-1}\}} \frac{1}{N_p}f({\mathbf w}),
	\end{align}
	where
	\begin{align}
	&\!\!\!\!\!\!\!\!\!f({\mathbf w})=  \sum\limits_{i=1}^{N_p}  \max \left( G_i({\mathbf w}),G_i({\mathbf w}_1), \cdots, G_i({\mathbf w}_{N-1}) \right).\label{Eq:OptiProN}
	 \end{align}

	This approach is only optimal if the desired codebook size is one and otherwise, it is suboptimal. However, it was shown in \cite{Automatic_Jianhua19} that it performs  well compared to other more sophisticated algorithms.

	Before wrapping up this section, we discuss the choice of the candidate set of codewords ${\mathcal W_d}$. There are many options to construct ${\mathcal W_d}$ as shown in \cite{Automatic_Jianhua19}. In this work, we select a subset of points $\mathcal Y$ from $\mathcal X$ (i.e., $\mathcal Y \subset \mathcal X$) that has a length $N_d \ll N_p$. Then, for each point $y\in \mathcal Y$, we select the codeword that maximizes the antenna gain at this point by eigenvalue decomposition. Finally, the phases of the codewords are quantized according to the number of bits of the phase shifters $N_b$.  Note that the choice of ${\mathcal W_d}$ is not very critical as shown in \cite{Automatic_Jianhua19} as long as $N_d$ is big enough.

	\subsection{Hand Model}

	There are several works in the literature that study the effect of the hand blockage on the antennas' radiation patterns in mmWave bands. For quantitative and analytical models, the 3GPP standard \cite{3GPP2017} assumes a 30 dB loss across a region on the sphere around the cell phone, where the boundaries of this region depend on whether the phone is held in landscape or portrait orientation. This model was revisited in \cite{Statistical_Raghavan18}, where a statistical model for the affected region was proposed instead of a flat 30 dB loss. However, both of these models do not differentiate between different hand grips and only distinguish the portrait and the landscape orientations of the phone.

	    As we mentioned earlier, different hand grips affect the radiation patterns in distinct ways although the phone orientation is the same. Consequently, we cannot rely on the models used in \cite{3GPP2017,Statistical_Raghavan18}.
		Hence, our approach is to model the human fingers and then include it into HFSS simulations which will take care of all the possible irregular effects of the hand on the antenna radiation pattern. More specifically,
	we consider a two-layer model, where the first corresponds to the skin and the second models the rest of the human finger. The dielectric properties for the skin are averaged over the wet and dry conditions and the dielectric properties for the second layer are averaged over the properties of the bone, muscle, and fat. The used values are shown in Table 1 and taken from     \cite{An_Andreuccetti12}. The size of the finger is taken to be the average size of personnel in the US Army as recorded in \cite{Hand_Greiner91} and the thickness of the skin is assumed to be $2$ mm \cite{mmWave_Zhao15}.

		\begin{table}[]
		\centering
		\caption{Dielectric properties of different materials at frequency $39$ GHz.}
		\label{tb:DiElec}
			\resizebox{\columnwidth}{!}{
		\begin{tabular}{|l|l|l|l|}
			\hline
			\rowcolor[HTML]{EFEFEE}
			Material &   Conductivity [S/m]     &  Relative permittivity  & Loss tangent       \\ \hline
			Skin (Dry) & 31.429 &	11.983&	1.2089  \\ \hline
			Skin (Wet) & 32.432 &	14.386&	1.0391 \\ \hline
			Muscle & 42.501 &	18.639 &	1.051  \\ \hline
			Fat & 2.174 &	3.424&	0.2926 \\ \hline
			Bone & 6.28 &	4.7268&	0.5637  \\ \hline
			Layer 1 & 31.9305 &	13.1845 &	1.124 \\ \hline
			Layer 2 & 12.703 & 7.248 &0.6069  \\ \hline
		\end{tabular}}
	\end{table}

    Given this model for the hand, we can show the effect of the hand blockage on the antenna's radiation pattern. In Fig. \ref{fig:RadWOandW}, we plot the spherical gain of one patch antenna element designed by us with and without blockage. Note that these results are directly taken from HFSS simulations. The figure shows about 20-25 dB loss in the boresight direction (z-axis). It also shows the irregular effect of the blockage on the radiation pattern which makes it hard to predict using an analytical model and justifies our reliance on HFSS simulations to capture the effect of reflections, couplings, and attenuation caused by fingers.

	\subsection{Simulating Different Hand Grips}\label{Sec:SDHG}

	Due to the diverse hand grips in terms of the position of the fingers on the phone, simulating all of them, where we take precisely the positions of the fingers on the phone, is infeasible. Hence, we consider a simplified way where we partition the faces of the phone into disjoint regions, each with the size of the antenna module. We focus on the cases where the region is fully blocked. In other words, in case of blocking, we assume that the finger covers the whole region. This is a reasonable assumption given that the antenna modules are small compared to the finger due to the short wavelength.

	Moreover, since the loss is more severe when the fingers are in close proximity to the antenna, due to the reflections, coupling, and attenuation as we mentioned earlier, we focus on the regions at the corners of the mobile phone, where the antenna modules are placed. Hence, in total, we have $9$ possible regions, each corresponds to one of the modules shown in Fig. \ref{fig:Designs}. Note that since we consider only the the $9$ regions directly located above the modules, we neglect the cases where the human finger is placed on the face of the phone. However, due to the high attenuation of the screen, as shown in Fig. \ref{fig:RadWOandW}, the attenuation caused by the finger on these regions can be neglected.

	Based on this, we have $2^{9}$  possible combinations of blocked regions. Simulating all of these is infeasible since simulators like HFSS are time-consuming. Consequently, we simulate the $9$ cases which correspond to the presence of the finger on each module separately; these cases are referred to as the elementary cases hereafter. For each elementary case, we have an antenna response vector for each point $x_i$, $\mathbf M_i^{(j)}$, where $j\in \{1, 2, \cdots, 9\}$, which we get from HFSS. Then for the cases where more than one module is blocked, we construct the radiation pattern using the elementary cases as follows.

	Assume that for a certain grip $n$, the blocked modules are given by the set $\mathcal B \subset \{1, 2, \cdots, 9\}$ and the antenna response vector for this grip at point $x_i$ is denoted as $\mathbf M^{(n)}_i$. Then the response for the $k^{\rm th}$ antenna at point $x_i$ is given by
	\begin{equation} \label{Eq:elementPatternHandgrip1}
	\left[\mathbf M^{(n)}_i \right]_k= \left[\mathbf M^{(j^{*})}_i \right]_k,
	\end{equation}
	where,
	\begin{equation}\label{Eq:elementPatternHandgrip2}
	j^{*}= \argmin_{j \in \mathcal B} \left|\left[\mathbf M^{(j)}_i \right]_k \right|,
	\end{equation}
	where $\left[\mathbf{A}\right]_k$ stands of the $k^{\rm th}$ element of a vector $\mathbf{A}$.
	Eq. \eqref{Eq:elementPatternHandgrip1}-\eqref{Eq:elementPatternHandgrip2} mean that for each antenna and each point $x_i$, the antenna response is chosen to be the one that has the minimum gain from all the responses of the cases given in $\mathcal B$.
	By following this approach, we can find the radiation pattern given any hand grip using just the $9$  elementary cases we discussed, which significantly simplifies finding the radiation patterns, since it can be done without the need of using HFSS.

\section{Activities and Hand Grips} \label{Sec:HandGrips}

\begin{table}[]
	\centering
	\caption{Different hand grips along with the blocked regions.}
	\label{tb:DiffGrips}
		\begin{tabular}{|l|l|l|l|}
			\hline
			\rowcolor[HTML]{EFEFEE}
			Grip ID &   Blocked Modules  &Grip ID &   Blocked Modules     \\ \hline
			1 &  None & 8 & 1, 2, 3, 5, 7, 9.  \\ \hline
			2 & 1, 3, 4, 5, 7,9. &9 &   4, 7, 8, 9. \\ \hline
			3 &   7, 8, 9. &10 & 1, 2, 3, 4, 5, 7.\\ \hline
			4 &    7, 8.& 11 & 1, 2, 3, 5, 6, 7, 8, 9.\\ \hline
			5 &   8.&12 &  2, 3, 4, 5, 6.  \\ \hline
			6 & 1, 2, 3, 4, 5, 7, 9.&13 & 1, 2, 3.\\ \hline
			 7 & 1, 2, 3, 4, 5, 7, 8, 9. &14 & 1, 4, 7.\\ \hline
	\end{tabular}
\end{table}

	 To the best of our knowledge, there is no available database that records how users hold their phones while performing certain activities. Hence, we performed our own experiment. We asked eight users to hold a phone and  perform certain activities and then the blocked modules, shown in Fig. \ref{fig:Designs}, were noted by covering the phone with stickers.  The users were asked to watch a video, play a game, make a phone call, and text a message in both landscape and portrait orientations. The obtained hand grips are summarized in Table \ref{tb:DiffGrips}, where we list the blocked modules for each grip. For comparison, we include the no-blockage case and denote it as Grip $1$. In Table \ref{tb:ActGrips}, we show the type of grips observed for each activity along with their approximate frequencies. In addition, we have included the case where the phone is in the user's pocket and the screen is facing outwards for comparisons

\begin{table}[]
	\centering
	\caption{Activities and hand grips.}
	\label{tb:ActGrips}
	{%
		\begin{tabular}{|l|l|l|}
			\hline
			\rowcolor[HTML]{EFEFEE}
			Activity & Grip IDs & Respective Probabilities \\ \hline
			Game Portrait &  3 & $1$\\ \hline
			Game Landscape &  6, 7 ,8 & $\nicefrac{3}{8}, \ \nicefrac{2}{8},\  \nicefrac{3}{8}.$\\ \hline
			Video Portrait &  4, 9, 12 & $\nicefrac{3}{4}, \ \nicefrac{1}{8}, \ \nicefrac{1}{8}.$\\ \hline
			Video Landscape &  3, 10, 11, 12 & $\nicefrac{1}{8}, \  \nicefrac{3}{8}, \ \nicefrac{1}{4}, \ \nicefrac{1}{4}.$\\ \hline
			Messaging Portrait &  3 & $1$\\ \hline
			Messaging Landscape &  2, 6, 13 & $\nicefrac{3}{8}, \ \nicefrac{1}{4}, \ \nicefrac{3}{8}$\\ \hline
			Voice Call & 3, 4, 5& $\nicefrac{1}{4}, \ \nicefrac{1}{2}, \ \nicefrac{1}{4} $\\ \hline
			Pocket  & 14& 1\\ \hline
	\end{tabular}}
\end{table}

\section{Codebook Adaptation with Hand Grips}\label{Sec:Codebook}

Using HFSS along with our models for the mobile phone and the hand, we can obtain the antenna gains for each grip in Table \ref{tb:DiffGrips}. This section focuses on how the codebook design can be adapted with these grips.

\subsection{Grip-Aware Scheme}

 For this scheme, we assume that the phone knows exactly the hand grip and the corresponding antenna radiation patterns. With this knowledge, the phone determines a codebook that is specifically optimized for the current user grip. Hence, the codebook design algorithm in this scheme is the same as designing the codebook for the free space case described in Section \ref{Sec:SCaH}, except that the antenna response vectors $\mathbf M_i, \ \forall i \in \{1, \cdots N_p \}$ are replaced by the antenna response vectors for each grip which are found by using the methods we described in Section \ref{Sec:SDHG}. In total, we have a codebook specifically designed for each hand grip.

{ Although estimating the user hand grip by the mobile phone, through capacitive touch sensors and infrared proximity sensors \cite{Sensing_Hinckley00,Hand_Kim06}, can bring many benefits in terms of providing a natural experience between the mobile phone and the user, current devices do not have the capabilities to provide an accurate estimation of the user hand grip. Moreover, it requires a different codebook for each different grip which may not be feasible due to storage limitation in the RF chipset and the switching overhead. Accordingly, this scheme can be thought of as an upper bound on the gain we can achieve by adapting the codebook based on the user grip.}

\subsection{Semi-Aware Scheme}

 In this scheme, only the orientation of the phone and the application the user is using are assumed to be known by the mobile device. The rationale behind it is that although users hold their phones in various ways while performing the same activity depending on their personal habits and the environment, there are certain patterns that are highly correlated for a given activity. An analogy was drawn in \cite{Hand_Kim06} with traditional hand tools (e.g., hammer, cup, etc.), where the grip can be different for individual users, but still there is a correlation between different grips.\footnote{Note that in our work, we try to estimate the grip based on the activity and the orientation. In \cite{Hand_Kim06}, it is the opposite, i.e., they tried to estimate the activity based on the grip.}  Hence, in this scheme, we exploit this correlation by designing a codebook for each activity, instead of a codebook for each hand grip, which significantly reduces the number of stored codebooks. Moreover, current mobile phones can distinguish the orientation of the phone along with the application the user is using (or at least the genre of the activity).

The codebooks are designed as follows: for each pair of activity and orientation, design a codebook that maximizes the weighted mean of the spherical coverage over the common hand grips for this activity and orientation.  We choose the {\it weighted} mean since some grips are less common than others. However, the weighted mean is just an example of the desired objective function. The same algorithm can be used to maximize the minimum over all the grips (i.e., the design is based on the worst case scenario) or the sum-log of the spherical coverage, to ensure some fairness across different grips.

Mathematically, denote the set of grips for an activity as $\mathcal B$ and the corresponding likelihood vector as ${\mathbf P}$. Then the codebook is found by solving the following optimization problem, which is an extension to \eqref{Eq:OptiPro}.
\begin{equation}
{\mathcal W_{c}}=\argmax_{ \left\{ {\mathbf w_1}, \cdots, {\mathbf w}_{N_c} \right\}\subset {\mathcal W_d}} \sum\limits_{j\in \mathcal B}{\mathbf P}(j) \bar{\mathcal{S}}^{(j)}(\{{{\mathbf w}_1, \cdots, {\mathbf w}_{N_c}}\}),\label{Eq:OptiProGrip}
\end{equation}
where $\bar{\mathcal{S}}^{(j)} (\cdot)$ is the average spherical gain, as defined in \eqref{Eq:AveSC}, for the $j^{\rm th}$ grip.

\subsection{Grip-Agnostic Scheme}
 This is the benchmark scheme, where the codebook is designed assuming no blockage, and the mobile phone does not adapt its codebook with different hand grips. Hence, the codebook is designed exactly as described in Section \ref{Sec:SCaH}.

 In the next section, we compare these schemes, and show the importance of including the hand grips into the beam codebook design.

\section{Simulation Results}\label{Sec:SimRes}
In this section, we study the performance of the different codebook adaptation schemes using the data presented in Section \ref{Sec:HandGrips}.  The raw radiation data is taken from HFSS and processed in MATLAB. For the spherical coverage, we focus on the region described by $0^\circ \leq \theta \leq 100^\circ$ and  $0^\circ\leq \phi <360^\circ$, where $\theta$ is  the elevation  angle, and $\phi$ is the azimuth angle, which includes the whole hemisphere facing the back of the phone, plus the adjacent $10$ degrees from the other hemisphere. The reason behind this choice is that the region directly facing the screen is already dead because of the screen blockage and the front-to-back attenuation of the patch antennas as we described earlier. Hence, changing the codebook design algorithms or the hand grip adaptation schemes will not have an impact on this region. The following values of the parameters are chosen: $N_p=5809$, $N_c=15$, and $N_d=363$.

\begin{table*}[t]
  \centering
  \caption{The gain in  the percentiles of the spherical coverage for different codebook adaptation schemes relative to the grip-agnostic scheme.}
    \begin{tabular}{|c|r|r|r|r|r|r|}
    \hline\rowcolor[HTML]{EFEFEE}
          & \multicolumn{2}{c|}{20$^{\rm th}$ Percentile} & \multicolumn{2}{c|}{50$^{\rm th}$ Percentile} & \multicolumn{2}{c|}{80$^{\rm th}$ Percentile} \\
    \hline\rowcolor[HTML]{EFEFEE}
    Activity & \multicolumn{1}{c|}{Semi-Aware} & \multicolumn{1}{c|}{Grip-Aware} & \multicolumn{1}{c|}{Semi-Aware} & \multicolumn{1}{c|}{Grip-Aware} & \multicolumn{1}{c|}{Semi-Aware} & \multicolumn{1}{c|}{Grip-Aware} \\
    \hline
    Call  & 26\%   & 27\%   & 19\%   & 19\%   & 8\%   & 10\% \\
    \hline
    Game Port & 37\%   & 37\%   & 21\%   & 21\%   & 12\%   & 12\% \\
    \hline
    Game Land & 34\%   & 49\%   & 44\%   & 54\%   & 25\%   & 30\% \\
    \hline
    Video Port & 20\%   & 29\%   & 16\%   & 18\%   & 11\%   & 11\% \\
    \hline
    Video Land & 20\%   & 29\%   & 16\%   & 18\%   & 11\%   & 11\% \\
    \hline
    Msg Port & 37\%   & 37\%   & 21\%   & 21\%   & 12\%   & 12\% \\
    \hline
    Msg Land & 13\%   & 23\%   & 7\%   & 15\%   & 10\%   & 18\% \\
    \hline
    Pocket & 57\%   & 57\%   & 40\%   & 40\%   & 26\%   & 26\% \\
    \hline
    \end{tabular}%
  \label{tab:MainRes}%
\end{table*}%

The 20$^{\rm th}$, 50$^{\rm th}$, and 80$^{\rm th}$ percentiles of the spherical coverage for the different codebook adaptation schemes are presented in Table \ref{tab:MainRes}. The results are found as follows.

For the {\it Grip-Agnostic} scheme, the codebook is designed based on the radiation vectors of the no blockage case.
Then the performance of this codebook is evaluated for each hand grip in Table \ref{tb:DiffGrips}, in terms of the spherical coverage. Hence, we have 14 different sets of data which represents the spherical coverage for each grip assuming the no blockage codebook. Then, for each activity, the weighted mean of the percentiles, based on Table \ref{tb:ActGrips}, is found. For the  {\it Grip-Aware} scheme, a codebook is designed for each hand grip, and then the spherical coverage is found for each grip assuming the codebook that is specifically designed for it. The shown percentiles for the different activities are also the weighted mean of the percentiles for each grip. Finally, for the {\it Semi-Aware} scheme, a single codebook is designed for each activity as described in Section \ref{Sec:Codebook}. Then for each activity, the spherical coverage distributions are evaluated for the activity's corresponding grips assuming the codebook designed for this activity. The percentiles are found in a similar way to the previous cases. To simplify the comparison, the results are normalized by the {\it Grip-Agnostic} data, i.e., the results are the gains compared to the {\it Grip-Agnostic} scheme.

First, we start by comparing the {\it Grip-Aware} scheme, which represents the maximum gain we can obtain by adapting the codebook according to the hand grip, and the {\it Grip-Agnostic} scheme, which is our benchmark scheme that is based on the no-blockage case. As the figures show, we get a considerable gain that ranges between $23\%$ to $57\%$ at $20^{\rm th}$ percentile by adapting the codebook according to the user hand grip. We also see gains at the $50^{\rm th}$ and the $80^{\rm th}$ percentiles. However, an improvement of the $20^{\rm th}$ percentile is more important for coverage, since it corresponds to the regions where we have a low signal quality, and the user might have a link-failure in case the signal comes from these regions. Additionally, note that the gap between the {\it Grip-Aware} and the {\it Grip-Agnostic} schemes varies depending on the activity. In general, the more elements are blocked by the grips, the more benefits brought by adapting the codebook. Hence, for the activities that have grips blocking many elements, the gap between the two schemes is larger. These results also show that the designer does need to take the hand grip into account while designing the beam codebook. A careful codebook design by taking the hand grips into account is necessary and results in a significant performance gain.

However, the obtained gains from the {\it Grip-Aware} scheme may be unrealistic given the current mobile devices, since it is based on the assumption that the mobile device can accurately detect the user hand grip and this feature is not fully available in the current mobile phones. Moreover, the beam codebook switching based on the grip may result in high overheads that reduce the gain obtained from this scheme. Hence, we compare the {\it Grip-Aware} scheme with the proposed {\it Semi-Aware} scheme, since it is a practical scheme that only requires the knowledge of the application the user is using and the orientation of the phone. Moreover, since the same codebook is used for each activity, the switching overheads mentioned previously are significantly reduced.

The results show that the {\it Semi-Aware} scheme provides gains ranging between $13\%$ and $57\%$ in terms of the $20^{\rm th}$ percentile, which are less compared to the gains offered by the {\it Grip-Aware}, but are still significant compared to the  {\it Grip-Agnostic} scheme. The variation in the gap between the {\it Semi-Aware} and the {\it Grip-Agnostic} schemes can be explained in the same way we explained the gap between the {\it Grip-Aware} and the {\it Grip-Agnostic} schemes. The variation in the gap between the {\it Grip-Aware} and the  {\it Semi-Aware} schemes can be explained by the grip correlation of a activity, i.e., the gap is smaller for the activities that have highly correlated grips. Of course, in the cases where there is only one grip, as in the case of the {\it Msg Portrait}, {\it Game Portrait}, and {\it Pocket} activities, the performance of the two schemes is exactly the same. Conversely, for the case of the {\it Call} activity, the performance is very close due to the high correlation between the different grips obtained for the Call activity as shown in Table \ref{tb:ActGrips}.  Overall, the results show that we can still harvest performance gains with just knowledge of the application and the mobile orientation.

\section{Conclusion} \label{Sec:Conc}
In this work, we studied how the mmWave beamforming codebook can be adapted based on the user handgrip. We consider a practical design of the antenna placement on the mobile phone and a practical codebook design scheme. Then we study three different codebook adaption schemes: a grip-aware scheme, where perfect knowledge of the hand grip is available; a semi-aware scheme, where just the application (voice call, messaging, etc.) and the orientation of the mobile handset is known; and a grip-agnostic scheme, where the codebook ignores hand blockage.  Our results show that the ideal grip-aware scheme and the practical semi-aware can provide up to $50\%$ gain in terms of the spherical coverage over the agnostic scheme, depending on the grips and user activities.

 \bibliographystyle{IEEEtran}

\section{Introduction}

   A critical aspect of millimeter-wave (mmWave) signals  is its sensitivity to blockage by the human hand \cite{Statistical_Raghavan18} which has to be accounted for while designing beamforming codebooks. Beamforming, which is required to combine the signals from different antennas, is a critical part of mmWave communications since it relies on high array gains \cite{Millimeter_Raghavan17}.

   Although digital beamforming is elegant theoretically and results in  excellent array gains, the commercial devices will most probably avoid using fully-digital beamforming due to its complexity, both in hardware and signal processing \cite{MIMO_Alkhateeb14, Automatic_Jianhua19}. Instead, analog beamforming, which is based on pre-designed codebooks, is proposed as an alternative and supported by the 3GPP 5G NR standard \cite{3GPP2018}.
   The idea is that a set of beamforming vectors (codewords) is predetermined, and the device switches between these codewords to select the one that maximizes the antenna gain in the direction of the received signal. A comparison between digital and analog codebook beamforming has been conducted recently in \cite{Antenna_Raghavan19}, where the authors showed that the codebook beamforming can balance the trade-off between the overhead complexity and array gain and can perform close to the digital beamforming. Another recent study was performed in \cite{Automatic_Jianhua19}, which proposes and compares different heuristic approaches to design the beam codebooks taking into account the antennas' radiation pattern.

	However, \cite{Automatic_Jianhua19} only considers the free space propagation without the possible hand blockage and \cite{Antenna_Raghavan19} focuses on comparing different antenna types and comparing the analog codebook beamforming and the digital one. Moreover, their model of the human hand is either based on a stochastic model \cite{3GPP2017}, which assumes a 30 dB flat loss in the antenna gain due to the hand blockage, or a statistical loss \cite{Statistical_Raghavan18}, which only differentiates between the blockage in landscape and portrait orientations. It is well-known that users hold their phones in different ways depending on the applications they are using, the environment,  and their habits. These different hand grips affect the radiation patterns in distinct ways even though the phone orientation is the same. For example, while in the landscape orientation, the user can hold the phone with both hands or a single hand. The effect of single hand blockage on the radiation patterns can be quite different from that of dual hand blockage because when the fingers are near the antenna, the radiation is influenced more by coupling, reflection, and attenuation caused by the finger \cite{mmWave_Zhao15,Efficiency_Khan18}.

	In this work, we focus on the problem of adapting the beam codebooks according to the available knowledge of the user hand grip. More specifically, we consider a practical placement of the antennas on the mobile device and a practical design algorithm of the beam codebooks. We also use high-frequency structure simulator (HFSS) to obtain the antenna radiation patterns, where we include our model of the human hand into the simulations to capture the irregularities in the radiation patterns caused by the hand and to avoid using oversimplified analytical models. To this end, we compare three codebook adaptation schemes: An idealistic {\it grip-aware} scheme, which assumes that the device can accurately detect the hand grip and use a codebook that is specifically designed for it; a more practical scheme we call the {\it semi-aware} scheme, which is based on the assumption that the device only knows the orientation of the device and the active application the user is using; and a benchmark {\it grip-agnostic} scheme, where the codebook is designed assuming no-blockage and does not accommodate the hand grip. We show that the {\it grip-aware} and the {\it semi-aware} schemes can achieve over $57\%$ gain in terms of the spherical coverage compared to the {\it grip-agnostic} scheme, where the gain depends on the activity. Overall, our results show that beamforming codebooks must be adapted to the hand grip. Otherwise, a significant loss of the spherical coverage is expected which might lead to a link failure.

	\section{System Model}\label{Sec:SysMod}

	\subsection{Antenna and Mobile Design}

	 A good design for the mobile device must have different antenna arrays with different orientations, such that each array is able to receive the signal from certain directions (coverage region). What's more, there must be overlap between the different coverage regions for the antenna arrays to account for possible hand blockage. To this end, different antenna designs were proposed in 3GPP meetings  \cite{Samsung_Consideration17,Qualcomm_Consideration17,Apple_Consideration17} and studied in the literature \cite{Antenna_Raghavan19} to ensure the previous requirements. We consider the design shown in Fig. \ref{fig:Designs}, where we have three $2\times 2$ patch antenna modules placed on top two corners and the right bottom corner of the back of the phone. Also, each is surrounded by two modules of dipole antennas on the edges.
	\begin{figure}[t]
		\centering
			\centerline{\includegraphics[width=  3in]{./D1_1.pdf}}
		\caption{\, The considered antenna placements.}
		\label{fig:Designs}
	\end{figure}
	Note that we consider a mix of edge (dipole) and face (patch) antenna arrays. This is because the $2\times2$ patch array provides good spherical coverage to the hemisphere on the back of the phone, but it cannot be used to receive (transmit) signals from (through) the front end of the phone because of the front-to-back ratio of the patch antenna as well as blockage by the screen \cite{Statistical_Raghavan18}. On the other hand, the dipole antenna arrays can be used to extend the coverage region to the sides of the device, but it also restricts us to linear antenna arrays due to size constraints. Note that there is also redundancy since some arrays point to the same direction. This is because we need to account for possible hand blockages which can severely reduce the gain of the blocked antenna as shown later in this work.

    To reduce the complexity of the management and design of the beam codebook, the mobile device is restricted to use one array at a time, referred to as an antenna module, which is either a $2 \times 2$ patch array or a $1 \times 2$ dipole array. This design will be studied in the following sections in terms of the spherical coverage in free space as well as in the presence of hand blockage.
	\subsection{Spherical Coverage and HFSS}\label{Sec:SCaH}

	The main performance metric considered in this work is {\it spherical coverage} which corresponds to the antennas' far field gain over all possible directions. To quantify it, we discretize the unit sphere uniformly, and then the antenna gain is found for each point on the sphere. More rigorously, let $\mathcal X=\left\{x_i=(\theta_i,\phi_i), \ \forall i \in \{1,2, \cdots, N_p\}\right\}$ be a set of points uniformly distributed on the surface of the unit sphere, where $N_p$ is the number of points
	and  $0^\circ \leq \theta_i \leq 180^\circ $, $0^\circ \leq \phi_i < 360^\circ$ are the spherical coordinates of the $i^{\rm th}$ point. Each point represents one possible direction for the signal to arrive from. In other words, we have discretized the possible angle of arrivals (AoAs). The handset has a set of beamforming vectors (codewords), referred to as a codebook $\mathcal W_c$, and chooses the codeword that maximizes the antenna gain given the AoA. Let the gain at point $x_i$ be denoted by $G_{i}({\mathbf w})\in \mathbb{R}_{+}$, given a codeword ${\mathbf{w}}\in \mathbb{C}^{N_t \times 1}$, where $N_t$ is the total number of antennas.  Then the spherical coverage is defined as follows
	 \begin{equation}\label{eq:SphericalCovMat}
	\mathcal{S}(\mathcal{W}_c)=\{\max_{{\mathbf w} \in {\mathcal W_c}} G_i({\mathbf w}), \ \forall i \in \{1,2, \cdots, N_p\}\}.
	\end{equation}

	Based on this, the mean spherical coverage across all points on the sphere given a codebook $\mathcal W_c$, denoted by $\bar{\mathcal{S}}(\mathcal W_c)$,  is given by
	\begin{equation}\label{Eq:AveSC}
	\bar{\mathcal{S}}({\mathcal W_c})=\frac{1}{N_p} \sum\limits_{i=1}^{N_p} \max_{\mathbf w \in {\mathcal W_c}} G_i(\mathbf w).
	\end{equation}

	To compute the antenna gain $G_{i}({\mathbf w})$ given a certain setup of antennas, we use an electromagnetic simulation software called HFSS, since the theoretical models fall short in capturing the irregularities in the antennas' radiation patterns. The design shown in Fig. \ref{fig:Designs} was built in HFSS, where the antennas were designed for 39 GHz carrier frequency with a half wavelength separation. In this design, we did not add the different components in the phone and only modeled the screen, since it is the main source of reflections and absorption.

	Using HFSS, we get the antenna response of each element in each array for each direction $x_i$. Hence, for a given direction $x_i$, we have an antenna response vector, which we denote by ${\mathbf{M}_{i}}\in \mathbb{C}^{1 \times N_t}$, and the antenna gain is given by
	\begin{equation}\label{Eq:Gain}
	G_{i}({\mathbf w})= {\mathbf{w}}^{H} {\mathbf{M}}_{ i}^{H} {\mathbf{M}}_{i} {\mathbf{w}},
	\end{equation}
	where ${\mathbf w}^{H}$ is the Hermitian (conjugate) transpose of the vector ${\mathbf w}$.

 \begin{figure*}
	\centering
	\begin{subfigure}{\columnwidth}
		\centerline{\includegraphics[width=  2.6in]{./RadWO2.png}}
		\caption{\, Without blockage.}
		\label{fig:RadWO}
	\end{subfigure}%
	\begin{subfigure}{\columnwidth}
		\centering
		\centerline{\includegraphics[width=  2.6in]{./RadW2.png}}
		\caption{\, With blockage.}
		\label{fig:RadW}
	\end{subfigure}
	\caption{The 3D antenna gain in dB of a patch antenna with and without blockage by a finger. }
	\label{fig:RadWOandW}\vspace{-0.4cm}
\end{figure*}

	At this point, we need to design the codebook  to maximize some function of the spherical coverage.
	In this work, we choose the codebook ${\mathcal W_c}$ that maximizes the mean spherical coverage out of a given large set of candidate codewords ${\mathcal W_d}$, where the set ${\mathcal W_d}$ satisfies all the required conditions on the maximum transmit power and the finite number of bits in the phase shifter. Hence, we have the following optimization problem
	\begin{equation}
	{\mathcal W_{c}}=\argmax_{ \left\{ {\mathbf w_1}, \cdots, {\mathbf w}_{N_c} \right\} \subset {\mathcal W_d}} \bar{\mathcal{S}}(\{{{\mathbf w}_1, \cdots, {\mathbf w}_{N_c}}\}),\label{Eq:OptiPro}
	\end{equation}
	which is a combinatorial problem and solving it using an exhaustive search is not feasible given a large set ${\mathcal W_d}$ and a large number of points $N_p$. Different heuristic approaches to solve this problem were discussed in detail in \cite{Automatic_Jianhua19}. In this work, we adopt the greedy approach which we now  describe. The greedy approach is an iterative one, where the first codeword is selected to maximize the mean spherical coverage given by \eqref{Eq:AveSC}. The second codeword is also chosen to maximize the mean spherical coverage, but given that we have already selected the first codeword. In other words, the second codeword is chosen such that the composite spherical coverage of the first and second codewords is maximized. Hence, the choice of second codeword is biased to select the one that points the beam in a different direction of the first codeword. Subsequently,  the $N^{\rm th}$ codeword is found by
	  \begin{align}
	{\mathbf w}_{N}=\argmax_{{\mathbf w}\in {\mathcal W_d} \setminus \{{\mathbf w}_1, \cdots,{\mathbf w}_{N-1}\}} \frac{1}{N_p}f({\mathbf w}),
	\end{align}
	where
	\begin{align}
	&\!\!\!\!\!\!\!\!\!f({\mathbf w})=  \sum\limits_{i=1}^{N_p}  \max \left( G_i({\mathbf w}),G_i({\mathbf w}_1), \cdots, G_i({\mathbf w}_{N-1}) \right).\label{Eq:OptiProN}
	 \end{align}

	This approach is only optimal if the desired codebook size is one and otherwise, it is suboptimal. However, it was shown in \cite{Automatic_Jianhua19} that it performs  well compared to other more sophisticated algorithms.

	Before wrapping up this section, we discuss the choice of the candidate set of codewords ${\mathcal W_d}$. There are many options to construct ${\mathcal W_d}$ as shown in \cite{Automatic_Jianhua19}. In this work, we select a subset of points $\mathcal Y$ from $\mathcal X$ (i.e., $\mathcal Y \subset \mathcal X$) that has a length $N_d \ll N_p$. Then, for each point $y\in \mathcal Y$, we select the codeword that maximizes the antenna gain at this point by eigenvalue decomposition. Finally, the phases of the codewords are quantized according to the number of bits of the phase shifters $N_b$.  Note that the choice of ${\mathcal W_d}$ is not very critical as shown in \cite{Automatic_Jianhua19} as long as $N_d$ is big enough.

	\subsection{Hand Model}

	There are several works in the literature that study the effect of the hand blockage on the antennas' radiation patterns in mmWave bands. For quantitative and analytical models, the 3GPP standard \cite{3GPP2017} assumes a 30 dB loss across a region on the sphere around the cell phone, where the boundaries of this region depend on whether the phone is held in landscape or portrait orientation. This model was revisited in \cite{Statistical_Raghavan18}, where a statistical model for the affected region was proposed instead of a flat 30 dB loss. However, both of these models do not differentiate between different hand grips and only distinguish the portrait and the landscape orientations of the phone.

	    As we mentioned earlier, different hand grips affect the radiation patterns in distinct ways although the phone orientation is the same. Consequently, we cannot rely on the models used in \cite{3GPP2017,Statistical_Raghavan18}.
		Hence, our approach is to model the human fingers and then include it into HFSS simulations which will take care of all the possible irregular effects of the hand on the antenna radiation pattern. More specifically,
	we consider a two-layer model, where the first corresponds to the skin and the second models the rest of the human finger. The dielectric properties for the skin are averaged over the wet and dry conditions and the dielectric properties for the second layer are averaged over the properties of the bone, muscle, and fat. The used values are shown in Table 1 and taken from     \cite{An_Andreuccetti12}. The size of the finger is taken to be the average size of personnel in the US Army as recorded in \cite{Hand_Greiner91} and the thickness of the skin is assumed to be $2$ mm \cite{mmWave_Zhao15}.

		\begin{table}[]
		\centering
		\caption{Dielectric properties of different materials at frequency $39$ GHz.}
		\label{tb:DiElec}
			\resizebox{\columnwidth}{!}{
		\begin{tabular}{|l|l|l|l|}
			\hline
			\rowcolor[HTML]{EFEFEE}
			Material &   Conductivity [S/m]     &  Relative permittivity  & Loss tangent       \\ \hline
			Skin (Dry) & 31.429 &	11.983&	1.2089  \\ \hline
			Skin (Wet) & 32.432 &	14.386&	1.0391 \\ \hline
			Muscle & 42.501 &	18.639 &	1.051  \\ \hline
			Fat & 2.174 &	3.424&	0.2926 \\ \hline
			Bone & 6.28 &	4.7268&	0.5637  \\ \hline
			Layer 1 & 31.9305 &	13.1845 &	1.124 \\ \hline
			Layer 2 & 12.703 & 7.248 &0.6069  \\ \hline
		\end{tabular}}
	\end{table}

    Given this model for the hand, we can show the effect of the hand blockage on the antenna's radiation pattern. In Fig. \ref{fig:RadWOandW}, we plot the spherical gain of one patch antenna element designed by us with and without blockage. Note that these results are directly taken from HFSS simulations. The figure shows about 20-25 dB loss in the boresight direction (z-axis). It also shows the irregular effect of the blockage on the radiation pattern which makes it hard to predict using an analytical model and justifies our reliance on HFSS simulations to capture the effect of reflections, couplings, and attenuation caused by fingers.

	\subsection{Simulating Different Hand Grips}\label{Sec:SDHG}

	Due to the diverse hand grips in terms of the position of the fingers on the phone, simulating all of them, where we take precisely the positions of the fingers on the phone, is infeasible. Hence, we consider a simplified way where we partition the faces of the phone into disjoint regions, each with the size of the antenna module. We focus on the cases where the region is fully blocked. In other words, in case of blocking, we assume that the finger covers the whole region. This is a reasonable assumption given that the antenna modules are small compared to the finger due to the short wavelength.

	Moreover, since the loss is more severe when the fingers are in close proximity to the antenna, due to the reflections, coupling, and attenuation as we mentioned earlier, we focus on the regions at the corners of the mobile phone, where the antenna modules are placed. Hence, in total, we have $9$ possible regions, each corresponds to one of the modules shown in Fig. \ref{fig:Designs}. Note that since we consider only the the $9$ regions directly located above the modules, we neglect the cases where the human finger is placed on the face of the phone. However, due to the high attenuation of the screen, as shown in Fig. \ref{fig:RadWOandW}, the attenuation caused by the finger on these regions can be neglected.

	Based on this, we have $2^{9}$  possible combinations of blocked regions. Simulating all of these is infeasible since simulators like HFSS are time-consuming. Consequently, we simulate the $9$ cases which correspond to the presence of the finger on each module separately; these cases are referred to as the elementary cases hereafter. For each elementary case, we have an antenna response vector for each point $x_i$, $\mathbf M_i^{(j)}$, where $j\in \{1, 2, \cdots, 9\}$, which we get from HFSS. Then for the cases where more than one module is blocked, we construct the radiation pattern using the elementary cases as follows.

	Assume that for a certain grip $n$, the blocked modules are given by the set $\mathcal B \subset \{1, 2, \cdots, 9\}$ and the antenna response vector for this grip at point $x_i$ is denoted as $\mathbf M^{(n)}_i$. Then the response for the $k^{\rm th}$ antenna at point $x_i$ is given by
	\begin{equation} \label{Eq:elementPatternHandgrip1}
	\left[\mathbf M^{(n)}_i \right]_k= \left[\mathbf M^{(j^{*})}_i \right]_k,
	\end{equation}
	where,
	\begin{equation}\label{Eq:elementPatternHandgrip2}
	j^{*}= \argmin_{j \in \mathcal B} \left|\left[\mathbf M^{(j)}_i \right]_k \right|,
	\end{equation}
	where $\left[\mathbf{A}\right]_k$ stands of the $k^{\rm th}$ element of a vector $\mathbf{A}$.
	Eq. \eqref{Eq:elementPatternHandgrip1}-\eqref{Eq:elementPatternHandgrip2} mean that for each antenna and each point $x_i$, the antenna response is chosen to be the one that has the minimum gain from all the responses of the cases given in $\mathcal B$.
	By following this approach, we can find the radiation pattern given any hand grip using just the $9$  elementary cases we discussed, which significantly simplifies finding the radiation patterns, since it can be done without the need of using HFSS.

\section{Activities and Hand Grips} \label{Sec:HandGrips}

\begin{table}[]
	\centering
	\caption{Different hand grips along with the blocked regions.}
	\label{tb:DiffGrips}
		\begin{tabular}{|l|l|l|l|}
			\hline
			\rowcolor[HTML]{EFEFEE}
			Grip ID &   Blocked Modules  &Grip ID &   Blocked Modules     \\ \hline
			1 &  None & 8 & 1, 2, 3, 5, 7, 9.  \\ \hline
			2 & 1, 3, 4, 5, 7,9. &9 &   4, 7, 8, 9. \\ \hline
			3 &   7, 8, 9. &10 & 1, 2, 3, 4, 5, 7.\\ \hline
			4 &    7, 8.& 11 & 1, 2, 3, 5, 6, 7, 8, 9.\\ \hline
			5 &   8.&12 &  2, 3, 4, 5, 6.  \\ \hline
			6 & 1, 2, 3, 4, 5, 7, 9.&13 & 1, 2, 3.\\ \hline
			 7 & 1, 2, 3, 4, 5, 7, 8, 9. &14 & 1, 4, 7.\\ \hline
	\end{tabular}
\end{table}

	 To the best of our knowledge, there is no available database that records how users hold their phones while performing certain activities. Hence, we performed our own experiment. We asked eight users to hold a phone and  perform certain activities and then the blocked modules, shown in Fig. \ref{fig:Designs}, were noted by covering the phone with stickers.  The users were asked to watch a video, play a game, make a phone call, and text a message in both landscape and portrait orientations. The obtained hand grips are summarized in Table \ref{tb:DiffGrips}, where we list the blocked modules for each grip. For comparison, we include the no-blockage case and denote it as Grip $1$. In Table \ref{tb:ActGrips}, we show the type of grips observed for each activity along with their approximate frequencies. In addition, we have included the case where the phone is in the user's pocket and the screen is facing outwards for comparisons

\begin{table}[]
	\centering
	\caption{Activities and hand grips.}
	\label{tb:ActGrips}
	{%
		\begin{tabular}{|l|l|l|}
			\hline
			\rowcolor[HTML]{EFEFEE}
			Activity & Grip IDs & Respective Probabilities \\ \hline
			Game Portrait &  3 & $1$\\ \hline
			Game Landscape &  6, 7 ,8 & $\nicefrac{3}{8}, \ \nicefrac{2}{8},\  \nicefrac{3}{8}.$\\ \hline
			Video Portrait &  4, 9, 12 & $\nicefrac{3}{4}, \ \nicefrac{1}{8}, \ \nicefrac{1}{8}.$\\ \hline
			Video Landscape &  3, 10, 11, 12 & $\nicefrac{1}{8}, \  \nicefrac{3}{8}, \ \nicefrac{1}{4}, \ \nicefrac{1}{4}.$\\ \hline
			Messaging Portrait &  3 & $1$\\ \hline
			Messaging Landscape &  2, 6, 13 & $\nicefrac{3}{8}, \ \nicefrac{1}{4}, \ \nicefrac{3}{8}$\\ \hline
			Voice Call & 3, 4, 5& $\nicefrac{1}{4}, \ \nicefrac{1}{2}, \ \nicefrac{1}{4} $\\ \hline
			Pocket  & 14& 1\\ \hline
	\end{tabular}}
\end{table}

\section{Codebook Adaptation with Hand Grips}\label{Sec:Codebook}

Using HFSS along with our models for the mobile phone and the hand, we can obtain the antenna gains for each grip in Table \ref{tb:DiffGrips}. This section focuses on how the codebook design can be adapted with these grips.

\subsection{Grip-Aware Scheme}

 For this scheme, we assume that the phone knows exactly the hand grip and the corresponding antenna radiation patterns. With this knowledge, the phone determines a codebook that is specifically optimized for the current user grip. Hence, the codebook design algorithm in this scheme is the same as designing the codebook for the free space case described in Section \ref{Sec:SCaH}, except that the antenna response vectors $\mathbf M_i, \ \forall i \in \{1, \cdots N_p \}$ are replaced by the antenna response vectors for each grip which are found by using the methods we described in Section \ref{Sec:SDHG}. In total, we have a codebook specifically designed for each hand grip.

{ Although estimating the user hand grip by the mobile phone, through capacitive touch sensors and infrared proximity sensors \cite{Sensing_Hinckley00,Hand_Kim06}, can bring many benefits in terms of providing a natural experience between the mobile phone and the user, current devices do not have the capabilities to provide an accurate estimation of the user hand grip. Moreover, it requires a different codebook for each different grip which may not be feasible due to storage limitation in the RF chipset and the switching overhead. Accordingly, this scheme can be thought of as an upper bound on the gain we can achieve by adapting the codebook based on the user grip.}

\subsection{Semi-Aware Scheme}

 In this scheme, only the orientation of the phone and the application the user is using are assumed to be known by the mobile device. The rationale behind it is that although users hold their phones in various ways while performing the same activity depending on their personal habits and the environment, there are certain patterns that are highly correlated for a given activity. An analogy was drawn in \cite{Hand_Kim06} with traditional hand tools (e.g., hammer, cup, etc.), where the grip can be different for individual users, but still there is a correlation between different grips.\footnote{Note that in our work, we try to estimate the grip based on the activity and the orientation. In \cite{Hand_Kim06}, it is the opposite, i.e., they tried to estimate the activity based on the grip.}  Hence, in this scheme, we exploit this correlation by designing a codebook for each activity, instead of a codebook for each hand grip, which significantly reduces the number of stored codebooks. Moreover, current mobile phones can distinguish the orientation of the phone along with the application the user is using (or at least the genre of the activity).

The codebooks are designed as follows: for each pair of activity and orientation, design a codebook that maximizes the weighted mean of the spherical coverage over the common hand grips for this activity and orientation.  We choose the {\it weighted} mean since some grips are less common than others. However, the weighted mean is just an example of the desired objective function. The same algorithm can be used to maximize the minimum over all the grips (i.e., the design is based on the worst case scenario) or the sum-log of the spherical coverage, to ensure some fairness across different grips.

Mathematically, denote the set of grips for an activity as $\mathcal B$ and the corresponding likelihood vector as ${\mathbf P}$. Then the codebook is found by solving the following optimization problem, which is an extension to \eqref{Eq:OptiPro}.
\begin{equation}
{\mathcal W_{c}}=\argmax_{ \left\{ {\mathbf w_1}, \cdots, {\mathbf w}_{N_c} \right\}\subset {\mathcal W_d}} \sum\limits_{j\in \mathcal B}{\mathbf P}(j) \bar{\mathcal{S}}^{(j)}(\{{{\mathbf w}_1, \cdots, {\mathbf w}_{N_c}}\}),\label{Eq:OptiProGrip}
\end{equation}
where $\bar{\mathcal{S}}^{(j)} (\cdot)$ is the average spherical gain, as defined in \eqref{Eq:AveSC}, for the $j^{\rm th}$ grip.

\subsection{Grip-Agnostic Scheme}
 This is the benchmark scheme, where the codebook is designed assuming no blockage, and the mobile phone does not adapt its codebook with different hand grips. Hence, the codebook is designed exactly as described in Section \ref{Sec:SCaH}.

 In the next section, we compare these schemes, and show the importance of including the hand grips into the beam codebook design.

\section{Simulation Results}\label{Sec:SimRes}
In this section, we study the performance of the different codebook adaptation schemes using the data presented in Section \ref{Sec:HandGrips}.  The raw radiation data is taken from HFSS and processed in MATLAB. For the spherical coverage, we focus on the region described by $0^\circ \leq \theta \leq 100^\circ$ and  $0^\circ\leq \phi <360^\circ$, where $\theta$ is  the elevation  angle, and $\phi$ is the azimuth angle, which includes the whole hemisphere facing the back of the phone, plus the adjacent $10$ degrees from the other hemisphere. The reason behind this choice is that the region directly facing the screen is already dead because of the screen blockage and the front-to-back attenuation of the patch antennas as we described earlier. Hence, changing the codebook design algorithms or the hand grip adaptation schemes will not have an impact on this region. The following values of the parameters are chosen: $N_p=5809$, $N_c=15$, and $N_d=363$.

\begin{table*}[t]
  \centering
  \caption{The gain in  the percentiles of the spherical coverage for different codebook adaptation schemes relative to the grip-agnostic scheme.}
    \begin{tabular}{|c|r|r|r|r|r|r|}
    \hline\rowcolor[HTML]{EFEFEE}
          & \multicolumn{2}{c|}{20$^{\rm th}$ Percentile} & \multicolumn{2}{c|}{50$^{\rm th}$ Percentile} & \multicolumn{2}{c|}{80$^{\rm th}$ Percentile} \\
    \hline\rowcolor[HTML]{EFEFEE}
    Activity & \multicolumn{1}{c|}{Semi-Aware} & \multicolumn{1}{c|}{Grip-Aware} & \multicolumn{1}{c|}{Semi-Aware} & \multicolumn{1}{c|}{Grip-Aware} & \multicolumn{1}{c|}{Semi-Aware} & \multicolumn{1}{c|}{Grip-Aware} \\
    \hline
    Call  & 26\%   & 27\%   & 19\%   & 19\%   & 8\%   & 10\% \\
    \hline
    Game Port & 37\%   & 37\%   & 21\%   & 21\%   & 12\%   & 12\% \\
    \hline
    Game Land & 34\%   & 49\%   & 44\%   & 54\%   & 25\%   & 30\% \\
    \hline
    Video Port & 20\%   & 29\%   & 16\%   & 18\%   & 11\%   & 11\% \\
    \hline
    Video Land & 20\%   & 29\%   & 16\%   & 18\%   & 11\%   & 11\% \\
    \hline
    Msg Port & 37\%   & 37\%   & 21\%   & 21\%   & 12\%   & 12\% \\
    \hline
    Msg Land & 13\%   & 23\%   & 7\%   & 15\%   & 10\%   & 18\% \\
    \hline
    Pocket & 57\%   & 57\%   & 40\%   & 40\%   & 26\%   & 26\% \\
    \hline
    \end{tabular}%
  \label{tab:MainRes}%
\end{table*}%

The 20$^{\rm th}$, 50$^{\rm th}$, and 80$^{\rm th}$ percentiles of the spherical coverage for the different codebook adaptation schemes are presented in Table \ref{tab:MainRes}. The results are found as follows.

For the {\it Grip-Agnostic} scheme, the codebook is designed based on the radiation vectors of the no blockage case.
Then the performance of this codebook is evaluated for each hand grip in Table \ref{tb:DiffGrips}, in terms of the spherical coverage. Hence, we have 14 different sets of data which represents the spherical coverage for each grip assuming the no blockage codebook. Then, for each activity, the weighted mean of the percentiles, based on Table \ref{tb:ActGrips}, is found. For the  {\it Grip-Aware} scheme, a codebook is designed for each hand grip, and then the spherical coverage is found for each grip assuming the codebook that is specifically designed for it. The shown percentiles for the different activities are also the weighted mean of the percentiles for each grip. Finally, for the {\it Semi-Aware} scheme, a single codebook is designed for each activity as described in Section \ref{Sec:Codebook}. Then for each activity, the spherical coverage distributions are evaluated for the activity's corresponding grips assuming the codebook designed for this activity. The percentiles are found in a similar way to the previous cases. To simplify the comparison, the results are normalized by the {\it Grip-Agnostic} data, i.e., the results are the gains compared to the {\it Grip-Agnostic} scheme.

First, we start by comparing the {\it Grip-Aware} scheme, which represents the maximum gain we can obtain by adapting the codebook according to the hand grip, and the {\it Grip-Agnostic} scheme, which is our benchmark scheme that is based on the no-blockage case. As the figures show, we get a considerable gain that ranges between $23\%$ to $57\%$ at $20^{\rm th}$ percentile by adapting the codebook according to the user hand grip. We also see gains at the $50^{\rm th}$ and the $80^{\rm th}$ percentiles. However, an improvement of the $20^{\rm th}$ percentile is more important for coverage, since it corresponds to the regions where we have a low signal quality, and the user might have a link-failure in case the signal comes from these regions. Additionally, note that the gap between the {\it Grip-Aware} and the {\it Grip-Agnostic} schemes varies depending on the activity. In general, the more elements are blocked by the grips, the more benefits brought by adapting the codebook. Hence, for the activities that have grips blocking many elements, the gap between the two schemes is larger. These results also show that the designer does need to take the hand grip into account while designing the beam codebook. A careful codebook design by taking the hand grips into account is necessary and results in a significant performance gain.

However, the obtained gains from the {\it Grip-Aware} scheme may be unrealistic given the current mobile devices, since it is based on the assumption that the mobile device can accurately detect the user hand grip and this feature is not fully available in the current mobile phones. Moreover, the beam codebook switching based on the grip may result in high overheads that reduce the gain obtained from this scheme. Hence, we compare the {\it Grip-Aware} scheme with the proposed {\it Semi-Aware} scheme, since it is a practical scheme that only requires the knowledge of the application the user is using and the orientation of the phone. Moreover, since the same codebook is used for each activity, the switching overheads mentioned previously are significantly reduced.

The results show that the {\it Semi-Aware} scheme provides gains ranging between $13\%$ and $57\%$ in terms of the $20^{\rm th}$ percentile, which are less compared to the gains offered by the {\it Grip-Aware}, but are still significant compared to the  {\it Grip-Agnostic} scheme. The variation in the gap between the {\it Semi-Aware} and the {\it Grip-Agnostic} schemes can be explained in the same way we explained the gap between the {\it Grip-Aware} and the {\it Grip-Agnostic} schemes. The variation in the gap between the {\it Grip-Aware} and the  {\it Semi-Aware} schemes can be explained by the grip correlation of a activity, i.e., the gap is smaller for the activities that have highly correlated grips. Of course, in the cases where there is only one grip, as in the case of the {\it Msg Portrait}, {\it Game Portrait}, and {\it Pocket} activities, the performance of the two schemes is exactly the same. Conversely, for the case of the {\it Call} activity, the performance is very close due to the high correlation between the different grips obtained for the Call activity as shown in Table \ref{tb:ActGrips}.  Overall, the results show that we can still harvest performance gains with just knowledge of the application and the mobile orientation.

\section{Conclusion} \label{Sec:Conc}
In this work, we studied how the mmWave beamforming codebook can be adapted based on the user handgrip. We consider a practical design of the antenna placement on the mobile phone and a practical codebook design scheme. Then we study three different codebook adaption schemes: a grip-aware scheme, where perfect knowledge of the hand grip is available; a semi-aware scheme, where just the application (voice call, messaging, etc.) and the orientation of the mobile handset is known; and a grip-agnostic scheme, where the codebook ignores hand blockage.  Our results show that the ideal grip-aware scheme and the practical semi-aware can provide up to $50\%$ gain in terms of the spherical coverage over the agnostic scheme, depending on the grips and user activities.

 \bibliographystyle{IEEEtran}