\documentclass[11pt,a4paper,bezier]{article}
\textheight = 24truecm
\textwidth = 16truecm
\hoffset = -1.6truecm
\voffset = -2truecm
\usepackage{amsmath,amssymb,amsfonts}
\parskip = 2.5 mm
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newtheorem{prethm}{{\bf Theorem}}
\renewcommand{\theprethm}{{\arabic{prethm}}}
\newenvironment{thm}{\begin{prethm}{\hspace{-0.5
em}{\bf.}}}{\end{prethm}}
%
\newtheorem{prepro}{{\bf Theorem}}
\renewcommand{\theprepro}{{\Alph{prepro}}}
\newenvironment{pro}{\begin{prepro}{\hspace{-0.5
em}{\bf.}}}{\end{prepro}}
%
\newtheorem{precor}{{\bf Corollary}}
\renewcommand{\theprecor}{{\arabic{precor}}}
\newenvironment{cor}{\begin{precor}{\hspace{-0.5
em}{\bf.}}}{\end{precor}}
%
\newtheorem{preconj}{{\bf Conjecture}}
\renewcommand{\thepreconj}{{\arabic{preconj}}}
\newenvironment{conj}{\begin{preconj}{\hspace{-0.5
em}{\bf.}}}{\end{preconj}}
%
\newtheorem{preremark}{{\bf Remark}}
\renewcommand{\thepreremark}{{\arabic{preremark}}}
\newenvironment{remark}{\begin{preremark}\em{\hspace{-0.5
em}{\bf.}}}{\end{preremark}}
%
\newtheorem{prelem}{{\bf Lemma}}
\renewcommand{\theprelem}{{\arabic{prelem}}}
\newenvironment{lem}{\begin{prelem}{\hspace{-0.5
em}{\bf.}}}{\end{prelem}}
%
\newtheorem{preproof}{{\bf Proof.}}
\renewcommand{\thepreproof}{}
\newenvironment{proof}[1]{\begin{preproof}{\rm
#1}\hfill{$\Box$}}{\end{preproof}}
\newenvironment{prooff}[1]{\begin{preproof}{\rm
#1}}{\end{preproof}}
\newcommand{\Deg}{\mbox{deg}\,}
%\newcommand{\span}{\rm span}
\usepackage{graphicx}
\begin{document}
\thispagestyle{empty}
\begin{center}
\null\vspace{-1cm}
{\footnotesize Available at:
{\tt http://publications.ictp.it}}\hfill IC/2010/060\\
\vspace{1cm}
United Nations Educational, Scientific and Cultural Organization\\
and\\
International Atomic Energy Agency\\
\medskip
THE ABDUS SALAM INTERNATIONAL CENTRE FOR THEORETICAL PHYSICS\\
\vspace{2.5cm}
{\bf ZERO-SUM FLOWS IN DESIGNS}\\
\vspace{2cm}
S. Akbari\\
{\it Department of Mathematical Sciences, Sharif University of
Technology, Tehran, Iran,\\
School of Mathematics, Institute
for Research in Fundamental Sciences, IPM, Tehran, Iran\\
and\\
The Abdus Salam International Centre for Theoretical Physics,
Trieste, Italy,}\\[1.5em]
G.B. Khosrovshahi\footnote{Corresponding author: rezagbk@ipm.ir}\\
{\it School of Mathematics, Institute
for Research in Fundamental Sciences, IPM, Tehran, Iran,\\
Department of Mathematics, University of Tehran, Tehran, Iran\\
and\\
The Abdus Salam International Centre for Theoretical Physics,
Trieste, Italy}\\[1em]
and\\[1em]
A. Mofidi\\
{\it School of Mathematics, Institute
for Research in Fundamental Sciences, IPM, Tehran, Iran\\
and\\
Department of Mathematics, Faculty of Mathematical Sciences,
Tarbiat Modares University, Tehran, Iran.}\\
\vfill
MIRAMARE -- TRIESTE\\
\medskip
July 2010\\
\end{center}
\vfill
%\noindent {Keywords: Nowhere-zero flow, zero-sum flow, incidence matrix, $t$-designs. }\\
%\noindent {AMS 2010 Subject Classification: 05B05, 05B20, 05C21, 05C22}.
\newpage
\setcounter{page}{1}
\centerline{\bf Abstract}
\baselineskip=18pt
\bigskip
Let $D$ be a $t$-$(v, k, \lambda)$ design and let $N_i(D)$, for $1 \leq i
\leq t$, be the higher incidence matrix of $D$, a $(0,1)$-matrix of size $\binom{v}{i}\times b$, where $b$ is the number of blocks of $D$. A {\it zero-sum flow}
of $D$ is a nowhere-zero real vector in the null space of $N_1(D)$. A {\it zero-sum k-flow} of $D$ is a zero-sum flow with values in $\{\pm 1, \ldots ,\pm (k-1)\}$. In this paper we show that every non-symmetric design admits an integral zero-sum flow, and consequently we conjecture that every non-symmetric design admits a zero-sum 5-flow. Similarly, the definition of zero-sum flow can be extended to $N_i(D)$, $1 \leq i
\leq t$. Let $D=t$-$(v,k,\binom{v-t}{k-t})$ be the complete design. We conjecture that $N_t(D)$ admits a zero-sum 3-flow and prove this conjecture for $t=2$.
\newpage
\section{Introduction}
Let $G$ be a directed graph. A {\it $k$-flow} of $G$ is an assignment of integers with maximum absolute value
$k - 1$ to each edge of $G$ such that for any vertex of $G$, the sum of the labels on incoming edges is equal
to that of the labels on outgoing edges. A {\it nowhere-zero $k$-flow} is a $k$-flow with no zeros.
A celebrated conjecture of Tutte is:
Conjecture(Tutte's $5$-flow Conjecture \cite{tute}). Every bridgeless graph has a nowhere-zero $5$-flow.
Clearly, in the language of linear algebra a nowhere-zero flow for a directed graph $G$ is a vector of the null space of the incidence matrix
of $G$ with no zero entry. Motivated with this concept in \cite{akb, akb2}, we defined the zero-sum flow for the simple graphs. For an undirected graph $G$, a {\it zero-sum flow} is a nowhere-zero
element in the null space of the incidence matrix of $G$. In this paper we would like to extend this concept to hypergraphs and in particular to $t$-designs.
A \emph{hypergraph} $H$ is a pair $H=(X, \mathcal{E})$, where $X$ is a set of elements called {\it vertices} and $\mathcal{E}$ is a set of nonempty subsets of $X$ called {\it hyperedges}.
Let $X=\{x_1,\ldots,x_n\}$ and $\mathcal{E}=\{\mathcal{E}_1,\ldots,\mathcal{E}_m\}$. Then, the incidence matrix of the hypergraph $H=(X,\mathcal{E})$ is an $n \times m$ $(0,1)$-matrix $N=[n_{ij}]$, where $n_{ij}$ is 1 if $x_i \in \mathcal{E}_j$ and 0 otherwise.
A \emph{zero-sum flow} for a hypergraph $H$ is a nowhere-zero real vector in the null space of the incidence matrix of $H$. An {\it integral zero-sum flow} is a flow with integer entries.
A \emph{$t$-$(v, k, \lambda)$ design} $D$ (briefly, $t$-design), is a pair $(X, \mathcal{B})$, where $X$ is a $v$-set of points
and $\mathcal{B}$ is a collection of $k$-subsets of $X$ (blocks) with the property that every $t$-subset
of $X$ is contained in exactly $\lambda$ blocks. Traditionally, in the case of 2-designs, the number of blocks and the frequency of occurrences of points in blocks are denoted by $b$ and $r$, respectively. A 2-design is called \emph{symmetric} if $b=v$. A 2-design is called \emph{resolvable} if there exists a partition of the set of blocks into parallel classes, each of which in turn partitions $X$. A 2-$(v,3,1)$ design is called a \emph{Steiner Triple System} of order $v$, $\emph{\emph{STS}}(v)$.
A $t$-$(v, k, \lambda)$ design is called \emph{complete} if it contains all the $k$-subsets of $X$.
Let $D$ be a $t$-$(v,k,\lambda)$ design with blocks $\mathcal{B}$ and let $I$ and $J$ be an $i$-subset and a $j$-subset of $\{1, \ldots , v\}$, respectively ($i,j\lambda$, we have
$$(r-\lambda)^{k-1}((r-\lambda)+(\lambda-1)k)(r-\lambda)^{v-k-1} > 0.$$
Now, we claim that $(r-\lambda)+\lambda(1+ak)(v-k) \neq 0$. To justify the claim, replace $a$ with $\frac{-\lambda}{(r-1)+(k-1)(\lambda-1)}$ and obtain the following expression:}
\emph{$$\textbf{h}:=(v-k)[\lambda(r-1)+(\lambda^2-\lambda)(k-1)-\lambda^2k]+r(r-1)$$
$$+r(\lambda-1)(k-1)-\lambda(r-1)-\lambda(\lambda-1)(k-1)$$
$$=((v-1)\lambda +r)(r-k-\lambda)+\lambda k^2.$$
}
\noindent \emph{It suffices to show that $\bf{h}$ is positive. To show this, we replace $\lambda(v-1)$ by $r(k-1)$ and we obtain
$$\textbf{h}=k(r-k)(r-\lambda).$$}
\emph{\noindent Since $r>k$ (by Fisher's inequality, \cite[p.222]{wil}), we have $\textbf{h}>0$. Therefore,
$$\emph{\emph{rank}}(L)=\emph{\emph{rank}}(M)=\emph{\emph{rank}}(N)=v.$$
This implies that every column of $N$ is a linear combination of the remaining columns of $N$. Hence for every $i$, $1 \leq i \leq b$, there is a vector in the $\emph{\emph{null}}(N)$ whose ith component is nonzero. Now assume that
}
\emph{$$\emph{\emph{U}}_i=\{\, x\in \emph{\emph{null}}(N) \,| \,x_i=0\, \} \ \ \ \ 1 \leq i \leq b.$$}
\emph{\noindent If $\emph{\emph{null}}(N) \subseteq \bigcup_{i=1}^b \emph{\emph{U}}_i$, then by \cite[p.283]{hal}, $\emph{\emph{null}}(N) \subseteq \emph{\emph{U}}_j$, for some $j, 1 \leq j \leq b$ which is a contradiction. Consequently, there exists an element $\alpha \in \emph{\emph{null}}(N) \backslash \bigcup_{i=1}^b \emph{\emph{U}}_i$ and by Lemma \ref{integer} we are done.}
$\hfill \square$
\end{preproof}
Now, we are in a position to state a conjecture similar to Tutte's 5-flow Conjecture (1954,~\cite{tute}) for $2$-designs.
\begin{conj}
The incidence matrix of every non-symmetric design admits a zero-sum $5$-flow.
\end{conj}
\begin{remark} The incidence matrix of every resolvable $2$-design admits a zero-sum $3$-flow. Moreover, if a complete design $D$ has a large set, then $N_i(D)$, $1 \leq i \leq t$, admits a zero-sum $3$-flow. A computer search shows that the incidence matrix of every STS$(v)$, $77$, admits a zero-sum $3$-flow.
\end{conj}
\section{Zero-sum flows for $W_{t,k}(v)$}
First we recall that for a \emph{$t$-$(v, k, \lambda)$} design $D$, by a zero-sum flow of $N_i(D)$ ($ 1 \leq i \leq t$), we mean an element of the $\emph{\emph{null}}(N_i(D))$. Also recall that if $D$ is a complete design with $v$ points and block size $k$, $N_t(D)$ is denoted by $W_{t,k}(v)$. In this section we focus our attention to zero-sum flows for $W_{t,k}(v)$.
A celebrated theorem due to Baranyai \cite{Baranyai} states that if $k|v$, then the complete design $1$-$(v,k, \binom{v-1}{k-1})$ is resolvable. Along this line the following result due to Hartman \cite{Hartman} is of great interest.
\begin{prelem}\label{hart} If $N$ is a natural number and $N$ divides both $\binom{v}{k}$ and $\binom{v-1}{k-1}$, then
${\rm LS}[N](1, k, v)$ exists.
\end{prelem}
We note that in this lemma by letting $N= \binom{v-1}{k-1}$, Baranyai's Result follows.
Now, we propose the following conjecture.
\begin{preconj} $\label{3flowW}$
The matrix $W_{t,k}(v), v\neq t+k$, admits a zero-sum $3$-flow.
\end{preconj}
\begin{remark} A celebrated conjecture due to A. Hartman (Halving Conjecture) states that:\begin{center}
$LS[2](t, k, v)$ exists if and only if $2\,|\, \binom{v-i}{k-i}$, for every $i$, $0\leq i\leq t$.
\end{center}
In the language of zero-sum flow the Hartman's
Conjecture is equivalent to the existence of zero-sum $2$-flow for the matrix $W_{t,k}(v)$.
\end{remark}
\begin{thm} $\label{conjreduce}$
Let $t$ be a positive integer. If the Conjecture \emph{\ref{3flowW}} is true for $k=t+1$, then it is true for every $v, k, t$, with $v\geq k+t+1$ and $k\geq t+1$.
\end{thm}
\begin{preproof}
\emph{For $t=1$ we have $k\geq 2$, and so $\binom{v}{k}\not | v$. Therefore, the equality $v\binom{v-1}{k-1}=k\binom{v}{k}$ implies that $\binom{v}{k}$ and $\binom{v-1}{k-1}$ are not coprime.
Now, by Lemma \ref{hart} we find
a zero-sum $3$-flow. Indeed if the number of partitions is even, then it has a zero-sum $2$-flow and otherwise, a zero-sum $3$-flow.
By assumption we may assume that $t\geq 2$ and $k > t+1$. We prove the theorem by induction on $v$.
If $v=k+t+1$, then by Corollary \ref{cor}, we have $$\emph{\emph{null}}(W_{t,k}(k+t+1))=\emph{\emph{null}}(W_{t,t+1}(k+t+1)),$$
and by assumption $W_{t,k}(k+t+1)$ admits a zero-sum $3$-flow. Thus suppose that $v\geq k+t+2$.
We have $k-1\geq t+1$ and $v-1\geq (k-1)+t+1$. So by induction hypothesis $W_{t,k-1}(v-1)$ admits a zero-sum $3$-flow, say $u$.
By Lemma $\ref{nullij}$, $u \in \emph{\emph{null}}(W_{t-1,k-1}(v-1))$. On the other hand $v-1\geq k+t+1$. Hence by induction hypothesis, there exists a zero-sum flow, say $y$, for $W_{t,k}(v-1)$. By a suitable ordering of the rows and the columns we obtain the following form of $W_{t,k}(v)$ as follows:}
{
\begin{center}
$W_{t,k}(v)=\left
[\begin{array}{ccccccccccc}
W_{t-1,k-1}(v-1) & & & 0\\
W_{t,k-1}(v-1) & & & W_{t,k}(v-1) \\
\end{array}\right ]. $
\end{center}
{\rm Clearly, the vector
$ \left[
\begin{array}{c}
u \\
y \\
\end{array}
\right]$
is a zero-sum 3-flow for $W_{t,k}(v)$ and the proof is complete.}$\hfill \square$}
\end{preproof}
\begin{precor}
Conjecture $\ref{3flowW}$, is true for $t=2$.
\end{precor}
\begin{preproof}
\emph{By Lemma \ref{conjreduce}, it is sufficient to prove that for every $v$, $v\geq 6,$ $W_{2,3}(v)$ admits a zero-sum $3$-flow.
For $v \geq 9$ every $2$-$(v,3,v-2)$, see \cite[p.98]{tute1} complete design has a large set and therefore admits a zero-sum 3-flow.
In the case of $v=7$, $k=3$, the complete design is partitioned into two Fano planes and a $2$-$(7,3,3)$ design \cite{ass}. Thus it admits a zero-sum $3$-flow. For the case $v=8$ we provide a zero-sum 3-flow explicitly as follows:}
\end{preproof}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
% after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
123 & 124 & 125 & 126 & 127 & 128 & 134 & 135 & 136 & 137 & 138 & 145 & 146 & 147 \\ \hline
-2 & 2 & 2 & -2 & 2 & -2 & -2 & 1 & 2 & -1 & 2 & -2 & -1 & 2 \\
\hline
\end{tabular}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
% after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
148 & 156 & 157 & 158 & 167 & 168 & 178 & 234 & 235 & 236 & 237 & 238 & 245 & 345 \\ \hline
1 & 1 & -1 & -1 & -1 & 1 & -1 & 2 & -1 & -2 & 1 & 2 & -2 & 1 \\
\hline
\end{tabular}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
% after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
247 & 248 & 256 & 257 & 258 & 267 & 268 & 278 & 246 & 346 & 347 & 348 & 356 & 357 \\ \hline
-2 & -1 & 1 & -1 & 1 & 1 & 1 & -1 & 1 & 1 & -1 & -1 & -1 & 1 \\
\hline
\end{tabular}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
% after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
358 & 367 & 368 & 378 & 456 & 457 & 458 & 467 & 468 & 478 & 567 & 568 & 578 & 678 \\ \hline
-1 & 1 & -1 & -1 & 1 & 1 & 1 & -1 & -1 & 1 & -1 & -1 & 1 & 1\\
\hline
\end{tabular}
\begin{remark}
\noindent We would like to close the paper with a report on the existence of zero-sum flows for small $t$-designs with $k=t+1$ and small
$t$.
\noindent $\bullet$ For $t=2$, the $2$-$(6,3,4)$ design is partitioned into two copies of $2$-$(6,3,2)$ designs \cite{tute1}, therefore $W_{2,3}(6)$ admits a zero-sum $2$-flows.
\noindent $\bullet$ For $t=3$, the $3$-$(8,4,5)$ design is partitioned into two copies of $3$-$(8,4,1)$ designs and a copy of $3$-$(8,5,3)$ design, \cite{ass}.
Thus $W_{3,4}(8)$ admits a nowhere-zero $3$-flow.
\noindent $\bullet$ For $t=4$, no result is known.
\noindent $\bullet$ For $t=5$, the $5$-$(12,6,7)$ design is partitioned into $2$ copies of $5$-$(12,6,1)$ designs (the famous small Witt design)
and a copy of $5$-$(12,6,5)$ design \cite{ass}. Therefore, there is a zero-sum $4$-flow for $W_{5,6}(12)$.
\noindent $\bullet$ For $t=6$, the $6$-$(14,7,8)$ design is partitioned into two copies of $6$-$(14,7,4)$ designs \cite{tute1} and hence admits a zero-sum $2$-flow.
\end{remark}
{\bf Acknowledgments.} This work was completed while the first and second authors were visiting the Abdus Salam International Centre
for Theoretical Physics (ICTP), Trieste, Italy, under the auspices of Combinatorics Program 2010. They would like to express their gratitude for the support.
\newpage
\begin{thebibliography}{}
\bibitem{akb} S. Akbari, N. Gharaghani, G.B. Khosrovshahi, A. Mahmoody, On zero-sum 6-flows of graphs, LAA 430 (2009), 3047-3052.
\bibitem{akb2} S. Akbari, A. Daemi, O. Hatami, A. Javanmard, A. Mehrabian, Zero-sum flows in regular graphs, Graphs and Combinatoris, to appear.
\bibitem{ass} E.F. Assmus, H.F. Mattson, H. F., Jr.
Disjoint Steiner systems associated with the Mathieu groups.
Bull. Amer. Math. Soc. 72 (1966), 843--845.
\bibitem{Baranyai} Z. Baranyai, On the factorizations of the complete uniform hypergraph, in Finite
and Infinite Sets, A. Hajnal, R. Rado, and V. T. Sos, eds., North-Holland,
Amsterdam, 1975, 91-108.
\bibitem{hal} P.R. Halmos, Linear Algebra Problem Book, The Mathematical Association of America, 1995.
\bibitem{Hartman} A. Hartman, Halving the complete design, Ann. Discrete Math. 34 (1987) 207-224.
\bibitem{tute1} G.B. Khosrovshahi and R. Laue, $t$-designs with $t \geq 3$, in: Handbook of Combinatorial Designs (C.J. Colbourn and J.H. Dinitz, eds),
Chapman Hall/CRC, Boca Raton, 2007, 79--101.
\bibitem{tute} W.T. Tutte, A contribution to the theory of chromatic
polynomials, Canad. J. Math. 6 (1954), 80--91.
\bibitem{wil1} R.M. Wilson, Linear algebra and designs, in: Handbook of Combinatorial Designs (C.J. Colbourn and J.H. Dinitz, eds),
Chapman Hall/CRC, Boca Raton, 2007, 783--791.
\bibitem{wil} J.H. van Lint, R.M. Wilson, A Course in Combinatorics, Second Edition, Cambridge University Press, Cambridge, 2002.
\bibitem{Wilson} R.M. Wilson, Incidence matrices of $t$-designs, LAA 46 (1982), 73--82.
\end{thebibliography}
\end{document}