\documentclass[12pt]{article} \usepackage{e-jc} \specs{P4.28}{21(4)}{2014} \usepackage{amsthm,amsmath,amssymb,graphicx} \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} \def\NZQ{\mathbb} % the font for N,Z,Q,R,C \def\NN{{\NZQ N}} \def\QQ{{\NZQ Q}} \def\ZZ{{\NZQ Z}} \def\RR{{\NZQ R}} \def\CC{{\NZQ C}} \def\AA{{\NZQ A}} \def\BB{{\NZQ B}} \def\PP{{\NZQ P}} \def\FF{{\NZQ F}} \def\GG{{\NZQ G}} \def\HH{{\NZQ H}} % % \def\ab{\mathbf{a}} \def\hb{\mathbf{h}} \def\eb{\mathbf{e}} \def\tb{\mathbf{t}} \def\xb{\mathbf{x}} \def\yb{\mathbf{y}} \def\eb{\mathbf{e}} %--------------------------------------------------- % \def\opn#1#2{\def#1{\operatorname{#2}}} % to make operators %------------------------------------------------ % Numerical invariants of rings, ideals, and modules % \opn\aff{aff} \opn\con{conv} \opn\relint{relint} \opn\st{st} \opn\lk{lk} \opn\cn{cn} \opn\core{core} \opn\vol{vol} \opn\link{link} \opn\star{star} %------------------------------------------------ \def\Ac{{\mathcal A}} \def\Bc{{\mathcal B}} \def\Hc{{\mathcal H}} \def\Sc{{\mathcal S}} \def\Cc{{\mathcal C}} \def\Gc{{\mathcal G}} \def\Fc{{\mathcal F}} \def\Pc{{\mathcal P}} \def\Nc{{\mathcal N}} \def\Ec{{\mathcal E}} \def\Qc{{\mathcal Q}} % % % \newtheorem{Theorem}{Theorem}[section] \newtheorem{Lemma}[Theorem]{Lemma} \newtheorem{Corollary}[Theorem]{Corollary} \newtheorem{Proposition}[Theorem]{Proposition} \newtheorem{Problem}[Theorem]{Problem} \newtheorem{Conjecture}[Theorem]{Conjecture} \newtheorem{Question}[Theorem]{Question} \theoremstyle{definition} \newtheorem{Remark}[Theorem]{Remark} \newtheorem{Remarks}[Theorem]{Remarks} \newtheorem{Example}[Theorem]{Example} \newtheorem{Examples}[Theorem]{Examples} \newtheorem{Definition}[Theorem]{Definition} \pagestyle{plain} \title{\bf Integer decomposition property\\ of dilated polytopes} \author{David A. Cox \\ \small Department of Mathematics and Science \\ [-0.8ex] \small Amherst College, USA \\ [-0.8ex] \small\tt dacox@amherst.edu \and Christian Haase \\ \small Institut f\"ur Mathematik, \\ [-0.8ex] \small Freie Universit\"at Berlin, Germany \\ [-0.8ex] \small\tt haase@math.fu-berlin.de \and Takayuki Hibi \\ \small Department of Pure and Applied Mathematics, \\ [-0.8ex] \small Osaka University, Japan \\ [-0.8ex] \small\tt hibi@math.sci.osaka-u.ac.jp \and Akihiro Higashitani\\ \small Department of Mathematics, \\ [-0.8ex] \small Kyoto University, Japan. \\ [-0.8ex] \small\tt ahigashi@math.kyoto-u.ac.jp } \date{\dateline{Mar 18, 2014}{Oct 24, 2014}{Nov 6, 2014}\\ \small Mathematics Subject Classifications: Primary 52B20; Secondary 14Q15, 14M25.} \begin{document} \maketitle \begin{abstract} An integral convex polytope $\Pc \subset \RR^N$ possesses the integer decomposition property if, for any integer $k > 0$ and for any $\alpha \in k \Pc \cap \ZZ^{N}$, there exist $\alpha_{1}, \ldots, \alpha_k \in \Pc \cap \ZZ^N$ such that $\alpha = \alpha_{1} + \cdots + \alpha_k$. A fundamental question is to determine the integers $k > 0$ for which the dilated polytope $k\Pc$ possesses the integer decomposition property. In the present paper, combinatorial invariants related to the integer decomposition property of dilated polytopes will be proposed and studied. \end{abstract} \section*{Introduction} Integral convex polytopes have been studied from the viewpoints of commutative algebra and algebraic geometry together with enumerative combinatorics, combinatorial optimization and statistics. Recall that an {\em integral} convex polytope $\Pc \subset \RR^N$ is a convex polytope all of whose vertices have integer coordinates. There is an entire network \cite[p.2313]{MFO07} of combinatorial and algebraic properties that involve integral convex polytopes and their positive integer multiples \cite{BGcover,BGT,KKMS}. In particular, some properties may fail for given polytope but hold for a large positive integer multiple $k \Pc$. We call $k \Pc = \{ k \alpha : \alpha \in \Pc \} \subset \RR^{N}$ a {\em dilated polytope}. The surprise is that the threshold where a given property starts to hold can differ from one property to the next. The goal of the present paper is to explore these thresholds and relate them to other interesting invariants of integer points in polytopes. We begin with four aspects of an integral convex polytope $\Pc$ that will lead to six invariants. After defining the invariants, we will say more about what they mean. \medskip \noindent {\bf (0.1) Integer Decomposition Property.} $\Pc \subset \RR^N$ possesses the {\em integer decomposition property} or (IDP) for short if, for every integer $k = 1, 2, \ldots$ and for all $\alpha \in k \Pc \cap \ZZ^{N}$, there exist $\alpha_{1}, \ldots, \alpha_k$ belonging to $\Pc \cap \ZZ^N$ such that $\alpha = \alpha_{1} + \cdots + \alpha_k$. The (IDP) is important in the theory and application of integer programming (\cite[\S22.10]{Sch}). It also arises naturally in the study of toric varieties (\cite{BGT} and \cite[Ch.\ 2]{CLS}). Not every integral polytope possesses (IDP), but sufficiently large dilations do. The threshold where this first occurs leads to two numerical invariants of $\Pc$: \begin{align} \label{midpdef} &\text{$\mu_\text{midp}(\Pc) =$ the smallest integer $k > 0$ for which $k\Pc$ has (IDP)}. \\ \label{idpdef} &\text{$\mu_\text{idp}(\Pc) =$ the smallest integer $k > 0$ for which $n\Pc$ has (IDP) for all $n \ge k$}. \end{align} The reason for two invariants is that even if $k\Pc$ has (IDP), the same need not be true for $(k+1)\Pc$. We will give examples of this phenomenon in Example~\ref{rei}. If we weaken (IDP) by replacing ``for every integer'' with ``for every sufficiently large integer'', we get the notion of {\em very ample}. Thus $\Pc$ is very ample if, for every sufficiently large integer $k \gg 0$ and for any $\alpha \in k\Pc \cap \ZZ^N$, there exist $\alpha_1, \ldots, \alpha_k$ belonging to $\Pc \cap \ZZ^N$ such that $\alpha = \alpha_1 + \cdots + \alpha_k$. In particular, if $\Pc$ possesses (IDP), then $\Pc$ is very ample. The term ``very ample'' arises from toric geometry. By \cite[Proposition 2.1]{BDG}, the definition of very ample polytope given here is equivalent to the toric version given in \cite[Definition 2.2.17]{CLS}. Not every integral polytope is very ample, but sufficiently large dilations are. Hence we get the following invariant: \begin{equation} \label{vadef} \text{$\mu_\text{va}(\Pc) =$ the smallest integer $k > 0$ for which $k\Pc$ is very ample}. \end{equation} Note that if $k\Pc$ is very ample, then so is $(k+1)\Pc$. \smallskip \noindent {\bf (0.2) The Hilbert Basis.} $\Pc \subset \RR^{N}$ gives the rational polyhedral cone $\Cc(\Pc) \subset \RR^{N+1}$ generated by the vertices of $\widetilde{\Pc} = \Pc\times\{1\} \subset \RR^{N+1}$. A finite set of integer vectors $\{ \hb_{1}, \ldots, \hb_{s} \} \subset \ZZ^{N+1}$ is a {\em Hilbert basis} of $\Cc(\Pc)$ if every point of $\Cc(\Pc) \cap \ZZ^{N+1}$ is a nonnegative integer combination of $\hb_{1}, \ldots, \hb_{s}$. A Hilbert basis exists~\cite{Gordan} and a minimal Hilbert basis is unique~\cite{vanDerCorput}. Let $\Hc(\Cc(\Pc))$ denote the minimal Hilbert basis of $\Cc(\Pc)$. The {\em degree} of $(\alpha,n) \in \Cc(\Pc) \cap \ZZ^{N+1}$ is $\deg (\alpha,n) = n$. Applied to the minimal Hilbert basis, we get the following invariant: \begin{equation} \label{Hilbdef} \text{$\mu_\text{Hilb}(\Pc) =$ the maximal degree of elements belonging to $\Hc(\Cc(\Pc))$}. \end{equation} \smallskip \noindent {\bf (0.3) The \boldmath{$\delta$}-Vector.} The number of integer points in the dilations of $\Pc$ gives the generating function \[ \sum_{k \ge 0} |k\Pc \cap \ZZ^N|\hskip1pt t^k = \frac{\delta_0 + \delta_1 t + \cdots + \delta_d t^d}{(1-t)^{d+1}},\quad d = \dim \Pc. \] We call $\delta(\Pc) = (\delta_{0}, \delta_{1}, \ldots, \delta_{d})$ the {\em $\delta$-vector} of $\Pc$ \cite[Chapter XI]{HibiRedBook}. It is also known that $\delta_0 = 1$ and $\delta_i \ge 0$ for all $i$. We note that the $\delta$-vector is sometimes called the $h^*$-vector or the Ehrhart $h$-vector. The largest index where $\delta_i > 0$ gives the following invariant: \begin{equation} \label{Ehrdef} \text{$\mu_\text{Ehr}(\Pc) =$ the maximal integer $i$ for which $\delta_i > 0$}. \end{equation} The above generating function is determined by the Ehrhart polynomial of $\Pc$, which explains the name of the invariant. For later purposes, we note that $(d+1)-\mu_\text{Ehr}(\Pc)$ is the least integer $k$ for which $k(\Pc \setminus \partial \Pc) \cap \ZZ^{N} \neq \emptyset$ \cite[Theorem 4.5]{BR}. Thus knowing $\mu_\text{Ehr}(\Pc)$ is equivalent to knowing the smallest dilation of $\Pc$ with an interior integer point. \medskip \noindent {\bf (0.4) Boxes and Holes.} A simplex $\Sc \subset \RR^{N}$ is {\em empty} if $\Sc \cap \ZZ^{N}$ is the set of vertices of $\Sc$. Given an empty simplex $\Sc \subset \RR^N$, we define the finite subset $\text{Box}(\Sc) \subset \Cc(\Sc)$ as follows: \[ \text{Box}(\Sc) = \bigg\{\sum_{v_i \in \Sc \cap \ZZ^N} r_i (v_i,1) \in \ZZ^{N+1} \, : \, 0 \leq r_i < 1 \bigg\}. \] It is well known that $\Hc(\Cc(\Sc)) \subset \text{Box}(\Sc) \cup (\widetilde{\Sc} \cap \ZZ^{N+1})$. If $\Pc \subset \RR^N$ has dimension $d$, then define $\text{Box}(\Pc)$ to be \[ \text{Box}(\Pc)=\bigcup_{\Sc} \text{Box}(\Sc) \setminus \ZZ_{\geq 0}(\widetilde{\Pc} \cap \ZZ^{N+1}), \] where the union is over all empty simplices $\Sc \subset \Pc$ of dimension $d$. Note that $\Hc(\Cc(\Pc)) \subset \bigcup_{\Sc} \Hc(\Cc(\Sc)) \subset \text{Box}(\Pc) \cup (\widetilde{\Pc} \cap \ZZ^{N+1})$. Each element of $\text{Box}(\Pc)$ is called a {\em hole} of $\Pc$. This leads to our final invariant: \begin{equation} \label{holedef} \text{$\mu_\text{hole}(\Pc) =$ the maximal degree of elements belonging to $\text{Box}(\Pc)$}, \end{equation} with the convention that $\mu_\text{hole}(\Pc) = 1$ if $\text{Box}(\Pc) = \emptyset$. \medskip An integral convex polytope $\Pc$ of dimension $d$ thus has the six invariants \[ \mu_\text{midp}(\Pc),\ \mu_\text{idp}(\Pc),\ \mu_\text{va}(\Pc),\ \mu_\text{Hilb}(\Pc),\ \mu_\text{Ehr}(\Pc),\ \mu_\text{hole}(\Pc) \] defined in \eqref{midpdef}--\eqref{holedef}. The goal of this paper is to study the relations among these invariants. These invariants have different flavors that involve geometry, algebra, and lattice points. Here are some brief comments: \begin{itemize} \item In \emph{toric geometry}, $\Pc$ determines a line bundle on the toric variety of the normal fan of $\Pc$. Then $\mu_\text{va}(\Pc)$ is the smallest multiple of this line bundle that is very ample in the sense of algebraic geometry. \item (IDP) and very ample are related to the \emph{lattice structure} of the polytope. More precisely, they describe two notions of what it means for $\Pc$ to have ``enough'' integer points:\ for (IDP), the integer points of $\Pc$ generate all integer points in its dilations, while for very ample, the integer points of $\Pc$ give the same toric variety as the normal fan of $\Pc$, as explained in \cite[Chapter 2]{CLS}. Thus $\mu_\text{midp}(\Pc)$ and $\mu_\text{va}(\Pc)$ give the smallest dilations of $\Pc$ with ``enough'' integer points in these two senses. Furthermore, $\mu_\text{idp}(\Pc)$ gives the smallest dilation where it and all further dilations have (IDP). \item Another invariant of the lattice structure is $\mu_\text{Ehr}(\Pc)$, since it is determined by counting integer points in dilations. \item In contrast, $\mu_\text{Hilb}(\Pc)$ is an invariant of the \emph{algebraic structure} of the semigroup $\Cc(\Pc)\cap\ZZ^{N+1}$ since it is determined by the semigroup's Hilbert basis. \item Finally, $\mu_\text{hole}(\Pc)$ is a mixture of the lattice structure (integer points in boxes) and the algebraic structure (removing the semigroup $\ZZ_{\ge0}(\widetilde{\Pc}\cap\ZZ^{N+1})$). \end{itemize} \begin{Remark} In the book \cite{BG}, two notions closely related to (IDP) are described. Let $\Pc \subset \RR^N$ be an integral convex polytope of dimension $d$. The authors of \cite{BG} define $\Pc$ to be {\em integrally closed} if $\Pc$ satisfies $$\ZZ_{\geq 0}(\widetilde{\Pc}\cap \ZZ^{N+1})=\Cc(\Pc) \cap \ZZ^{N+1}$$ and {\em normal} if $\Pc$ satisfies $$\ZZ_{\geq 0}(\widetilde{\Pc}\cap \ZZ^{N+1})=\Cc(\Pc) \cap \ZZ(\widetilde{\Pc} \cap \ZZ^{N+1}).$$ Then $\Pc$ satisfying (IDP) is equivalent $\Pc$ being integrally closed, but not necessarily equivalent to $\Pc$ being normal. To complicate matters, the books \cite{CLS} and \cite{MS} use the term ``normal'' for a polytope that is integrally closed in the sense of \cite{BG}. Because of this inconsistency, we use the term ``(IDP)'' for this concept. Besides avoiding confusion, (IDP) has the advantage of being more descriptive, in that lattice points in dilations of a polytope with (IDP) have ``integer decompositions'' as sums of integers points of the polytope. As noted earlier, the term ``(IDP)'' is widely used in integer programming. \end{Remark} We now discuss the contents of the paper. In Section $1$, we give basic inequalities which the invariants satisfy. More precisely, Theorem \ref{invariant} says that \begin{equation} \label{introdiagram} \begin{array}{c} \begin{picture}(300,52) \put(5,20){$1 \le \mu_\text{va}(\Pc) $} \put(64.5,29){\rotatebox{25}{$\le$}} \put(82,8){\rotatebox{-20}{$\le$}} \put(83,39){$\mu_\text{midp}(\Pc) \le \mu_\text{idp}(\Pc)$} \put(264,39){$\mu_\text{Ehr}(\Pc) \le d$} \put(118,2){$\mu_\text{Hilb}(\Pc)$} \put(264,2){$d-1$} \put(202,20){$\mu_\text{hole}(\Pc)$} \put(175,6){\rotatebox{25}{$\le$}} \put(246,12){\rotatebox{-30}{$\le$}} \put(184,33){\rotatebox{-30}{$\le$}} \put(246,29){\rotatebox{25}{$\le$}} \end{picture} \end{array} \end{equation} Various examples, some new and some old, will be supplied in Section $2$. In Theorem \ref{Berkeley}, we construct, given integers $d \geq 3$ and $2 \leq j \leq d - 1$, an empty simplex $\Pc$ of dimension $d$ with all six invariants equal to $j$. At the other extreme, we give examples of integral convex polytopes $\Pc$, $\Pc'$ and $\Pc''$ with \begin{itemize} \item $\mu_\text{va}(\Pc) < \mu_\text{midp}(\Pc), \, \, \mu_\text{va}(\Pc) < \mu_\text{Hilb}(\Pc)$; \item $\mu_\text{midp}(\Pc') < \mu_\text{idp}(\Pc') < \mu_\text{hole}(\Pc'), \, \, \mu_\text{Hilb}(\Pc') < \mu_\text{hole}(\Pc')$; \item $\mu_\text{hole}(\Pc'') < \mu_\text{Ehr}(\Pc'')$, \end{itemize} showing that the inequalities in \eqref{introdiagram} can be strict. In Theorem \ref{Boston}, we construct, given an integer $d \geq 4$, an integral convex polytope $\Pc$ of dimension $d$ such that \[ \mu_\text{midp}(\Pc) = \mu_\text{idp}(\Pc) = d - 2 < d - 1 = \mu_\text{Hilb}(\Pc). \] We also give an example where $\mu_\text{Hilb}(\Pc) < \mu_\text{midp}(\Pc)$. These last two inequalities show that there is no general comparison between $\mu_\text{midp}(\Pc)$ and $\mu_\text{Hilb}(\Pc)$. This explains the middle of \eqref{introdiagram}. Moreover, in Section $3$, more detailed relations between $\mu_\text{midp}(\Pc)$ and $\mu_\text{idp}(\Pc)$ will be discussed (Theorem \ref{teiri}). Finally, we compute in Section $4$ the invariants of edge polytopes arising from finite graphs. \section{Invariants related to dilated polytopes} In this section, we discuss the six invariants of an integral convex polytopes $\Pc$ of dimension $d$ related to (IDP). More precisely, we prove the following. \begin{Theorem}\label{invariant} For the invariants appearing in the introduction of an integral convex polytope $\Pc \subset \RR^N$ of dimension $d \ge 2$, the following inequalities hold: \begin{equation}\label{diagram} \begin{array}{c} \begin{picture}(300,52) \put(5,20){$1 \le \mu_\text{{\em va}}(\Pc) $} \put(64.5,29){\rotatebox{25}{$\le$}} \put(82,8){\rotatebox{-20}{$\le$}} \put(83,39){$\mu_\text{{\em midp}}(\Pc) \le \mu_\text{{\em idp}}(\Pc)$} \put(264,39){$\mu_\text{{\em Ehr}}(\Pc) \le d$} \put(118,2){$\mu_\text{{\em Hilb}}(\Pc)$} \put(264,2){$d-1$} \put(202,20){$\mu_\text{{\em hole}}(\Pc)$} \put(175,6){\rotatebox{25}{$\le$}} \put(246,12){\rotatebox{-30}{$\le$}} \put(184,33){\rotatebox{-30}{$\le$}} \put(246,29){\rotatebox{25}{$\le$}} \end{picture} \end{array} \end{equation} \end{Theorem} \begin{proof} The inequalities $1 \leq \mu_\text{va}(\Pc) \leq \mu_\text{midp}(\Pc) \leq \mu_\text{idp}(\Pc)$ and $\mu_\text{Ehr}(\Pc) \leq d$ are clear from their definitions. On the other hand, since the assertions are obvious if $\Pc$ has (IDP), we assume that $\text{Box}(\Pc)$ is not empty. \medskip\noindent $\bullet$ $\mu_\text{idp}(\Pc) \leq \mu_\text{hole}(\Pc)$: This inequality is proved, though not stated, in \cite{LiuTrotterZiegler}. We give the proof for the sake of completeness. It follows from Gordan's Lemma \cite[Theorem 16.4]{Sch} and Carath\'eodory's Theorem \cite[Corollary 7.1i]{Sch} that $\Cc(\Pc) \cap \ZZ^{N+1}$ consists of the elements of $$\{ \alpha + x \ : \ \alpha \in \text{Box}(\Pc) \cup \{0\}, \ x \in \ZZ_{\geq 0}(\widetilde{\Pc} \cap \ZZ^{N+1})\}.$$ Thus for $n \geq \mu_\text{hole}(\Pc)$ and an element $\alpha \in (\ell n)\Pc \cap \ZZ^N$, we can write $(\alpha,\ell n) \in \Cc(\Pc) \cap \ZZ^{N+1}$ as $ (\alpha_0,n_0) + (\alpha_1,1) + \ldots + (\alpha_r,1) $ with $n_0 \le n$ for some $(\alpha_0,n_0) \in \Cc(\Pc) \cap \ZZ^{N+1}$ and $(\alpha_i,1) \in \Cc(\Pc) \cap \ZZ^{N+1}$ for each $1 \leq i \leq r$. These summands can now be grouped into $\ell$ elements of $n\widetilde{\Pc} \cap \ZZ^{N+1}$. \medskip\noindent $\bullet$ $\mu_\text{hole}(\Pc) \leq \mu_\text{Ehr}(\Pc)$: Let $(\alpha,\mu_\text{hole}(\Pc)) \in \text{Box}(\Pc)$ attain $\mu_\text{hole}(\Pc)$. Then, by definition of $\text{Box}(\Pc)$, we can describe $(\alpha,\mu_\text{hole}(\Pc))$ as a linear combination of $(d+1)$ linearly independent lattice vectors in $\widetilde{\Pc}$. Say, $(\alpha,\mu_\text{hole}(\Pc)) = \sum_{i=0}^{d} r_i (v_i,1)$ with $0 \le r_i <1$. Let $\beta=\sum_{i=0}^{d} (1-r_i) v_i \in \ZZ^N$. Since $1-r_i > 0$ and $\sum_{i=0}^{d} (1-r_i) = d+1-\mu_\text{hole}(\Pc)$, one has $\beta \in (d+1-\mu_\text{hole}(\Pc))(\Pc \setminus \partial \Pc) \cap \ZZ^N$, certifying $d+1-\mu_\text{Ehr}(\Pc) \leq d+1-\mu_\text{hole}(\Pc)$. \medskip\noindent $\bullet$ $\mu_\text{va}(\Pc) \leq \mu_\text{Hilb}(\Pc)$: Let $\alpha$ be a vertex of $\Pc$, and let $\beta$ be an integer point in the cone generated by $\Pc-\alpha$. Then, for a sufficiently large integer $k$, we have $(\beta+k\alpha,k) \in \Cc(\Pc) \cap \ZZ^{N+1}$. This point can be written as a nonnegative integral linear combination of $\Hc(\Cc(\Pc))$: $(\beta+k\alpha,k) = \sum_{h \in \Hc(\Cc(\Pc))} w_h h$ with $w_h \in \ZZ_{\geq 0}$. This implies that $$(\beta,0) \ = \ \sum_{h \in \Hc(\Cc(\Pc))} w_h \bigl[ (h+ (\mu_\text{Hilb}(\Pc)-\deg(h)) (\alpha,1)) \ - \ \mu_\text{Hilb}(\Pc) (\alpha,1) \bigr]$$ is a nonnegative integral linear combination of integer points in $\mu_\text{Hilb}(\Pc) (\Pc-\alpha) \times \{0\}$, showing that $\mu_\text{Hilb}(\Pc)\Pc$ is very ample. \medskip\noindent $\bullet$ $\mu_\text{Hilb}(\Pc) \leq \mu_\text{hole}(\Pc)$: This follows from $\Hc(\Cc(\Pc)) \subset \text{Box}(\Pc) \cup (\widetilde{\Pc} \cap \ZZ^{N+1})$. \medskip\noindent $\bullet$ $\mu_\text{hole}(\Pc) \leq d-1$: Here is the argument from \cite{LiuTrotterZiegler}. Let $\Sc \subset \RR^N$ be an empty simplex of dimension $d$ and let $v_0,v_1,\ldots,v_d$ be its vertices. Given $v \in \text{Box}(\Sc)$ there are $r_0,r_1,\ldots,r_d$ with $0 \leq r_i < 1$ such that $v=\sum_{i=0}^d r_i(v_i,1)$. Since $r_i <1$, one has $\deg(v)=\sum_{i=0}^d r_i < d+1$. Suppose that $\deg(v)=d$. Then all $r_i$ must be positive. Moreover, we have $\sum_{i=0}^d(1-r_i)=1$ and $0 < 1-r_i <1$. Thus the integer point $\sum_{i=0}^d (1-r_i) v_i$ belongs to the interior of $\Sc$, a contradiction. Hence $\deg(v) \leq d-1$. \end{proof} \section{Proper inequalities of \eqref{diagram}} In this section, we present a series of examples of integral convex polytopes. Each example satisfies a proper inequality in \eqref{diagram}. Before giving them, we prove that there exists an integral convex polytope $\Pc$ attaining $\mu_\text{va}(\Pc)=\mu_\text{midp}(\Pc)=\mu_\text{idp}(\Pc)=\mu_\text{Hilb}(\Pc)=\mu_\text{hole}(\Pc)=\mu_\text{Ehr}(\Pc)$. \begin{Theorem}\label{Berkeley} Given integers $d \geq 3$ and $2 \leq j \leq d - 1$, there exists an empty simplex $\Pc$ of dimension $d$ with $\mu_\text{{\em va}}(\Pc)=\mu_\text{{\em midp}}(\Pc)=\mu_\text{{\em idp}}(\Pc) =\mu_\text{{\em Hilb}}(\Pc)=\mu_\text{{\em hole}}(\Pc)=\mu_\text{{\em Ehr}}(\Pc)=j$. \end{Theorem} % % % % \begin{proof} Fix positive integers $d$ and $j$ with $d \geq 3$ and $2 \leq j \leq d-1$ and let $\eb_1,\ldots,\eb_d$ be the standard basis of $\RR^d$. Then we define $\Pc \subset \RR^{d}$ to be the convex hull of $\{ v_0, v_1,\ldots,v_d \} \subset \ZZ^d$, where $v_0={\bf 0}=(0,\ldots,0)$, $v_i = \eb_i$ for $i = 1,\ldots,d-1$ and \[ v_d = (\underbrace{1,\ldots,1}_{j},0,\ldots,0,j). \] Let $(\delta_0,\delta_1,\ldots,\delta_d)$ be the $\delta$-vector of $\Pc$. We will prove that $\Pc$ enjoys the required properties. Since the determinant of the matrix with columns $v_1,\dots,v_d$ is $j$, the normalized volume of $\Pc$ is $j$. Moreover, \begin{equation}\label{hilb} \frac{q}{j}(v_0,1)+\frac{q}{j}\sum_{i=1}^j(v_i,1)+\frac{j-q}{j}(v_d,1)=(\eb_1+\cdots+\eb_j+(j-q)\eb_d,q+1), \end{equation} where $q=1,\ldots,j-1$. Thus $\delta_q \geq 1$ for $q=2,\ldots,j$ (\cite[Proposition 27.7]{HibiRedBook}). Since $\sum_{i=0}^d \delta_i =j$ and each $\delta_i$ is nonnegative, one has $$(\delta_0,\delta_1,\ldots,\delta_d)=(1,0,\underbrace{1,1,\ldots,1}_{j-1},0,\ldots,0).$$ In particular, $\mu_\text{Ehr}(\Pc)=j$. Moreover, from $\delta_1=0$, $\Pc$ is an empty simplex. Thus, once we show $\mu_\text{va}(\Pc) \geq j$, we conclude that $\Pc$ has the desired properties by \eqref{diagram} in Theorem \ref{invariant}. Using \eqref{hilb}, one can show without difficulty that the Hilbert basis $\Hc(\Cc(\Pc))$ is \[(\widetilde{\Pc} \cap \ZZ^{d+1}) \cup \{(\eb_1+\cdots+\eb_j+(j-q+1)\eb_d,q) : q =2,\ldots,j\}.\] Now, we show that $k \Pc$ cannot be very ample for $1 \leq k < j$. Let $k$ be an integer with $1 \leq k \mu_\text{midp}(\Pc)$ and $\mu_\text{Hilb}(\Pc)>\mu_\text{idp}(\Pc)$. \begin{Theorem}\label{Boston} Given an integer $d \geq 4$, there exists an integral convex polytope $\Pc$ of dimension $d$ such that $\mu_\text{{\em Hilb}}(\Pc) = d - 1$ and $\mu_\text{{\em midp}}(\Pc)=\mu_\text{{\em idp}}(\Pc)=d-2$. \end{Theorem} Let $d \geq 4$ be an integer and let $M=d(d-2)+1$. We define $v_{j} \in \ZZ^{d}$, $1 \leq i \leq d$, as follows: \begin{eqnarray*} v_j= \begin{cases} {\bf 0}, &j=0, \\ \eb_j, &j=1,\ldots,d-1, \\ \eb_1+\cdots+\eb_{d-1}+M\eb_d, &j=d. \end{cases} \end{eqnarray*} Let $v_j'=v_j+\eb_d$ for $j=0,1,\ldots,d$. We write $\Pc \subset \RR^d$ for the integral convex polytope of dimension $d$ with the vertices $v_0, v_{1}, \ldots, v_{d}$ and $v'_0, v'_{1}, \ldots, v'_{d}$. Such a convex polytope appears in \cite[Theorem 2]{EwaldWessels}. The following Lemmas \ref{lem1} and \ref{lem2} prove Theorem \ref{Boston}, that is, they show that $\Pc$ enjoys the required properties in Theorem \ref{Boston}. Let $$u_s^{(k)}=\eb_1+\cdots+\eb_{d-1}+((k-1)d+s)\eb_d \text{ for }k=1,\ldots,d-2 \text{ and } s=1,\ldots,d$$ and $$u=u_d^{(1)}=\eb_1+\cdots+\eb_{d-1}+d \eb_d.$$ \begin{Lemma}\label{lem1} Let $\Pc$ be as above. Then the Hilbert basis $\Hc(\Cc(\Pc))$ is equal to \begin{align}\label{hilbert} (\widetilde{\Pc} \cap \ZZ^{d+1}) \cup \{(u_s^{(k)},d-k) : k=2,\ldots,d-2, s=1,\ldots,d\} \cup \{(u,d-1)\}. \end{align} Thus, in particular, $\mu_\text{{\em Hilb}}(\Pc)=d-1$. \end{Lemma} \begin{proof} \noindent If $q \in \{1,\ldots,M-1\}$, then there exist unique integers $k$ and $s$ with $1 \leq k \leq d-2$ and $1 \leq s \leq d$ such that $q=(k-1)d+s$. Since \begin{align*} &\frac{(d-2)s-k+1}{M}(v_0,1)+\frac{M-q}{M}\sum_{j=1}^{d-1}(v_j,1)+\frac{q}{M}(v_d,1) \\ &\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad =(\eb_1+\cdots+\eb_{d-1}+q\eb_d, d-k) =(u_s^{(k)},d-k) \in \ZZ^{d+1}, \end{align*} it follows that $(u_s^{(k)},d-k)=(\eb_1+\cdots+\eb_{d-1}+q\eb_d, d-k) \in \Cc(\Pc) \cap \ZZ^{d+1}$. When $k=1$ and $s=1,\ldots,d-1$, one has $q=s$ and \[ (\eb_1+\cdots+\eb_{d-1}+q\eb_d, d-1)=\sum_{j=1}^s (v_j',1) + \sum_{j=s+1}^{d-1} (v_j,1). \] Hence $(\eb_1+\cdots+\eb_{d-1}+q\eb_d, d-1)$ cannot belong to $\Hc(\Cc(\Pc))$ for $q \leq d-1$. Now, it is routine work to show that, by considering the facets of the cone $\Cc(\Pc)$, the Hilbert basis $\Hc(\Cc(\Pc))$ coincides with \eqref{hilbert}. \end{proof} \begin{Lemma}\label{lem2} We have $\mu_\text{{\em midp}}(\Pc)=\mu_\text{{\em idp}}(\Pc)=d-2$. \end{Lemma} \begin{proof} \noindent One can easily see the identities \begin{itemize} \item[] $(u,d-1)+(v_i,1)=(v_i',1)+\sum_{j=1}^{d-1}(v_j', 1) \;\;\text{for}\;\;i=0,1,\ldots,d,$ \item[] $(u,d-1)+(v_i',1)=(v_0,1)+(v_i,1)+(u_1^{(2)},d-2) \;\;\text{for}\;\;i=0,1,\ldots,d,$ \item[] $(u,d-1)+(u_s^{(d-2)},2)=(v_0,1)+(v_d,1)+\sum_{j=1}^{s-1}(v_j',1)+\sum_{j=s}^{d-1}(v_j,1),$ \item[] $(u,d-1)+(u_s^{(k)},d-k)=(u_s^{(k+1)},d-k-1)+\sum_{j=0}^{d-1}(v_j,1)$ for $k=2,\ldots,d-3,$ \item[] $(u,d-1)+(u,d-1)=(u_d^{(2)},d-2)+\sum_{j=0}^{d-1}(v_j,1).$ \end{itemize} It then follows that \[(\Cc(\Pc) \cap \ZZ^{d+1}) \setminus \{(u,d-1)\} = \ZZ_{\geq 0} (\Hc(\Cc(\Pc)) \setminus \{(u,d-1)\}).\] Moreover, if $k+k' \geq d$, then \begin{align*} &(u_s^{(k)},d-k)+(u_{s'}^{(k')},d-k')=\\ &\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \begin{cases} (v_d,1)+(u_{s+s'-1}^{(k+k'-d+1)}, 2d-k-k'-1), &\;\;\text{if}\;\;s+s'\leq d+1, \\ (v_0,1)+(v_d,1)+(u_{s+s'-1-d}^{(k+k'-d+2)}, 2d-k-k'-2), &\;\;\text{if}\;\;s+s'\geq d+2. \end{cases}\end{align*} If $k+k' \leq d-1$, then \begin{align*} &(u_s^{(k)},d-k)+(u_{s'}^{(k')},d-k')=\\ &\;\;\;\;\;\;\;\; \begin{cases} (u_s^{(k+k'-1)},d-k-k'+1)+\sum_{j=1}^{s'}(v_j',1)+\sum_{j=s'+1}^{d-1}(v_j,1), &\;\;\text{if}\;\;s'\leq d-1, \\ (u_s^{(k+k')},d-k-k')+\sum_{j=0}^{d-1}(v_j,1), &\;\;\text{if}\;\;s'= d. \end{cases}\end{align*} Consequently, when we write $\alpha \in \Cc(\Pc) \cap \ZZ^{d+1}$ by using at least two $u_s^{(k)}$'s, we can reduce one $u_s^{(k)}$. Hence $\alpha$ can be expressed by using at most one $u_s^{(k)}$ belonging to $\Hc(\Cc(\Pc))$. Let $\Pc'=(d-2)\Pc$ and $\alpha \in n \Pc' \cap \ZZ^d$. Since $d \geq 4$, one has $n(d-2) \neq d-1$. Thus $(\alpha,n(d-2)) \not=(u,d-1)$. By the above discussions, there exists an expression of $\alpha$ of the form \[ (\alpha, n(d-2)) = v' + \sum_{j=1}^{n(d-2)-\deg(v')}(v_j'',1), \] where $v' \in \{(u_s^{(k)},d-k) : k=2,\ldots,d-2, s=1,\ldots,d\}$ and each $v_j'' \in \Pc \cap \ZZ^d$. Since the degree of $v'$ is at most $d-2$, there exists an expression of $\alpha$ of the form \[ \alpha=\alpha_1+\cdots+\alpha_n \] with each $\alpha_i \in \Pc' \cap \ZZ^d$. Hence $\Pc'$ possesses (IDP). By $\mu_\text{idp}(\Pc) \leq d-1$, $k\Pc$ possesses (IDP) for $k \geq d-1$. Thus, we obtain $\mu_\text{idp}(\Pc) \leq d-2$. Now it is easy to see that for $r < d-2$, $r \Pc$ never possesses (IDP). Therefore, we conclude that $\mu_\text{midp}(\Pc)=\mu_\text{idp}(\Pc)=d-2$. \end{proof} \section{Restrictions on invariants} In this section, we discuss more restrictions on the invariants. We consider the following question. \begin{Question}\label{toi}{\em Let $d, a_1, a_2, a_3, a_4, a_5, a_6$ be positive integers satisfying \begin{align*} a_1 \leq a_2 \leq a_3 \leq a_5 \leq a_6 \leq d \;\text{ and }\; a_1 \leq a_4 \leq a_5 \leq d-1. \end{align*} Then does there exist an integral convex polytope $\Pc$ of dimension $d$ such that \begin{eqnarray*} &\mu_\text{va}(\Pc)=a_1,\ \mu_\text{midp}(\Pc)=a_2,\ \mu_\text{idp}(\Pc)=a_3, \ \mu_\text{Hilb}(\Pc)=a_4,\ \mu_\text{hole}(\Pc)=a_5 \\ &\text{ and } \mu_\text{Ehr}(\Pc)=a_6\text{?} \end{eqnarray*} }\end{Question} {}From some easy observations, we cannot assign these positive integers freely. In fact, it is obvious that \begin{itemize} \item if either $\mu_\text{midp}(\Pc)$ or $\mu_\text{Hilb}(\Pc)$ is 1, then $\mu_\text{va}(\Pc)=\mu_\text{midp}(\Pc)=\mu_\text{idp}(\Pc)=\mu_\text{Hilb}(\Pc) =\mu_\text{hole}(\Pc)=1$; \item if $\mu_\text{midp}(\Pc)<\mu_\text{idp}(\Pc)$, then $\mu_\text{idp}(\Pc) \geq \mu_\text{midp}(\Pc) +2$. \end{itemize} Moreover, we also see non-trivial restrictions. \begin{Theorem}\label{teiri} The following assertions hold: \begin{itemize} \item[(1)] if $\mu_\text{{\em midp}}(\Pc) \geq (d-1)/2$, then $\mu_\text{{\em idp}}(\Pc)=\mu_\text{{\em midp}}(\Pc)$; \item[(2)] if $\mu_\text{{\em midp}}(\Pc) \leq (d-1)/2$, then $\mu_\text{{\em idp}}(\Pc) \leq (d-3)/2+\mu_\text{{\em midp}}(\Pc)$. \end{itemize} \end{Theorem} Before proving these, we recall the following lemma. \begin{Lemma}[cf. {\cite[Theorem 2.2.12]{CLS}}]\label{hodai} Let $\Pc \subset \RR^N$ be an integral convex polytope of dimension $d$. Given $\alpha \in n \Pc \cap \ZZ^N$ for $n \geq d-1$, $\alpha$ can be written like $$\alpha=\alpha'+\alpha_1+\cdots+\alpha_{n-d+1},$$ where $\alpha' \in (d-1) \Pc \cap \ZZ^N$ and $\alpha_1,\ldots,\alpha_{n-d+1} \in \Pc \cap \ZZ^N$. \end{Lemma} A proof of this lemma appears in the proof of \cite[Theorem 2.2.12]{CLS}. \begin{proof}[Proof of Theorem \ref{teiri}] (1) It suffices to show that for an integral convex polytope $\Pc \subset \RR^N$ of dimension $d$ with $\mu_\text{midp}(\Pc) \geq (d-1)/2$, $n\Pc$ possesses (IDP) for every $n \geq \mu_\text{midp}(\Pc)$. Let $k=\mu_\text{midp}(\Pc)$. Let $n \geq k$ and let $\alpha \in m(n\Pc) \cap \ZZ^N$ for $m \geq 2$. Since $mn \geq 2n \geq 2k \geq d-1$, thanks to Lemma \ref{hodai}, we obtain $$\alpha=\alpha'+\alpha_1+\cdots+\alpha_{mn-d+1},$$ where $\alpha' \in (d-1)\Pc \cap \ZZ^N$ and $\alpha_1,\ldots,\alpha_{mn-d+1} \in \Pc \cap \ZZ^N$. Moreove, since $k\Pc$ has (IDP), there are $\alpha_1'$ and $\alpha_2'$ in $k\Pc \cap \ZZ^N$ such that $$\alpha_1'+\alpha_2'=\alpha'+\alpha_{mn-2k+1}+\cdots+\alpha_{mn-d+1} \in 2k \Pc \cap \ZZ^N.$$ Therefore, $$\alpha=\underbrace{\alpha_1'+\sum_{i=1}^{n-k}\alpha_i}_{n \Pc \cap \ZZ^N}+ \underbrace{\alpha_2'+\sum_{i=n-k+1}^{2(n-k)}\alpha_i}_{n \Pc \cap \ZZ^N}+ \sum_{i=1}^{m-2}\underbrace{\sum_{j=1}^n\alpha_{2(n-k)+(i-1)n+j}}_{n \Pc \cap \ZZ^N}.$$ This implies that $n\Pc$ possesses (IDP). \\ % % (2) It suffices to prove that for an integral convex polytope $\Pc \subset \RR^N$ of dimension $d$ with $\mu_\text{midp}(\Pc) \leq (d-1)/2$, $n\Pc$ possesses (IDP) for every $n \geq (d - 3)/2+\mu_\text{midp}(\Pc)$. For $m \geq 2$, let $\alpha \in m(n\Pc) \cap \ZZ^N$. Since $mn \geq 2n \geq d-3 + 2 \mu_\text{midp}(\Pc) \geq d-1$, thanks to Lemma \ref{hodai}, we obtain $$\alpha=\alpha'+\alpha_1+\cdots+\alpha_{mn-d+1},$$ where $\alpha' \in (d-1)\Pc \cap \ZZ^N$ and $\alpha_1,\ldots,\alpha_{mn-d+1} \in \Pc \cap \ZZ^N$. Let $k=\mu_\text{midp}(\Pc)$ and $\ell = \min\{ i : ik \geq d-1\}$. Since $k\Pc$ has (IDP), an element $\alpha'+\alpha_{mn-\ell k +1}+\cdots+\alpha_{mn - d+1}$ belonging to $\ell (k \Pc) \cap \ZZ^N$ can be written such as $\alpha_1'+\cdots+\alpha_\ell'$, where $\alpha_i' \in k \Pc \cap \ZZ^N$. Remark that $\ell k - d+1 \leq mn- d +1$ because $$mn - \ell k \geq 2n - \ell k \geq d-3+2k-\ell k \geq d-2 - (\ell - 1) k \geq 0.$$ Thus $\alpha$ can be rewritten as $$\alpha=\alpha_1'+\cdots+\alpha_\ell' + \alpha_1+\cdots+\alpha_{mn-\ell k}.$$ Let $p=\lfloor n/k \rfloor$ and $q=n-pk$, i.e., $n=pk+q$ with $0 \leq q \leq k-1$. When $p \geq \ell$, since $n \geq \ell k$, it follows easily that $\alpha$ can be written as a sum of $m$ elements of $n \Pc \cap \ZZ^N$. Assume that $p < \ell$. Then we have $mn-\ell k \geq q$ and $n - (\ell-p)k \geq 0$. In fact, \begin{align*} mn - \ell k -q &\geq 2n-\ell k -q=n-(\ell-p)k \\ &\geq d-3+2k-\ell k -(k-1) = d-2 - (\ell -1 )k \geq 0. \end{align*} Thus we obtain that $$\alpha=\underbrace{\sum_{i=1}^p\alpha_i'+\sum_{j=1}^q \alpha_j}_{n \Pc \cap \ZZ^N} +\underbrace{\sum_{i=p+1}^\ell \alpha_i'+\sum_{j=1}^{n-(\ell-p)k}\alpha_{q+j}}_{n \Pc \cap \ZZ^N} +\sum_{r=1}^{m-2}\underbrace{\sum_{i=1}^n \alpha_{n-(\ell-p)k+q+(r-1)n+i}}_{n \Pc \cap \ZZ^N}.$$ This says that $n \Pc$ possesses (IDP), as desired. \end{proof} As an immediate corollary of Theorem \ref{teiri}, we obtain the following. \begin{Corollary} If $\mu_\text{{\em idp}}(\Pc)=d-1$, then $\mu_\text{{\em midp}}(\Pc)=d-1$. \end{Corollary} \begin{proof} Suppose that $\mu_\text{midp}(\Pc)\not=d-1$. In particular, $\mu_\text{midp}(\Pc) < d-1$. If $\mu_\text{midp}(\Pc) \geq (d-1)/2$, then $\mu_\text{idp}(\Pc)=\mu_\text{midp}(\Pc)1$. Is it true that $\mu_\text{{\em Hilb}}(\Pc)=2$ if $\mu_\text{{\em va}}(\Pc)=1$? \end{itemize} \end{Question} \begin{Remark}\label{workofLM} The recent preprint \cite{LM} contains examples that shed light on our invariants. \begin{itemize} \item[(1)] In an earlier version of our paper, we asked in Question \ref{mondai}(1) if there exists a polytope $\Pc$ such that $\mu_\text{{\em midp}}(\Pc) < \mu_\text{Hilb}(\Pc) < \mu_\text{idp}(\Pc)$. As shown in \cite[Sec.\ 4]{LM}, the answer is yes. \item[(2)] In the earlier version, we asked in Question \ref{mondai}(2) if $\mu_\text{midp}(\Pc)=\mu_\text{idp}(\Pc)=2$ when $\mu_\text{va}(\Pc)=1$ and $\mu_\text{idp}(\Pc)>1$. An example from \cite[Sec.\ 4]{LM} show that this can fail. \item[(3)] In the earlier version, we also asked if $(n+m)\Pc$ possesses (IDP) whenever $n\Pc$ and $m\Pc$ possess (IDP). The paper \cite{LM} constructs a 50-dimensional polytope $\Pc_{25,27}$ such that $2\Pc_{25,27}$ and $3\Pc_{25,27}$ have (IDP) while $5\Pc_{25,27}$ does not. \end{itemize} \end{Remark} \section{The case of dilated edge polytopes} Finally, we discuss the case of edge polytopes. Recall that for a connected simple graph $G$ on the vertex set $\{1,\ldots,d\}$ with the edge set $E(G)$, the {\em edge polytope} of $G$ is the convex polytope $\Pc_G \subset \RR^d$ which is the convex hull of $\{\eb_i+\eb_j : \{i,j\} \in E(G)\}$. Also: \begin{itemize} \item An {\em odd} cycle is a cycle with odd length. \item A cycle $C$ in $G$ is called {\em minimal} if $C$ possesses no chord. \item A pair of disjoint odd cycles $C$ and $C'$ in $G$ is said to be {\em exceptional} if there is no bridge between $C$ and $C'$ in $G$. \item We say that $G$ satisfies the {\em odd cycle condition} if each pair of disjoint odd cycles is not exceptional. \end{itemize} It is known by the proof of \cite[Theorem 2.2]{OH} that for a connected graph $G$, $\Pc_G$ has (IDP) if and only if $\Pc_G$ is normal, although this fact is not mentioned explicitly. It is also proved that $\Pc_G$ is normal if and only if $G$ satisfies the odd cycle condition (\cite[Corollary 2.3]{OH}). \begin{Proposition} Let $G$ be a connected simple graph on $\{1,\ldots,d\}$ which does not satisfy the odd cycle condition. For disjoint odd cycles $C_1$ and $C_2$, let \begin{align*} m(C_1,C_2)=\frac{\ell(C_1)+\ell(C_2)}{2}, \;\; \end{align*} where $\ell(C_i)$ denotes the length of a cycle $C_i$. For an edge polytope $\Pc_G$, one has \begin{align*} \mu_\text{{\em va}}(\Pc_G)&=\mu_\text{{\em Hilb}}(\Pc_G)\\ &=\max\left\{m(C,C') : (C,C') \; \text{{\em is an exceptional pair of minimal odd cycles}}\right\} \end{align*} and $$\mu_\text{{\em hole}}(\Pc_G)=\max\left\{\sum_{i=1}^l m(C_{2i-1},C_{2i})\right\},$$ where $C_1,\ldots,C_{2l}$ are disjoint and each of $(C_{2i-1},C_{2i})$ is an exceptional pair of minimal odd cycles. If there is no exceptional pair, we let these maximums be one. \end{Proposition} \begin{proof} In the case of edge polytopes, by \cite[Theorem 2.2]{OH}, $\Hc(\Cc(\Pc_G))$ and Box$(\Pc_G)$ can be written in terms of exceptional pairs of minimal odd cycles as follows: For a pair of minimal odd cycles $C$ and $C'$, let $$e(C,C')=\sum_{i \in V(C) \cup V(C')}\eb_i,$$ where $V(C)$ denotes the set of vertices of a cycle $C$. Then we have $$\Hc(\Cc(\Pc_G))=\{e(C, C') : (C, C') \text{ is an exceptional pair of minimal odd cycles}\}$$ and \begin{align}\label{box} \text{Box}(\Pc_G)=\left\{\sum_{i=1}^le(C_{2i-1},C_{2i})\right\},\end{align} where $C_1,\ldots,C_{2l}$ are disjoint and each of $(C_{2i-1},C_{2i})$ is an exceptional pair of minimal odd cycles. Since $e(C_1,C_2) \in m(C_1,C_2)\Pc_G \cap \ZZ^N$, we obtain $\mu_\text{Hilb}(\Pc_G)=M$, where $M=\max\{m(C,C') : (C,C') \; \text{is an exceptional pair of minimal odd cycles}\}$, and $\mu_\text{hole}(\Pc_G) = \max\left\{\sum_{i=1}^l m(C_{2i-1},C_{2i})\right\}$. Our goal is to show $\mu_\text{va}(\Pc_G) \geq M$. Let $C_1$ and $C_2$ be disjoint minimal odd cycles and let $(C_1,C_2)$ be exceptional and $M=m(C_1,C_2)$. Assume that $\{i_1,i_2\}$ is one edge in $C_1$. For each positive integer $\ell$, since there is no bridge between $C_1$ and $C_2$ and these cycles are minimal, one has $$e(C_1,C_2)+\ell(\eb_{i_1}+\eb_{i_2}) \in ((M+\ell)\Pc_G \cap \ZZ^N) \setminus \{\alpha_1+\cdots+\alpha_{M+\ell} : \alpha_i \in \Pc_G \cap \ZZ^N\}.$$ Fix a positive integer $n$ with $n