text:
\begin{document}

\maketitle

\begin{abstract}
In large scale distributed storage systems (DSS) deployed in cloud computing, correlated failures resulting in simultaneous failure (or, unavailability) of blocks of nodes are common. In such scenarios, the stored data or a content of a failed node can only be reconstructed from the available live nodes belonging to available blocks. To analyze the resilience of the system against such block failures, this work introduces the framework of Block Failure Resilient (BFR) codes, wherein the data (e.g., file in DSS) can be decoded by reading out from a same number of codeword symbols (nodes) from each available blocks of the underlying codeword. Further, repairable BFR codes are introduced, wherein any codeword symbol in a failed block can be repaired by contacting to remaining blocks in the system. Motivated from regenerating codes, file size bounds for repairable BFR codes are derived, trade-off between per node storage and repair bandwidth is analyzed, and BFR-MSR and BFR-MBR points are derived. Explicit codes achieving these two operating points for a wide set of parameters are constructed by utilizing combinatorial designs, wherein the codewords of the underlying outer codes are distributed to BFR codeword symbols according to projective planes.
\end{abstract}

\section{Introduction}
Increasing demand for storing and analyzing \textit{big-data} as well as several applications of cloud computing systems require efficient cloud computing infrastructures. One inevitable nature of the storage systems is node failures. In order to provide resilience against failures, redundancy is introduced in the storage. Classical redundancy schemes range from \emph{replication} to \emph{erasure coding}. Erasure coding allows for better performance in terms of reliability and redundancy compared to replication, however repair bandwidth in reconstructing a failed node is higher. Regenerating codes are proposed to overcome this problem in the seminal work of Dimakis et al. \cite{Dimakis:Network10}. In such a model of distributed storage systems (DSS), the file $\Mc$ is encoded to $n$ nodes such that any $k\leq n$ nodes (each with $\alpha$ symbols) allow for reconstructing the file and any $d\geq k$ nodes (with $\beta\leq \alpha$ symbols from each) reconstruct a failed node with a repair bandwidth $\gamma=d\beta$. The trade-off between per node storage ($\alpha$) and repair bandwidth ($\gamma$) is characterized and two ends of the trade-off are named as minimum storage regenerating (MSR) and minimum bandwidth regenerating (MBR) points \cite{Dimakis:Network10}. Several explicit codes have been proposed to achieve these points recently \cite{Tamo:Zigzag13,Rashmi:Optimal11,Dimakis:Survey11}. Another metric for an efficient repair is repair degree $d$, and regenerating codes necessarily have $d\geq k$. Codes with locality and locally repairable codes with regeneration properties~\cite{Gopalan:Locality12,Papailiopoulos:Locally12,Oggier:Self11,Rawat:Optimal14,Kamath:Codes12,Kamath:Explicit13} allow for a small repair degree, wherein failed nodes are reconstructed via local connections. Instances of such codes are recently considered in DSS~\cite{Sathiamoorthy:XORing13,Huang:Erasure12}.

In large-scale distributed storage systems (such as GFS \cite{Ghemawat:Google03}),  \textit{correlated failures} are unavoidable. As analyzed in~\cite{Ford:Availability10}, these simultaneous failures of multiple nodes affect the performance of computing systems severely. The analysis in~\cite{Ford:Availability10} further shows that these correlated failures arise due to \textit{failure domains}. For example, nodes connected to the same power source or nodes belonging to the same rack exhibit these failure bursts. The unavailability periods are transient, and largest failure bursts almost always have significant rack-correlation. In order to overcome from failures having such patterns, a different approach is needed.

In this paper, we develop a framework to analyze resilience against block failures in DSS with node repair efficiencies. We consider a DSS with a single failure domain, where nodes belonging to the same failure group constitute a block of the codeword. We introduce block failure resilient (BFR) codes, which allow for data collection from any $b_c= b-\rho$ blocks, where $b$ is the number of blocks, and $\rho$ is the resilience parameter of the code. Considering a load-balancing among blocks, a same number of nodes are contacted within these $b_c$ blocks. (A total of $k=k_cb_c$ nodes and downloading $\alpha$ - i.e., all - symbols from each.) This constitutes data collection property of BFR codes. ($\rho=0$ case can be considered as a special case of batch codes introduced in ~\cite{Ishai:Batch04}.) Then, we introduce repairability in BFR codes, where any node of a failed block can be reconstructed from any $d_r$ of any remaining $b_r\leq b-1$ blocks. (A total of $d=d_rb_r$ nodes and downloading $\beta$ symbols from each.) As introduced in~\cite{Dimakis:Network10}, we utilize graph expansion of DSS employing these repairable codes, and derive file size bounds and characterize BFR-MBR and BFR-MSR points. (We note that the blocks in our model can be used to model racks in DSS. Such a model is related to the work \cite{Gaston:realistic13} which differentiates between within-rack communication and cross-rack communication. Our focus here would correspond to the case where within rack communication is much higher than the cross-rack communication, as no nodes from the failed rack can be contacted to regenerate a node.) We construct explicit codes achieving these points for a wide set of parameters.  For a system with $b=2$ blocks case, we show that achieving both MSR and MBR properties simultaneously is asymptotically possible. (This is somewhat similar to the property of Twin codes \cite{Rashmi:Enabling11}, but here the data collection property is different.) Then, for a system with $b\geq 3$ blocks case, we consider utilizing multiple codewords, which are placed into DSS via a combinatorial design based codeword placement algorithm. We show this technique establishes optimal codes for a wide set of parameter ranges.

The paper is organized as follows. Section II introduces model and preliminaries. Section III is devoted to the analysis of file size bounds. Code constructions are provided in Section IV. Section V includes extensions and concluding remarks.

\section{Background and Preliminaries}
\label{sec:Background}
\subsection{Block failure resilient codes and repairability}
Consider a code $\Cc$ which maps $\Mc$ symbols (over $\FF_q$) in $\fv$ (file) to length $n$ codewords (nodes) $\cv=(c_1,\cdots,c_n)$ with $c_i\in \FF_q^\alpha$ for $i=1,\cdots,n$. These codewords are distributed into $b$ blocks each with block capacity $c=\frac{b}{n}$ nodes per block. We have the following definition.

\begin{definition}[Block Failure Resilient (BFR) Codes]
An $(n,b,\Mc,k,\rho,\alpha)$ block failure resilient (BFR) code encodes $\Mc$ elements in $\FF_q$ ($\fv$) to $n$ codeword symbols (each in $\FF_q^\alpha$) that are grouped into $b$ blocks such that $\fv$ can be decoded by accessing to any $\frac{k}{b-\rho}$ nodes of from each of the  $b-\rho$ blocks.
\end{definition}

We remark that, in the above, $\rho$ represents the resilience parameter of the BFR code, i.e., the code can tolerate $\rho$ block erasures. Due to this data collection (file decoding) property of the code, we denote the number of blocks accessed as $b_c=b-\rho$ and number of nodes accessed per block as $k_c=\frac{k}{b_c}$. Noting that $k_c\leq c$ should be satisfied, we differentiate between \emph{partial} block access, $k_c<c$, and \emph{full} block access $k_c=c$. Throughout the paper, we assume $n|b$. i.e., $c$ is integer, and $(b-\rho)|k$, i.e., $k_c$ is integer.

Remarkably, any MDS array code \cite{McWilliams:Theory77} can be utilized as BFR codes for the full access case. In fact, such an approach will be optimal in terms of minimum distance, and therefore for resilience $\rho$. However, for $k_c<c$, MDS array codes may not result in an optimal code. Constructing optimal BFR codes in terms of the trade-off between resilience $\rho$ and code rate $\frac{\Mc}{n\alpha}$ will be studied elsewhere. In this work, we focus on repairable BFR codes, as defined in the following.

\begin{definition}[Block Failure Resilient Regenerating Codes (BFR-RC)]
An $(n,b,\Mc,k,\rho,\alpha,d,\sigma,\beta)$ block failure resilient regenerating code (BFR-RC) is an $(n,b,\Mc,k,\rho,\alpha)$ BFR code (data collection property) with the following repair property: Any node of a failed block can be reconstructed by accessing to any $d_r=\frac{d}{b-\sigma}$ nodes of any $b_r=b-\sigma$ blocks and downloading $\beta$ symbols from each of these $d=b_rd_r$ nodes.
\end{definition}

We assume $(b-\rho)|d$, i.e., $d_r$ is integer. (Note that $d_r$ should necessarily satisfy $\frac{d}{b-\sigma}=d_r\leq c=\frac{n}{b}$ in our model.) We consider the trade-off between the \emph{repair bandwidth} $\gamma=d\beta$ and \emph{per node storage} $\alpha$ similar to the seminal work ~\cite{Dimakis:Network10}. In particular, we define $\alpha_{\textrm{BFR-MSR}}=\frac{\Mc}{k}$ as the minimum per node storage and $\gamma_{\textrm{BFR-MBR}}=\alpha$ as the minimum repair bandwidth for an $(n,b,\Mc,k,\rho,\alpha,d,\sigma,\beta)$ BFR-RC.
When deriving this trade-off, we focus on systems having $d_r=\frac{d}{b-\sigma}\geq k_c=\frac{k}{b-\rho}$, i.e., data collection process contacts to less number of nodes per block as compared to symbol regeneration. (We note that, similar to regenerating codes, without loss of generality, one should only consider systems that satisfy $d\geq k$, i.e., $d_r(b-\sigma)\geq k_c (b-\rho)$. Therefore, our $d_r\geq k_c$ assumption can be made without loss of generality for systems having $\rho\leq \sigma$.)

\subsection{Information flow graph}
The operation of a DSS employing such codes can be modeled by a multicasting scenario over an information flow graph \cite{Dimakis:Network10}, which has three types of nodes: 1) Source node ($S$): Contains original file $\fv$. 2) Storage nodes, each represented as $x_i$ with two sub-nodes($(x^{\rm in}_i,x^{\rm out}_i)$), where $x^{\rm in}$ is the sub-node having the connections from the live nodes, and $x^{\rm out}$ is the storage sub-node, which stores the data and is contacted for node repair or data collection (edges between each $x^{\rm in}_i$ and $x^{\rm out}_i)$ has $\alpha$-link capacity). 3) Data collector ($\rm{DC}$) which contacts $x^{\rm{out}}$ sub-nodes of $k$ live nodes (with edges each having $\infty$-link capacity). (As described above, for BFR codes these $k$ nodes can be any $\frac{k}{b-\rho}$ nodes from each of the $b-\rho$ blocks.) Then, for a given graph $\Gc$ and DCs $\rm{DC}_i$, the file size can be bounded using the max flow-min cut theorem for multicasting utilized in network coding~\cite{Ho:random06,Dimakis:Network10}.
\begin{lemma}[Max flow-min cut theorem for multicasting] \label{lma:MFMCforMulticast}
$$\Mc \leq \min_{\Gc} \min_{\rm{DC}_i} \rm{max flow}(S \to \rm{DC}_i,\Gc),$$
where $\rm{flow}(S \to \rm{DC}_i,\Gc)$ represents the flow from the source
node $S$ to $\rm{DC}_i$ over the graph $\Gc$.
\end{lemma}
Therefore, $\mathcal{M}$ symbol long file can be delivered to a DC, only if the min cut is at least $\mathcal{M}$. In the next section, similar to Dimakis et al., \cite{Dimakis:Network10}, we consider $k$ successive node failures and evaluate the min-cut over possible graphs, and obtain a file size bound for a DSS operating with BFR-RC.

