@techreport{TR-DCC-92-05,
  number = {DCC-92-05},
  author = {Lucchesi, Cláudio L. and Younger, Dan H.},
  title = {An $(l,u)$-Transversal Theorem for Bipartite Graphs},
  month = {June},
  year = {1992}, 
  institution = {Department of Computer Science, University of Campinas},
  note = {In English, 11 pages.
    \par\selectlanguage{english}\textbf{Abstract}
      Continuing the work begun by Philip Hall in 1935, we here give
      necessary and sufficient conditions for the existence, in a
      bipartite graph, of a set of edges satisfying specified lower
      and upper bounds.  Here the graph is directed bipartite; lower
      and upper bounds are specified by integer-valued functions, $l$
      and $u$, on the collection of all directed sets of vertices, or
      perhaps on some subcollection, such as the collection of
      singletons. We require these functions to be super- and
      sub-modular, respectively. An {\em $(l,u)$-transversal} is a set
      $t$ of edges that satisfies these bounds.  A second restriction,
      $q \subseteq t \subseteq r$, for edge sets $q$ and $r$, is also
      permitted.
    \par
      One might hope to give necessary and sufficient conditions for
      the existence of a general $(l,u)$-transversal. In this paper,
      this is done for the special case in which the domain of one of
      the functions, say $u$, is restricted to singletons.  Graph $G$
      contains an $(l,u)$-transversal $t$ such that $q \subseteq t
      \subseteq r$ if and only if for each $X$ in $\mathop{\rm dom} l$
      and each subset $N$ of $VG$, $l X \leq u N + [q,r](X \oplus
      N)$. This function $[q,r]$, when applied to a set $Y$ of
      vertices of $G$, is the number of edges of $r$ directed away
      from $Y$ minus the number of edges of $q$ directed toward $Y$.
    \par
      This work is motivated by the Woodall Conjecture, which states:
      in any directed graph, a largest packing of transversals of
      directed coboundaries is equal in size to a smallest directed
      cut. We observe that the domain of this Conjecture can be
      reduced to directed bipartite graphs.  For such graphs, the
      partial $(l,u)$-theory developed here is used to show that the
      edge set of any directed bipartite graph can be partitioned into
      two subsets, one a transversal of directed coboundaries, the
      other a $(k-1)$-transversal of the vertex coboundaries.  In this
      application we require the supermodularity of the size of a
      maximum partition of a directed coboundary into directed cuts.
  }
}