\input amstex \input amsppt.sty \nologo \magnification1200 \hsize13cm \vsize19cm \def\al{\alpha} \def\be{\beta} \def\F{\Cal F} \topmatter \title The Greedy Algorithm as a Combinatorial Principle \endtitle \author U. Faigle \endauthor \address Fachbereich Mathematik, Technische Hochschule Darmstadt, D-6100 Darmstadt, Germany \endaddress \endtopmatter \document One of the best known results of combinatorial matching theory is Hall's ``marriage theorem". In fact, matching theory may be based on this theorem (cf\. \cite{5}). It can either be proved directly or derived from stronger theories, e.g., the theory of flows in networks \cite{4} or the theory of polyhedral matroids \cite{2}. The latter theories are both usually seen as manifestations of the duality principle in linear programming --- an ``explanation" which is not very satisfactory from a purely combinatorial point of view. In this note, we want to give an outline how a combinatorial theory including, in particular, matching theory may be based on a very simple combinatorial principle. This principle states that, under certain restrictions, an optimal combinatorial object can be constructed in a straight-forward manner, namely by the ``greedy algorithm". It seems to be an open problem to give a definition of ``combinatorics" which everyone agrees upon. For our purposes, the following standpoint is appropriate: combinatorics is the study of the processes involved in building up a combinatorial object step by step so that certain requirements are met (cf\. \cite{8}). What we study here are the implications if we know that an optimal combinatorial object can be obtained by taking the greedy algorithm as our rule of construction. \vskip10pt \subhead The Greedy Algorithm\endsubhead \vskip10pt Let $P$ be a (finite) partially ordered set. A {\it sequential family} (over $P$) is a non-empty collection $S$ of sequences $\al=(x_1,x_2, \dots)$, $x_i\in P$, such that \roster \item "(S$_1$)" for every $\al=(x_1,x_2,\dots)\in S$, $x_i\le x_j$ implies $i\le j$,\newline (in particular: $\vert\al\vert\le \vert P\vert$). \item "(S$_2$)" for every $\al=(x_1,\dots,x_k)\in S$, $0\le m\le k$, $\al_m=(x_1,\dots,x_m )\in S$.\newline We define $\al_0=\emptyset$ and $\vert \al_0\vert=0$. \endroster A ({\it compatible}) {\it weighting} of $P$ is a function $w:P\to \Bbb R$ such that $x\le y$ implies $w(x)\ge w(y)$. (Note that $w$ reverses the order.) $w$ extends to a weighting of $S$ via $$w(\al)=\cases \sum _{x\in \al} ^{}w(\al)&\text{if }\emptyset\ne\al\in S,\\ 0&\text{if }\al=\emptyset.\endcases$$ The combinatorial object we seek to construct is an element $\al\in S$ such that $w(\al)$ is maximal. The {\it greedy algorithm} now is the following procedure: \smallskip {\it Step 1}: Choose $x_1\in P$ such that $w(x_1)$ is maximal under the conditions: $w(x_1)>0$ and $(x_1)\in S$. If no such choice is possible, stop. Otherwise continue. \hbox to13cm{\leaders \hbox to1em{\hss.\hss}\hfill} {\it Step $k$}: Choose $x_k\in P\backslash \{x_1,\dots,x_{k-1}\}$ such that $w(x_k)$ is maximal under the conditions: $00$, the greedy algorithm proceeds from one element to the next and adjoins the element to the sequence already constructed if the resulting sequence is a member of $S$. As the greedy algorithm will not necessarily produce an optimal sequence for an arbitrary sequential family $S$, we have to characterize those families for which it does. \proclaim{Theorem \rm\cite{3}} The greedy algorithm produces, for every weighting of $P$, an optmimal sequence of $S$ if and only if $S$ satisfies the two conditions: \roster \item "(GS$_1$)" for every $\al,\be\in S$ with $\vert\al\vert<\vert\be\vert$, there is an $x\in\be$ and $y\le x$ such that $(\al,y)\in S$. \item "(GS$_2$)" if $A\subseteq B$ are ideals of $P$, $p\in A$ an isthmus of $S(B)$, then $p$ is an isthmus of $S(A)$.\quad \quad \qed \endroster \endproclaim Thereby we call $p\in P$ an {\it isthmus} of $S$ is $p$ occurs in every {\it basis} of $S$, i.e., in every $\be\in S$ such that $\vert\be\vert=\max\{\vert\al\vert:\al\in S\}$. Furthermore, we define for an ideal $A\subseteq P$, $$S(A)=\{\al\in S:\al\subseteq A\}.$$ Finally, an ({\it order}) {\it ideal} of $P$ is a subset $A\subseteq P$ such that $x\in A$ and $y\le x$ imply $y\in A$. \vskip10pt \subhead Rank Functions\endsubhead \vskip10pt Assume from now on that the sequential family $S$ satisfies properties (GS$_1$) and (GS$_2$), and consider the collection $\F=\F(P)$ of all ideals of $P$. $\F$ is a distributive lattice with respect to union and intersection. Moreover, via $$\text{for }A\in \F, \ r(A)=\max\{\vert\al\vert:\al\in S(A)\},\tag1$$ $S$ induces a {\it rank function} $r$ on $\F$, i.e., \roster \item "(R$_0$)" $r(\emptyset)=0$, \item "(R$_1$)" for $A\subseteq B\in\F$, $0\le r(B)-r(A)\le \vert B-A\vert$, \item "(R$_2$)" for $A,B\in\F$, $r(A\cup B)+r(A\cap B)\le r(A)+r(B)$. \endroster One can show that every rank function on $\F$ arises this way. Another construction to obtain rank functions is essentially due to Dilworth (see \cite{1}): Say that the function $f:\F\to\Bbb N$ is a {\it pre-rank function} if $f$ satisfies (R$_0$) and (R$_2$) and the weaker property \roster \item "(R$_1'$)" for $A\subseteq B\in \F$, $r(A)\le r(B)$. \endroster \noindent $f$ induces a rank function $r$ on $\F$ via $$\text{for }a\in\F,\ r(A)=\min\{\vert A-B\vert+f(B):B\in\F\}.\tag2$$ Note that formulas (1) and (2) capture a mini-max principle for a rank function $r$ on $\F$ which lies at the heart of matching theory. We could now develop the theory of (integral) polyhedral matroids (see \cite{2}, \cite{6}) by specializing to the case where $\F$ is the set of all vectors with integer coefficients in $\Bbb R^n$ that are less than or equal to some non-negative vector $c\in \Bbb R^n$ ($c$ would then play the role of a ``capacity restriction"). But let us instead turn to an even more special and much-studied case: the case where $P$ is trivially ordered. \vskip10pt \subhead Matroids\endsubhead \vskip10pt If $P$ is trivially ordered, $\F(P)$ is just the collection of all subsets of $P$. The properties (R$_0$), (R$_1$), and (R$_2$) then are the defining properties of a {\it matroid\/} in terms of its rank function (see, e.g., \cite{7}). A subset $X\subseteq P$ is {\it independent\/} if $$r(X)=\vert X\vert.\tag $1'$ $$ Thus the independent sets are exactly the subsets of $P$ whose arrangements make up the sequences of the corresponding sequential family $S$. On the other hand, if the matroid is derived from the pre-rank function $f$, an independent set $X\subseteq P$ is characterized by $$\text{for }A\in\F,\ f(A)\ge \vert X\cap A\vert.\tag $2'$ $$ We may illustrate the formulas ($1'$) and ($2'$) as follows: If $G=(U\cup V,E)$ is a bipartite graph, define for every $A\subseteq V$, $$f(A)={}\text{number of vertices of $U$ related to vertices of $A$.}$$ $f$ clearly is a pre-rank function on $\F(V)$. To say that $V$ is independent in the associated matroid, means according to ($2'$): $$f(A)\ge\vert A\vert \quad \text{for all }A\subseteq V.$$ This is Hall's condition for the existence of a matching from $U$ onto $V$. Let us remark that, within the context of polyhedral matroids, one can {\it prove} Hall's marriage theorem just by suitably interpreting the formulas analogous to ($1'$) and ($2'$). If we accept Hall's theorem, property (GS$_1$) of the underlying sequential family immediately implies that every (partial) matching can be augmented to a maximal matching. This, of course, also follows from the augmentation path theorem. But we do not need it to derive this information. \Refs \ref\no 1\by P. Crawley and R. P. Dilworth\book Algebraic Theory of Lattices \publ Prentice--Hall\publaddr Englewood Cliffs, N.J.\yr 1973\endref \ref\no 2\by J. Edmonds\paper Submodular functions, matroids and certain polyhedra\inbook Proc\. Int\. Conf\. on Combinatorics (Calgary)\publ Gordon and Breach\publaddr New York\yr 1970\pages 69--87\endref \ref\no 3\by U. Faigle\paper The greedy algorithm for partially ordered sets\jour Discrete Math\.\vol 28\yr 1979\pages 153--159\endref \ref\no 4\by L. R. Ford and D. R. Fulkerson\book Flows in Networks\publ Princeton University Press\publaddr Princeton\yr 1962\endref \ref\no 5\by L. H. Harper and G.-C. Rota\paper Matching theory: an introduction\jour Adv\. Probab\.\vol 1\yr 1971\pages 169--213\endref \ref\no 6\by C. J. H. McDiarmid\paper Rado's theorem for polymatroids\jour Math\. Proc\. Cambridge Philos\. Soc\.\vol 78\yr 1975\pages 263--281 \endref \ref\no 7\by D. J. A. Welsh\book Matroid Theory\publ Academic Press\publaddr London\yr 1976\endref \ref\no 8\by H. S. Wilf\paper A unified setting for sequencing, ranking, and selection algorithms for combinatorial objects\jour Adv\. Math\.\vol 24\yr 1977\pages 281--291\endref \endRefs \enddocument