\subsection{Block designs and projective planes}

We first provide the definition of balanced incomplete block designs (BIBDs) \cite{Stinson:Combinatorial04}.
\begin{definition}[Balanced incomplete block design]
A $(v,\kappa,\lambda)$-BIBD has $v$ points distributed into blocks of size $\kappa$ such that any pair of points are contained in $\lambda$ blocks.
\end{definition}

\begin{corollary}\label{thm:BIBDcorollary}
For a $(v,\kappa,\lambda)$-BIBD,
\begin{itemize}
\item Every point occurs in $r=\frac{\lambda (v-1)}{\kappa-1}$ blocks.
\item The design has exactly $b=\frac{vr}{\kappa}=\frac{\lambda(v^2-v)}{\kappa^2-\kappa}$ blocks.
\end{itemize}
\end{corollary}

In the achievable schemes of this work, we utilize a special class of block designs that are called projective planes.
\begin{definition}
A $(v=p^2+p+1,\kappa=p+1,\lambda=1)$-BIBD with $p\geq 2$ is called a projective plane of order $p$.
\end{definition}

Projective planes have the property that every pair of blocks intersect at a unique point (as $\lambda=1$). In addition, due to Corollary~\ref{thm:BIBDcorollary}, in projective planes, every point occurs in $r=p+1$ blocks, and there are $b=v=p^2+p+1$ blocks.

\section{File Size Bound for Repairable BFR Codes}
\label{sec:FileSize}

Information flow graph analysis, similar to that of considered in \cite{Dimakis:Network10}, can be performed to obtain file size bounds for repairable BFR codes. In this paper, we focus on the case $\sigma=1$, i.e., regeneration of a node in a failed block is performed by contacting to all remaining live blocks. In the following, we first analyze $\rho=0$ case, i.e., data collector connects all the blocks to reconstruct the data.

\subsection{$\rho=0$, $b=2$ case}

\begin{figure}[t]
 \centering
 \includegraphics[width=0.6\columnwidth]{two-block}
 \caption{Repair process for $b=2$ (two blocks) case.}
\label{fig:Two-block}
\end{figure}

Consider $b=2$-block case as in Fig.~\ref{fig:Two-block} and assume $2|k$. From Lemma~\ref{lma:MFMCforMulticast}, the file size $\Mc$ can be upper bounded with the repair procedure shown in Fig.~\ref{fig:Two-block}, which displays one of the ``minimum-cut'' scenarios, wherein any two consecutive node failures belong to different blocks. Assuming $k$ is even and $d\geq \frac{k}{2}$,
\begin{equation}
\Mc \leq \sum_{i=0}^{\frac{k}{2}-1}\min(\alpha,(d-i)\beta) + \sum_{i=1}^{\frac{k}{2}}\min(\alpha,(d-i)\beta).
\label{eq:min-cut_two}
\end{equation}
Achieving this upper bound \eqref{eq:min-cut_two} with equality would yield maximum possible file size. One particular instance is shown in Fig.~\ref{fig:Two-block}, and we note that the order of failed nodes does not matter as the sum of the cut would be the same with different order of failures as long as we consider connection from data collector to $\frac{k}{2}$ repaired nodes from each block.

For MSR point, $\alpha=\alpha_{\textrm{BFR-MSR}}=\frac{\Mc}{k}$. In the bound \eqref{eq:min-cut_two}, we then have $\alpha_{\textrm{BFR-MSR}} \leq (d-\frac{k}{2})\beta_{\textrm{BFR-MSR}}$. Achieving equality would give the minimum repair bandwidth for the MSR case. Hence, BFR-MSR point is given by
\begin{equation}
(\alpha_{\textrm{BFR-MSR}},\gamma_{\textrm{BFR-MSR}}) = (\frac{\Mc}{k},\frac{2\Mc d}{2kd-k^2}).
\label{eq:min-cut_two-MSR-values}
\end{equation}

BFR-MBR codes, on the other hand, have the property that $d\beta=\alpha$ with minimum possible $d\beta$ while achieving the equality in \eqref{eq:min-cut_two}. Inserting $d\beta=\alpha$ in \eqref{eq:min-cut_two}, we obtain that

\begin{equation}
(\alpha_{\textrm{BFR-MBR}},\gamma_{\textrm{BFR-MBR}}) = (\frac{4\Mc d}{4dk-k^2},\frac{4\Mc d}{4dk-k^2}).
\label{eq:min-cut_two-MBR-values}
\end{equation}
Same analysis can be done for odd values of $k$ as well,
\begin{equation}
(\alpha_{\textrm{BFR-MSR}},\gamma_{\textrm{BFR-MSR}}) =
\begin{cases}
	(\frac{M}{k},\frac{2Md}{2kd-k^2-k}), \textrm{ if $k$ is odd} \\
    (\frac{M}{k},\frac{2Md}{2kd-k^2}), \textrm{ o.w.}
\end{cases}
\label{eq:MSR_cases}
\end{equation}
\begin{equation}
(\alpha_{\textrm{BFR-MBR}},\gamma_{\textrm{BFR-MBR}}) =
\begin{cases}
	(\frac{4Md}{4dk-k^2+1},\frac{4Md}{4dk-k^2+1}), \textrm{ if $k$ is odd} \\
    (\frac{4Md}{4dk-k^2},\frac{4Md}{4dk-k^2}), \textrm{ o.w.}
\end{cases}
\label{eq:MBR_cases}
\end{equation}

Here, we compare $\gamma_{\textrm{BFR-MSR}}$ and $\gamma_{\textrm{MBR}}$. We have $\gamma^{\textrm{k-odd}}_{\textrm{BFR-MSR}} \geq \gamma^{\textrm{k-even}}_{\textrm{BFR-MSR}} \geq \gamma_{\textrm{MBR}}=\frac{2\Mc d}{k(2d-k+1)}$, and, if we have $2d-k \gg 1$, then $\gamma^{\textrm{k-odd}}_{\textrm{BFR-MSR}} \approx \gamma^{\textrm{k-even}}_{\textrm{BFR-MSR}} \approx \gamma_{\textrm{MBR}}$. This implies that BFR-MSR codes with $b=2$ achieves repair bandwidth of MBR and per-node storage of MSR codes simultaneously for systems with $d \gg 1$. We provide the generalization of these bounds to $b \geq 2$ case in the following.

\subsection{$\rho=0$, $b\geq2$ case}

The same steps described above can be used to derive the file size bound for $b$-blocks.

\begin{lemma}
The optimal file size is given by
\begin{align}
\begin{split}
\Mc  =  & \sum_{i=0}^{\frac{k}{b}-1}\min(\alpha,(d-(b-1)i)\beta) \\
& + \sum_{i=0}^{\frac{k}{b}-1}\min(\alpha,(d-1-(b-1)i)\beta) + \ldots \\
& + \sum_{i=0}^{\frac{k}{b}-1}\min(\alpha,(d-(b-1)-(b-1)i)\beta).
\end{split}
\end{align}
\end{lemma}

\begin{proposition}
BFR-MSR and BFR-MBR points are as follows,
\begin{equation}
(\alpha_{\textrm{BFR-MSR}},\gamma_{\textrm{BFR-MSR}}) = \left(\frac{\Mc}{k},\frac{\Mc d}{kd-\frac{k^2(b-1)}{b}}\right)
\label{eq:min-cut_b-MSR-values}
\end{equation}

\begin{equation}
(\alpha_{\textrm{BFR-MBR}},\gamma_{\textrm{BFR-MBR}}) = \left(\frac{\Mc d}{kd-\frac{k^2(b-1)}{2b}},\frac{\Mc d}{kd-\frac{k^2(b-1)}{2b}}\right)
\label{eq:min-cut_b-MBR-values}
\end{equation}
\end{proposition}

We observe that $\gamma_{\textrm{BFR-MSR}} \leq \gamma_{\textrm{MSR}}=\frac{\Mc d}{k(d-k+1)}$ for $b \leq k$, which is the case here as $b \mid k$. Also, we have $\frac{\gamma_{\textrm{BFR-MSR}}}{\gamma_{\textrm{MBR}}} = \frac{d-\frac{k-1}{2}}{d-k\frac{b-1}{b}} \geq 1$ when $b \geq \frac{2k}{k+1}$ which is always true. Hence, $\gamma_{\textrm{BFR-MSR}}$ is between $\gamma_{\textrm{MSR}}$ and $\gamma_{\textrm{MBR}}$.

\subsection{$\rho>0$ case}

If we restrict data collector to connect $b_c<b$ blocks (i.e., $\rho>0$), but keep the repair process same as before, the above analysis follows and corresponding MSR and MBR points are given by replacing $b$ in \eqref{eq:min-cut_b-MSR-values} and \eqref{eq:min-cut_b-MBR-values} with $b_{c}=b-\rho$ - for systems satisfying $d_r\geq k_c$. (This follows as the repair from these $\rho$ blocks will not contribute to the cut between the source $S$ and DC.)

\section{BFR-MSR and BFR-MBR Code Constructions}
\label{sec:CodeConst}

\subsection{Transpose code for b=2 case}

One instance of BFR codes is given in the Fig.~\ref{fig:Transpose}. We set $\alpha=d=\frac{n}{2}$, and store the transpose of the first block's symbols in the second block. The repair of a failed node $i$ in the first block can be performed by connecting all the nodes in the second block and downloading only $1$ symbol from each node. That is, $d\beta=\alpha$. Further, we set $\Mc=kd-(\frac{k}{2})^2$, and use an $[N=\alpha^2,K=\Mc]$ MDS code to encode file $\fv$ into symbols denoted with $x_{i,j}$, $i,j=1,...,\alpha$. BFR data collection property allows for reconstructing the file, as connecting any $\frac{k}{2}$ nodes from each block assures at least $K$ distinct symbols. This code is a BFR-MBR code for $\beta=1$ (scalar code), as the optimal file size in \eqref{eq:min-cut_two-MBR-values}, i.e., $\Mc=kd-(\frac{k}{2})^2$, is achieved with $d\beta=\alpha$. A similar code to this construction is Twin codes introduced in \cite{Rashmi:Enabling11}, where the nodes are split into two types and a failed node of a a given type is regenerated by connecting to nodes only in the other type. However, Twin codes, as opposed to our model, do not have balanced node connection for data collection. In particular, DC connects to only (a subset of $k$ nodes from) a single type. On the other hand, BFR codes, for $b=2$ case, connects to $\frac{k}{2}$ nodes from each block.

\begin{figure}[t]
 \centering
 \includegraphics[width=0.60\columnwidth]{2-block_trans}
 \caption{Transpose code is a two-block BFR-MBR code.}
\label{fig:Transpose}
\end{figure}

\subsection{Block design based regenerating code symbol placement}

Consider that the file $\Fc$ of size $\Mc$ contains 3 sub-files $\Fc_{1}$, $\Fc_{2}$ and $\Fc_{3}$ each of size $\tilde{\Mc}$. We encode these sub-files with $[\tilde{n}=10,\tilde{k}=4,\tilde{d}=5,\tilde{\alpha},\tilde{\beta}]$ regenerating code $\tilde{\Cc}$, represent the resulting symbols with $\Pc_{1}=p_{1,1:\tilde{n}}$ for $\Fc_1$, $\Pc_{2}=p_{2,1:\tilde{n}}$ for $\Fc_2$, and $\Pc_{3}=p{_{3,1:\tilde{n}}}$ for $\Fc_3$. These symbols are grouped in a specific way placed into nodes within blocks as represented in Fig.~\ref{fig:3-block BFR-RC}, where each node contains two symbols each coming from two of the different sets $\Pc_{1},\Pc_{2},\Pc_{3}$. We set the sub-code $\tilde{\Cc}$ parameters as $[\Mc=3\tilde{\Mc}, k=\frac{3}{2}\tilde{k}, d=2\tilde{d}, \alpha=2\tilde{\alpha}, \beta=\tilde{\beta}]$.

Assume Block 1 is unavailable and its first node, which contains codeword $c_{1}$, has to be reconstructed. Due to underlying regenerating code, contacting $5$ nodes of Block 2 and accessing to $p_{1,6:10}$ repairs $p_{1,1}$. Similarly, $p_{2,1}$ can be reconstructed from Block 3. Any node failures can be handled similarly, by connecting to remaining 2 blocks and repairing each symbol of lost node by connecting $\tilde{d}$ nodes in a block. As we have $k=6$, DC, connecting to 2 nodes from each block, obtains $12$ symbols which has 4 different symbols from each of $\Pc_{1}$, $\Pc_{2}$ and $\Pc_{3}$. As the embedded regenerating code has $\tilde{k}=4$, all $3$ sub-files can be recovered.

We generalize the BFR-RC construction above utilizing projective planes. First, the file $\fv$ of size $\Mc$ is partitioned into $v$ parts, $\Mc_{1}$, $\Mc_{2}$,...,$\Mc_{v}$. Each part, of size $\tilde{\Mc}$, then encoded using $[\tilde{n},\tilde{k},\tilde{d},\tilde{\alpha},\tilde{\beta}]$ regenerating code $\tilde{\Cc}$. We represent the resulting symbols with $\Pc_{i}=p_{i,1:\tilde{n}}$ for $i=1,\cdots, v$. We then consider index of each part as a point in a $(v=p^2+p+1,\kappa=p+1,\lambda=1)$ projective plane. (Indices of symbol sets $\Pc_\Jc$ and points $\Jc$ of projective plane are used interchangeably in the following.) We perform the placement of each point in the system using this projective plane mapping. (The setup in Fig. \ref{fig:3-block BFR-RC} can be considered as a toy model. Although the combinatorial design with blocks given by $\{p_1,p_2\},\{p_1,p_3\},\{p_2,p_3\}$ has projective plane properties, it is not considered as an instance of a projective plane.) In this placement, total of $\tilde{n}$ nodes from each partition $\Pc_{i}$ are distributed to $r$ blocks evenly, each block contains $\frac{\tilde{n}}{r}$ nodes where each node stores $\alpha=\kappa\tilde{\alpha}$ symbols. Note that blocks of projective plane give the indices of parts $\Pc_i$ stored in the nodes of the corresponding block in DSS. That is, all nodes in a block stores symbols from unique subset of $\Pc=\{\Pc_1,\cdots,\Pc_v\}$ of size $\kappa$. Overall, the system can store a file of size $\Mc=v\tilde{\Mc}$ with $b=v$ blocks. We set the sub-code $\tilde{\Cc}$ parameters as
\begin{equation}
M=v\tilde{M}, k=\frac{b}{r}\tilde{k}, d=\kappa\tilde{d}, \alpha=\kappa\tilde{\alpha}, \beta=\tilde{\beta}
\label{eq:assignment-b}
\end{equation}
where we choose parameters to satisfy $r-1 \mid \tilde{d}$, $r \mid \tilde{n}$ and $r \mid \tilde{k}$.

\emph{Node Repair:} Consider that one of the nodes in a block is to be repaired. Note that the failed node contains $\kappa$ symbols, each coming from a distinct subfile's regenerating codeword. Using projective planes' property that any $2$ blocks has only $1$ point in common, any remaining block can help for in the regeneration of $1$ symbol of the failed node. Furthermore, as any point has a repetition degree of $r$, one can connect to $r-1$ blocks, $\frac{\tilde{d}}{r-1}$ nodes per block, to repair one symbol of a failed node. Combining these two, node regeneration is performed by connecting $(r-1)\kappa$ blocks. Substituting $\kappa=p+1$ and $r=p+1$, connecting to $p^{2}+p=b-1$ blocks allows for reconstructing any node of a failed block.

\emph{Data Collection:} DC, connects $\frac{\tilde{k}}{r}$ nodes per block from all $b_{c}=b$ blocks, i.e., a total of $k=\frac{b}{r}\tilde{k}$ nodes each having encoded symbols of $\kappa$ subfiles. These total of $v\tilde{k}$ symbols include $\tilde{k}$ symbols from each subfile, from which all subfiles, hence the file $\fv$, can be decoded.

\begin{figure}[t]
 \centering
 \includegraphics[width=0.6\columnwidth]{3-block}
 \caption{Three-block BFR-RC via projective plane symbol placement.}
\label{fig:3-block BFR-RC}
\end{figure}

\subsubsection{BFR-MSR}
To construct a BFR-MSR code, we set each subcode $\tilde{\Cc}$ as an MSR code, which has
\begin{equation}
\tilde{\alpha}=\frac{\tilde{\Mc}}{\tilde{k}}, \tilde{d}\tilde{\beta}=\frac{\tilde{\Mc}\tilde{d}}{\tilde{k}(\tilde{d}-\tilde{k}+1)}.
\end{equation}

This, together with \eqref{eq:assignment-b}, results in the following parameters of our BFR-MSR construction
\begin{equation}
\alpha=\tilde{\alpha}\kappa=\frac{\Mc}{k}, d\beta=\kappa \tilde{d}\tilde{\beta}=\frac{\Mc d}{k(d-\frac{k(p+1)^{2}}{p^2+p+1}+p+1)}.
\label{eq:bfr-msr}
\end{equation}

We remark that if we utilize ZigZag codes\cite{Tamo:Zigzag13} as the sub-code $\tilde{\Cc}$ above, we have
$[\tilde{n},\tilde{k},\tilde{d}=\tilde{n}-1,\tilde{\alpha}=\tilde{r}^{\tilde{k}-1},\tilde{\beta}=\tilde{r}^{\tilde{k}-2}, \tilde{r}=\tilde{n}-\tilde{k}]$, and having $\tilde{d}=\tilde{n}-1$ requires connecting to $1$ node per block for repairs in our block model. On the other hand, product matrix MSR codes \cite{Rashmi:Optimal11} can be used as the sub-code $\tilde{\Cc}$ for any $\tilde{d} \geq 2\tilde{k}-2$, for which we do not necessarily have $\frac{\tilde{d}}{r-1}=1$. We observe from \eqref{eq:min-cut_b-MSR-values} and \eqref{eq:bfr-msr} that MSR point is achieved for $\tilde{k}=p+1$, meaning $k=b$.

\subsubsection{BFR-MBR}

To construct a BFR-MBR code, we set each subcode $\tilde{\Cc}$ as a product matrix MBR code \cite{Rashmi:Optimal11}, which has
\begin{equation}
\tilde{\alpha}=\tilde{d}\tilde{\beta}= \frac{2\tilde{\Mc}\tilde{d}}{\tilde{k}(2\tilde{d}-\tilde{k}+1)}.
\end{equation}

This, together with \eqref{eq:assignment-b}, results in the following parameters of our BFR-MSR construction
\begin{equation}
\alpha=d\beta=\frac{2\Mc d}{k(2d-\frac{k(p+1)^2}{p^2+p+1}+p+1)}.
\label{eq:bfr-mbr}
\end{equation}

From \eqref{eq:min-cut_b-MBR-values} and \eqref{eq:bfr-mbr}, MBR point is achieved for $\tilde{k}=p+1$.

\section{Extensions and concluding remarks}
\label{sec:Discussion}

\subsection{$\rho>0$ case}

In the above, we considered the cases where DC connects all $b$ blocks in file reconstruction. In order to support $b_{c}<b$, we consider employing Gabidulin codes \cite{Gabidulin:Theory85} as an outer code similar to the constructions provided in \cite{Rawat:Optimal14,Kamath:Explicit13}. We briefly discuss our approach here. Detailed results will be provided elsewhere. $[N,K,D=N-K+1]_{q^{m}}$ Gabidulin code $C^{Gab}$, $m\geq N$, has a codeword $( f(g_{1}),f(g_{2}),...,f(g_{N})) \in \FF_{q^{m}}^N$, where $f(x)$ is a linearized polynomial over $\FF_{q^{m}}$ of $q$-degree $K-1$ with $K$ message symbols as its coefficients and $g_{1},g_{2},...,g_{N} \in \FF_{q^{m}}$ are linearly independent over $F_{q}$ \cite{Gabidulin:Theory85}.

\begin{remark}
Given evaluations of $f(\cdot)$ at any $K$ linearly independent (over $\FF_{q}$) points in $\FF_{q^{m}}$, one can reconstruct the message vector.
\end{remark}

Here, before partitioning the message into $v$ parts, we encode the file with a Gabidulin code first, then partition the resulting codeword into $v$ parts and follow remaining steps as before. With this approach, decoding the message at DC follows by obtaining at least $K$ independent evaluations from $k$ nodes, $k_c=\frac{k}{b_{c}}$ nodes per block from a total of $b_{c}=b-\rho$ blocks. As considered in \cite{Rawat:Optimal14,Kamath:Explicit13}, the number of such evaluations can be derived from the rank accumulation profile of the inherent MSR/MBR codes $\tilde{\Cc}$ as in the following
\begin{equation}
\tilde{a_{j}} =
\begin{cases}
    \tilde{\alpha},& \text{if $\tilde{\Cc}$ is MSR and } 1\leq j\leq \tilde{k} \\
    \tilde{\alpha}-(j-1)\tilde{\beta},              & \text{if $\tilde{\Cc}$ is MBR and } 1\leq j\leq \tilde{k} \\
    0,              & \text{if $\tilde{\Cc}$ is MSR/MBR and } \tilde{k}+1\leq j\leq \tilde{n} \\
\end{cases}
\end{equation}
Note that because of projective plane property, connecting $b-1$ blocks would result in getting $k_cr$ evaluations for $v-\kappa$ points and $k_c (r-1)$ evaluations for $\kappa$ points. Hence DC can decode the message by using an outer Gabidulin code if
\begin{equation}
\sum_{t=1}^{v-\kappa}\sum_{j=1}^{k_c r}\tilde{a}_{j} + \sum_{t=1}^{\kappa}\sum_{j=1}^{k_c (r-1)}\tilde{a}_{j}\geq K.
\end{equation}

Similarly, for $b_{c}=b-2$, decoding at DC is possible if
\begin{equation}
\sum_{t=1}^{v-(2\kappa-1)}\sum_{j=1}^{k_c r}\tilde{a}_{j} + \sum_{t=1}^{2\kappa-2}\sum_{j=1}^{k_c (r-1)}\tilde{a}_{j}+\sum_{j=1}^{k_c (r-2)}\tilde{a}_{j}\geq K.
\end{equation}
With such an approach, for $b_{c}\leq b-3$ there are multiple collection possibilities for DC. For example, by connecting $b-3$ blocks DC can observe either a) $k_cr$ evaluations for $v-(3\kappa-2)$, $k_c(r-1)$ evaluations for $3(\kappa-1)$ points and $k_c(r-3)$ evaluations for 1 point, or b) $k_cr$ evaluations for $v-(3\kappa-3)$, $k_c(r-1)$ evaluations for $3(\kappa-2)$ points and $k_c(r-2)$ evaluations for 3 points. Therefore, we need to ensure that minimum rank accumulations of all cases is at least $K$.

\subsection{Concluding remarks}

We introduced the framework of block failure resilient (BFR) codes that can recover data stored in the system from a subset of available blocks with a load balancing property. Repairability is studied, file size bounds are derived, BFR-MSR and BFR-MBR points are characterized, explicit code constructions for a wide set of parameters are provided.


TITLE: What's the difference between these two signs
QUESTION [0 upvotes]: Are these just two different notations or does each refer to something different?

REPLY [0 votes]: It may be easier to learn from illustrative examples. An explanation may be too lengthy and verbose.
In the first there is one dependent variable $f(x)$ and one independent variable $x$. To indicate this $d$ is used as symbol for them both in the front as the simplest differential operator. While differentiating coefficients are left as they are and unattached constants vanish.
In the second case there are two or more dependent variables $f(x,y,z,..) $ for example $ 8x-2 y+ z^2$ and one independent variable, say $x$. To indicate this operation $d$ becomes $ \partial $ for all the variables, dependent or  independent. While differentiating, independent variable or its functions are operated same way as above, however non-$x$ functions, i.e., other $(y,z)$ or their functions are treated as constant (in  coefficient or additive association) to leave they as they are.


text:
\begin{document}

\begin{verbatim}\end{verbatim}\vspace{2.5cm}

\begin{center}
\textsc{\Large\textbf{Generalized minor inequalities for the set covering polyhedron
related to circulant matrices}}
\end{center}
\smallskip

\begin{center}
\large Paola B.\,Tolomei\footnote{ptolomei@fceia.unr.edu.ar}
\end{center}
\begin{center}
\textit{Departamento de Matem\'atica, Facultad de Ciencias Exactas, Ingenier\'ia y Agrimensura, Universidad Nacional de Rosario, Santa Fe, Argentina}
\medskip

\textit{and CONICET, Argentina}
\end{center}

\smallskip

\begin{center}
\large Luis M.\,Torres\footnote{luis.torres@epn.edu.ec}
\end{center}

\begin{center}
\textit{Centro de Modelización Matemática ModeMat - Escuela Politécnica Nacional, Quito, Ecuador}
\end{center}

\medskip

\begin{abstract}
We study the set covering polyhedron related to circulant matrices.
In particular, our goal is to characterize the first Chvátal closure
of the usual fractional relaxation. We present a family of
valid inequalities that generalizes the family of minor inequalities
previously reported in the literature and includes
new facet-defining inequalities.
Furthermore, we propose a polynomial time separation algorithm for a particular subfamily of
these inequalities.

\medskip

\noindent Keywords: \textit{set covering\;\; circulant matrices\;\; Chvátal closure}
\end{abstract}

\section{Introduction}
The \emph{weighted set covering problem} can be stated as
$$
\mbox{(SCP)} \;\;\min\{c^Tx: Ax\geq \onevec, x\in  \{0,1\}^n\}
$$
where $A$ is an $m\times n$ matrix with $0,1$ entries, $c \in \Z^n$,
and $\onevec \in \R^m$ is the vector having all entries equal to one.
The SCP is a classic problem in combinatorial optimization
with important practical applications (crew scheduling, facility location,
vehicle routing, to cite a few prominent examples), but hard to
solve in general. One
established approach to tackle this problem is to study the
polyhedral
properties of the
set of its feasible solutions. \cite{BalasNg89,CornuejolsSassano89,NobiliSassano89,Sa}.

The \emph{set covering polyhedron} $\Qi{A}$ is defined as the convex
hull of all feasible solutions of SCP. Its \emph{fractional
  relaxation} $\Q{A}$ is the feasible region of the linear programming
relaxation of SCP, i.e.,
$$
\Q{A}:=\{x\in [0,1]^n: Ax\geq \onevec \}.
$$

It is known that SCP can be solved in polynomial time if $A$ belongs
to the particular class of \textit{circulant matrices} defined in the
next section. Hence, it is natural to ask whether an
explicit description in terms of linear inequalities can be provided for $\Qi{A}$ in
this case, an issue that has been addressed in several recent studies by researchers
in the field (see \cite{circu,BNTDAM13,BNTMMOR13,CN} among others). For the related
\emph{set packing polytope} of circulant matrices,
$$
\Pint{A}:= \conv (\{Ax\leq \onevec, x\in  \{0,1\}^n\})
$$
such a description follows from the results published in \cite{EisenbrandEtAl05}.

Bianchi et al.~introduced in \cite{BNTDAM13} a family of facet-defining
inequalities for $\Qi{A}$ which are associated with certain structures
called circulant minors. Moreover, the authors presented in \cite{BNTMMOR13} two families
of circulant matrices for which $\Qi{A}$ is completely described by
this class of \emph{minor inequalities}, together with the full-rank
inequality and the inequalities defining $\Q{A}$, usually denoted as
boolean facets. The existence of a third family of circulant matrices having this
property follows from previous results obtained by Bouchakour et al.~\cite{Mah} in the context
of the dominating set polytope of some graph classes.

If an inequality $a^Tx \leq b$ is valid for a polytope $P \subset \R^n$ and
$a \in \Z^n$, then $a^Tx \leq \floor{b}$ is valid for the integer polytope
$P_I:= \conv(P \cap \Z^n)$. This procedure is called Chvátal-Gomory
rounding, and it is known that the system of all linear inequalities which
can be obtained in this way defines a new polytope $P'$, the
\emph{first Chvátal closure of $P$}. Moreover, iterating this procedure yields $P_I$
in a finite number of steps. An inequality is said to have \emph{Chvátal rank} of
$t$ if it is valid for the $t$-th Chvátal closure of a polytope.
All inequalities mentioned above have Chvátal rank less than or
equal to one.

With the aim of investigating if the results in \cite{BNTMMOR13,Mah}
can be generalized to all circulant matrices,
we have tried to characterize the first Chvátal
closure of $\Q{A}$ for any circulant matrix $A$.
In particular, we addressed the question whether the system consisting
of minor inequalities, boolean facets, and the
full-rank inequality is sufficient for describing $\Qp{A}$. We have obtained a
negative answer to this question in the form of a new class of valid inequalities for $\Qi{A}$ which contains minor
inequalities as a proper subclass. All inequalities from this class
have Chvátal rank equal to one, and besides, some of them define new
facets of $\Qi{A}$, as we show by an example.

This paper is organized as follows. In the next section, we introduce some
notation and preliminary results required for our work. In Section~\ref{sec:clausura}
we describe our approach for computing the first Chvátal closure of $\Q{A}$
and define the new class of \emph{generalized minor inequalities}. A separation
algorithm for a particular subclass of these is provided in Section \ref{sec:separation}.
Finally, some conclusions and possible directions for future work are discussed
in Section~\ref{sec:conclusions}. A preliminary version of this article appeared without proofs in \cite{TolomeiTorres13}.

\section{Notations, definitions and preliminary results}
\label{sec:notations}

For $n \in \N$, let $[n]$ denote the additive group defined on the set
$\tabulatedset{1, \ldots, n}$, with integer addition modulo $n$.
Throughout this article, if $A$ is a $0,1$ matrix of order $m\times
n$, then we consider the columns (resp. rows) of $A$ to be indexed by
$[n]$ (resp. by $[m]$). In particular, addition of column (resp. row) indices
is always considered to be taken modulo $n$ (resp. modulo $m$). Two matrices $A$ and $A'$ are
\emph{isomorphic}, denoted by $A\approx A'$, if $A'$ can be
obtained from $A$ by permutation of rows and columns. Moreover, we say
that a row $v$ of $A$ is a \textit{dominating row} if $v\geq u$ for
some other row $u$ of $A$, $u\neq v$.

Given $N\subset [n]$, the \emph{minor of} $A$ \emph{obtained by
  contraction of} $N$, denoted by $A/N$, is the submatrix of $A$ that
results after removing all columns with indices in $N$ and all
dominating rows.
In this work, when we refer to \emph{a minor} of $A$ we always
consider a minor obtained by contraction.

Let $n, k \in \N$ with $2\leq k\leq n-2$, and
$C^i:=\{i,i+1,\ldots,i+(k-1)\}\subset [n]$ for every $i\in [n]$.
With a little abuse of notation we will also use $C^i$ to denote
the incidence vector of this set. A
\emph{circulant matrix} $C_n^{k}$ is the square matrix of order $n$ whose $i$-th
row vector is $C^i$.  Observe that
$C^i=\sum_{j=i}^{i + k-1} e^j$, where $e^j$ is the $j$-th canonical vector
in $\R^n$.

A minor of $C_n^k$ is called a \emph{circulant minor} if it is isomorphic to
a circulant matrix $C_{n'}^{k'}$. As far as we are aware, circulant minors were
introduced for the first time in \cite{CN}, where the authors used them as a tool
for establishing a complete description of ideal and minimally nonideal circulant matrices.
More recently, Aguilera \cite{Nes} completely characterized the subsets $N$ of
$[n]$ for which $\C{n}{k}/N$ is a circulant minor. We review at next his
main result, as some terms will be needed for the separation algorithm presented
in Section~\ref{sec:separation}.

Given $C^{k}_n$, the digraph $G(C^{k}_n)$ has vertex set $[n]$ and $(i,j)$ is an arc
of $G(C^{k}_n)$ if $j\in \{i+k,i+k+1\}$. We call arcs of the form $(i,i+k)$ \emph{short} arcs
and arcs of the form $(i,i+k+1)$ \emph{long} arcs. Associated with any directed cycle $D$
in $G(C^{k}_n)$, three parameters can be defined: its number $n_2$ of short arcs, its number $n_3$
of long arcs, and the number $n_1$ of turns around the set of nodes  it makes. Hence, the
relationship $n_1 n = n_2 k + n_3(k+1)$ must hold for the integers $n, k, n_1, n_2,$ and $n_3$.
In our current notation, Theorem 3.10 of \cite{Nes} states the following.

\begin{theorem} \cite{Nes} \label{minorsgrafo}
Let $n,k$ be integers verifying $2\leq k \leq n-1$ and let $N\subset \Z_n$ such that $1\leq |N|\leq n-2$.
Then, the following are equivalent:
\begin{enumerate}
\item $C_n^k/N$ is isomorphic to $C_{n'}^{k'}$.
\item $N$ induces in $G(C^{k}_n)$ $d\geq 1$ disjoint simple dicycles $D_0,\ldots,D_{d-1}$, each of them having the same parameters $n_1$, $n_2$ and $n_3$ and such that
$|N|=d(n_2+n_3)$,
$n'=n-d(n_2+n_3)\geq 1$, and $k'=k-dn_1\geq 1$.
\end{enumerate}
\end{theorem}

The structure of $\Qi{\C{n}{k}}$ has been the subject of many previous
studies. It is known that $\Qi{\C{n}{k}}$ is a full dimensional
polyhedron. Furthermore, for every $i\in [n]$, the constraints
$x_i\geq 0$, $x_i\leq 1$ and $\sum_{j\in C^{i}} x_j \geq 1$ are facet
defining inequalities of $\Qi{\C{n}{k}}$ and we call them
\emph{boolean facets} \cite{Sa}. We will denote by $\sys_0$ the system of linear
inequalities corresponding to boolean facets.

The \emph{rank constraint} $\sum_{i=1}^n x_i\geq \ceil{\frac{n}{k}}$
is always valid for $\Qi{\C{n}{k}}$ and defines a facet if and only if $n$
is not a multiple of $k$ \cite{Sa}.
In \cite{BNTDAM13} the authors obtained another family of
facet-defining inequalities for $\Qi{\C{n}{k}}$ associated with
circulant minors.

\begin{lemma} \cite{BNTDAM13} \label{nosotras}
Let $N\subset [n]$ such that $\C{n}{k}/ N \approx \C{n'}{k'}$,
and let $W=\{i\in N : i-k-1 \in N\}$.
Then, the  inequality
\begin{equation}\label{ecu}
\sum_{i\in W} 2 x_i + \sum_{i\notin W} x_i \geq \ceil{\frac{n'}{k'}}
\end{equation}
is a valid inequality for $Q'(C^k_n)$. Moreover, if $2\leq k'\leq
n'-2$, $\left\lceil \frac{n'}{k'}\right\rceil >
\left\lceil\frac{n}{k}\right\rceil$ and $n'= 1(\mathrm{mod} \,k')$,
this inequality defines a facet of $\Qi{\C{n}{k}}$.
\end{lemma}

Observe that the set $W$ uniquely determines the set $N$, and hence
the minor $\C{n}{k}/ N$ associated with it.
The authors termed \eqref{ecu} as the \emph{minor inequality
  corresponding to} $W$. Moreover, the authors showed that
every non boolean facet-defining inequality of $\Qi{C^3_n}$ (whose
facetial structure had been previously characterized in \cite{Mah})
is either the rank constraint or a minor inequality.
Similarly, $\Qi{C_{2k}^k}$ and $\Qi{C_{3k}^k}$ are completely described by boolean facets and
minor inequalities, for any $k \geq 2$ \cite{BNTMMOR13}.

\section{Computing the first Chvátal closure}
\label{sec:clausura}

In our attempt at finding a linear description of the first
Chvátal closure of $\Q{\C{n}{k}}$, we use the following well-known
result from integer programming:
\begin{lemma}
Let $P=\setof{x \in \R^n}{Ax \geq b}$ be a nonempty polyhedron
with $A$ integral and $Ax \geq b$ totally dual integral. Then,
$P'=\setof{x \in \R^n}{Ax \geq \ceil{b}}$.
\end{lemma}

As we shall see below, if all vertices of $P$ are known then a totally
dual integral system describing the polyhedron can be computed from
this information. This is the case for $\Q{\C{n}{k}}$, whose vertices
have been completely characterized by Argiroffo and Bianchi
\cite{circu}.
\begin{lemma}[\cite{circu}]
\label{th:vertices}
Let $x^*$ be a vertex of $\Q{\C{n}{k}}$.
Then one of the following statements holds:
\begin{enumerate}
\renewcommand{\theenumi}{\roman{enumi}}
\renewcommand{\labelenumi}{(\theenumi)}
\item $x^*$ is integral.
\item $x^*= \frac{1}{k} \onevec$
\item There exists $N \subset [n]$ with $\C{n}{k}/N \cong
\C{n'}{k'}$ and $\gcd(n', k')=1$ such that
$$
x_i^*:= \left\{
\begin{array}{ll}
\frac{1}{k'}, & \mbox{if $i \not\in N$}, \\
0, & \mbox{otherwise}.
\end{array}
\right.
$$
\end{enumerate}
\end{lemma}

In order to express $\Q{\C{n}{k}}$ via a totally dual integral system
of linear inequalities, we use the method described below
(see, e.g., \cite[Ch.~8]{libro}). Given a polyhedral cone $K \subset \R^n$,
consider the points in the lattice $L:= K \cap \Z^n$. An
\emph{integral generating set} for $L$ is a set $H \subseteq L$ having
the property that every $x \in L$ can be written as a linear
combination $\sum_{i=1}^k \alpha_i h_i$ of some elements $h_1, \ldots,
h_k \in H$ with integral non negative coefficients $\alpha_1, \ldots,
\alpha_k$.

The method consists in adding redundant inequalities to the
original system $\sys_0$ until the following property is verified: If
$\setof{a_i^T x \geq b_i}{i \in I(x^*)}$ is the set of linear
inequalities satisfied with equality by a vertex $x^* \in
\Q{\C{n}{k}}$ and $K(x^*)$ is the cone generated by the set of vectors
$H(x^*):= \setof{a_i}{i \in I(x^*)}$, then $H(x^*)$ is
an integral generating set for $K(x^*) \cap \Z^n.$

This idea leads to the following procedure for computing $\Qp{\C{n}{k}}$:
\begin{enumerate}
\renewcommand{\theenumi}{\arabic{enumi}}
\renewcommand{\labelenumi}{\theenumi.}
\renewcommand{\theenumii}{\arabic{enumii}}
\renewcommand{\labelenumii}{\theenumi.\theenumii}
\item Let $\sys:= \sys_0$.
\item For every vertex $x^*$ of $\Q{\C{n}{k}}$ do
\begin{enumerate}
\item Compute an integral generating set $H(x^*)$ of
$K(x^*) \cap \Z^n$.
\item \label{proc:add-ineq}For all $a_i \in H(x^*)$, let $b_i:= a_i^T x^*$
and add the inequality $a_i^T x \geq \ceil{b_i}$ to $\sys$.
\end{enumerate}
\item Return $\sys$ as a linear description of $\Qp{\C{n}{k}}$.
\end{enumerate}

Observe that the inequality $a_i^T x \geq b_i$ at step~2.2 is valid
for $\Q{\C{n}{k}}$, since $x^*$ minimizes $a_i^T x$ over this polyhedron
for any $a_i \in K(x^*)$. Moreover, if $x^*$ is integral, then the new
inequality added to the system $\sys$ is redundant, as $b_i \in
\Z$. Therefore, new inequalities for $\Qp{\C{n}{k}}$ may only arise
from integer generating sets $H(x^*)$ related to fractional vertices belonging to
one of the two latter clases described in Lemma~\ref{th:vertices}.

Firstly, we analyze all inequalities arising from the vertex
$x^*=\frac{1}{k} \onevec$.  The point $x^*=\frac{1}{k} \onevec$ is
known to be a vertex of $\Q{\C{n}{k}}$ if and only if
$\gcd(n,k)=1$. In this case, $\setof{C^i x \geq 1}{i\in[n]}$ are the
inequalities of the original system $\sys_0$ satisfied at equality by
$x^*$. In order to find an integral generating set for $K(x^*) \cap \Z^n$ we
need the following result.

\begin{lemma}
\label{th:Cnk-sys}
Let $x \in \R^n, b \in \Z^n$ be two vectors such that $\zerovec
\leq x < \onevec$ and $\C{n}{k} x = b$, with $\gcd(n,k)=1$. Then there
exists $r \in \tabulatedset{0, 1, \ldots, k-1}$ such that $x=
\frac{r}{k} \onevec$ and $b= r \onevec$.
\end{lemma}

\begin{proof}
Observe that $x^*$ is the solution of the linear system
$$
C^i x = \sum_{j=i}^{i + k-1}x_j = b_i, \quad \forall 1 \leq i \leq n.
$$
Subtracting each equation from the previous one, and the first from
the last, we obtain $x_i - x_{i + k} = b_i - b_{i + 1}$,
for $1 \leq i \leq n$. Moreover, from $\zerovec \leq x < \onevec$ it
follows $-1 < x_i - x_{i + k} < 1$ and, since $b$ is integral, we
must have $x_i - x_{i + k} = b_i - b_{i + 1} = 0$. As a
consequence, $b = r \onevec$ for some $r \in \Z$.

On the other hand, as $\C{n}{k} \onevec = k \onevec$, we can write $b
= \C{n}{k} (\frac{r}{k} \onevec)$ and substitute this expression in
the original system. Since $\gcd(n,k)=1$, the matrix $\C{n}{k}$ is
invertible and we obtain $x= \frac{r}{k} \onevec$. Finally, from
$\zerovec \leq x < \onevec$ we have $r \in \tabulatedset{0, 1, \ldots,
  k-1}$.
\end{proof}

With this result we can compute an integral generating set for $K(x^*)$.

\begin{theorem}\label{1sobrek}
Let $\C{n}{k}$ be a circulant matrix such that $\gcd(n,k)=1$ and
consider the vertex $x^*=\frac{1}{k} \onevec$ of $\Q{\C{n}{k}}$. Then
an integral generating set for $K(x^*) \cap \Z^n$ is given by $H(x^*)=
\tabulatedset{ C^1, C^2, \ldots, C^n, \onevec}.$
\end{theorem}

\begin{proof}
Let $b \in K(x^*) \cap \Z^n$. Then there exists a non negative
vector $\hat{d} \in \R_{+}^n$ such that $b^T = \hat{d}^T \C{n}{k}$.
Moreover, as the (unordered) sets of row and column vectors
of a circulant matrix are equal, this is equivalent to saying that
there exists $d \in \R_{+}^n$ with $\C{n}{k}d = b$. Let
$x= d - \floor{d}$. We have $\zerovec \leq x < \onevec$ and
$$
\C{n}{k}(x + \floor{d}) = b \quad \Leftrightarrow \quad
\C{n}{k} x = b - \C{n}{k} \floor{d}.
$$

Since $b - \C{n}{k} \floor{d}$ is integral, applying
Lemma~\ref{th:Cnk-sys} yields $\C{n}{k} x= r \onevec$,
for some $r \in \tabulatedset{0, 1, \ldots, k-1}$. Hence,
$$
b = r \onevec + \C{n}{k} \floor{d}
$$
and thus $b$ can be written as a linear combination
of the elements of $H(x^*)$ where all coefficients are
non negative integers.
\end{proof}

When applying step~2.2. of the procedure described at the beginning of this section,
the vectors $C^i$ yield the inequalities $(C^i)^T x \geq 1$ from $\sys_0$,
while for the last vector we obtain the rank constraint of
$\Qi{\C{n}{k}}$:

\begin{corollary}
If $\gcd(n,k)=1$, then the inequality
$\onevec^T x \geq \ceil{\onevec^T x^*} = \ceil{\frac{n}{k}}$
is valid for $\Qp{\C{n}{k}}$.
\end{corollary}

On the other hand, given a vertex $x^*$ corresponding to a circulant
minor $\C{n'}{k'}$, the task of finding an integral generating set for
$K(x^*) \cap \Z^n$ turns out to be more complicated. We present here
a partial result which is however sufficient for deriving a new class
of facet-defining inequalities for $\Qi{\C{n}{k}}$.

Consider a circulant minor $\C{n'}{k'} \approx \C{n}{k}/N$ of
$\C{n}{k}$, and let $x^*$ be the corresponding vertex of
$\Q{\C{n}{k}}$, defined as in Lemma~\ref{th:vertices}(iii). From
Lemma~2.1 and Lemma~2.4 in \cite{Nes} it follows that $\C{n'}{k'}$ can be
obtained from  $\C{n}{k}$ by deleting each column $j$ with $j \in N$
and each row $i$ with $i+1 \in N$.
Hence, $\card{C^i \setminus N}= k'$ holds for $i+1 \not\in N$ and
$x^*$ satisfies the following inequalities with equality:
\begin{align}
&(C^i)^T x \geq 1, \mbox{ for all } i \mbox{ such that } i+1 \not\in N; \label{eq:cnk}\\
& (e^j)^T x \geq 0, \mbox{ for all } j \in N. \label{eq:nonneg}
\end{align}
Observe that there might be other inequalities from $\sys_0$ satisfied tightly
by $x^*$. In the following we denote by $K$ the subcone of $K(x^*)$
spanned by the normal vectors of the left-hand sides of \eqref{eq:cnk}
and \eqref{eq:nonneg}.
\begin{theorem}
\label{th:minors-gs}

Let $x^*$ be a vertex of $\Q{\C{n}{k}}$ associated with a minor $\C{n}{k}/ N \approx \C{n'}{k'}$,
and let $W=\setof{i\in N}{i-k-1 \in N}$. An integral generating set for $K \cap \Z^n$ is given by
$$
\setof{C^i}{i+1 \not\in N} \cup \setof{e^j}{j \in N} \cup
\setof{r\onevec + \sum_{j \in W} e^j}{1 \leq r \leq k'-1}.
$$
\end{theorem}

\begin{proof}
Let $A$ be the square coefficient matrix of the system
\eqref{eq:cnk}-\eqref{eq:nonneg}. Reordering the columns, we may
assume that $A$ has the following block form:
$$
A= \left(
\begin{array}{c|c|c}
B^1 & B^2 & C \\
\hline
I_1 & \OM & \OM \\
\hline
\OM & I_2 & \OM
\end{array}
\right),
$$
where the first $n_3:= \card{W}$ columns correspond to indices in
$W$, the next $n_2:= \card{N - W}$ columns correspond to indices in
$N-W$ and the last $n'$ columns correspond to indices not in $N$.
Moreover, $C:=\C{n'}{k'}$, and $I_1, I_2, \OM$ are identity
and zero matrices of the appropriate sizes.

Let $b \in K \cap \Z^n$. Then there exist $d \in \R_{+}^{n'}$,
$f \in \R_{+}^{n_3}$, and $g \in \R_{+}^{n_2}$ with $b^T=(d^T,
f^T, g^T) A$. Now consider the vectors $x:= d - \floor{d}$,
$y:= f - \floor{f}$, $z:= g - \floor{g}$, and define:
\begin{equation}
\label{eq:btilde}
\tilde{b}^T:= b^T - \left(\floor{d^T}, \floor{f^T}, \floor{g^T}\right) A.
\end{equation}
Observe that $\tilde{b} \in \Z^n$ and $\tilde{b}^T=(x^TB^1 + y^T,
x^TB^2 + z^T, x^TC)$. From Lemma~\ref{th:Cnk-sys} it follows
that $x^TC = r \onevec^T$ and
$x= \frac{r}{k'} \onevec$, for some $r \in \tabulatedset{0, \ldots,
k'-1}$. Moreover, if $r=0$ then we must have $\tilde{b}=0$
and from \eqref{eq:btilde} we conclude that $b^T$ is an
integral conic combination of the row vectors of $A$,
which finishes the proof.

Now assume $r \in \tabulatedset{1, \ldots, k'-1}$. For $\ell \in
\tabulatedset{1, 2}$, we have $x^TB^\ell = \frac{r}{k'} {\onevec}^T
B^\ell$. From the proof of Theorem~3 in \cite{BNTDAM13}, it follows
that each column of $B^1$ has support equal to $k' + 1$ and
each column of $B^2$ has support equal to $k'$. Thus,
$$
\tilde{b}^T=\left(\frac{r(k'+1)}{k'} \onevec^T + y^T, r \onevec^T + z^T, r \onevec^T\right).
$$

Finally, since $\tilde{b}^T \in \Z^n$, $\zerovec \leq y <
\onevec$, and $\zerovec \leq z < \onevec$, we must have
$y=(1-\frac{r}{k'}) \onevec$, $z= \zerovec$, and hence
$\tilde{b}^T=((r+1) \onevec^T, r \onevec^T, r \onevec^T) = r \onevec^T
+ \sum_{j \in W} (e^j)^T$. Then the statement of the theorem follows
from \eqref{eq:btilde}.
\end{proof}

Vectors in the first two sets of last theorem give rise to boolean inequalities
after applying step~2.2. of the procedure from the beginning of this section.
For the third set, we have $\ceil{r \onevec^T x^* + \sum_{j \in W} (e^j)^T x^*} =
\ceil{\frac{rn'}{k'}}$, and hence we obtain:

\begin{corollary}
Let $N\subset [n]$ be such that $\C{n}{k}/N \approx \C{n'}{k'}$ and $W=\{i\in N : i-k-1 \in N \}$.
The inequalities
\begin{equation}
\label{eq:r-minors}
\sum_{i \in W} (r+1) x_i + \sum_{i \not\in W} r x_i \geq
\ceil{\frac{rn'}{k'}},
\end{equation}
with $r \in \tabulatedset{1, \ldots, k'-1}$, are valid for $\Qp{\C{n}{k}}$.
\end{corollary}

For $r=1$, these inequalities are the minor inequalities described in
\cite{BNTDAM13}.  Accordingly, we have called \eqref{eq:r-minors} as
\emph{generalized $r$-minor inequalities}.  In some cases, generalized $r$-minor
inequalities with $r> 1$ can be obtained from the addition of (classical) minor
inequalities and the rank constraint, and are thus redundant for
$\Qp{\C{n}{k}}$.
However, this is not true in general. For instance, consider $W:=
\setof{6+5k}{0 \leq k \leq 10}$ and $N:= W \cup
\tabulatedset{1}\subset [59]$.  One can verify that $\C{59}{4}/N
\approx\C{47}{3}$ and the corresponding inequality \eqref{eq:r-minors}
for $r=2$ has the form $\sum_{i \in W} 3x_i + \sum_{i \not\in W} 2x_i
\geq 32$. Moreover, it can be shown that this inequality defines a facet of
$\Qi{\C{59}{4}}$. As a consequence we have the following result.

\begin{theorem}
There are circulant matrices $\C{n}{k}$ for which minor inequalities,
boolean facets, and the rank constraint are not enough to describe
$\Qp{\C{n}{k}}$.
\end{theorem}

\section{Separation algorithms for generalized minor inequalities}
\label{sec:separation}

A polynomial
time algorithm to separate 1-minor inequalities associated with particular classes of circulant minors
has been proposed by S. Bianchi et al.~in \cite{BNTDAM13}. In this section we extend some of their results
to the case of generalized minor inequalities. More precisely, we address the separation problem
for $r$-minor inequalities corresponding to circulant minors having parameters $d=n_1=1$.

Following the ideas presented in \cite{BNTDAM13}, let us first prove a technical lemma
that will be required for our separation procedure.

\begin{lemma}\label{alfa}
Let $d, n_1=1, n_2$, and $n_3$ be the parameters associated with a circulant minor of $C^k_n$ such that
$n_3=p\, (\mathrm{mod} \,(k-d))$
with  $1\leq p< k-d$.
Then
$$
\left\lceil \frac{rn'}{k'}\right\rceil=
\left\lceil r\ \frac{n-d(n_2+n_3)}{k-d}\right\rceil= \left[r\frac{n}{k}+\left(\left\lceil \frac{rp}{k-d}\right\rceil-\frac{rp}{k-d}\right)\right]+\frac{r}{k(k-d)}dn_3. $$
\end{lemma}

\begin{proof}
Let $s$ be the nonnegative integer such that $n_3=s(k-d)+p$.
Since $n= n_1 n =k(n_2+n_3)+n_3$ we have that
$$\left\lceil r\ \frac{n-d(n_2+n_3)}{k-d}\right\rceil= \left\lceil r\ \frac{(k-d)(n_2+n_3)+n_3}{k-d}\right\rceil= r\left(n_2+n_3\right)+\left\lceil \frac{rn_3}{k-d}\right\rceil.$$

From $s=\frac{n_3- p}{k-d}$ and $n_2+n_3=\frac{n-n_3}{k}$ it follows that
\begin{align*}
r\left(n_2+n_3\right)+\left\lceil \frac{rn_3}{k-d}\right\rceil &= r\ \frac{n-n_3}{k} + r\ \frac{n_3-p}{k-d}+\left\lceil \frac{rp}{k-d}\right\rceil\\
& =\left[r\frac{n}{k}+\left(\left\lceil \frac{rp}{k-d}\right\rceil-\frac{rp}{k-d}\right)\right]+\frac{r}{k(k-d)}dn_3
\end{align*}
and the proof is complete.
\end{proof}

Observe that if $n_3$ is a multiple of $k-d$, then the corresponding $r$-minor inequality
is redundant for $\Q{\C{n}{k}}$, as the value $\frac{rn'}{k'}$ on the right-hand side is integer.
Otherwise, if $W\subset [n]$ defines a minor of $C_n^k$ with parameters $d, n_1=1, n_2$, and $n_3$, where $n_3=p\, (\mathrm{mod} \,(k-d))$
and  $1\leq p< k-d$, the previous lemma implies that
the corresponding $r$-minor inequality can be written as
$$\sum_{i\in W} x_i+r\sum_{i=1}^n x_i  \geq  \alpha(d,p) +\beta(d) \left|W\right|$$
where
$$\alpha(d,p)= r\frac{n}{k}+\left(\left\lceil \frac{rp}{k-d}\right\rceil-\frac{rp}{k-d}\right),\quad \beta(d)=\frac{r}{k(k-d)},$$
or, equivalently,
\begin{equation}\label{faceta}
\sum_{i\in W} (x_i - \beta(d))  \geq   \alpha(d,p)- r\sum_{i=1}^n x_i.
\end{equation}

Given $C^k_n$ and two integer numbers $d,p$ with $1\leq d\leq k-2$ and $1\leq p <k-d$,
we define the function $c^d$ on $\R$ by $c^d(t):= t - \beta(d)$ and the function $L^{d,p}$ on $\R^n$ by $L^{d,p}(x):= \alpha(d,p)- r\sum_{i=1}^n x_i$.

Then, inequality (\ref{faceta}) can be written as

\begin{equation}\label{faceta2}
\sum_{i\in W} c^d (x_i) \geq   L^{d,p} (x).
\end{equation}

Following the same notation introduced in \cite{BNTDAM13}, let $\mathcal{W}(d,p)$ be the family of sets $W\subset [n]$ defining minors with parameters $d, n_1=1, n_2, n_3=p\, (\mathrm{mod} \, (k-d))$.
We are interested in the separation of generalized $r$-minor inequalities corresponding to
sets $W \in \mathcal{W}(1,p)$.

To this end, given $n,k$
let $K_n^k(p)=\left(V, A\right)$ be the digraph with set of nodes
$$V=\bigcup\limits_{j\in [k-1]}V^j \cup \{t\}$$
where $V^j=\{v^j_i :i\in [n]\}$
and set of arcs defined as follows: first consider in $A$ the arcs
\begin{itemize}
	\item $(v_1^1,v_l^{2})$ for all $l$ such that $k+2\leq l\leq n$ and $l=2$ (mod $k$),
\end{itemize}
then consider in a recursive way for $j\in[k-1]$:
\begin{itemize}
	\item for each $(v,v_i^{j})\in A$, add $(v_i^j,v_l^{j+1})$ whenever $l$ is such that $i+k+1\leq l\leq n$ and $l-i=1$ (mod $k$),
\end{itemize}
and finally,
\begin{itemize}
  \item for each $(v,v_i^{p})\in A$, add $(v_i^p,t)$ whenever $i$ is such that $i\leq n-k$ and $n-i=0$ (mod $k$).
\end{itemize}

Note that, by construction, $K_n^k(p)$ is acyclic. In Figure \ref{fig:caminosep} we sketch the digraph $K_{59}^4(2)$ where only the arcs corresponding to a particular $v_1^1t$-path are drawn.

\begin{figure}[h]
	\centering
		\includegraphics[width=.32\textwidth]{caminosep2.eps}
	\caption{A $v_1^1t$-path in the digraph $K_{59}^4(2)$.}
	\label{fig:caminosep}
\end{figure}

For the proof of the next lemma, we need the following observation.
\begin{remark}\label{condW}
Let $W=\{w_i: i\in [n_3]\}$ with
$1\leq w_1< \dots< w_{n_3}\leq n$, then $W$ defines a circulant minor with parameters $d=n_1=1$ if and only if $w_{i+1}-w_{i}=1$ (mod $k$) and $w_{i+1}-w_{i}\geq k+1$, for all $i\in [n_3]$.
\end{remark}

Now we can state our result.

\begin{lemma}
There is a one-to-one correspondence between $v_1^1 t$-paths in $K_n^k(p)$ and subsets $W\in \mathcal{W}(1,p)$ with $1\in W$.
\end{lemma}

\begin{proof}

Let $W\in \mathcal{W}(1,p)$ and assume that $W=\{i_j: j\in [n_3]\}\subset [n]$ with $1=i_1<i_2<\ldots<i_{n_3}\leq n$.

Then, by Remark \ref{condW}, $i_{j+1}- i_j= 1$ (mod $k$) and $i_{j+1}- i_j\geq k+1$ for all $j\in [n_3]$.
Thus, the set of nodes $P \cup \left\{t\right\}$ with
$$P:=\left\{v_{i_j}^\ell\,:\, i_j\in W ,\,\, \ell=j\, (\mathrm{mod} \, (k-1)) \right\}$$
induces a $v_1^1 t$-path in $K_n^k(p)$.

Conversely, let $P$ be a $v_1^1 t$-path in $K_n^k(p)$. By construction, there exists a
nonnegative integer $s$ such that
$|V(P)\cap V^j|= s+1$ for all $j\in \{1, \ldots, p\}$ and $|V(P)\cap V^j|= s$ for $j \in \{p+1, \ldots, k-1\}$.
Then, $|V(P)-\{t\}|=s(k-1)+p$.

Now, if we define
$$W= \setof{i \in [n]}{v_i^j \in V(P) \mbox{ for some } j \in [k-1]}$$
we have $|W|=s(k-1)+p$ and from Remark \ref{condW} it follows that $W\in \mathcal{W}(1,p)$.
\end{proof}

\begin{theorem}\label{sep}
Given $C^k_n$ and $r \in \{ 1, \ldots, k-1\}$, the separation problem for $r$-minor inequalities corresponding to minors with parameters $d=n_1=1, n2,$ and $n_3=p\, (\mathrm{mod} \,(k-1))$ can be polynomially reduced to at most $n$ shortest path problems in an acyclic digraph.
\end{theorem}

\begin{proof} Let $\hat{x} \in \mathbb{R}^n$. We will show that the problem of deciding if, given $j\in [n]$, there exists $W\in \mathcal{W}(1,p)$ with $j\in W$ and such that $\hat{x}$ violates the inequality (\ref{faceta2}) can be reduced to a shortest path problem. W.l.o.g we set $j=1$.

Consider the digraph $K_n^k(p)$ and associate the cost $c^1(\hat{x_i})$ with every arc $(v_l^j, v_i^{j+1})\in A$, and the cost $c^1(\hat{x_1})$ with every arc $(v_l^p, t)\in A$.

Clearly, if $W$ is the subset of $[n]$ corresponding to a $v_1^1 t$-path $P$ in $K_n^k(p)$, the length of $P$ is equal to $\sum_{i\in W} c^1(\hat{x_i})$.

Then, there exists $W\in \mathcal{W}(1,p)$ with $1\in W$ and such that $\hat{x}$ violates the inequality \eqref{faceta2}, if and only if the length of the shortest $v_1^1 t$-path in $K_n^k(p)$ is less than
$L^{1,p} (\hat{x})$.
\end{proof}

Since $K_n^k(p)$ is acyclic, computing each shortest path from the last theorem can be accomplished in $O(\card{A})$ time (see, e.g., \cite[Theorem 2.18]{CookEtAl98}). Moreover, from the definition
of $K_n^k(p)$ it follows that each node has outdegree
of order $O(\frac{n}{k})$ and that the graph contains $O(nk)$ nodes. Hence, each shortest
path computation requires $O(n^2)$ time, and the separation problem of $r$-minor inequalities can be solved in $O(n^3)$ time for fixed $p,r \in \{1, \ldots, k-1 \}$.
Repeating this procedure for each possible value of $p$ and $r$, we obtain the following result.

\begin{theorem}\label{sep2}
For a fixed $k$, the separation problem for $r$-minor inequalities corresponding to minors of $C_n^k$ with parameters $d=n_1=1$ can be solved in polynomial time.
\end{theorem}

\section{Conclusions}
\label{sec:conclusions}

We have presented a new class of valid inequalities for $\Qi{\C{n}{k}}$
whose Chvátal rank is at most one. These inequalities strictly generalize the class
of minor inequalities described in \cite{BNTDAM13}. Moreover, some
of these inequalities give rise to new facets of $\Qi{\C{n}{k}}$, as shown by
the example at the end of Section~\ref{sec:clausura}. Hence,
despite of the results obtained for $\Qi{C^3_n}$ in \cite{Mah} and $\Qi{C_{2k}^k}, \Qi{C_{3k}^k}$
in \cite{BNTMMOR13}, (classic) minor inequalities, together with boolean
facets and the rank constraint are not sufficient to provide a complete linear
description of $\Qi{\C{n}{k}}$ in general.

An apparently weaker problem consists in finding a complete linear description for the
first Chvátal closure of $\Q{\C{n}{k}}$.  However, as far as we are aware from
literature, no circulant matrix $\C{n}{k}$ is known for which the Chvátal rank of
$\Q{\C{n}{k}}$ is strictly larger than one. To complete the characterization
of $\Qp{\C{n}{k}}$ following the path presented here, more work is still
needed in order to fully characterize integral generating sets for the cones
$K(x^*)$ associated with the fractional vertices defined in Lemma~\ref{th:vertices}(iii).
All computational experiments we have conducted so far support the conjecture
that generalized minor inequalities, together with boolean facets and the rank constraint
are sufficient for describing $\Qp{\C{n}{k}}$.

Besides of the search for complete linear descriptions of $\Qp{\C{n}{k}}$ and $\Qi{\C{n}{k}}$,
one line of future research could be the study of necessary and sufficient conditions for a
generalized minor
inequality to define a facet of the integer polytope, similar to the conditions presented in \cite{BNTDAM13}
for classic minor inequalities. Moreover, the separation problem for generalized minor
inequalities corresponding to minors with parameters $d>1$ or $n_1>1$ is an issue
that requires further investigation.

Another possible line of research involves establishing analogies between set
packing and set covering polyhedra. As mentioned in the introduction, a
complete linear description for set packing polytope $\Pint{\C{n}{k}}$ related
to circulant matrices (in fact, to the more general class of \emph{circular} matrices) has
been reported in \cite{EisenbrandEtAl05}. The authors show that
this polytope is described by nonnegativity constraints, clique inequalities
and so-termed \emph{clique family} inequalities. The first two families
can be regarded as counterparts of boolean facets for the set covering
polyhedron. Determining whether there is also an analogous class to clique family inequalities
in the case of $\Qi{\C{n}{k}}$,
and how this class is related to the class of generalized minor inequalities
could shed more light
on the structure of this polyhedron. For instance, similarly to generalized minor inequalities, clique family inequalities have only two different coefficients, which are consecutive integers.
First steps in this direction have been undertaken in \cite{rowfamily,genrowfamily}.

config: arxiv


TITLE: Proof for a rank-one Decomposition theorem
QUESTION [6 upvotes]: Consider the following result which I recently came across in a research paper in my area (Signal Processing)

Let $X$ be a $N\times N$ positive semidefinite (psd) matrix whose rank
  is $r$. Let $A$ be any symmetric $N\times N$ matrix. Then, there exist
  a set of vectors $x_1,\dots,x_r$ such that \begin{align} X & =
 \sum_{i=1}^{r}x_ix_i^T \\ x_i^TAx_i &=
 \frac{\mbox{trace}\{AX\}}{r},~~~\forall i \end{align}

The following is the proof for it which I can't verify.
Proof:
Consider the following step-wise procedure whose inputs are $X$ and $A$.
$~~$0.$~~$ Inputs are $X$ (given $X\geq 0$, $rank(X)=r$) and $A$ (symmetric).

Decompose $X=RR^T$.
Generate the eigen decomposition $R^TAR=U\Lambda U^T$.
Let $h$ be any $N\times 1$ vector such that $\lvert h_i\rvert=1$ (each entry of $h$). Generate the vector $x_1$ and matrix $X_1$ as
\begin{align}
x_1&=\frac{1}{\sqrt{r}}RUh \\
X_1&=X-x_1x_1^T
\end{align}
Outputs are $X_1$ and $x_1$.

The paper then claims that

$X_1$ is psd and has rank $r-1$
$x_1^TAx_1=\frac{1}{r}trace(AX)$

While I am able to verify the second claim, am not able to verify the first one? How is it true? If this can be done, the rest of the proof is straight forward. I am looking for a rigorous proof.
Read this if you are interested to know where this proof heads. Now do the stepwise algorithm earlier with inputs $X_1$ and $A$ to get $x_2$ and $X_2$ such that \begin{align}X_2&=X_1-x_2x_2^T\\&=X-x_1x_1^T-x_2x_2^T\end{align} and $$x_2^TAx_2=\frac{1}{r-1}trace(AX_1)=\frac{1}{r}trace(AX)$$ Then the result of the paper is that you can do this procedure $r$ times and get a rank-one decomposition $$X=\sum_{i=1}^{r}x_ix_i^T$$ with the property $$x_i^TAx_i\,=\,\frac{1}{r}trace(AX),~\forall i$$for any given psd X with rank $r$ and any symmetrix $A$.

REPLY [3 votes]: From the famous inequality ${\sf rank}(f+g)\leq {\sf rank}(f)+{\sf rank}(g)$
and from ${\sf rank}(x_1x_1^T)=1$, we deduce
${\sf rank}(X-x_1x_1^T) \geq {\sf rank}(X)-1$. On the other hand,
${\sf rank}(X-x_1x_1^T)$ can be equal to ${\sf rank}(X)$ under the conditions
you gave (you probably forgot some additional constraints). Consider
the following example :
$$
X=\left(\begin{array}{ccc} 10 & 6 & 0 \\ 6 & 5 & 0  \\ 0 & 0 & 0 \end{array}\right),
A=\left(\begin{array}{ccc} 0 & 0 & 3 \\ 0 & 0 & -2  \\ 3 & -2 & 0 \end{array}\right) \tag{1}
$$
In step $1$, I can write $X=RR^T$ where
$$
R=\left(\begin{array}{ccc} 1 & 0 & 3 \\ 0 & 1 & 2  \\ 0 & 0 & 0 \end{array}\right) \tag{2}
$$
It happens then that $RAR^T={\sf diag}(18,-8,0)$ and $R^TAR=0$ are already diagonal, so that in step 2 we may take $U=I_3$. In step 3, if we take all the entries of $h$ equal to $1$,
$$
x_1=\frac{1}{\sqrt{2}}\left(\begin{array}{c} 4 \\ 3  \\ 0 \end{array}\right),
x_1x_1^{T}=\left(\begin{array}{ccc} 8 & 6 & 0 \\ 6 & \frac{9}{2} & 0  \\ 0 & 0 & 0 \end{array}\right),
X-x_1x_1^{T}=\left(\begin{array}{ccc} 2 & 0 & 0 \\ 0 & \frac{1}{2} & 0  \\ 0 & 0 & 0 \end{array}\right) \tag{3}
$$
so that ${\sf rank}(X-x_1x_1^T)=2={\sf rank}(X)$.


TITLE: construction set of natural number logic
QUESTION [3 upvotes]: I identify the natural number $0$ with the empty set $\emptyset$, $1$ with $S(0)$, $2$ with $S(1)$, etc, etc.
The axiom of infinity says $\exists x (\emptyset\in x\wedge \forall z\in x\space  z\cup\{z\}\in x)$ and the Axiom schema of specification says $\forall y_0,...,y_n\exists x\forall z (z\in x\leftrightarrow (z\in y_0\wedge \phi(z,y_1,...,y_n)))$.
My question now: Why is there now a smallest element $x$ which can be identified with the natural numbers?

REPLY [5 votes]: Let $y$ be an inductive set whose existence follows from the axiom of infinity, then consider $\{x\subseteq y\mid x\text{ is inductive}\}$. This is a definable collection of members of the power set of $y$, so it is a set, and $y$ is there so it's not an empty set.
Now take the intersection of all those sets. This is an inductive set as well (you have to prove this, of course). Call this inductive set $N$. Now prove that if $x$ is any inductive set then $N\subseteq x$, by considering $M=N\cap x$. Show that $M$ is inductive as well, and $M\subseteq y$, now use the property which defined $N$ to conclude $N=M$ and therefore $N\subseteq x$.
And now we're done.


TITLE: On isomorphic measurable spaces
QUESTION [7 upvotes]: Let $(X, \mathcal{A})$ and $(Y, \mathcal{B})$ be measurable spaces. Suppose furthermore that $X$ is a topological space, with topology $\tau$, and that $\mathcal{A}$ is the $\sigma$-algebra generated by $\tau$.
Now suppose that $(X, \mathcal{A})$ and $(Y, \mathcal{B})$ are isomorphic, i.e. there exists a bijection $f: X \rightarrow Y$ such that both $f$ and $f^{-1}$ are measurable. We can define a topology $\tau'$ on $Y$ by
$$\tau' := \{ f(V): V \in \tau \}.$$
My question is the following : is $\mathcal{B}$ necessarily generated by the topology $\tau'$?
It is easy to see that $\mathcal{B}$ contains the Borel $\sigma$-algebra generated by $\tau'$, but can it be strictly larger?
Thank you,
Malik

REPLY [6 votes]: No, it can't be larger. The family $\mathcal{A}'=\{f^{-1}(B):B\in\sigma(\tau')\}$ is a $\sigma$-algebra on $X$ that contains $\tau$ and hence also $\sigma(\tau)=\mathcal{A}$. Hence $\{f(A):A\in\mathcal{A}'\}\supseteq\mathcal{B}$. But by construction, $\{f(A):A\in\mathcal{A}'\}=\sigma(\tau')$ and therefore $\mathcal{B}\subseteq\sigma(\tau')$.


TITLE: Hilbert polynomial of the graph and boundedness of Hom scheme?
QUESTION [3 upvotes]: Let $X,Y$ be two projective variety over an algebraically closed field, then we know $Hom(X,Y)$ has a scheme structure by considering the embedding as a open subscheme of $Hilb(X\times Y)$ using the graph.
We know for each fixed polynomial $P$, the Hilbert scheme with Hilbert polynomial $P$ is projective hence finite type. And it seems that the graph of any $f:X\longrightarrow Y$ is isomorphic to $X$ hence has the same Hilbert polynomial viewed as a closed subscheme of $X \times Y$. However, Hom scheme can have infinitely many component (for example consider $End(E)$ where $E$ is an elliptic curve). So where does my intuition goes wrong? If $X,Y$ are both smooth curves, can we decide all of the connected components?

REPLY [3 votes]: To define a Hilbert polynomial you need to choose an ample line bundle. A reasonable choice on $X \times Y$ is $L_X \boxtimes L_Y$, where $L_X$ and $L_Y$ are line bundles on $X$ and $Y$. Then if $f \colon X \to Y$ is a morphism, the restriction of $L_X \boxtimes L_Y$ to the graph $\Gamma(f)$ of $f$ corresponds to the line bundle $L_X \otimes f^*L_Y$ on $X$, hence the Hilbert polynomial of $\Gamma(f)$ equals the Hilbert polynomial of $X$ with respect to $L_X \otimes f^*L_Y$. In particular, it does depend on $f$.


TITLE: Finding the union and intersection set with fractions
QUESTION [0 upvotes]: How can I find the intersection and union of this family of set.
For each natural number $n\ge3$ let $A_n=[\frac{1}{n},2+\frac{1}{n}]$ and the family $L=\{A_n:n\ge3\}$
$A_3=[1/3,7/3]$
$A_4=[1/4,9/4]$
$A_5=[1/5,11/5]$
It seem with this set the largest value it will reach is $\frac{7}{3}$ and the smallest will eventually be zero.
so my union over the family L would be $(0,\frac{7}{3})$
But the intersection I cannot seem to figure out.

REPLY [2 votes]: You're right about the union: for any $x > 0$ there is some $n$ such that ${1 \over n} < x$, and this ensures that $x \in A_n \subset \cup_k A_k$. The set is "decreasing on the right" as you note, so indeed $\cup_k A_k = (0, {7 \over 3}]$. Note that no $x \le 0$ is in the union, as all $A_k \subset (0, \infty)$.
But a similar argument can be held for the intersection: the largest element on the left we reach is ${1 \over 3}$, in $A_3$, and points less than it cannot be in the intersection, because they're not even in $A_3$. But every point between $\frac{1}{3}$ and $2$ (endpoints included) is in all $A_n$, as for such $x$ $\frac{1}{n} \le \frac{1}{3} \le x \le 2 < \frac{1}{n} + 2$, so $x \in A_n$. But if $x > 2$, again for some large enough $x$, $2 + \frac{1}{n} < x$ and for such $n$, $x \notin A_n$, so not in $\cap_k A_k$ as well.
So $\cap_k A_k = [\frac{1}{3}, 2]$.


TITLE: Removing $1^{\infty}$ indeterminacy
QUESTION [0 upvotes]: There is a way to remove $1^{\infty}$ indeterminate form by considering it as function as $(f(x)/g(x))^{h(x)}$ and then converting it to form $e^{((f(x)/g(x))-1)\cdot h(x)}$.
Can you derive it?

REPLY [3 votes]: Basically, you can rewrite it as:
$$\lim f(x)^{h(x)}=e^{\lim \ln (f(x)) h(x)}$$
Now you just resolve the upper limit whatever way you want. It entirely depends on each case. You may have noticed that it's not necessary to split $f(x)$ into a fraction, but it may be useful. As $\lim f(x)=1$, it could indeed be helpful to use $\ln (f(x))\approx f(x)-1$, which is the expression you got.