\documentstyle{article}
%my makros

\textwidth=105mm
\textheight=160mm
\addtolength{\oddsidemargin}{-3cm}
\addtolength{\topmargin}{-3cm}
\sloppy
\def\t{\bigskip\bigskip}
\def\te{\bigskip\bigskip}
\def\ta{\nopagebreak\medskip\nopagebreak}
\def\tb{\nopagebreak\medskip\nopagebreak}
\def\tc{\nopagebreak\bigskip\nopagebreak\noindent}
\setcounter{tocdepth}{1}

%Bouchet's macros
\newtheorem{statement}{}

\font\sc = cmcsc10

\def \idx #1{{\it #1}}
\def \resp #1{(resp. #1)}
\def \ath #1{{\sc #1}}
%\def \iff { if and only if }

\def \cardinal #1{|#1|}
\def \inter {\cap}
\def \union {\cup}
\def \set #1{\{#1\}}

\def \N {{\bf N}}
\let \nq = q

\let \Mm = Q
\let \Mmset = U
\let \Mmpart = \Omega
\let \Mmrank = r
\def \mmrank #1{\Mmrank(#1)}
\def \Mmtriple {(\Mmset, \Mmpart, \Mmrank)}
\let \Mmclass = \omega
\let \Mmindep = I
\let \Mmbase = B
\let \Mmcircuit = C
\let \Mmelm = x
\let \Mmelmb = y

\let \Sbt = A
\let \Sbtb = B
\def \subtrans #1{{\cal S}(#1)}
\let \Gfond = G
\def \gfond #1#2{\Gfond_{#1}(#2)}

%Cameron's macros

\newtheorem{theorem}{Theorem}[subsection]
\newtheorem{ccor}[theorem]{Corollary}
\newcommand{\head}[1]{\medbreak\noindent{\em#1}.\ }
\font\tenbb=msbm10 \newfam\bbfam \textfont\bbfam=\tenbb
\newcommand{\bb}{\fam\bbfam}

%Galluccio's macros

\newtheorem{Definition}{\bf Definition}[subsection]
\newtheorem{Example}[Definition]{\bf Example}
\newtheorem{Remark}[Definition]{\bf Remark}
\newtheorem{Lemma}[Definition]{\bf Lemma}
\newtheorem{Theorem}[Definition]{\bf Theorem}
\newtheorem{Corollary}[Definition]{\bf Corollary}
\newtheorem{Proposition}[Definition]{\bf Proposition}
\newtheorem{Conjecture}[Definition]{\bf Conjecture}

\def\Re{I\!\!R}
\def\gt{>}
\def\lt{<}
\def\sp{\;\;}
\def\wug{=^{\!\!\!\!\!^{q}}}
\def\wnug{\ne^{\!\!\!\!\!^{q}}}

%Haemers' macros

\def\s{\Phi}
\def\d{\delta}
\def\8{\infty}

%Hochstaedtler's macros
\def\Nscr{{\cal N}}  \def\Cscr{{\cal C}}  \def\Kscr{{\cal K}}
\def\Fscr{{\cal F}}  \def\Gscr{{\cal G}}  \def\Hscr{{\cal H}}
\def\Sscr{{\cal S}}  \def\Dscr{{\cal D}}  \def\Lscr{{\cal L}}  
\def\R{\hbox{I\hskip-0.23em R}}
\newtheorem{rem}{Remark}[section]
%\newtheorem{lem}{Lemma}[section]
\newtheorem{theo}{Theorem}[section]
%\newtheorem{ccor}{Corollary}[section]
\newtheorem{defin}{Definition}[section]
\newtheorem{prop}{Proposition}[section]
\newtheorem{ex}{Example}[section]
\def\proof{\par\medbreak\noindent{\bf Proof.}\enspace}
\def\endproof{ \nopagebreak \hfill $\Box$ \vspace{.5cm} \pagebreak[3] }
\def\supp{\mbox{supp}\,}
\def\sep{\mbox{sep}\,}
\def\conv{\mbox{conv}\,}
\renewcommand{\theequation}{$\ast$}

%Pudlak's macros

\newtheorem{ttheorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}{Definition}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{problem}{Problem}
\def\prf{{\it Proof. }}
\def\eps{\varepsilon}
\def\sub{\subseteq}
\def\ph{\varphi}
\def\dts{,\dots,}
\def\qed{\hfill $\Box$\par\bigskip}
\def\kraj{Kra\-j\'{\i}\-\v{c}ek}
\def\p{\bar{p} }
\def\q{\bar{q} }
\def\r{\bar{r} }
\def\a{\bar{a} }
\def\et{\wedge }
\def\vel{\vee }
\def\F{{\cal F}_{l,r}}
\def\V{[V]^{\leq l}}
\def\R{{\sf\bf R}}

%Sebo's macros
\newcommand{\Hs}{{\cal H}}
\newcommand{\As}{{\cal K}}
\newcommand{\Ks}{{\cal K}}
\newcommand{\Qs}{{\cal Q}}
\def\Nset{\hbox{I\hskip-0.20em I\hskip-0.35em N}}
\def\Qset{\hbox{\hbox{Q\hskip-0.525em\lower-0.097ex
          \hbox{\vrule height1.47ex width0.07em}}\hskip0.50em}}
\def\Rset{\hbox{I\hskip-0.23em R}}
\def\Zset{\hbox{Z\hskip-0.38em Z}}
%\newtheorem{thm}{Theorem}[section]
\newtheorem{lm}{Lemma}
%\newtheorem{cor}[thm]{Corollary}
\newenvironment{pf}{\par\smallskip\noindent{\bf Proof:}\ }{\qed\medskip}
\newenvironment{case}[1]
{\[ #1 \left\{\begin{array}{ll}}{\end{array}\right.\]}

%Triesch's macros

\def\mod{{\rm mod}}
\def\lc{\lceil}
\def\lf{\lfloor}
\def\rc{\rceil}
\def\rf{\rfloor}
\def\nel{\notin}
\def\tm{\subset}
\def\P{{\cal P}}
\def\A{{\cal A}}
\def\S{{\cal S}}
\def\G{{\cal G}}
\def\V{V^{(2)}}
\def\Z{{\bf Z}}
\def\Zn{{\bf Z}_n}
\def\Aut{\mathop{\rm Aut}\nolimits}
\def\Zp{{\bf Z}_p}
\def\Zm{{\bf Z}_m}
\def\g{\gamma}
\def\hyp{\approx}
\def\mi{\setminus}
\def\ffi{\varphi}
\def\D{\cal D}
\def\N{\cal N}
\def\L{\cal L}
\def\dom{\preceq}
\def\iff{\Longleftrightarrow}
\def\Ga{\Gamma}
\def\O{\cal O}
\def\imp{\Longrightarrow}
\def\Gd{\overrightarrow G}
\def\I{\cal I}
\def\d{\delta}
\def\ep{\varepsilon}
\def\be{\beta_1}
\def\3{{\ss}}
\def\Om{\Omega_n}
\def\a{\alpha}
\def\l{\ell}
\def\lm{\ell_{\max}}
\def\R{{\cal R}}
\def\Rel{{\cal R}=(N;R_1,\ldots,R_k)}
\def\Rela{{\cal R}'=(N';R_1',\ldots,R_k')}
\parindent=0pt
\newtheorem%
{thm}{Theorem}
\newtheorem{lem}{Lemma}
%\newtheorem{cor}{Corollary}
\newtheorem{pro}{Problem}


\title{THIRD ANNUAL DONET MEETING 1996}
\date{}
\author{ed. M. Klazar}

\begin{document}

\maketitle
\thispagestyle{empty}
\newpage
\pagenumbering{roman}
\tableofcontents

\newpage
\section{Preface}

Third Annual Meeting of the Discrete Optimization Network (DONET)
was held at \v Sti\v r\'\i n Castle in the Prague Area, May 19-24, 1996.
This was the last of the DONET Annual meetings 
 within the present framework of 
DONET. The previous annual meetings were held in Trento in 1993
and in London in 1995. We enclose shorter abstracts
 of most of the talks presented at the meeting. We are also happy to include 
extended abstracts and short papers
covering most of the invited talks. Perhaps this, together with some 
photos and (a few memories) will provide us with an encouragement to the 
future. One can see 
 that DONET contributed in an essential way to the development of Discrete Optimization in Europe, especially by providing 
 opportunities for the critical group of young researchers.
We thank to the founder of the project prof. B. Korte (Bonn)
and the present acting director of DONET project prof. J. Fonlupt (Paris)
for all their energy in starting and managing this project. And we hope that 
we have enough luck to be able to continue and deepen our activity in 
similar framework in future.

\bigskip\noindent 

\rightline{Jaroslav Ne\v set\v ril~~~~~~}

\newpage
\pagenumbering{arabic}

\section{List of participating institutions and the local coordinators}

\bigskip\bigskip
\begin{tabular}{lll}
{\bf Amsterdam} & A. Schrijver & {\it Stichting Mathematisch Centrum}\\
 & & {\it Kruislann 413}\\
 & & {\it 1098 SJ Amsterdam}\\
 & & {\it Netherlands}\\
 & & \\
{\bf Bonn} & B. Korte & {\it Forschungsinstitut f\"ur Diskrete Mathematik}\\
 & & {\it Universit\"at  Bonn}\\
 & & {\it Nassestrasse 2 }\\
  & & {\it D-5300 Bonn 1}\\
 & & {\it Germany}\\
 & & \\
{\bf Budapest} & A. Frank & {\it E\"otv\"os Lorand University}\\
 & & {\it Computer Science}\\
 & & {\it Muzeum Krt 6--8}\\
 & & {\it 1088 Budapest}\\
 & & {\it Hungary}\\
 & & \\
{\bf Grenoble} & D. Naddef & {\it Universit\'e Joseph Fourier}\\
 & & {\it 380421 Grenoble Cedex 9}\\
 & & {\it France}\\
 & & \\
{\bf London} & B. Shepherd & {\it London School of Economics}\\
 & & {\it Houghton}\\
 & & {\it WC2A 2AE London}\\
 & & {\it United Kingdom}\\
 & & \\
\end{tabular}

\newpage
\begin{tabular}{lll}
{\bf Padua} & M. Comforti & {\it University of Padua}\\
 & & \\
{\bf Paris} & J. Fonlupt & {\it Universit\'e Pierre et Marie Curie}\\
 & & {\it Tour 46--56 --- 5\`eme \'etage}\\
 & & {\it 4 Place Jussien}\\
 & & {\it 75005 Paris}\\
 & & {\it France}\\
 & & \\

{\bf Prague} & J. Ne\v set\v ril & {\it Charles University}\\
 & & {\it Department of Applied Mathematics}\\
 & & {\it Malostransk\'e n\'am\v est\'\i\ 25}\\
 & & {\it 118 00 Praha 1}\\
& & {\it Czech Republic}\\
& & \\

{\bf Oxford} & D. Welsh & {\it University of Oxford}\\
 & & {\it Mathematical Institute}\\
& & {\it St. Gilles 22--24}\\
& & {\it OX1 2LB Oxford}\\
& & {\it England}\\
& & \\

{\bf Rome} & B. Simeone & {\it Universita di Roma "La Sapienza"}\\
 & & {\it Dipartimento di statistica}\\
 & & {\it Piazzala Aldo Moro 5}\\
 & & {\it 00185 Rome}\\
 & & {\it Italia}\\

\end{tabular}

\newpage

\section{Andr\'{e} Bouchet\\ Multimatroids. Tightness and fundamental graphs}

%\centerline{\Large Multimatroids. Tightness and} 

%\smallskip
%\centerline{\Large fundamental graphs} 

\bigskip
\begin{center}
{\it
D\'{e}partement d'Informatique \\
  Universit\'{e} du Maine \\
  72017 Le Mans Cedex \\
  FRANCE\\
{\tt bouchet@lium.univ-lemans.fr}

}
\end{center}

Consider a partition $\Mmpart$ of a finite set $\Mmset$. A \idx
{subtransversal} \resp {\idx {transversal}} of $\Mmpart$ is a subset
$\Sbt \subseteq \Mmset$ such that $\cardinal {\Sbt \inter \Mmclass} \le
1$ \resp {$\cardinal {\Sbt \inter \Mmclass} = 1$} holds for all
$\Mmclass$ in $\Mmpart$. We denote by $\subtrans \Mmpart$ the set of
subtransversals of $\Mmpart$.

A \idx {multimatroid} is a triple $\Mm = \Mmtriple$ with a partition
$\Mmpart$ of a finite set $\Mmset$ and a \idx {rank function} $\Mmrank :
\subtrans \Mmpart \to \N$ satisfying the four following axioms:

\begin{statement}
  \label{mm1}
  $\mmrank \emptyset = 0$;
\end{statement}

\begin{statement}
  \label{mm2}
  $\mmrank \Sbt \le \mmrank {\Sbt + \Mmelm} \le \mmrank \Sbt + 1$ is
  satisfied if $\Sbt$ is a subtransversal of $\Mmpart$, $\Mmelm$ is an
  element of $\Mmset$, and $\Sbt + \Mmelm$ is a subtransversal;
\end{statement}

\begin{statement}
  \label{mm3}
  {\bf Submodularity inequality:}
  $\mmrank \Sbt + \mmrank \Sbtb \ge \mmrank {\Sbt \union \Sbtb} +
  \mmrank {\Sbt \inter \Sbtb}$ is satisfied if $\Sbt$, $\Sbtb$ and $\Sbt
  \union \Sbtb$ are subtransversals;
\end{statement}

\begin{statement}
  \label{mm4}
  $\mmrank {\Sbt+\Mmelm} - \mmrank \Sbt + \mmrank {\Sbt + \Mmelmb} -
  \mmrank \Sbt \ge 1$ is satisfied if $\Sbt$ is a subtransversal of
  $\Mmpart$, $\set {\Mmelm, \Mmelmb}$ is a pair contained in a class
  $\Mmclass$ of $\Mmpart$, and $\Sbt$ is disjoint from $\Mmclass$.
\end{statement}

An \idx {independent set} is a subtransversal $\Mmindep$ such that
$\mmrank \Mmindep = \cardinal \Mmindep$, a \idx {base} is a maximal
independent set, and a \idx {circuit} is a subtransversal that is not
independent and minimal with this property. If each skew class has
cardinality equal to the positive integer $\nq$ then $\Mm$ is also
called a \idx {$\nq$-matroid}.

The multimatroid $\Mm$ is \idx {nondegenerate} if every class has at
least two elements. Then it is easy to prove, by using the fourth axiom,
that every base is a transversal. A basic result of the theory of
multimatroids says that the union of every base with every class of
$\Mmpart$ contains at most one circuit. The multimatroid $\Mm$ is said
to be \idx {tight} if it is nondegenerate and the union of a base with a
class of $\Mmpart$ always contains a circuit, called \idx {fundamental
circuit}.

The fundamental circuits, with respect to matroids and tight
multimatroids, play similar roles. In particular they can be used to
define a fundamental graph $\gfond \Mm \Mmbase$ associated to every base
$\Mmbase$ of $\Mm$. This graph carries a great part of the information
concerning the connectivity of $\Mm$. The first basic result says that
$\Mm$ is connected if and only if $\gfond \Mm \Mmbase$ is connected. Here a
multimatroid is said to be \idx {connected} if, for every bipartition
$\set {X_1, X_2}$ of $\Mmset$ such that $X_1$ and $X_2$ are unions of
classes of $\Mmpart$, there exists a circuit $\Mmcircuit$ such that
$\Mmcircuit \inter X_1 \neq \emptyset \neq \Mmcircuit \inter X_2$.

At a deeper level one can extend, by specifying the transformations of
fundamental graphs when the base is modified, some relations between
minors and connectivity. Here the \idx {minor} of a multimatroid $\Mm$,
with respect to an element $\Mmelm$ contained in the class $\Mmclass$ of
$\Mmpart$, is the multimatroid $\Mm'$ defined by the rank function
$\Mmrank'(\Sbt) = \mmrank {\Sbt + \Mmelm} - \mmrank \Mmelm$, for $\Sbt
\in \subtrans {\Mmpart - \Mmclass}$. Thus, if $\Mm$ is a tight
$\nq$-matroid, we define $\nq$ minors of $\Mm$ with respect to the $\nq$
elements in $\Mmclass$. We prove that at least $\nq - 1$ of these minors
are connected. This extends a theorem of \ath {Tutte} in matroid theory,
saying that, if we contract and delete one element in a connected
matroid, then at least one of the two minors is connected.

There is a notion of linear representability for a multimatroid. We have
given, with \ath {Duchamp}, a characterization of the binary 2-matroids
by means of two excluded minors. \ath {Gasse} has recently proved that,
if a connected tight 2-matroid $\Mm$ is not binary, then every element
belongs to a minor equal to one of the two forbidden minors. This
extends a theorem of \ath {Seymour} in matroid theory. An extension of a
theorem of \ath {Lehmann}, saying that a connected matroid is determined
by the set of its circuits containing a given element, has also been
extended to tight multimatroids.

To complete this abstract we note that the preceding properties become
false with multimatroids that are not tight.

\newpage

\section{Peter J. Cameron \\
Fixed Points and Derangements}

%\centerline{\Large Fixed Points and Derangements} 

\bigskip
\begin{center}
{\it
School of Mathematical Sciences\\
Queen Mary and Westfield College\\
Mile End Road\\
London E1 4NS\\
U.K.\\
{\tt P.J.Cameron@qmw.ac.uk}
}
\end{center}

\bigskip
\begin{abstract}

This note concerns numbers of fixed points of elements of a
permutation group. A simple transformation relates the
probabiliity generating function for the number of fixed points
of a random group element with the exponential generating
function for the number of orbits of the group on ordered tuples.
For infinite groups, this no longer applies. The formalism
often produces a number which in the finite case would be the
proportion of derangements; in the infinite case its meaning is
usually not clear.

The article concludes with a result of Parker extending the
orbit-counting lemma from fixed points to cycles. One open
question concerns whether Block's Lemma extends to this situation.

\end{abstract}

\subsection{Fixed points}

Throughout the following, $G$ is a permutation group on a set
$\Omega$, which may be finite or infinite. (The cardinality of
$\Omega$ is the {\em degree} of $G$.)

The basic tool relating fixed points to orbits is the {\em
orbit-counting lemma} (mis-attributed to Burnside):

\begin{theorem}
Let $G$ have finite degree; let $c(g)$ be the number of fixed
points of $g\in G$. Then the number of orbits of $G$ is given by
\[{1\over|G|}\sum_{g\in G}c(g).\]
\end{theorem}

The well-known proof involves counting edges in the bipartite
graph on $\Omega\times G$, where $x\in\Omega$ is joined to
$g\in G$ if and only if $g$ fixes $x$. Mark Jerrum has pointed
out that a random walk on this bipartite graph can be used to
choose a random $G$-orbit from the uniform distribution.

The following consequence of the orbit-counting lemma was pointed
out to me by Nigel Boston. Let $G$ be a permutation group of
finite degree $n$. Let $X(t)$ be the probability generating
function for the number of fixed points of a random element of $G$:
thus,
\[X(t)={1\over|G|}\sum_{i=0}^n f_it^i,\]
where $f_i$ is the number of elements of $G$ which have exactly
$i$ fixed points. Now let $m_i$ be the number of orbits of $G$
in its induced action on $i$-tuples of distinct elements of $\Omega$,
and $Y(t)$ the exponential generating function for this sequence;
that is,
\[Y(t)=\sum_{i=0}^n{m_it^i\over i!}.\]

\begin{theorem}
\[Y(t)=X(t+1).\]
\end{theorem}

\head{Proof} If an element $g$ fixes $i$ points, then it fixes
$(i)_j=i(i-1)\cdots(i-j+1)$ ordered $j$-tuples. So
\[m_j={1\over|G|}\sum_{i=j}^nf_i(i)_j.\]
The result follows by simple manipulation.

\medbreak

A {\em derangement} is a permutation with no fixed points. Thus,
the proportion of derangements in $G$ is $f_i=|G|X(0)$, and we
have:

\begin{ccor}
With the above notation, the probability that a random element
of $G$ is a derangement is $Y(-1)$.
\end{ccor}

\head{Question} What (linear or non-linear) constraints are
satisfied by the vector $(f_0/|G|,\ldots, f_m/|G|)$?

\medbreak

That there are some non-trivial constraints is shown by the
following result of Arjeh Cohen:


\begin{theorem}
If $G$ is transitive with degree $n$,
then at least $|G|/n$ elements of $G$ are derangements, with
equality if and only if $G$ is sharply $2$-transitive. Moreover, the
subgroup generated by the derangements is transitive and contains
all elements of $G$ whose number of fixed points is not equal to $1$.
\end{theorem}

This is shown by transferring from $Y$ to $X$ the following constraint
satisfied by the numbers $m_i$ of orbits on $i$-tuples:
$m_2\ge m_1(m_1-1)+m^*_1$, where $m^*_1$ is the number of
orbits on points with cardinality greater than $1$. (A
permutation group $G$ is {\em sharply $2$-transitive} if any
$2$-tuple of distinct points is mapped to any other by a
unique element of $G$. Such finite groups have been completely
determined by Zassenhaus in the 1930s.)

\medbreak

Now let $G$ be a permutation group of infinite degree. There
is no obvious way in which to speak of proportions of elements
with a given number of fixed points. However, numbers of
orbits can be counted. We say that $G$ is {\em oligomorphic}
if it has only finitely many orbits on $i$-tuples of distinct
elements of $\Omega$, for all non-negative integers $i$. If
$m_i$ is this number of orbits, then we can define the
generating function $Y(t)$ as above. Often it turns out that
$Y(-1)$ can be calculated, as we will see; the meaning of this
number is not clear.

\subsection{Examples}

\head{Example 1}
First we look at the classical example, the number of derangements
in the symmetric group. There are many entirely different ways of
computing this number. The argument here, though, may be new.
The symmetric group $S_n$ has a unique orbit on $i$-tuples for
$i\le n$, and none for $i>n$. So $Y(t)$ is the exponential
series $\sum t^i/i!$, truncated at the term $t^n/n!$. The
proportion of derangements is obtained by substituting $t=-1$,
and we obtain the familiar formula, and the fact that it is
approximately $1/{\rm e}$.

Moreover, for the infinite symmetric group, the number of
orbits on $i$-tuples is $1$ for all $i$. So $Y(t)={\rm e}^t$.
This series converges for all $t$, and $Y(-1)={\rm e}^{-1}$,
the limiting value of the proportion of derangements in
finite symmetric groups.

\head{Example 2} Let $G$ be the group of order-preserving
permutations of the rational numbers (or of the real numbers).
Then $G$ is oligomorphic: it has $i!$ orbits on $i$-tuples,
corresponding to the $i!$ different permutations relating the
order of the $i$-tuple to the natural order in $\bb Q$ or $\bb R$.
So
\[Y(t)=\sum_{i=1}^\infty t^i={1\over1-t}.\]
This would suggest that $Y(-1)={1\over2}$. More formally,
\[Y(-1)=1-1+1-1+\ldots\ ;\]
the series is not convergent, but can be summed by any number
of methods to $1\over2$. For example, the radius of convergence
of $X(t)$ is $1$, but there is a unique singularity on the
unit circle (at $1$), and $X(t)$ can be analytically continued
to all other points of $\bb C$: its value at $-1$ is $1\over2$.

Is there any sense in which half of the elements of this group
are derangements?

\head{Example 3} Let $G$ be the group $S_r^{\{2\}}$,
defined to be $S_r$ acting on $2$-sets, with degree $n={r\choose2}$.
Then $m_i$ is the number of graphs with $r$ unlabelled vertices
and $i$ labelled edges. Moreover, it can be shown (using results
about the cycle distribution in random permutations) that
\begin{eqnarray*}
f_0/|G|&=&\sum_{i=0}^n(-1)^im_i/i!\\
&\to& 2{\rm e}^{-3/2}=0.446260\ldots\hbox{ as $r\to\infty$.}
\end{eqnarray*}

Moreover, we can take the limiting case to be $S^{\{2\}}$,
the infinite symmetric group acting on $2$-sets. Then
$m_i(S_r^{\{2\}})\to m_i(S^{\{2\}})$ as $r\to\infty$. Indeed,
the number of graphs with $r$ vertices and $i$ edges increases
until $r=2i$ and then remains constant.

\head{Question} Is there some sense of convergence in which
the series $Y(-1)$ for the group $S^{\{2\}}$ converges to
$2{\rm e}^{-3/2}$?

\subsection{Parker's Lemma}

The following result was proved by Richard Parker. It suggests a
technique for obtaining information about an unknown permutation
group by looking at the cycle structure of a random element. (This
situation arises in computatioonal Galois theory: given an integer
polynomial, we can compute the cycle structure of the Frobenius
automorphism on the roots of its reduction modulo a prime.)

\begin{theorem}{\em(Parker's Lemma)}
Let $G$ be a finite permutation group of degree $n$. Let $c_i(g)$
be the number of $i$-cycles of the element $g\in G$. Let
${\cal C}_i$ be the set of all $i$-cycles which occur in the
decomposition of some element of $G$ (with $G$ acting by conjugation
on ${\cal C}_i$). Then the number of orbits of $G$ on ${\cal C}_i$
is
\[{1\over|G|}\sum_{g\in G}ic_i(g).\]
\end{theorem}

The proof is ingenious but elementary. In particular, the
Orbit-Counting Lemma (which is the special case $i=1$, since every
point occurs as a $1$-cycle in the identity) is not used in the
proof.

Parker's Lemma has the following curious consequence.

\begin{ccor}
With the notation of Parker's Lemma, let ${\cal C}=\bigcup_i
{\cal C}_i$ be the set of all cycles of elemens of $G$. Then
the number of orbits of $G$ on $\cal C$ is $n$.
\end{ccor}

For $\sum_iic_i(g)=n$ for all $g\in G$.

\medbreak

The {\em Parker vector} of $G$ is the $n$-tuple $(a_1, \ldots, a_n)$,
where $a_i$ is the number of orbits of $G$ on ${\cal C}_i$.
At the two extremes, the trivial group has Parker vector
$(n,0,\ldots, 0)$, and the symmetric group has Parker vector
$(1,1,\ldots,1)$. The components of the Parker vector need not
be monotonic. If $G$ is the cyclic group of order $n$ acting
regularly, its Parker vector has components
\[a_i=\cases{\phi(i), & if $i$ divides $n$,\cr 0, & otherwise,\cr}\]
where $\phi$ is Euler's function.

\head{Question} What is the convex hull of the set of Parker
vectors of permutation groups of degree $n$?

\medbreak

Suppose that $G$ is a group of automorphisms of an incidence
structure of points and blocks, whose incidence matrix has `full
rank' (rank equal to the number of points). Examples of such
structures include non-trivial $2$-designs (balanced incomplete
block designs). Then {\em Block's Lemma} asserts that $G$ has
at least as many orbits on blocks as on points. That is, the
first component of the Paarker vector on blocks dominates that
on points. The following generalisation seems unlikely, but I
know of no counterexamples.

\head{Question} Under the above hypothesis, is it true that the
first $n$ components of the Parker vector of $G$ on blocks
dominate those for $G$ on points, where $n$ is the number of
points?

\newpage

\section{Andr\'as Frank\\ 
Orientations of graphs and submodular flows}


%\centerline{{\Large Orientations of graphs and submodular flows}
%\footnote{ Research
%supported by the Hungarian National Foundation for Scientific Research
%Grant, OTKA T17580.  This is the Introduction of a paper appeared in:
%Congressus Numerantium, 113 (1996) (A.J.W.  Hilton, ed.) pp. 111-142.
%}}

\bigskip
\begin{center}
{\it
Department of Operations Research\\
 E\"otv\"os University\\
 M\'uzeum krt. 6-8\\
 Budapest\\
 HUNGARY H-1088\\
{\tt frank@cs.elte.hu}
\footnote{ Research
supported by the Hungarian National Foundation for Scientific Research
Grant, OTKA T17580.  This is the Introduction of a paper appeared in:
Congressus Numerantium, 113 (1996) (A.J.W.  Hilton, ed.) pp. 111-142.
}}
\end{center}

%\parindent 12pt


\font\ninerm=cmr9


%\centerline { {\bf ORIENTATIONS OF GRAPHS}}


%\bigskip

%\centerline {{\bf AND }}

%\bigskip

%\centerline {{\bf SUBMODULAR FLOWS}\footnote{ $\sp{+}$} {\rm Research
%supported by the Hungarian National Foundation for Scientific Research
%Grant, OTKA T17580.  This is the Introduction of a paper appeared in:
%Congressus Numerantium, 113 (1996) (A.J.W.  Hilton, ed.) pp. 111-142.
%} }


\bigskip \bigskip

%\centerline {Andr\'as Frank\footnote{*} {\rm Department of Operations
%Research, E\"otv\"os University, M\'uzeum krt. 6-8, Budapest, Hungary,
%H-1088. e-mail:  {\tt frank at cs.elte.hu }}}


\bigskip \bigskip

%\bigskip \bigskip




\font\ninerm=cmr9

\noindent {\ninerm {\bf ABSTRACT} Generalizing an earlier result of
H.E.  Robbins \lbrack 1939\rbrack , C.St.J.A.  Nash-Williams \lbrack
1960\rbrack \ proved that an undirected graph $G$ has a
$k$-edge-connected orientation if and only if $G$ is
$2k$-edge-connected.  In a recent paper Nash-Williams \lbrack
1995\rbrack \ found a necessary and sufficient condition for the
existence of a strongly-connected orientation of a mixed graph so that
every node $v$ has at least a prescribed number of newly oriented
edges entering $v$.  It was known earlier how the first of these
theorems derives from the theory of submodular flows.  In this paper
we describe how (a generaliztion of) the second does.  As a main
device, we prove a simplified feasibility theorem for submodular flows
constrained by crossing submodular functions.  }


%\hsize = 16.5 cm \leftskip = .5 cm


% \leftskip = 1 in

% \hsize = 5.5 in

\bigskip \bigskip \bigskip

\noindent {\bf I. INTRODUCTION}

\bigskip




Let $G=(V,E)$ be an undirected graph and $h:2\sp V \rightarrow {\bf Z}
\cup \{-\infty \}$ an integer-valued set-function with $h(\emptyset )
= h(V)=0$.  The general form of the orientation problem we consider
consists of finding an orientation of the edges of $G$ so that in the
resulting digraph $\vec G$ there are at least $h(X)$ edges entering
$X$ for every subset $X\subseteq V$.  More precisely, the goal is to
find necessary and sufficiant conditions for the existence of such an
orientation.  (Sometimes the problem is formulated in an equivalent
form where $h$ is defined only on a family ${\cal F}$ of subsets of
$V$ and $h$ is finite-valued.  In this case $h$ may be extended to
each subset of $V$ by defining $h(X)=-\infty $ for subsets not in
${\cal F}$.)

We will also consider orientation problems when the input is a mixed
graph $M=(V,E+ \vec A)$ composed from an undirected graph $G=(V,E)$
and from a directed graph $\vec D=(V,\vec A)$.  In this case the
elements of $E$ has to be oriented and $\vec D$ will serve only to
express the requirement for the orientation.


This problem formulation is too general in the sense that NP-complete
problems may be formulated as a special case.  Therefore we restrict
our attention to a special class of functions, namely, when $h$ is
{\bf crossing $G$-supermodular,} that is, $$h(A) + h(B) \leq h(A\cup
B) + h(A \cap B)+ d(A,B)\eqno(1.1)$$ holds for every pair $\{A,B\}$ of
subsets of $V$ for which none of $A-B,B-A,A\cap B, V-(A\cup B)$ is
empty where $d(A,B)$ denotes the number of edges in $G$ with one and
in $A-B$ and the other end in $B-A$.

All orientation problems to be considered in this paper may be
described by such a function.  There are some other orientation
theorems which do not fit this framework, most notably, Nash-Williams'
\lbrack 1960\rbrack \ difficult theorem (which may be called the
strong orientation theorem) on the existence of well-balanced
orientations.  This easily implies Nash-Williams' weak orientation
Theorem 1.1 (mentioned in the abstract).




\bigskip

The earliest orientation result is due to H.E.  Robbins \lbrack
1939\rbrack \ who proved that {\sl $G$ has a strongly connected
orientation if and only if $G$ is 2-edge-connected.} \bigskip

(A digraph is called {\bf strongly connected} if there is a directed
path from every node to every other.  More generally, a digraph is
called $k$-{\bf edge-connected} if there are $k$ edge-disjoint paths
from every node to every other node.  By Menger's theorem this is
equivalent to requiring that every non-empty, proper subset of nodes
has at least $k$ entering edges.  An undirected graph is called
$k$-{\bf edge-connected} if every cut contains at least $k$ edges.)

Nash-Williams generalized Robbins' theorem, as follows.


\bigskip

\noindent {\bf THEOREM 1.1} \lbrack Nash-Williams, 1960\rbrack \ {\sl
For any positive integer $k$ an undirected graph $G=(V,E)$ has a
$k$-edge-connected orientation if and only if $G$ is
$2k$-edge-connected.}

\bigskip

F. Boesch and R. Tindell \lbrack 1980\rbrack \ found another extension
of Robbins' theorem concerning orientations of mixed graphs.  Let
$M=(V,E+\vec A)$ be a mixed graph.  We say that a path $P$ from $u$ to
$v$ in $M$ is {\bf correct} if $P$ may use undirected edges
arbitrarily and directed edges pointing forward along the path.  $M$
is called {\bf traversable} if there is a correct path from $u$ to $v$
for every ordered pair of nodes $(u,v)$.  This is easily seen to be
equivalent to requiring that $M$ has no directed cuts and the
undirected graph arising from $M$ by de-orienting the directed edges
is connected.  (A {\bf directed cut} of a mixed graph is the set of
directed edges entering some $\emptyset \subset X\subset V$ provided
that there are no directed edge leaving $X$ and that there are no
undirected edges connecting $X$ and $V-X$.)  Note that in case $M$ is
undirected (that is, $\vec A=\emptyset $) traversable is the same as
connected, while if $M$ is directed, traversable is the same as
srongly connected.  \bigskip

Boesch and Tindell proved:  {\sl A mixed graph $M$ has a strongly
connected orientation if and only if $M$ is traversable and has no
undirected cut edges.} \bigskip

(A short proof of this result consists of a greedy-type procedure that
considers the undirected edges in an arbitrary order and orient them
one by one in such a way that no directed cut arises, that is, the
traversability is preserved.  It can rather easily be shown that, at
every step, among the two possible orientations of the current edge at
least one will always do).

The question naturally emerges:  when does there exist a
$k$-edge-con\-nec\-ted orientation of a mixed graph?  This can be
answered with the use of submodular flows.  The notion of submodular
flows was introduced by J. Edmonds and R. Giles \lbrack 1977\rbrack .
They proved (among others) that the submodular flow polyhedron is
integral.  It was observed in \lbrack Frank 1982\rbrack \ that there
is a strong link between $0-1$-valued submodular flows and
orientations of graphs.  For example, the integrality of the
submodular flow polyhedron easily implies Nash-Williams' result.  (It
is a great challenge to relate Nash-Williams' strong orientation
theorem to submodular flows or more general integral polyhedra.)

The generality of the notion of submodular flows made it possible to
derive several extensions of the weak orientation theorem that will be
accounted in the next section.  One of the most general problem of
this type concerns degree-constrained $k$-edge-connected orientations
of mixed graphs.  Unfortunately the necessary and sufficient condition
is pretty complicated (due to the fact that the corresponding
feasibility theorem for submodular flows is complicated.)


Recently, however, Nash-Williams \lbrack 1995\rbrack \ found a much
simpler characterization for the special case $k=1$ (:strong
connectivity).  To formulate his result we need some notions and
notation.  For an undirected graph $G$, $d_G(X)$ denotes the number of
edges between $X$ and $V-X$.  Let $e(X)=e_G(X)$ (respectively,
$i(X)=i_G(X)$) denote the number of edges with at least one end (with
both ends) in $X$.  For a digraph $\vec D=(V,\vec A)$, $\varrho (X):=
\varrho _{\vec A}(X):= \varrho _{\vec D}(X)$ denotes the number of
edges entering $X$ and is called the {\bf in-degree} of $X$ (in $\vec
D$).  The function $\varrho _{\vec D}$ is called the {\bf in-degree
function} of $\vec D$.  Similarly, $\delta (X):= \delta _{\vec A}(X):=
\delta _{\vec D}(X)$ denotes the number of edges leaving $X$.

Let $M=(V,E+\vec A)$ be a mixed graph.  It is clearly an equivalence
relation of the nodes when two nodes $u$ and $v$ are in relation if
there are correct paths from $u$ to $v$ and from $v$ to $u$.  An
equivalence class $C$ is called a {\bf di-component.} If no directed
edge enters $C$, it is called an {\bf initial di-component.} Clearly,
$M$ is traversable precisely if there is only one equivalence class.


For a subset $Z\subset V$, let $c(M,Z)$ denote the number of those
initial di-components $C$ of $M-Z$ which are not entered by any
directed edge with tail in $Z$.  Since no undirected edge connects $C$
and $V-(Z\cup C)$, for any strongly connected orientation of $M$ there
must be at least one newly oriented edge with head in $C$ and tail in
$Z$, and therefore there are at least $c(M,Z)$ newly oriented edges
leaving $Z$.


Let $f:V\rightarrow {\bf Z} $ be a non-negative, integer-valued
function and let $f(Z):=\sum _{v\in Z} f(v)$.



%\vfill\eject

\bigskip

\noindent {\bf THEOREM 1.2} \lbrack Nash-Williams, 1995\rbrack \ {\sl
A mixed graph $M=(V,E+\vec A)$ has a strongly connected orientation
$(V,\vec E+\vec A)$ satisfying $$ \varrho _{\vec G}(v) \geq f(v)
\hbox{ for every}\ v\in V \eqno(1.2 )$$ if and only if $M$ is
traversable, $M$ has no undirected cut-edge, and $$e_G(Z) \geq f(Z) +
c(M,Z)\eqno(1.3 )$$ holds for every non-empty subset $Z\subseteq V$.}


\bigskip From the above considerations the necessity of (1.3) is easy.
Indeed, for an orientation $(\vec G+\vec D)$ of $M$ satisfying the
requirements, one has $e_G(Z) = \sum _{v\in Z} \varrho _{\vec G}(v) +
\delta _{\vec G}(Z) \geq f(Z) + c(M,Z)$.


Actually, Nash-Williams considered this orientation problem in a
slightly different form.  He wanted to find a partial orientation of
the undirected edges of $M$ (that is, not necessarily all undirected
edges have to get oriented) so that the resulting mixed graph is
traversable and $(*)$ there are exactly $f(v)$ newly oriented edges
entering every node $v$.  This problem, however, is equivalent to the
one in Theorem 1.2.  Indeed, if a required partial orientation exists,
then, by the theorem of Boesch and Tindell, the remaining undirected
edges can be oriented so as to obtain a strongly connected digraph.
This orientation clearly satisfies (1.2).  Conversely, if there is a
strongly connected orientation satisfying (1.2), then de-orienting a
sufficient number of newly oriented edges we obtain a traversable
mixed graph in which $(*)$ holds.

\bigskip

In the present paper we will show how a generalization of Theorem 1.2
can be derived via submodular flows.  As a main tool, we prove a
simplified feasibility theorem for submodular flows constrained by
crossing submodular functions.  The simplification is based on a the
notion of full-truncation of a set-function, a new form of what was
called earlier bi-truncation.

\newpage

\section{Anna Galluccio and Martin Loebl\\
Even cycle in directed graphs}

%\centerline{\Large Even cycle in directed graphs}

\bigskip
\begin{center}
{\it
\begin{tabular}{cc}
IASI - CNR & Department of Applied Mathematics\\
 & Charles University\\
 Roma & Prague \\
 ITALY & CZECH REPUBLIC\\
 {\tt galluccio@iasi.rm.cnr.it} & {\tt loebl@kam.ms.mff.cuni.cz}
\end{tabular}
}
\end{center}

\bigskip
\begin{abstract}
The aim of this note is to survey  different concepts together with
the results obtained so far, related 
to the {\bf Even Cycle Problem}, introduced in the beginning of seventies
 by Younger. This seemingly innocent problem to decide whether a directed graph contains an even length directed cycle belongs to the central problems of combinatorial optimization.
\end{abstract}


 
\subsection{Permanents and Determinants}
 
Let $A=(a_{ij})$ be an $n\times n$ matrix and $\pi$ a permutation in the 
symmetric group $S_n$.
The {\it permanent} of $A$ is defined as:

$$perm(A)=\sum_{\pi\in S_n} \prod_{i=1}^n a_{i\pi (i)}$$

\noindent
and it differs from computing the determinant of $A$ only for the 
sign of the permutations. In fact,

$$det(A)=\sum_{\pi\in S_n} sgn(\pi) \prod_{i=1}^n a_{i\pi (i)}.$$

\noindent
where $sgn(\pi)$ is $+1$ if the permutation $\pi$ is even and $-1$ 
otherwise. Now, while the determinant of
a matrix may be computed in polynomial time using the Gaussian
elimination, a computation of the permanent seems to be much harder.
Valiant (\cite{Val}) proved that it is $\#P$-complete, even for 
$(0,1)$-matrices. 
 
In 1913, Polya (\cite{Polya}) suggested
computing the permanent of a $(0,1)$-matrix by multiplying some
entries by $-1$ so that the original permanent becomes the
determinant of the resulting matrix. Such a transformation however
needs not exist, as noticed in the same year by Szego
(\cite{Szego}). 
 
Following this scheme let us call a $(0,1,-1)$-matrix {\it rigid}
if the nonzero terms in its determinant expansion all have the same sign.
A $(0,1)$-matrix is called {\it convertible} if it is possible
to multiply some of its entries by $-1$ to get a rigid matrix.

Note that the permanent of a $(0,1)$-matrix which is the adjacency
matrix of a bipartite graph $G$ equals to the number of perfect matchings
of $G$.


\subsection{The Number of Perfect Matchings and Pfaffians}

Let $D$ be a digraph on $n$ vertices. Let  
$B(D)=(b_{ij})$ be a skew-symmetric $m \times m$ matrix  defined by


$$b_{ij}=\left \{\begin {array}{ll}
1    & \mbox{if $v_iv_j$ is an arc of $D$}\\
-1   & \mbox{if $v_jv_i$ is an arc of $D$}\\ 
0    & \mbox{otherwise}
\end{array}
\right.$$

\noindent
The {\it Pfaffian} of a skew-symmetric matrix $B$ of size 
$2n\times 2n$ is defined as 
 
$$Pf(B)=\sum_{P} sgn(P) \times b_{i_1j_1} \cdots b_{i_nj_n}$$
 
\noindent
where $P=\{\{i_1j_1\},\cdots,\{i_nj_n\}\}$ is a partition of $\{1,\dots,2n\}$
into pairs and $sgn(P)$ equals to the sign of the permutation
$(i_1j_1,\dots,i_nj_n)$.
 
By a classical result of Cayley 
$det(B)=Pf^{2} (B)$ for a skew-symmetric matrix $B$.

Each  nonzero term of the expansion of the Pfaffian of $B(D)$ corresponds 
to a perfect matching of $D$. 
Hence all the nonzero terms of the expansion of the Pfaffian of $B(D)$ have 
the same sign if and only if $M(D)^{2} = det(B(D))$, where $M(D)$ denotes 
the number of perfect matchings of the underlying graph of $D$.
A digraph is called {\it Pfaffian} if it has this property.
A digraph obtained by orienting each edge of a graph $G$ is called 
an {\it orientation} of $G$. A graph is {\it Pfaffian} if it has 
a Pfaffian orientation.

Summarizing, if $G$ is Pfaffian and we know its Pfaffian orientation $D(G)$, 
the number of perfect matchings of $G$ may be computed in polynomial time
since its square is equal to $det(B(D(G)))$.

This method has been proposed by Kasteleyn in the beginning of sixties 
in order to compute the number
of perfect matchings of general graphs (\cite{Kast}).
He also showed that all planar graphs are Pfaffian and proved that a digraph $D$ is Pfaffian if 
and only if each alternating cycle $C$ of the underlying 
undirected graph $G$ (with respect to an arbitrary perfect matching of $G$) 
has an odd number of edges directed clockwise.
For an extension of the Kasteleyn's method see (\cite{GL6}).

In $1975$ Little \cite{Li2} observed that a matrix is convertible
if and only if it is the  incidence matrix of a
Pfaffian bipartite graph. In this seminal paper he also characterized the 
Pfaffian bipartite graphs in terms of a forbidden structure: he showed that 
a bipartite graph $G$ is Pfaffian if and only if it has an even subdivision
$K$ of $K_{3,3}$ with a perfect matching in $G-V(K)$. 

\subsection{Minimally non-bipartite hypergraphs, sign-nonsingular matrices
and even digraphs}



A {\it hypergraph} is a set of finite subsets (called {\it edges})
of a set whose elements are called {\it vertices}.
A hypergraph is {\it bipartite} if there is a subset of vertices
intersecting all the edges and containing none completely. 
%If a hypergraph $H$ is not bipartite but every proper subset of $H$
% is bipartite, than $H$ is called {\it condenser}.
% A hypergraph is {\it square} if it has the same number of vertices and edges.

%Let $D$ be a strongly connected directed graph. Let $H(D)$ be the
%hypergraph on the same vertex set and with the edges $\{x\}\cup
%\{y:$ $xy$ {\sl arc of} $D\}$,  $x$ vertex of $D$. 

%Observe that if $D$ has no even directed cycle then $H(D)$ is not bipartite. 

In $1973$ Seymour (\cite{Sey1}) proved that the recognition of non-bipartite
 hypergraphs with the same number of edges as vertices is equivalent to
 the even cycle problem.
This is important since the recognition of general bipartite hypergraphs
is an NP-complete problem.

%The characterisation goes as follows: every square condenser $H$ has a matching 
% of vertices and edges such that each edge is assigned to exactly one 
% vertex, which moreover belongs to it. Any such matching $M$ defines 
% a digraph $D(H)$ with the same vertices as $H$ and with the arcs
% $(xy)$, $y$ being an element of $M(x)$ different from $x$.
% The result of Seymour asserts that $D(H)$ is strongly connected
% and without even directed cycles.

%\section{Sign-nonsingular matrices}
 
A {\it sign-nonsingular matrix} is a real matrix such that the columns of
any real matrix of the same size and with the same sign pattern
are linearly independent. 

This notion appears in economics models, for details see the paper of Lancaster 
(\cite{Lanc}). 
 
The problem of recognizing sign-nonsingular matrices is proved to be
NP-complete by Klee, Ladner and Manber (\cite{KLM}) and also Brualdi and Shader (\cite{BS}). However, the
important special case of square sign-nonsingular matrices is
open, and in fact it is simply equivalent to the rigidity of
matrices.

It is proved by Butkovic (\cite{But}) that the even cycle problem is equivalent
 to testing regularity of matrices in min-algebra.
%let $A$ be a $(0,1,-1)$ matrix of size $n \times n$ and let
%$M=sgn(\pi) a_{1\pi(1)}\cdots a_{n\pi(n)}$ be a nonzero term of the
%determinant expansion of $A$. Let $B$ be a nonnegative matrix of
%order $n$  with the same zero pattern as $A$, with $b_{j\pi(j)}=1$,
%$j=1,\dots,n$ and with all the other nonzero entries  equal to a
%small positive $\epsilon$. Let $A*B$ denote the Hadamard
%(entrywise) product of $A$ and $B$.  $A*B$ has the same sign
%pattern as $A$ and $sgn(det(A*B))=M$. 

%Since the determinant is a continuous function, it follows that
%all the terms in the determinant expansion of a square $(0,1,-1)$ 
%sign-nonsingular matrix have the same sign. The inverse 
%statement also holds, so a square
%$(0,1,-1)$ matrix $A$ is sign-nonsingular if and only if all the terms 
%in its determinant expansion have the same sign if and only if A is rigid.

In $1987$ Seymour and Thomassen \cite{ST} introduced {\it even digraphs}.
A digraph $D$ is {\it even} if any subdivision of $D$
 has an even directed cycle. They showed that the Even Cycle
Problem is equivalent to the Even Digraphs Recognition Problem
and they characterized even digraphs in terms of a forbidden structure.
This has been extended in \cite{GL3} to a characterization of the digraphs $D$
 such that each subdivision of $D$ contains a directed cycle of length
 different from $p$ modulo $q$, for any $p,q$.

In $1989$ Vazirani and Yannakakis \cite{VY} observed that the Even Digraphs  
Recognition Problem is equivalent to recognition of convertible matrices.
Hence recognition of even digraphs and of Pfaffian bipartite graphs
are computationally equivalent. Moreover, the characterization of even digraphs due to Seymour and Thomassen and the characterization of Pfaffian bipartite graphs due to Little may be deduced one from the other (see \cite {GL5}).


\subsection{Computational Results} 

In $1975$ Lov\'asz (\cite{Lo2}) raised two questions:

Does there exist $k$ such that any digraph in which there are at least
 $k$ arcs leaving each vertex has a directed cycle of an even length?

Does there exist $k$ such that strongly $k$-connected digraph has
 a directed cycle of an even length?

\noindent
Partial results on these two questions were given by  Friedland 
(\cite{Fried}) and Alon and Linial (\cite{AL}). Thomassen disproved 
the first question in \cite{TH1} and settled the second one affirmatively in \cite{TH4}.
He proved that each strongly $3$-connected digraph has a directed cycle of 
 an even length. 
Each such digraph must have a directed cycle of length
different from $p$ modulo $q$ for any $p,q$ as observed in \cite{GL3}.

It is proved by Chung, Goddard and Kleitman
(\cite{CGK}) that every strongly connected digraph with $n$ vertices 
and at least $(n+1)^2/4$ arcs must contain a directed cycle of even length.

In $1990$ a polynomial-time algorithm to solve the Even Cycle Problem in
the class of planar digraphs was proposed by Thomassen 
(\cite{TH3}) and independently in \cite{GL1}.

This was extended in \cite{GL5} by showing that the Even Cycle Problem
(and more general modularity problems as well)
 for the digraphs of any class ${\cal D}$ closed for taking subdigraphs
 and subdivisions is solvable in polynomial time in case the
 $P_i$-homeomorphism Problem, $i \leq 5$, may be solved in polynomial 
 time in ${\cal D}$. $P_i$ denotes a path with $i$ vertices. The
 {\sl $H$-homeomorphism Problem} is defined as follows:
\begin{itemize}
\item[] let $H = (V(H),A(H))$ be a fixed digraph. Given a digraph $D = (V(D),A(D))$
 and a function $f$ from $V(H)$ to $V(D)$ such that $f(x) \neq f(y)$ for 
$x \neq y$, decide whether there is a homeomorphism from $H$ to $D$ which 
extends $f$.
\end{itemize}

The $H$-homeomorphism problem is known to be polynomially solvable
in the class of acyclic digraphs (i.e. digraphs without
directed cycles) (see \cite{FHW}) and in any class of digraphs
embedded on a fixed surface (see \cite{SCH,Schr2}). Hence, the same
 holds for the Even Cycle Problem.

On the other hand, if $H$ is not a star where all arcs go from
its center or to its center then the $H$-homeomorphism problem
in the class of all digraphs is NP-complete (see \cite{FHW}).

In the end of 1996, Robertson, Seymour and Thomas announced that the Even Cycle Problem is polynomially solvable for general digraphs.

In the end, let us mention that the problem ``Does a digraph $D$ have
 a directed cycle of length $p$ modulo $q$" is proved to be NP-complete
 for $p>0$ and $q>2$ in \cite{APY}.

\bibliographystyle{plain}

\bibliography{stirin}

\newpage

\section{Willem H. Haemers\\
Disconnected vertex sets and equidistant code pairs}

%\centerline{\Large Disconnected vertex sets}

%\smallskip
%\centerline{\Large and equidistant code pairs}

\bigskip
\begin{center}
{\it
Dept. of Econometrics\\
Tilburg University\\
P.O.Box 90153 \\
5000 LE \ Tilburg\\
THE NETHERLANDS\\
{\tt Haemers@kub.nl}
}
\end{center}

\bigskip
Let $G$ be a graph with vertex set $V$.
Two disjoint subsets $A$ and $B$ of $V$ are {\it disconnected} if
there is no edge between $A$ and $B$.
We define $\s(G)$ to be the maximum of $\sqrt{|A|\cdot|B|}$
for disconnected sets $A$ and $B$ in $G$.
Suppose $V$ is the set of words of length $n$ over an alphabet
$\{1,\ldots,q\}$ and define two words adjacent if their Hamming
distance (i.e. the number of coordinates in which they differ)
is not equal to a fixed $\d\in\{1,\ldots,n\}$.
Then a pair of disconnected sets becomes an {\it equidistant code 
pair}.

The quantity $\s(G)$ has an application in information theory and 
leads to a lower bound for the two-way communication complexity of 
functions defined on $V \times V$ that are constant over the 
non-edges of $G$.
About ten years ago this application caused some activity in the study
of equidistant code pairs.
The best result is due to Ahlswede~\cite{ahl}, who gives the exact 
value of $\s(G)$ for $q=2$, 4 and 5, for every $\d$ and $n$.

In this paper we will give a bound for $\s(G)$ in terms of the
eigenvalues of a matrix associated with $G$.
In case the complement of $G$ is given by a relation of an association
scheme the bound takes an easy form, which applied to the Hamming 
scheme leads to a bound for equidistant code pairs.
This bound is not as accurate as Ahlswede's result, but it is more 
general and it turns out to be sharp for some values of $q$, $n$ and 
$\d$, and for $q\rightarrow\8$ for any fixed $n$ and $\d$.

\begin{thebibliography}{99}
\bibitem{ahl} R. Ahlswede,
{\it On code pairs with specified Hamming distances,}
Colloquia Mathematica Societas J\'anos Bolya {\bf 52},
Combinatorics, Eger (Hungary), 1987, pp. 9-47.
\end{thebibliography}
\newpage


\section{Winfried Hochst\"attler and Jaroslav Ne\v{s}et\v{r}il\\
Farkas' Lemma and Morphism Duality}

%\centerline{\Large Farkas' Lemma and Morphism Duality}

\smallskip
\centerline{\Large (Extended Abstract)\footnote{The second author was 
partially supported  
by GA\v{C}R
    2167, GAUK 251}}

\bigskip
\begin{center}
{\it
\begin{tabular}{cc}
Universit\"at zu K\"oln & Department of Applied Mathematics (KAM)\\
Weyertal 86-90 & Malostransk\'e n\'am\v{e}st\'\i\ 25\\
  D--50931 K\"oln  & 118 00 Prague \\
 GERMANY & CZECH REPUBLIC\\
{\tt WH@MI.UNI-KOELN.DE} & {\tt nesetril@kam.ms.mff.cuni.cz}
\end{tabular}
}
\end{center}

%\author{Winfried Hochst\"attler\\ Universit\"at zu K\"oln, \and
%  Jaroslav Ne\v{s}et\v{r}il\thanks{Supported partially by GA\v{C}R
%    2167, GAUK 251}\\ Charles University, Prague}

%\title{Farkas' Lemma and Morphism Duality\\(Extended Abstract)}

\bigskip
%\pagestyle{myheadings}
%\markboth{W.~Hochst\"attler and J.~Ne\v{s}et\v{r}il}
%{Farkas' Lemma and Morphism Duality}

%\keywords{oriented matroids, strong maps, homomorphisms, duality}
%\mathsubject{05B35, 05C99, 18B99, 90C05}
%\begin{document}
%\zprtitle{95.209}{Linear Programming Duality and Morphisms}
%{W.~Hochst\"attler, J.~Ne\v{s}et\v{r}il}{~}{1995}{ W.~Hochst\"attler\\ 
%  Universit\"at zu K\"oln \\ Weyertal 86-90 \\ D--50931 K\"oln \\ 
%  Germany \\ Telefon (0221) 470--6012 \\ e--Mail {\scriptsize
%    WH@MI.UNI-KOELN.DE}\\ ~\\ J.~Ne\v{s}et\v{r}il\\ Department of
%  Applied Mathematic(KAM) \\Faculty of Mathematics and Physics,
%  Charles University \\Malostransk\'e n\'am\v{e}sti 25\\118 00 Praha
%  1\\Czech Republic\\{\scriptsize
%    NESETRIL@KAM.MS.MFF.CUNI.CZ} } 


%\maketitle
There is a great variety of combinatorial optimization results which
are of min-max type or ``good characterizations'' \cite{Edmonds} and
from the point of view of theoretical computer science these results
establish the membership in the class $NP \cap co$-$NP$. However, it
seems to be convenient for a better understanding to have a more
uniform and perhaps technically more fitting description of certain
classes of characterizations. The most important here is of course the
linear programming approach and the duality of linear programming
serves as a prototype and master theorem which implies many (but not
all) min-max results. Yet, there are other approaches for example the
lattice method of A.~Hoffman \cite{Hoffmann1}, \cite{Hoffmann2}, or
general methods related to the Ellipsoid Method~\cite{LGS}; see
also~\cite{Bland}. Another possible approach of algebraic flavour was
suggested in ~\cite{Pultr}, \cite{Komarek1}, \cite{Hell2} and relies
on the definition of classes by means of special morphisms. (Although
this has a definitive category theory flavour one does not make use of
any of the deep results of the theory of categories and thus we do not
have to use the formal language of this theory.) One proceeds as
follows:

Suppose that $\Kscr$ is a class of objects together with a certain
class of maps (``homomorphisms'', ``morphisms'') between them. Given
two objects $A,B$ of $\Kscr$ we denote by $A \to B$ the existence of a
map from $A$ to $B$. Given a fixed object $A$ we denote by

$$\to (A)$$

the class of objects of $\Kscr$ which map to $A$:

$$\to (A) \quad := \quad \{B \in \Kscr \mid B\to A\}.$$

Similarly, $ (A) \to \quad := \quad \{B \in \Kscr \mid A\to B\}.$

The complementary classes will be denoted by $\not \to (A)$ and $ (A)
\not \to$. Explicitly, $\not \to (A)$ is the class of objects which do
not map into $A$.

A {\em homomorphism duality theorem for $\Kscr$} is the following
equation of two classes

\begin{equation}
  (B) \to \quad = \quad \not \to (A).
\end{equation}


The equation $(\ast)$ is the equation of two classes and thus,
explicitly, it means:

For every object $C$ of $\Kscr: \quad B \to C$ iff $C \not \to A$.

Examples of homomorphism duality are numerous. The class of graphs and
homomorphisms between them was studied in greater detail in
\cite{Pultr}, \cite{Komarek1}, \cite{Hell2}, \cite{Hell3} (a
homomorphism $f: G \to H$ is any edge preserving mapping of the
vertices).  

The purpose of the full version of this paper \cite{homhom} is to
demonstrate the power of Homomorphism Duality-scheme $(\ast)$ by
showing that the duality theorem of linear programming, Farkas' Lemma,
may be interpreted within this framework. We can show that the
standard class of morphisms for oriented matroids yields a particular
instance of duality which is equivalent to Farkas' Lemma.  Moreover,
we show that with properly defined morphisms this is the only existing
duality.  Thus, in this setting, Farkas' Lemma is the only valid
duality (i.e.\ it is the only valid duality for oriented matroids with
a given class of maps.).

The use of oriented matroids for linear programming in the context of
homomorphism dualities was suggested by L.~Lov\'asz and A.~Schrijver
\cite{oral}. Our approach here is motivated by this and by their
question whether there exists a homomorphism duality for Farkas' Lemma
of such a form, that on both sides of the equation $(\ast)$ is the
same type of morphisms (as is the case for homomorphisms of graphs;
indeed our formulation of a homomorphism duality covers only such
cases).

Thus our main results have the simple form of a class-equation

\vspace{0.8em}


\noindent{\bf Theorem A:} {\em 
$$ (\Lscr,1)  \leadsto \quad = \quad \not \leadsto (\Lscr^\ast,1).$$
}

\vspace{0.8em}


where the objects are affine oriented matroids and the morphisms are
generalized affine strong maps which we define as alternating chains
of strong maps (for our purposes best done by means of the notion of
convexity) and their duals. Note that our construction of these maps
is analogous to several constructions in homology theory and as well
to the definition of a minor by means of homomorphisms.

It is interesting to note that in this setting Farkas' Lemma is the
only homomorphism duality. More precisely we have

\vspace{0.8em}

\noindent{\bf Theorem B:} 
  Let $(B,1) \leadsto \quad = \quad \not \leadsto (A,1)$ be a
  homomorphism duality theorem for oriented matroids and generalized
  affine strong maps. Then $(B,1)$ is morphic to the loop and $(A,1)$
  is morphic to the coloop.


\begin{thebibliography}{92}
\bibitem{Walter}
A.~Bachem, W.~Kern,
 \newblock {\em Linear Programming Duality: 
 An Introduction to Oriented Matroids,}
 \newblock {Springer, Berlin etc., (1992)}.

\bibitem{Bacik} R.~Bacik, S.~Mahajan, \newblock {``Interactive proof
systems and polynomial Algorithms,''} {\em (preprint).}

\bibitem{Guenter}
A.~Bj\"orner, M.~Las Vergnas, B.~Sturmfels, N.~White, G.~M.~Zieg\-ler,{\em 
 \newblock Oriented Matroids (Encyclopedia of Mathematics and its
Applications 46), Cambridge University Press, (1993).}

\bibitem{Bland}R.G.~Bland, B.L.~Dietrich,{\newblock ``An abstract
  duality,'' }{\em Discrete Math.~70 (1988), 203 -- 208.}

\bibitem{LasVegas}
R.~G.~Bland and M.~Las Vergnas: \newblock Orientability of Matroids
\newblock {\sl Journal of Combinatorial Theory, Series B 24 94-123
(1978)}
 
 \bibitem{Edmonds} J.~Edmonds, {\newblock ``Paths, Trees and
  Flowers,'' }{\em Canadian J.~Math.~17 (1965), 449--467.}

\bibitem{Farkas}
 G.~Farkas, {
\newblock ``Theorie der einfachen Ungleichungen,''
\newblock }{\em J.\ Reine Angew.\ Math.\ 124 (1902), 1 -- 27.}

\bibitem{Feder} T.~Feder, M.Y.~Vardi, { \newblock ``Monotone Monadic SNP
  and Constraint Satisfaction,'' }{\em Proc.~25th ACM STOC 1993, 612-622.}

\bibitem{Folkman}
J.~Folkman and J.~Lawrence:
 \newblock Oriented Matroids
 \newblock {\sl Journal of Combinatorial Theory, Series B 25 199-236 (1978)}

\bibitem{LGS} M.~Gr\"otschel, L.~Lov\'asz, A.~Schrijver, ``The
    Ellipsoid Method and its Consequences in Combinatorial
    Optimization,'' {\em Combinatorica 1, (1981), 169 -- 197}.

\bibitem{Hell1} P.~Hell, X.~Zhu, ``Homomorphisms to oriented
  paths,'' {\em Discrete Math (to appear).}

\bibitem{Hell2} P.~Hell, J.~Ne\v{s}et\v{r}il, X.~Zhu, { \newblock
``Duality and polynomial testing of tree homomorphisms,'' }{\em Trans.~
  Amer.~ Math.~ Soc.~(to appear).}

\bibitem{Hell3} P.~Hell, J.~Ne\v{s}et\v{r}il, X.~Zhu, { \newblock
``Complexity of tree homomorphisms,'' }{\em (submitted).}


\bibitem{Matusek}W.~Hochst\"attler, {\newblock ``A
    Note on the Weak Zone Theorem,'' }{\em Congressus Numerantium 98
    (1993), 95--103.} 

\bibitem{homhom}W.~Hochst\"attler, J.~Ne\v{s}et\v{r}il {\newblock ``Linear Programming
    Duality and Morphisms,'' }{\em submitted}

\bibitem{Hoffmann1}A.J.~Hoffman, D.E.~Schwartz, ``On partitions of
  partially ordered sets,'' {\em J.~Comb.~Th.~B {\bf 23}, (1977), 3--13.}

\bibitem{Hoffmann2}A.J.~Hoffman, ``On lattice polyhedra,'' {\em
    Proceedings 5th Hungarian Coll.~on Combinatorics, } pp.~593--598,
  North Holland, 1978.

\bibitem{Komarek1}P.~Komarek, \newblock ``Some New Good
    Characterizations of Directed Graphs,'' {\em Casopis.\ Pest.\ 
      Math.~51 (1984), 348--354.}

\bibitem{Komarek2}P.~Komarek, {\newblock \em Good Characterizations}, {
  Thesis, Charles University, Prague, 1983}.

\bibitem{oral}L.~Lov\'asz, A.~Schrijver, {\em (oral communication)}.

\bibitem{Minty} G.J.~Minty, {\newblock ``On the axiomatic foundations of
the theories of directed linear graphs, electrical networks and
network-programming,'' }{\em J.~Math.~and Mechanics, 15, (1966), 485 --
  520.}

\bibitem{Pultr} J.~Ne\v{s}et\v{r}il, A.~Pultr, {  \newblock
``On Classes of Relations and Graphs Determined by
Subobjects and Factorobjects,'' }{\em Discrete Math. 22(1978), 287--300.}

\bibitem{Nestril} J.~Ne\v{s}et\v{r}il, {\em  Theory of Graphs, }{SNTL,
  Praha, (1979).} 

\bibitem{Schrijver} A.~Schrijver, {\em Theory of Linear and Integer
  Programming}, Wiley-Inter\-science, Chichester (1986).

\bibitem{White}
N.~White (editor), {\em 
 \newblock Theory of Matroids (Encyclopedia of Mathematics and its
Applications 26),} Cambridge University Press, (1986).



\end{thebibliography}
\newpage


\section{Monique Laurent\\
Positive Semidefinite Programming for Max-Cut: Geometric Results}

%\centerline{\Large 
%Positive Semidefinite Programming for}

%\smallskip
%\centerline{\Large Max-Cut: Geometric Results}

\medskip
\centerline{\Large (In Memory of Svata Poljak)}

\bigskip
\begin{center}
{\it
LIENS\\
 Ecole Normale Sup\'erieure\\
Paris\\
FRANCE\\
{\tt monique@cwi.nl
%?
}

}
\end{center}

\bigskip
This talk is devoted to results obtained jointly with
Svata Poljak on the geometry of the semidefinite relaxation
for the max-cut problem.
Svata had, in fact, introduced me to this topic in September 1993 at
the occasion of a one month visit in Paris and  our collaboration
continued thereafter.

\medskip
Positive semidefinite programming has been applied successfully 
for several combinatorial optimization problems, in particular,
for  the maximum stable set problem in perfect graphs
(by the work of Gr\"otschel, Lov\'asz and Schrijver)
and, more recently, for the max-cut problem.
Goemans and Williamson have shown  how to design good 
and efficient approximation algorithms  for max-cut 
 by optimizing over the set
${\cal E}_n$ of $n\times n$ symmetric positive
semidefinite matrices with diagonal entries one.
Since then, it has been recognized that 
similar techniques apply for several other problems (such as max 2-sat, 
graph coloring, max $k$-cut, 
or maximum bisection problems)  using  the set ${\cal E}_n$ 
with possibly some additional linear constraints.

Our work with Svata focused, in particular, on trying to understand
the geometry of the set ${\cal E}_n$, that we called an 
{\it elliptope} (standing for {\it ellip}soid and poly{\it tope}).
Indeed, we believe that a better insight into the geometric 
properties of the elliptope could possibly  yield  
refinements and improvements on the algorithmic side.

\medskip
The elliptope ${\cal E}_n$ constitutes a linear (nonpolyhedral) relaxation 
of the usual cut polytope $P_n$. It retains several features of this polytope.
For instance, the elliptope ${\cal E}_n$ has vertices (that is, 
points on its boundary having a full-dimensional normal cone)
that correspond  precisely to the cuts of the complete graph $K_n$.
Moreover, $P_n$ and ${\cal E}_n$ have a lot of faces in  common 
 up to dimension $\log n$; in fact, any set of cuts in general
position yields a (simplex) face for  both $P_n$ and ${\cal E}_n$.
This geometric feature indicates that the elliptope is 
`wrapped' fairly tightly around the cut polytope.

As the elliptope is a nonpolyhedral convex body, the spectrum of its
face dimensions may be lacunary. This is indeed the case. All 
possible dimensions for the faces of ${\cal E}_n$ are known 
as well as for its polyhedral faces.
In fact, ${\cal E}_n$ has proper faces up to dimension 
$n-1\choose 2$ (faces of that maximum dimension 
being isomorphic to ${\cal E}_{n-1}$) and polyhedral faces up
to dimension about $\sqrt {2n}$.  Thus, though nonpolyhedral,
${\cal E}_n$ has yet large dimensional polyhedral faces.

It is possible to obtain a tighter relaxation of the cut 
polytope by strengthening  the linear 
inequalities that define the elliptope. Along this line, we find the 
so-called gap inequalities that contain many known classes of inequalities
such as triangle inequalities or hypermetric inequalities.
Gap inequalities turn out, however, to be fairly complicated.
Their structure is
far from being well understood. It is, for instance, not known whether 
there exist gap inequalities yielding facets 
of the cut polytope with  a gap greater than or equal to 2 
(that is, yielding new  facets not belonging to the known  class of 
hypermetric facets).

\medskip
It is well-known that every stable set problem on a graph $G$ 
can be easily formulated as a  max-cut problem on the graph $\nabla G$,
obtained from $G$ by adding a new node adjacent to all 
nodes of $G$. In fact, the same connection exists between 
the associated polytopes and their positive semidefinite relaxations
as well. Therefore, the set ${\rm TH}(G)$, which is the convex body 
considered by Gr\"otschel, Lov\'asz and Schrijver for
formulating the positive
semidefinite relaxation for the stable set problem on a graph $G$, can be seen as 
the intersection of the elliptope of the graph $\nabla G$ 
by a set of hyperplanes.
In this manner we have a unified setting for the various 
positive semidefinite approximations considered in the literature.

\medskip
Interestingly, the elliptope has also been intensively studied in
connection with other problems relevant to
combinatorial matrix theory. Indeed, the so-called completion problem 
for positive semidefinite matrices which has received a lot of attention in the literature
of linear algebra, is nothing but the problem of finding a closed-form description 
for projections of the elliptope ${\cal E}_n$.
The set of entries on which one projects can be seen as the edge set of a graph 
$G$ and then we have the problem of describing 
the elliptope ${\cal E}(G)$ of a graph $G$.
Good characterizations  are available for some classes of graphs;
for instance, for series-parallel graphs or for graphs 
without certain excluded wheels as induced subgraph.
The description of ${\cal E}(G)$ involves then 
certain conditions relying on the cut polytope of $G$.
\newpage

\section{Pavel Pudl\'ak\\
Lower bounds for cutting plane proofs}

%\centerline{\Large Lower bounds for cutting plane proofs}

%\smallskip
\centerline{\Large  (abstract of a lecture)}

\bigskip
\begin{center}
{\it
Mathematical Institute\\
Academy of Sciences \\
\v Zitn\'a 25\\
Praha\\
CZECH REPUBLIC\\
{\tt pudlak@beba.cesnet.cz}

}
\end{center}

\bigskip

We prove an exponential lower bound on the length of cutting
plane proofs. The proof uses an extension of a lower bound for
monotone circuits to circuits which compute with real numbers
and use nondecreasing functions as gates. 

In cutting plane proofs we use the usual propositional
variables $\p$ with the interpretation 0 = {\em false} and 1 =
{\em true}. A proof line is an inequality
$$
\sum_k c_kp_k\geq C,
$$
where $c_k$ and $C$ are integers. 

The {\bf axioms} are $p_k\geq 0$ and
$-p_k\geq -1$ (i.e. $0\leq p_k\leq 1$) for every propositional
variable $p_k$. 

The rules are
\begin{enumerate}
\item {\bf addition:} from $\sum_k c_kp_k\geq C$ and
$\sum_k d_kp_k\geq D$ derive $\sum_k (c_k+d_k)p_k\geq C+D$;
\item {\bf division:} from $\sum_k c_kp_k\geq C$ derive 
$\sum_k \frac{c_k}d p_k\geq \left\lceil\frac Cd\right\rceil$,
provided that $d>0$ is an integer which divides each $c_k$;
\item {\bf multiplication:} from $\sum_k c_kp_k\geq C$
derive $\sum_k dc_k p_k\geq dC$, where $d$ is an arbitrary
positive integer.
\end{enumerate}

Cutting plane system is a refutation system: we want to
refute a set of inequalities by deriving a contradiction,
represented as $0\geq 1$.

A {\em monotone real circuit} is a circuit which computes with
real numbers and uses arbitrary nondecreasing real unary and
binary functions as gates. 

We say that a monotone real circuit
computes a boolean function (uniquely determined by the
circuit), if for all inputs of 0's and 1's the circuit outputs
0 or 1.

\begin{ttheorem}\label{t-4}
Let $P$ be a cutting plane proof 
of the contradiction $0\geq 1$ 
from inequalities 
$$
\sum_{k}c_{i,k}p_k+\sum_{l}b_{i,l}q_l\geq A_i,
i\in I,
$$
$$
\sum_{k}c'_{j,k}p_k+\sum_{m}d_{j,m}r_m\geq B_j, j\in J.
$$
Suppose that all the coefficients $c_{i,k}$ are nonnegative, or all
the coefficients $c'_{i,k}$ are nonpositive, then one can
construct a  real monotone circuit $C(\p )$ such that for every 0-1 assignment
$\a $ for $\p $

   \medskip $C(\a )=0\quad \Rightarrow\quad
\sum_{k}c_{i,k}a_k+\sum_{l}b_{i,l}q_l\geq A_i, i\in I$ are
unsatisfiable, and 

   \medskip $C(\a )=1\quad \Rightarrow\quad
\sum_{k}c'_{j,k}a_k+\sum_{m}d_{j,m}r_m\geq B_j, j\in J$ are
unsatisfiable. 

\medskip \noindent The size of the circuit is polynomial in the
binary length of the numbers $A_i, i\in I, B_j, j\in J$ and the number of
inequalities in $P$.

Moreover, we can construct in polynomial time a cutting plane
proof of the contradiction 
$0\geq 1$ from inequalities 
$\sum_{k}c_{i,k}a_k+\sum_{l}b_{i,l}q_l\geq A_i, i\in I$ if $C(\a )=0$, 
respectively $\sum_{k}c'_{j,k}a_k+\sum_{m}d_{j,m}r_m\geq B_j,
j\in J$ if $C(\a )=1$; the length of this proof is less than
or equal to the length of $P$.
\end{ttheorem}

The idea of the proof is as follows. 
Given an assignment for the common
variables $\p$, we want to split the proof, so that we get a
refutation either from q-clauses or from r-clauses. Now the rule
which can mix variables $\q$ with variables $\r$ is the addition
of two inequalities. Thus our strategy is not to perform this
rule in such a case and keep two inequalities. In the original
proof this would spoil the divisibility condition for the
division rule, but as we replace variables $\p$ by an
assignment, we can treat them as a part of the constant term and
we do not need the divisibility condition for them. The final
inequalities in both proofs contain only constant terms and one
of them is contradictory. To find out which, it suffices to
compute successively the constant terms in one of the parts, say,
in the $\q$ inequalities, which can be done by a monotone real
circuit.  

The following theorem is proved by adapting Razborov's lower
bound on monotone boolean circuits \cite{razb-lower} to monotone real circuits.

\begin{ttheorem}\label{t-mon}
Suppose that the inputs for a monotone real circuit $C$ are 0-1
vectors of length ${n\choose 2}$ encoding in the natural way
graphs on an $n$-element set.  Suppose that $C$ outputs 1 on all
cliques of size $m$ and outputs 0 on all complete $m-1$-partite
graphs where $m=\lfloor\frac 18 (n/\log n)^{2/3}\rfloor$. Then
the size of the circuit is at least 
$$ 
2^{\Omega((n/\log n)^{1/3})}.  
$$
\end{ttheorem}

Let $n$ and $m$ be given. We shall
use variables $p_{i,j}$, $1\leq i<j\leq n$ to code a graph on $n$
vertices; variables $q_{k,i}$ will code a one-to-one mapping from
an $m$ element set into the vertices of the graph; variables $r_{i,l}$ 
will code an $m-1$-coloring of the graph. Hence the following
inequalities express that a graph contains  a clique of size $m$
and it is $m-1$-colorable.
\begin{equation}\label{e-a}
\sum_i q_{k,i}\geq 1,\quad\mbox{ for }k=1\dts m;
\end{equation}
\begin{equation}
\sum_k q_{k,i}\leq 1,\quad\mbox{ for }i=1\dts n;
\end{equation}
\begin{equation}
p_{i,j}-q_{k,i}-q_{k',j}\geq -1\quad\mbox{ for }1\leq i<j\leq n,
1\leq k,k'\leq m, k\neq k';
\end{equation}
\begin{equation}
\sum_l r_{i,l}\geq 1,\quad\mbox{ for }i=1\dts n;
\end{equation}
\begin{equation}\label{e-z}
p_{i,j}+r_{i,l}+r_{j,l}\leq 2,\quad\mbox{ for }1\leq i<j\leq n,
                                         l=1\dts m-1.
\end{equation}
As there are no such graphs the inequalities are inconsistent.
The decision whether 
the first three are inconsistent or the last two are inconsistent is equivalent
to the decision whether the graph coded by $p_{i,j}$'s does not contain
an $m$-clique or it is not $m-1$-colorable. Thus combining
Theorems \ref{t-4} and \ref{t-mon} we get:

\begin{corollary}
Any cutting plane proof of $0\geq 1$ from the inequalities
(\ref{e-a}) -- (\ref{e-z}) has at least $2^{\Omega((n/\log n)^{1/3})}$
steps.
\end{corollary}

\begin{thebibliography}{1}

\bibitem{bonet-pitassi-raz}
Bonet, M., Pitassi, T. and Raz, R., {\it Lower bounds for
Cutting Planes proofs with small coefficients,} Proc. 27-th
STOC, 1995, 575-584.

\bibitem{razb-lower}
A.A. Razborov, {\it Lower bounds on the monotone complexity of some
boolean functions,} Doklady Akad. Nauk SSSR 282, (1985), 1033-1037


\bibitem{pudlak} Pudl\'{a}k P.: {\it Lower bounds for resolution and
cutting plane proofs  and monotone computations,} to appear in The
Journal of Symbolic Logic.

\end{thebibliography}
\newpage

\section{Andr\'as Seb\H o\\
Gaps and Jumps}

%\centerline{\Large Gaps and Jumps}

\bigskip
\begin{center}
{\it
CNRS, Laboratoire Leibniz-imag\\ 
Dept. of Discrete Mathematics\\
Grenoble\\
FRANCE\\
{\tt Andras.Sebo@imag.fr.}
}
\end{center}

\bigskip
A {\em jump system\/} \cite{BC} is a set $J\subseteq\Zset ^n$ with the
property that for all $x,y\in J$ and each vector $x'$ at one step from
$x$ towards $y$ there exists a vector $x''\in J$ at one step from $x'$
towards $y$.  (We say that $x'$ is at one step from $x$ towards $y$ if
$x'-x$ is $\pm 1$ times a unit vector and the non-zero coordinate of
$x'-x$ has the same sign as the corresponding coordinate of $y-x$.)

Jump systems generalize, among others, matroids, delta-matroids,
and degree sequences of the subgraphs of a graph (easy exercises, see
also \cite{BC}, \cite{CK}).
Their convex hulls constitute the most general class of polyhedra for
which the greedy algorithm works.

They have a property which is substantially new comparing to most
objects of polyhedral combinatorics: they do not contain all
the integer  points of their convex hull.  Those they do
not contain -- called {\it gaps} -- are the subject of this talk.  The
study of gaps allows to cease and generalize some phenomena of matching
theory, which can then also be applied elsewhere.

In the first part of the talk I explain the fundamental results of
Lov\'asz (proved at a previous meeting partially supported by DONET)
\cite{L2}.

These generalize the main ideas of well-known structure theorems in
matching theory.  Then I show some particular consequences that came out
of discussions of Cunningham, Geelen and Seb\H o using Lov\'asz's
toolbox.  (A joint article with a complete account of the results is
under preparation.)  Namely, it will be proved that every gap is the
average of two closest points of the jump system.  This result is then
used to derive several consequences.

In this extended abstract I  cover most of the talk,
including the hints of the proofs.
An interested reader might reconstruct the full proofs along these
lines.

\vskip 0.3cm\noindent{\bf 1. Lov\'asz's structure theory}\vskip 0.1cm


The {\em membership problem}: Let $v\in\Zset ^n$. Is $v\in J$ true ?  It
is not possible to give a `good' (characterization) answer to this
question, since that would imply  a good characterization for general
matroid matching. Still, Lov\'asz's theorem provides an answer which
becomes a good characterization in important special cases including
matroid intersection, or graph factors.
%It is advisable to keep the example
%of graph factors in mind in order to understand the kind of
%difficulties we may encounter about gaps; it may
%help to give a more concrete sense to the related results.

A {\em box} is a set of the form $\{x\in\Rset ^n: a\le x\le b\}$, where
$a,b\in\Rset ^n$, $a\le b$. For $x,y\in\Rset^n$ we use the notation
$d(x,y)=\sum _{i=1}^n |x_i-y_i|$, and for $X,Y\subseteq\Rset^n$,
$d(X,Y)=$inf$\{d(x,y):x\in X, y\in Y\}$ (this infimum will always
be a minimum). If $J$ is a jump system and $A$ is a box, then
let $J_A:=\{x\in J: d(x,A)=d(J,A)\}$.

The following lemma is the most important simple tool for proving
a certain kind of statements.  It often happens that proofs are
simplified by applying it with a better chain of
boxes. It is actually often more convenient to use this,  than
the subsequent theorem.

\vskip 0.2cm\noindent
{\bf The Common Optimum Lemma}:\cite{L2}
{\sl If $A\supseteq \ldots \supseteq Z$ are boxes, then
$J_A\cap\ldots\cap J_Z\ne\emptyset$.}

\vskip 0.1cm\noindent
{\bf Proof}: (hint)
First, prove that an arbitrary $x\in J$ can be `$A$-pushed' to $J_A$,
that is, there exist a sequence $x_0:=x,x_1,\ldots ,x_t=a\in J_A$,
($x_i\in J$), so that $x_i$ is at one or two steps from $x_{i-1}$ and
$d(x_i,A)\le d(x_{i-1},A)$, $i=1,\ldots , t$.

Second, remark that in case $A\supseteq B$, an $A$-push is also a
$B$-push.

Third, finish the proof by deleting $A$
%(the biggest set)
and using
induction: let $x\in J_B\cap\ldots\cap J_Z$ and apply the first proven
statement to $x$ and $A$; then apply the second remark  to
conclude.\qed


We state only a restricted version of Lov\'asz's theorem, which
contains though the main point, and everything we will need later.
(To restrict oneself to the box $0\in\Rset^n$ does not really restrict
generality.)  The folowing notation and this way of stating Lov\'asz's
theorem was introduced by Jim Geelen:
let $V^+:=\{i\in\{1,\ldots ,n\} : \hbox{ there exists  $x\in J_0$ with
$x_i>0$}\}$,
$V^-:=\{i\in\{1,\ldots ,n\} : \hbox{ there exists  $x\in J_0$ with
$x_i<0$}\}$.

\vskip 0.2cm\noindent
{\bf Lov\'asz's theorem}:
{\sl If $J\subseteq \Zset^n$ is a jump system, then there exists a
unique maximal box $\bar 0$ so that $0\in\bar 0$ and
dist$(J,\bar 0)=$dist$(J,0)$. Moreover $$\bar
0=(-\infty,0]^{V^+\setminus V^-}\times [0,\infty)^{V^-\setminus
V^+}\times 0^{V^+\cap V^-}\times (-\infty ,\infty)^{V\setminus (V^+\cup
V^-)},$$  for all $v\in J_0$ and $i\in V^+\cap V^-$,
$v_i\in\{-1,0,1\}$,
and resigning $v$ on $V^+\cap V^-$ in an arbitrary way we get again a
vector in $J_0$.}


\vskip 0.1cm\noindent
{\bf Proof}: (hint) If there were two maximal boxes with the stated
property, then taking for every $i$ the union and the intersection of
their defining intervals, we get two boxes, $A$ and $B$, $A\supseteq B$.
But then $J_A\cap J_B\ne\emptyset$ by the Common Optimum Lemma, and
dist$(J, A)=$dist$(J,0)$ follows easily, in contradiction with the
maximality of the original boxes. The other two statements also follow
by applying the Common Optimum Lemma to a pair of appropriate boxes.
\qed


\vskip 0.2cm\noindent
{\bf Example}: The Gallai-Edmonds structure theorem for matchings
describes the set of maximum matchings of a graph $G$ with the help of a
partition of the vertex-set into three sets $D(G)$, $A(G)$, $C(G)$ (see
\cite{LLP} page 94).  Let us partition $D(G)$ into two sets, $D_1(G)$,
$D_2(G)$, where $D_1(G)$ is the union of components of $D(G)$ consisting
of one vertex, and $D_2(G)$ is the union of the bigger components.  Now
let $J$ consist of the degree vectors of subgraphs of $G$ after
subtracting  the all
$1$ vector from each: dist$(J,0)$ is then the deficiency of a maximum
matching.
(It is easy to see that we cannot get closer to the all $1$ vector
if besides vertices of degree 0 and 1, we also allow vertices of degree
$2$.)  It can be checked now that
%the sets $V^+$ and $V^-$ are
%defined by:
$V^+\cap V^-=D_2(G)$, $V^-\setminus V^+=D_1(G)$,
$V^+\setminus V^-=A(G)$, $\{1,\ldots ,n\}\setminus (V^+\cup V^-)=C(G)$
(these four sets correspond to the for types of intervals in Lov\'asz's
theorem, whence they immediately define $\bar 0$).


\vskip 0.3cm\noindent{\bf 2. Gaps}\vskip 0.1cm

Given $x\in\Zset^n$ and a jump system $J\subseteq \Zset^n$,
$x\notin J$ can have two very different reasons:

\noindent
 1. $v\notin$conv$(J)$.

\noindent
 2. $v\in$conv$(J)\setminus J$, that is, $v$ is a {\em gap}.

In the first case we have a convincing certificate of the
non-membership. Our goal here is to show some surprising consequences if
the second case holds.

%\noindent
%{\bf Corollary} (Fat Box Theorem) {\sl }
%
%\noindent {\bf Proof}:
%
%\qed
%When is given vector in the convex hull of matching degree sequences  ?
%For instance the all $1$ vector is in the convex hull if and only
%there
%is a $2$-factor. So useful to separate into two parts the reason of not
%being in the convex hull. On the example:

On the example of matchings: a first reason for the nonexistence of a
perfect matching in a graph can be that the all $1$ vector is not
in the convex hull of degree sequences of subgraphs of $G$. (This is
the case if and only if there is no $2$-matching in the graph, and then
the corresponding violated linear condition is a good certificate.)
In case the all $1$ vector is in the convex hull
the essential part of Tutte's theorem enters the game.

In case $0$ is a gap there exists vectors in $J_0$ which
have more particular properties than those claimed by
Lov\'asz's theorem:

\vskip 0.2cm
\noindent {\bf Theorem}: {\sl If $J$ is a jump-system and $0\in\Zset^n$
is a hole in $J$, then there exists $v\in J_0$ so that $v\in \{0,1\}^n$;
 every signing of of $v$ is in $J$.}


\vskip 0.1cm
\noindent {\bf Proof}: (hint) Let $A=(-\infty,0]^{V^+\setminus V^-}
\times[0,\infty)^{V^-\setminus V^+}\times (-\infty ,\infty)^{V\setminus
V^+\triangle V^-}$, where $V^+\triangle V^-=(V^+\setminus V^-)\cup
(V^-\setminus V^+)$, and $B=0$. By the Common Optimum Lemma
$J_A\cap J_B\ne\emptyset$. Now an arbitrary $v\in J_A\cap J_B$ will do !
(It is not trivial though that $v$ has the claimed properties: one first
has to show, using Lov\'asz's theorem, that dist$(J,A)=0$, implying
$v\in A$. Now compare $A$ with what Lov\'asz's theorem claims.)
\qed

\vskip 0.1cm
\noindent
{\bf Corollary 1}: {\sl If $J$ is a jump-system, and $h\in\Zset^n$ is a
hole in $J$, then there exist $x,y\in J_h$ :
$h=(x+y)/2$.}\qed

\vskip 0.2cm
A jump system $J\subseteq \{0,1\}^n$ is called a {\em delta-matroid}.
If the charcteristic vector of a subset of $\{1,\ldots
,n\}$ is in $J$, then it is called a {\em feasible set}.  If all
feasible sets have even cardinality, the delta-matroid is said to be
{\em even}.  It is a well-known problem of Bouchet and Jackson to
characterize the existence of a partition of $\{1,\ldots, n\}$ into
two feasible sets of an even delta-matroid. The following
corollary, conjectured by Cunningham, shows a half-integer
weakening.


\vskip 0.1cm\noindent
{\bf Corollary 2}: (The feasible set double cover theorem) {\sl Let $J$
be a jump-system and suppose there exist two vectors in conv$(J)$ which
sum up to the all $1$ vector.  Then there exist $v_1,v_2,v_3,v_4\in J$
such that $1=(v_1+v_2+v_3+v_4)/2$.}


\vskip 0.1cm
\noindent {\bf Proof}:  Let $F=\{v_1+v_2: v_1,v_2\in J\}$. According to
a lemma of
Bouchet and Cunningham \cite {BC}, $F$ is a jump system, so the previous
corollary can be applied: $1=(x+y)/2$, $(x,y\in F)$. \qed

It is well-known that $J_B$ is a jump system (see a lemma in \cite{L2}),
and it follows easily that the faces of $J$ (that is sets of the form
$J\cap F$, where $F$ is a face of conv$(J)$)  are also jump
systems.
It was conjectured by Tamir that  in case $a\in\{-1,1\}^n$
the face of vectors in $J$ optimizing $a$ also constitute a jump system.
%(Such faces are not very special:
%it is also well-known \cite{BC}, \cite{L2} that every face can
We prove this conjectre in the following sharper form:

Denote  max$(J,a):=\{v\in J: a^Tv=
\hbox{max$_{x\in J}a^Tx$}$.
The projection (restriction) of a set of vectors $W\subseteq \Rset ^n$
onto $I\subseteq \{1,\ldots ,n\}$ is $\{(x_i:i\in I) : x\in W\}$.

\vskip 0.1cm\noindent
{\bf Corollary 3}: {\sl Let $J$ be a jump-system, and $a\in
\{-1,0,1\}^n$. The projection $F$ of max$(J,a)$ onto the support of $a$
is a convex jump system.}


\vskip 0.1cm\noindent
{\bf Proof}: We know that $F$ is a jump system. Suppose
without loss of generality that $0\in\Rset ^n$ is a hole of $F$.
According to Corollary 1 there exists a vector $y\in F_0$ such that
$-y\in F_0$, without loss of generality $y\ge 0$. But since $F$ is a
jump system, if $y'=y-e_i$ is at one
step from $y$ towards $-y$, there exists a second step $y''=y'-e_j\in F$
at one step from $y'$ towards $-y$. Note that $y'\in F$ is not possible,
because then $d(y',0)<d(y,0)$ contradicting $y\in F_0$, and
for the same reason $j=i$. Since $i$ is in the support of
$a$, for $y$ and $y''=y-2e_i$
(or more precisely for the vectors whose projections
are $y$ and $y''$) $a^Ty=a^Ty''$
cannot hold. \qed

The following theorem was first proved by Cunningham many years ago
with submodular and matrix techniques.

\noindent {\bf Corollary 4} {\sl Let $J_1$ and $J_2$ be jump-systems.
Then conv$(J_1)\cap$conv$(J_2)$ is a half-integer
polyhedron.}


\vskip 0.1cm\noindent
{\bf Proof}: It is enough to prove that
conv$(J_1)\cap$conv$(J_2)$, if non-empty, has a half
integer point, because then this statement can be applied
to faces (which, as already mentioned, are also jump
systems). But conv$J_1\cap$conv$J_2\ne\emptyset$ if and
only if $0\in$conv$\{v_1-v_2:v_1\in J_1, v_2\in J_2\}$.
The set of differences, as it has already been mentioned,
is a jump system (\cite{BC}), denote it by $J$. If $0\in
J$, we are done; if not, $0$ is a hole, and applying
Corollary 1, $0=x+y$: $x,y\in J$, that is, $x=x_1-x_2$,
$y=y_1-y_2$, $(x_i,y_i\in J_i, i=1,2)$. Substituting  and
rearranging: $x_1+y_1=x_2+y_2$. Dividing by two the left
hand side is in conv$(J_1)$, the right hand side in
conv$(J_2)$.
 \qed

\vspace {-5mm}
\begin{thebibliography}{aaa}
\bibitem{BC}
A. Bouchet, W. Cunningham, Delta-matroids,  Jump-systems and
Bisubmodular polyhedra, SIAM J. DIscrete Mathematics,  February 1995.
\bibitem{CK}
W.H. Cunningham and J. Green-Kr\'otki,
$b$-matching degree-sequence polyhedra,
{\it Combinatorica} {\bf 11} (1991) 219-230.
\bibitem{L2} L. Lov\'asz, The membership problem in jump systems,
Workshop on bisubmodular polyhedra, Grenoble, June 1995, to appear in
JCT/B.
\bibitem{LLP} L. Lov\'asz, M. Plummer, Matching Theory, Akad\'emiai
Kiad\'o, Budapest (1986)
\end{thebibliography}
\newpage

\section{Bruce Reed, Neil Robertson, Paul Seymour and Robin Thomas\\
Packing directed circuits}

\bigskip
\begin{center}
Bruce Reed\footnote{Research partially supported by DONET
ECHM contract CHRXCT930090.}\\
{\it
Equipe Combinatoire, Case 189\\
Universit\'{e} de Paris VI\\
4 Place Jussieu\\
75252 Paris Cedex 05\\
FRANCE\\
}
\vspace{.2in}
Neil Robertson\footnote{Research partially supported by 
DIMACS, by NSF grant DMS-8903132 and by ONR grant N00014-92-J-1965,
and partially performed
under a consulting agreement with Bellcore.} \\
{\it
Department of Mathematics\\
Ohio State University \\
231 W. 18th Ave. \\
Columbus, Ohio 43210, USA \\
}
\vspace{.2in}
Paul Seymour \\
{\it
Bellcore\\
445 South St.
\\
Morristown, New Jersey 07960, USA
\\
\vspace{.2in}
}
and
\\
\vspace{.2in}
Robin Thomas\footnote{Research partially supported by
DIMACS, by Universit\'{e} de Paris VI, by NSF grant DMS-9303761 and by ONR 
grant N00014-93-1-0325,
and partially performed under a consulting agreement with Bellcore.}
\\
{\it 
School of Mathematics\\
Georgia Institute of Technology \\
Atlanta, Georgia 30332, USA\\
{\tt thomas@math.gatech.edu}
}
\end{center}

\bigskip
A well-known theorem of Erd\H{o}s and P\'{o}sa  states
the following.
\\
\\
(1)
\begin{em}
For any integer $n \geq 0$ there exists an integer $t \geq 0$
such that for every graph G, either G has n circuits that are
pairwise vertex-disjoint, or there exists $T \subseteq V(G)$
with $|T| \leq t$ such that T meets every circuit of $G$.
\end{em}
\\
\\


In 1973, Younger conjectured that there was an analogue of (1) for
directed circuits in digraphs. (The question probably occurred to other
workers before then - for instance, it seems that Fulkerson worked on it
in the 1950's, but put nothing in print.)
For $n=0$ and 1 this is obvious.
For $n=2$ it was conjectured independently by Gallai  (who also
considered the $n>2$ case without publishing it), and eventually
was answered by McCuaig  in the following strong form.
\\
\\
(2)
\begin{em}
For every digraph G, either G has two vertex-disjoint directed
circuits, or there exists $T \subseteq V(G)$ with
$|T| \leq 3$ such that T meets every directed circuit of G.
\end{em}

But Younger's conjecture in general (and even for $n=3$)
has remained open until the present.
For a digraph $G$ we denote by $\nu (G)$ the maximum $n$ such that $G$
has $n$ directed circuits, pairwise vertex-disjoint, and by $\tau (G)$
the minimum $t$ such that there exists $T \subseteq V(G)$ with
$|T| = t$ meeting all directed circuits.
Evidently
$\nu (G) \leq \tau (G)$, and Younger's conjecture is that $\tau (G)$
is at most $f( \nu (G))$ for some function $f$ independent of $G$.
Thus, our main result  is the following.
\\
\\
(3)
\begin{em}
For every integer $n \geq 0$ there exists a (minimum) integer
$t_{n} \geq 0$ such that for every digraph G, either
$\nu (G) \geq n$ or $\tau (G) \leq t_{n}$.
\end{em}

Let $t_{n}$ be defined as in (3); we 
prove by induction on $n$ that $t_{n}$ exists for all $n$.
Obviously $t_{0} = t_{1} =0$, and from McCuaig's theorem
$t_{2} =3$.

We prove an upper bound on $t_{n}$, but it is very
large (a multiply iterated exponential, where the number of iterations is
also a multiply iterated exponential) 
and probably far from best
possible. The best {\em lower} bound on $t_{n}$ that we know is 
$O(n log(n))$, due to Alon (unpublished).



The proof is organized as follows.
First, we apply Ramsey's theorem to deduce a lemma which implies
 that to prove (3) in general, it suffices
to prove it for digraphs in which each vertex has indegree and
outdegree 2, and with a number of other properties.
Then we prove a second lemma that says roughly that if
$G$ has as a subdigraph a kind of grid together with some
additional paths, then $\nu (G)$ is large.
Third, we prove that digraphs with the properties implied
by the first lemma  do contain such grids.
Finally,  we use (3) to obtain a polynomial-time
algorithm for the problem.
\newpage

\section{Carsten Thomassen\\
The genus problem for graphs}

%\centerline{\Large The genus problem for graphs}

\bigskip
\begin{center}
{\it 
Department of Mathematics\\
building 303\\
Technical University of Denmark\\
 DK-2800 Lyngby\\
DENMARK\\
{\tt C.Thomassen@mat.dtu.dk}
}
\end{center}

\bigskip

The genus problem, which is mentioned as unsolved problem 3 in the book by 
Garey and Johnson on NP-completeness is the following: Given a graph $G$ and a 
nonnegative integer $g$, is it possible to draw (or embed) $G$ on the 
orientable 
surface of genus $g$, that is the sphere with $g$ handles added. A special 
variant was suggested already at the 1976 Kalamazoo conference by Gerhard 
Ringel: Given a graph $G$, is it possible that $G$ triangulates some orientable 
surface. If $g$ denotes the genus of that surface, and $n,e$ denote the number of 
vertices and edges, respectively, of $G$, then Euler's formula implies that
                   $$   e=3n-6+6g. $$

Hence there is only one orientable surface that $G$ may triangulate. Any other 
surface that $G$ can be drawn on must have larger genus. Hence Ringel's 
question is a special case of the genus problem. The motivation for Ringel's 
question is that a sufficiently simple solution the the triangulation problem 
might result in a unified proof of the genus problem for complete graphs 
which was raised in 1890 by Heawood and solved about 80 later by Ringel and 
Youngs. 

In 1989 ({\em J.Algorithms\/} {\bf 10}, 568-576) I proved that the genus problem is NP-
complete. In 1993 ({\em J.Combinatorial Theory B\/} {\bf 57}, 196-206) I proved that even 
the more special problem of Ringel is NP-complete. In 1991 Bruce Richter 
(private communication) pointed out that vertices of large degree play an 
important role in the construction and asked about the complexity of the 
genus problem when restricted to cubic graphs. In some sense, this problem is 
dual to the triangulation problem, but the NP-completeness of the 
triangulation problem does not seem to have immediate consequenses to the 
dual problem. First of all, we do not know the dual graph before we know the 
embedding. Secondly, the property of being a minimum genus embedding is not 
preserved under duality.

 Also, the complexity of a graph problem may change when we restrict the 
problem to cubic graphs. For example, the graph isomorphism problem for cubic 
graphs is polynomial. But, the complexity for general graphs is not known.

In a forthcoming paper in {\em J.Combinatorial Theory B\/}, I prove the following.

\bigskip\noindent
{\bf Theorem.} The genus problem for cubic graphs in NP-complete.

\bigskip
The proof easily extends to $r$-regular graphs for $r$ equal to 4 or 5 and 
probably, with a little more effort, to any fixed $r$. But, if $r$ is not fixed 
the situation is different. I believe that the genus problem is polynomial 
for graphs with $n$ vertices all of which have degree $99n/100$ since I believe 
that every such graph (almost) triangulates a surface in which case the genus 
is simply determined by the number of vertices of the graph. The complexity 
may be different for graphs with $n$ vertices all of which have degree $n/100$.
\newpage


\section{Eberhard Triesch\\
Elusive Graph Properties}

%\centerline{\Large Elusive Graph Properties}

\bigskip
\begin{center}
{\it
Forschungsinstitut f\"ur Diskrete Mathematik\\
 Nassestra\ss e 2\\
 D-53113 Bonn\\
GERMANY\\
{\tt triesch@or.uni-bonn.de}
}
\end{center}

\bigskip
 \subsection{Introduction.}
Let $T$ be some finite set and denote by $\cal P$ a property of subsets of $T$,
i.e. ${\cal P}\subset 2^{T}$, the power set of $T$. Imagine two players $\A$ ({\sl Algy\/}) and $\S$ ({\sl Strategist\/}). playing the following game:
Player $\A$ wants to learn from $\S$ whether an unknown set $X\tm T$ is in $\P$ or not by asking
him questions of the form ${\sl Is\ }x\in\ X$? $(x\in T)$.
The goal of $\A$ is to minimize the number of questions but $\S$ wants
to force $\A$ to ask as many questions as possible.
If both players play optimally from their point of view,
then the number of questions which are asked in the game
is called the {\sl recognition complexity} of $\P$
(also: {\sl Boolean decision tree complexity}) and is denoted by $c(\P)$.
If $\S$ can force $\A$ to probe all elements of $T$,
then $\P$ is called {\sl elusive} (also: {\sl evasive}).
As an example for proving lower bounds for $c(\P)$, associate with $\P$
its so-called {\sl enumeration polynomial} $q(\P,z)$ (first introduced in
\cite{BBL} and \cite{RV}):
$$q(\P,z):= \sum_{X\in \P}z^{|X|}=\sum_{i=1}^{|T|}a_i(\P)z^i.$$
Then $a_i(\P)$ is the number of $i$--element sets in $\P$.
If $(1+z)^k$ does not divide $q(\P,z)$, then $c(\P)>|T|-k$.
In fact, suppose that $\A$ asks the element $x$ as his first question.
This question divides $\P$ into two disjoint subsets $\P_1$ and $\P_2$,
namely the sets in $\P$ containing $x$ and those which do not.
We clearly have
$$q(\P,z)=q(\P_1,z)+q(\P_2,z).$$
Hence, if $(1+z)^k$ does not divide $q(\P,z)$, it does not divide at least one of the summands
$q(\P_i,z)$. Now $\S$ answers in such a way that the set of all sets in $\P$
compatible with all the answers given has an enumeration polynomial not divisible by $(1+z)^k$.
Following the same strategy for questions $2,3,\ldots$, we see that after $|T|-k$
questions, the subsets of $T$ compatible with all the answers
form an interval $\cal I$ of length $k$ in the Boolean lattice $2^T$. Because $(1+z)^k$
does not divide the enumeration polynomial of ${\cal I}\cap \P$, 
it follows that some of the sets in $\cal I$ are in $\P$ and some are not. Hence,
at least one further question must be asked.
In particular, if $1+z$ does not divide $q(\P,z)$, then $\P$ is elusive. 


The recognition complexity has been studied by various authors during the last 23 years
(see all the references except \cite{Ol} and \cite{Sm}). The greatest efforts
have been devoted to the case that $T$ equals $\V$,
the set of two--element subsets of some finite set $V$.
In this case the subsets of $T$ can be interpreted as graphs with vertex set $V$.
A {\sl graph property} is a subset $\P\tm 2^T$, $T=\V$, such that $\P$ contains
with each graph $G$ also each isomorphic copy of $G$ (with vertex set $V$). A graph
property $\P$ is called {\sl nontrivial} if $\P\neq \emptyset, \P\neq 2^{T}$. It is called {\sl decreasing} if, for each $G\in\P$, all subgraphs of $G$ (with vertex set $V$) are contained in $\P$, {\sl increasing} if $2^{T}\setminus\P$ is decreasing and {\sl monotonic} if it is increasing or decreasing.


In 1973, Rosenberg \cite{Ro} conjectured that there exists some $\g>0$ such that
$$c(\P)\ge \g n^{2}$$
for all nontrivial graph properties $\P$, $n=|V|$.

This conjecture was soon disproved (see \cite{BBL}) and, together with Aanderaa,
Rosenberg modified his conjecture as follows:

{\it There exists $\g>0$ such that for all nontrivial, monotonic graph properties $\P$ we have} $c(\P)\ge\g n^{2}.$

This version turned out to be true and was proved by Rivest and Vuillemin in 1975 with $\g =1/16$ (see \cite{RV})
by first proving that $c(\P)\ge n^2/4$ if $n$ is a power of two and
then applying some interpolation argument for the other values of $n$.
Kleitman and Kwiatkowski \cite{KK} improved the value of $\g$ from $1/16$
to $1/9$ for $n$ large. They proceeded in a way similar to Rivest--Vuillemin but showed that
$c(\P)\ge n^2/3$ if $n$ is a power of three. Both results were proved by a
different method in \cite{Tr2}.
 

Then, in 1984, Kahn, Saks and Sturtevant \cite{KSS} proved that
$c(\P)\ge (n^2/4)+o(n^{2})$.
This is up to now the best approximation for the following conjecture of Karp:

{\it All nontrivial, monotonic graph properties are elusive.}


In fact, Kahn, Saks and Sturtevant proved Karp's conjecture in case $n$
is a prime power (see below). In the following sections, we are now going to describe their method
(which uses algebraic topology)
and show several applications.

\subsection{Tools from algebraic topology.}
From now on, we assume that $\P$ is a monotone, nontrivial graph property.

Since $c(\P)=c(2^T\setminus \P)$, it suffices to study decreasing graph properties.
A decreasing graph property can be seen as an (abstract)
simplicial complex. Hence, its {\sl Euler characteristic} $\chi(\P)$ is defined as
$$\chi(\P):=\sum_{i= 1}^{|T|}(-1)^{i-1}a_i =1-q(\P,-1)$$
If $G$ is an abelian group (here: $G={\bf Z}$ or $G={\bf Z}/p{\bf Z}=\Zp$, $p$ prime),
the complex is called {\sl G--acyclic} if
$$H_0(\P,G)=0\quad {\rm and}\quad H_i(\P,G)=0\quad {\rm for}\ i>0$$
Here, $H_i(\P,G)$ denotes the $i$--dimensional homology group of $\P$ with respect to $G$.
Kahn, Saks and Sturtevant established the following connection between complexity theory
and algebraic topology :

\begin{thm}[Kahn, Saks and Sturtevant]
If $\P$ is not elusive, then it is contractible and hence ${\bf Z}_p$--acyclic for all primes p. In particular, $\chi(\P)=1$.
\end{thm}
The proof of this result is quite easy and similar to the proof of divisibility
of $q(\P,z)$ by $1+z$ if $\P$ is not elusive. 


It is a striking fact discovered by P.A. Smith, that in some cases the condition $\chi(\P)=1$ is preserved
when the complex $\P$ is replaced by a much simpler ``complex of orbits''.

Denote by $\G$ the set of all finite groups $G$ containing a normal $p$--subgroup $G_1$, $G_1\unlhd  G$, such that the factor group
$G/G_1$ is cyclic.
If $G$ is a permutation group on $T$ leaving $\P$ invariant, we define the simplicial complex $\P_G$ with vertex set $T_G:=\{B\in \P: B\ {\rm orbit\ of}\ G\}$ by
$$\{B_1,\ldots,B_k\}\in \P_G:\Longleftrightarrow B_1\cup\ldots\cup B_k \in \P.$$
The following result of P.A. Smith and R.G. Oliver (see \cite{Sm} and \cite{Ol})
 is crucial:
\begin{thm}[Smith, Oliver]
If $G\in\G$ is a permutation group on $T$ leaving the ${\bf Z}_p$--acyclic complex $\P$ invariant, then
$$\chi(\P_G)=1.$$
In particular, $\P_G$ is nonempty.
\end{thm}

\subsection{Some applications.} 
In case that the number of vertices is a prime power, Kahn, Saks and Sturtevant
assumed that the vertex set $V$ is the Galois field $GF(n)$ and considered
the group $G$ of affine--linear transformations ``$\tau(x)=ax+b$'' with $a,b\in V$
and $a\neq 0$. Clearly, $G$ contains the normal subgroup of all
translations $(a=1)$ which is isomorphic to the additive group of the field
$V$ and thus is a $p$--group. The factor group $G/G_1$ is isomorphic to
the multiplicative group of the field $V$ which is cyclic. It follows that
$G$ is in $\G$.
Any (nontrivial) decreasing graph property is clearly invariant under $G$.
If it is not elusive, then, by the above result, the complex $\P_G$ is
nonempty. But $G$ acts doubly transitive on $V$ and thus transitive on the
set $\V$. We conclude that $\P$ contains the complete graph on $V$ and
thus all graphs on $V$ contradicting our assumption that $\P$ is nontrivial.
This is the proof of
\begin{thm}[Kahn, Saks and Sturtevant]
If $n=|V|$ is a prime power, then all nontrivial, monotone graph
properties are elusive.
\end{thm}

It is a pity that nobody knows how to get an $(n^2/2)+o(n^2)$--bound
from this for general $n$. Since a proof or disproof of Karp's Conjecture
can be very difficult, we separately state the following problem:

\begin{pro}
Prove that all nontrivial, monotone graph properties satisfy
$$c(\P)\ge {n\choose 2}+o(n^2).$$
\end{pro}

The topological method has been used afterwards by several people. 
V. King applied it to digraph properties and A. Yao proved the following
interesting result:

\begin{thm}[Yao]
All nontrivial, monotone bipartite graph properties are elusive.
\end{thm}
Here, a bipartite graph property means the following:
Fix two disjoint, nonempty and finite sets $U$ and $W$ and let
$T:=\{uw:u\in U,\ w\in W\}$. 
A bipartite graph property is a subset of $2^T$ which is invariant under all
permutations of $U$ and $W$.


{\bf Proof:} It suffices to consider a cyclic group $G$ acting
transitively on one colour class, say $W$. Let some decreasing
bipartite graph property $\P$ be given. Then $\P_G$ is a complex on
the set of all stars with centers in $U$. By isomorphism invariance
and monotonicity, there is some
number $k\le u:=|U|$ such that $\P_G$ consists of all sets of at most $k$ stars.
If $\P$ is nontrivial, $k<u$ and we have:
$$\displaylines{
1-\chi(\P_G)=\sum_{i=0}^k(-1)^i{u\choose i}\cr
=\sum_{i=0}^k(-1)^i\left[{u-1\choose i-1}+{u-1\choose i}\right]\cr
=(-1)^k{u-1\choose k}\neq 0.\cr}
$$
It follows that $\P$ is elusive.
\begin{flushright}
$\Box$
\end{flushright}
Recently, the following analogue of Yao's theorem was proved (see \cite{Tr4}):

\begin{thm}
All (nontrivial) decreasing graph properties consisting of bipartite
graphs only are elusive.
\end{thm}

Recall that the {\sl girth} of a graph is the length of its shortest cycle (the girth of a forest being defined as $\infty$).
We want to prove the following result from \cite{Tr3}:

\begin{thm}
Suppose $\P$ is a decreasing, (nontrivial) graph property such that all graphs of $\P$ have girth greater than 4.
Then $\P$ is elusive.
\end{thm}

{\bf Proof:} If $n$ is a power of 2, then elusiveness follows from Theorem 3.
Hence, we may assume that some odd prime $p$ divides $n$,
$n=pm$ say, and $V=\Zp\times\Zm$.
Let $G:=\langle\tau\rangle$, the group generated by $\tau:\Zp\to\Zp:x\to x+1$,
and $H:=\langle\sigma\rangle$ where
$\sigma:\Zm\to\Zm:y\to y+1$.

Recall that the {\sl wreath product} $G\wr H$ is a permutation group on $V$ defined as follows:
$$G\wr H:=\{(f;\pi)|f:\Zm\to G,\pi\in H\}$$
For $(i,j)\in V$ and $(f;\pi)\in G\wr H$ we have
$$(f;\pi)(i,j):=(f(\pi(j))(i),\pi(j)).$$
$G\wr H$ contains the normal subgroup
$$G_1:=\{(f;1_H)|f:\Zm\to G\}$$
which is isomorphic to the $m$--fold direct product $G^m=G\times\cdots\times G$. Hence, $G_1$ is a $p$--group and we have $(G\wr H)/G_1\simeq H$.
It follows that $G\wr H$ is in $\G$.

Now suppose there was a nonelusive decreasing
graph property $\P$ which contained graphs of girth greater than 4 only.
By Theorems 1 and 2 we must have 
$$\chi(\P_{G\wr H})=1.$$
To obtain a contradiction, we consider two cases:
\begin{itemize}
\item[(a)] $p=3$: The orbit of an edge joining two vertices in some set $V_i:=\Zp\times\{i\}$, $i\in\Zm$, is isomorphic to $mK_3$, the graph consisting of $m$ disjoint triangles. But $K_3$ has girth 3. The orbit of an edge joining vertices in $V_i$ and $V_j\ (i\neq j)$ is easily seen to contain the complete bipartite graph $K_{3,3}$ as a subgraph which has girth 4. We infer that $\P_G$ is empty, a contradiction.
\item[(b)] $p>3$: Similarly to (a), the orbits of edges joining nodes in $V_i$ and $V_j,\ i\neq j,$ are easily seen to contain some complete bipartite graph $K_{p,p}$ which has girth 4 and therefore cannot be contained in $\P$.

The orbits of edges joining two points in $V_i$ are isomorphic to
$mC_p$, the graph consisting of $m$ disjoint copies of the $p$--cycle $C_p$, and there are $(p-1)/2$ such orbits. We claim that the union of two such orbits contains a 4--cycle.

It obviously suffices to show that the union of two orbits
of $G$ acting on the unordered pairs of $\Zp$ contains a 4--cycle.
These orbits are given by the representatives
$\{\{0,j\}|1\le j\le (p-1)/2\}$.
But for each $x\in \Zp$, the vertices $x,x+j,x+j+k,x+k$ lie on a 4--cycle in
the union of the orbits containing $\{0,j\}$ and $\{0,k\}$. 

It follows that $\chi(\P_{G\wr H})=(p-1)/2>1$, again a contradiction.
\end{itemize}
\begin{flushright}
$\Box$
\end{flushright}

The last two theorems suggest the following problem:
\begin{pro}
Prove that all decreasing graph properties consisting of triangle--free graphs
only are elusive.
\end{pro}

\subsection{Special Graph Properties.}

In this last section, we list some of the results on the elusiveness of
graph properties often considered by graph theorists. A natural approach is to
find a strategy for player $\S$ and show that this strategy forces $\A$ to probe
all possible edges. It is not difficult to characterize all graph properties
for which a so--called {\sl simple strategy} works:


Say either always ``yes'' or always ``no''. (see \cite{Ai,Bo1,Tr1,Tr2}).

By a simple strategy, we can, e.g., prove the elusiveness of {\sl planarity}
or {\sl connectedness}. For 2--connectedness, a more refined strategy works
(see \cite{Tr1}). We offer the following problem:

\begin{pro}
Prove that k--connectedness is elusive for $k\ge 3$.
\end{pro}

Bollob\'as gave ingenious strategies for the properties of containing
a complete graph of order at least $k,\ 2\le k\le n$ as well as for
$\chi(G)\ge k,\ 2\le k\le n$, where here $\chi(G)$ denotes the chromatic number
of $G$.

By using the topological method, it was shown in \cite{Tr3} that the properties
$\Delta(G)\le k,\ 0\le k< n-1$ and $\nu(G)\le k,\ 0\le k<\lf n/2\rf$ are elusive as well.
Here, $\Delta(G)$ and $\nu(G)$ denote the maximum degree and the matching
number, respectively. Please note that you get more elusive properties by
considering $2^T\setminus \P$ and $\{H|H \mbox{\ is the complementary graph
of some graph in $\P$}\}$.

We close this survey by another open problem:
\begin{pro}
Prove that the property of containing a Hamiltonian cycle is elusive.
\end{pro}

\begin{thebibliography}{[12]}


\bibitem{Ai}
{\sc M. AIGNER}, {\it Combinatorial Search}, Wiley--Teubner, Stutt\-gart and Chi\-che\-ster, 1988.

\bibitem{BBL}
{\sc M.R. BEST, P. VAN EMDE BOAS, H.W. LENSTRA JR.} {\it A sharpened version of the Aanderaa--Rosenberg conjecture}, Math. Centrum Tracts, Amsterdam, 1974.

\bibitem{Bo1}
{\sc B. BOLLOB\'AS}, {\it Complete subgraphs are elusive}, J. Combinatorial Theory B 21 (1976), pp. 1--7.

\bibitem{Bo2}
{\sc B. BOLLOB\'AS}, {\it Extremal Graph Theory}, Academic Press, London, 1978.

\bibitem{Gr}
{\sc D. GRIESER}, {\it Some results on the complexity of sets},
Disc. Math. 88 (1991), pp. 179--192.

\bibitem{Ki}
{\sc V. KING}, {\it A lower bound for the recognition of digraph properties}, Combinatorica 10 (1990), pp. 53--59.

\bibitem{KK}
{\sc D.J. KLEITMAN AND D.J. KWIATKOWSKI}, {\it Further results on the Aanderaa--Rosenberg conjecture}, J. Combinatorial Theory B (1980), pp. 85--95.

\bibitem{KSS}
{\sc J. KAHN, M. SAKS AND D. STURTEVANT}, {\it A topological approach to evasiveness}, Combinatorica 4 (1984), pp. 297--306.

\bibitem{Ol}
{\sc R. OLIVER}, {\it Fixed point sets of group actions on finite acyclic complexes}, Comment. Math. Helv. 50 (1975), pp. 155--177.

\bibitem{Ro}
{\sc A.L. ROSENBERG}, {\it On the time required to recognize properties of graphs: a problem}, SIGACT News 5 (1973), pp. 15--16.

\bibitem{RV}
{\sc R.L. RIVEST AND J. VUILLEMIN}, {\it On recognizing graph properties from adjacency matrices}, Theor. Comput. Sci. 3 (1976/77), pp. 371--384.

\bibitem{Sm}
{\sc P.A. SMITH}, {\it Fixed point theorems for periodic transformations}, Amer. J. Math. 63 (1941), pp. 1--8.

\bibitem{Tr1}
{\sc E. TRIESCH}, {\it Elusive properties}, in ``Combinatorial Theory'', Proceedings Schlo\ss\ Rauischholzhausen (1982) (D. Jungnickel and K. Vedder, eds.), Springer Lecture Notes in Math., pp. 321--326.

\bibitem{Tr2}
{\sc E. TRIESCH}, {\it \"Uber die Komplexit\"at von Grapheneigenschaften}, Dissertation, Aachen, 1984.

\bibitem{Tr3}
{\sc E. TRIESCH}, {\it Some results on elusive graph properties}, SIAM J. Comput.
23 (1994), pp. 247--254.

\bibitem{Tr4}
{\sc E. TRIESCH}, {\it On the recognition complexity of some graph properties},
Combinatorica 16 (1996), pp. 259--268.


\bibitem{Yao}
{\sc A. C-C. YAO}, {\it Monotone bipartite graph properties are evasive}, SIAM J. Comput. 17 (1988), pp. 517--520.
\end{thebibliography}
\newpage

\section{Shorter abstracts}


\bigskip
\centerline{\bf Gautam Appa}
\ta
\centerline{\bf Bimodular Network Matrices} 
\tb
\centerline{\it LSU, London}
\tc
Network matrices provide an important class of totally unimodular matrices which
arise as a natural extension of the node-arc incidence matrices of directed graphs.  They can
be interpreted as arc-path incidence matrices in which each column represents the unique path
between a pair of vertices in a directed tree graph, while rows represent the arcs of the tree
graph.  We provide a similar extension for the node-edge incidence matrices of undirected
graphs.  
      The node-edge incidence matrix (call it N) of an undirected graph, consisting of
exactly two $+1$ entries in each column, has two important properties.  
First, $N$ is totally
bimodular, i.e., any square sub-matrix of $N$
 has a determinant  $0$ or $2k$ where $k$ is any non-
negative integer.  Second, $N$ is $2$-integral.  Non-singular submatrices of $N$
contain, in general, decomposable balanced sub-matrices of type $R1$ with determinant $q1$ or
type $R2$ with determinant $q2$.  We identify the graphical structure of each type.  $R1$ represents
the incidence matrix of a tree graph augmented by one self-loop, while $R2$ turns out to be the
incidence matrix of a connected graph with exactly one odd cycle of length 
 at least three.  We
concentrate on the only new structure in this setting, viz., incidence matrices of connected
graphs with exactly one odd cycle of length three or more.  Let $G$ represent a connected
graph with $n$ nodes and $n$ edges, having exactly one such odd cycle.  Then we define
generalised paths/tours involving any two nodes of $G$, and write a bimodular network matrix,
called BINET and denoted by $B$, as the edge-tour incidence matrix of these generalised tours. 
In general, elements of $B$ are $0, q1$ and $q2$.  
      We show that a binet matrix $B$ is totally bimodular and 2-integral.  We show
connections to the ternary packing and covering problems.  
      One surprising result shown is that one of the two five by five
 unimodular matrices, known
not to be a network matrix, is a binet matrix.

\t

\centerline{\bf Jorgen Bang-Jensen}
\ta
\begin{center}{\bf A Polynomial Algorithm For The Hamiltonian Cycle Problem
For Semicomplete Multipartite Digraphs}\end{center}
\tb
\centerline{\it Odense University, Denmark}
\tc
A {\em semicomplete digraph} is a digraph whose
underlying
graph is complete. A {\em semicomplete multipartite digraph} is
a digraph 
that can be obtained from some  semicomplete digraph $D$ by
choosing a spanning collection of vertex disjoint induced 
subgraphs of $D$ and
deleting all arcs inside each of these.
When the number
of subgraphs above is precisely two, we obtain the 
{\em semicomplete bipartite digraphs}.
 While the Hamiltonian cycle problem is very easy for
semicomplete digraphs and relatively easy for semicomplete
bipartite
digraphs (in which case there is still a nice mathematical
characterization), it has been an open problem for more than 10 years in
the case of semicomplete multipartite digraphs. Recently the authors have
proved (constructively) that there is a polynomial algorithm
 for the Hamiltonian
cycle problem for semicomplete multipartite digraphs.
In this talk we will give the necessary background and, if time
permits,  a very
brief sketch of the algorithm.

\t


\centerline{\bf Kathie Cameron}
\ta
\begin{center}{\bf Finding a $b$-Detachment of a Graph with a Minumum Number of Components }
\end{center}
\tb
\centerline{\it Technical University of Denmark}
\tc
Let $G = (V,E)$ be a graph and $b = (b(v): v \in V)$ be a vector of positive 
integers.  A $b$-detachment of $G$ is a graph obtained from $G$ by splitting
each vertex $v$ into $b(v)$ vertices.  More formally, a $b$-detachment of $G$
 is 
obtained by replacing each vertex $v$ by a set $S(v)$ of $b(v)$ vertices,
and replacing each edge $e=(u,v)$ of $G$ by an edge with one end in $S(u)$ and 
the other end in $S(v)$.  Nash-Williams proved that the minimum number of
components in a $b$-detachment of $G$ equals
	maximum $\{ b(X) + c(G-X) -|L(X)| : X$ is a subset of $V \}$,
where $b(X)$ is the sum of $b(v)$ for $v  \in X$, 
$c(G-X)$ is the number of 
components of $G-X$, and $L(X)$ is the set of edges of $G$ with at least one
end in $X$.  We give a direct polytime algorithm for finding a $b$-detachment
with a minimum number of components.




\t


\centerline{\bf Michele Conforti}
\ta
\begin{center}{\bf A Theorem of Truemper about Wheels and Three-Path
 Configurations}\end{center}
\tb
\centerline{\it University of Padova}
\tc
Suppose one has to "sign" the edges of a graph with
even an odd labels so that, for each chordless cycle
H, the parity of the set of odd edges of H satisfies a
given requirement (is even, is odd).
Klaus Truemper has proven an important theorem about
the minimal forbidden subgraphs for this property.
We give a novel and easy proof for this result. 
We also describe several applications of this
theorem: In particular,

-The characterization of Tutte of regular matroids
and  Reid for matroids representable over GF3

-The characterization of universally signable ghraphs

-The characterization of balanceable graphs

-The characterzation of the graph that can be signed
so that every
hole is either even or odd.

These results were jointly obtained with Cornuejols,
Kapoor and Vuskovic.



\t


\centerline{\bf Gerard Cornu\'ejols}
\ta
\centerline{\bf Ideal and Balanced Matrices}
\tb
\centerline{\it University of Toulouse and Carnegie Mellon University}
\tc
A $0,1$ matrix $A$ is perfect if the polytope $\{x \leq 0:
Ax \leq 1\}$ is an integer polytope. It is ideal if
$\{x \geq 0: Ax \geq 1\}$ is an integer polyhedron. It is 
balanced if no square submatrix of odd order contains
exactly two ones per row and per column. In this 
talk, we survey results and open problems about 
these and related classes of matrices.



\te

    
\centerline{\bf Bert Gerards}
\ta
\centerline{\bf The Matroids Representable Over The 4-element Field} 
\tb
\centerline{\it CWI, Amsterdam}
\tc
Together with Jim Geelen and Ajai Kapoor, we present the complete list
of forbidden minors for GF(4)-representable matroids.





\t


\centerline{\bf Winfried Hochst\"attler}
\ta
\centerline{\bf On Bases of Circuit Lattices} 
\tb
\centerline{\it University of Koeln}
\tc
This is joint work with Martin Loebl.
Given a binary matrix $B$ the circuit lattice of the corresponding
binary matroid is the integer hull of the $0,1$-vectors in the kernel of
$B$. We discuss a couple of observations concerning the following
conjecture: The circuit lattice of a binary matroid has a basis of
$0,1$-vectors or, in other words, the integer lattice of a binary code has
a basis of codewords.

We relate this conjecture to a certain Sylvester-type Hadamard matrix $M$
and prove a duality statement about submatrices of full row length.

Finally, we disprove a stronger version of the above conjecture,
indicating, that it, if true, does not have a local character.




\te


\centerline{\bf Sandor Fekete}
\ta
\centerline{\bf Angle-Restricted Tours in the Plane} 
\tb
\centerline{\it University of Koeln}
\tc
Earlier this year, Aggarwal, Coppersmith, Khanna, Motwani, and
Schieber showed that the so-called ``Angular-Metric TSP'' is
NP-complete. In this problem, one has to find a Hamiltonian path for a given
set of points in the Euclidean plane, such that the sum of the direction
changes at each vertex along the tour is minimized.
This result has important consequences for the problem of matroid parity,
as it resolves the long-standing open question about the hardness of the
weighted linear matroid parity problem in the affirmative.

The Angular-Metric TSP is closely related to the problem
``Angle-Restricted Tour'' (ART):
For a given set $A\subseteq\ (-\pi;+\pi]$ of angles, we have
to decide whether a set $P$ of $n$ points
in the Euclidean plane allows a closed directed tour consisting of straight
line segments, such that all angles between consecutive line segments are
from the set $A$.

We present a variety of algorithmic and combinatorial results on this
problem.
In particular, we show that any finite set of at least five points in general
position allows
a ``pseudoconvex'' tour (i.\,e.\ a tour where all angles are nonnegative),
and we derive a fast algorithm for constructing such a tour.
Moreover, we give a complete classification (from the computational
complexity point of view) for the special cases where the tour has to be
part of the orthogonal grid.

The paper presented is joint work with Gerhard Woeginger (Graz).



\t

\centerline{\bf Anjai Kapoor}
\ta
\centerline{\bf Triangle Free Graphs That Are Odd-Signable} 
\tb
\centerline{\it University of Padova}
\tc
A graph is odd-signable if there exists 
an assignment of "odd" and "even" labels to the
edges so that every hole has an odd number of odd
edges. Graphs with no even holes are a subclass of
this class. Triangle-free (TF) odd-signable graphs form a class of basic graphs for 
cap-free odd-signable graphs, which in turn are a
basic class in the study of graphs with no even
holes. 

Here we give a decomposition theorem and recognition
algorithm for TF odd-signable graphs. We also show
that all TF odd-signable graphs can be constructed
by a sequence of "ear additions". We make some
conjectures regarding the description of the stable
set polytope for these graphs.

These results were jointly obtained with Cornuejols,
Conforti and Vuskovic.





\t

\centerline{\bf Kyriakos Kilakos}
\ta
\centerline{\bf Polytopes of Bounded Stable Sets} 
\tb
\centerline{\it LSU London}
\tc
The {\em $t$-stable set polytope} of a graph is the convex hull  of incidence
vectors of stable sets of cardinality at most $t$ in the graph.
For $t=3$, we describe the facet defining inequalities of the
$t$-stable set polytope of any bipartite
graph $G$.  In addition, we show that 
for any integral weighting on the vertices of $G$, the chromatic
number of $G$ (with respect to this weighting) is equal to the
round up of its fractional chromatic number plus one.

\medskip
More generally,  for any integer $t$,
we discuss  facet defining inequalities of the 
$t$-stable set polytope  of bipartite graphs.

\te



\centerline{\bf Colin McDiarmid}
\ta
\centerline{\bf Colouring Proximity Graphs in The Plane} 
\tb
\centerline{\it University of Oxford}
\tc
Given a set $S$ of points in the plane, and given $d>0$,
let $G(S,d)$ denote the graph with vertex set $S$ and with distinct
vertices adjacent whenever the Euclidean distance between them is less
than $d$.
We are interested in colouring such `proximity' or `interference'
graphs.  One application where this
problem arises is in the design of mobile telephone networks,
when we need to assign radio frequency bands (colours) to transmitters
(points in $S$) to avoid interference.
We find for example that, if the set $S$ has density $\sigma$, then
the chromatic number $\chi$ satisfies
$\chi(G(S,d))/d^2 \rightarrow \sigma \sqrt{3}/2$
as $d \rightarrow \infty$.
This is joint work with Bruce Reed.




\t


\centerline{\bf Denis Naddef}
\ta
\centerline{\bf Discovering The TSP Polytope}
\tb
\centerline{\it University Joseph Fourier, Grenoble}
\tc
In this talk, which is inspired greatly by discussions with Yves
Pochet of CORE, I will try to give you a feeling of what most of the known
valid inequalities for that polytope say. I will end by my favorite
conjecture on that polytope.




\te


\centerline{\bf Rudi Pendavingh}
\ta
\centerline{\bf A Polynomial Time Algorithm For Bibranching}
\tb
\centerline{\it University of Amsterdam}
\tc
This is  joint work with J. Keijsper.
Let $D=(V,A)$ be a digraph, $W\subset V$ a subset of its vertices.
A {\it bibranching} is a set $B\subset A$ such that
\begin{enumerate}
\item  for all $v\in W$, $B$ contains a directed path from $v$ to a vertex in
$V\setminus W$, and
\item  for all $v\in V\setminus W$, $B$ contains a directed path from a vertex in $W$ to 
$v$.
\end{enumerate}
\par\noindent For $W=\{r\}$, a bibranching is exactly an $r$-branching, i.e. a directed
tree rooted at $r$. Given a bipartite
graph, let $W$ be one of the colour classes and orient all arcs away from $W$. A set of
arcs is a
bibranching of the resulting digraph iff it is an edge cover of the original graph.
\par Now let $w$ be a positive integer weight function on the arrow set.
 Then, the linear programming duality equation for minimum weight bibranching
 has integral optimum solutions.
We will present a primal-dual algorithm for constructing a bibranching 
of minimum 
weight in polynomial time.

\t

\centerline{\bf Bruce Shepherd}
\ta
\begin{center}{\bf A Node capacitated routing problem arising in local
 optical networks}\end{center}
\tb
\centerline{\it LSU, London}
\tc
We discuss several problems arising in network routing
and design. In particular we consider a node-capacitated
routing problem related to ring networks of passive optical
networks.




\t

\centerline{\bf Bruno Simeone}
\ta
\centerline{\bf Generation of all $k$-partitions of an $n$-set }
\centerline{\bf in amortized
constant time per partition}
\tb
\centerline{\it University La Sapienza, Rome}
\tc
This is a joint work with Fabio Grasso. The present paper deals with the sequential generation of all $k$-partitions of an $n$-set, for a fixed 
 $1 \leq k \leq n$. The fastest known algorithm for this task is due to
 Ehrlich: it takes $O(k)$ time per partition. Here we propose another algorithm
 which takes only amortised constant time per partition. The algorithm
 is a modification of a previous procedure described by Nijenhuis and Wilf.
 We give an implementation which makes use of simple data structures, requires only $2n + k +c$ memory locations, where $c$ is a small constant, 
 and achieves the above time bound. Such bound is established
 through a careful analysis of the changes between any two consecutive
 partitions.  
 



\t

\centerline{\bf L. A. Sz\'{e}kely}
\ta
\begin{center}{\bf The number of nucleotide sites needed to accurately reconstruct
 large evolutionary trees}\end{center}
\tb
\centerline{\it Eotvos University, Budapest}
\tc
This is joint work with M. A. Steel  and P. L. Erd\H{o}s.
Biologists seek to reconstruct evolutionary trees for increasing numbers of
species, $n$, from aligned genetic sequences.  How
fast the sequence length $N$  must grow, as a function of $n$, in order to 
accurately
recover the underlying tree with probability $1-\epsilon$, 
if the sequences evolve according to simple
stochastic models of nucleotide substitution?  We show that for certain models,
the sequence length $N$
can grow surprisingly slowly with $n$ 
(sublinearly for a wide range parameters, and even
as a power of $\log n$ in a narrow range, which roughly  meets the lower bound
from information theory). By contrast, a more traditional technique (maximum 
compatibility)
provably requires $N$ to grow faster than linearly in $n$. Our approach is
 based on
a new, and computationally efficient approach for reconstructing 
phylogenetic trees from aligned DNA sequences.




\te

\centerline{\bf Jens Vygen}
\ta
\centerline{\bf A Linear--Time Algorithm for }
\centerline{\bf  Partitioning
 2-Dimensional Pointsets}
\tb
\centerline{\it University of Bonn}
\tc
At the DONET Conference 1995 in London I introduced a theorem describing
the structure of the optimum solutions of a crucial problem during VLSI-placement.
I mentioned that this leads to a linear--time algorithm at least for a special
case. Today I can show how the results can be extended to the general case.

The mathematical description of the problem is as follows:
Given a finite set $S$ of points in the plane, weights $w:S\to R_+$, and
capacities $\kappa_0,\kappa_1,\kappa_2,\kappa_3$ of the four quadrants,
we are looking for a fractional partition $g:S\times\{0,1,2,3\}\to[0,1]$ 
with $\sum_{i=0}^3 g(s,i)=1$ for all $s\in S$, such that the capacity
constraints $\sum_{f(s)=i} w(s) \le \kappa_i$ ($i=0,1,2,3$) are met and
the total movement $\sum_{s\in S}\sum_{i=0}^3 w(s) g(s,i) d(s,Q_i)$ is minimized.
Here $Q_i$ denotes the $i$-th quadrant and $d$ denotes the $L_1$-distance.





\t

 \centerline{\bf Dominic Welsh}
\ta
\centerline{\bf Polynomial time randomised approximation schemes for}
\centerline{\bf Tutte-Gr\"{o}thendieck invariants}
\tb
\centerline{\it University of Oxford }
\tc
The Tutte polynomial $T(G;x,y)$ of a graph $G$ encodes numerous interesting 
combinatorial quantities associated with the graph.  Its evaluation in various 
points in the $(x,y)$ plane give the number of spanning forests of the graph, 
the number of its strongly connected orientations, the number of its proper 
$k$-colourings, the (all terminal) reliability probability of the graph, and 
various other invariants the exact computation of each of which is well known 
to be $\#P$-hard.  Here I survey the problem of finding a fully polynomial 
randomised approximation schemes for approximating the value of $T(G;x,y)$.  
In particular I shall describe recent results obtained with Noga Alon and Alan 
Frieze which will give an fpras for evaluating $T$ for any dense graph $G$, that is, 
any graph on $n$ vertices whose minimum degree is $\Omega (n)$, whenever 
$x\geq 1$ and $y\geq 1$, and in various additional points.  This region 
includes evaluations of reliability and partition functions of the 
ferromagnetic $Q$-state Potts model, and extends to linear matroids where $T$ 
specialises to the weight enumerator of linear codes.

\newpage

\section{List of participants}


Karen Aaardal, University of Utrecht

Christopher Anhalt, University of Bonn

Gautam Appa, LSU, London

Jorgen Bang-Jensen, Odense University, Denmark 

\hskip .2in (non-Donet participant)
      
Eric Bartels,  University of Oxford

V.L.Beresnev, University of Novosibirsk

\hskip .2in (non-Donet participant)

Adrian Bondy, University of Lion

Andr\'{e} Bouchet, University of Le Mans

Michel Burlet, University Joseph Fourier, Grenoble

Kathie Cameron, Technical University of Danemark

\hskip .2in (non-Donet participant)

Peter J. Cameron, Queen Mary and Westfield College 

\hskip .2in (non-Donet participant)

Ond\v rej \v Cepek, Charles University, Prague
 
Michele Conforti, University of Padova 

Gerard Cornu\'ejols, University of Toulouse and 

Carnegie Mellon University
 \hskip .2in (non-Donet participant)

Andrea De Vitis, University La Sapienza, Rome

Reinhard Diestel, University of Chemnitz

\hskip .2in (non-Donet participant)

Jack Edmonds, Technical University Danemark

\hskip .2in (non-Donet participant)

Sandor Fekete, University of Koeln

\hskip .2in (non-Donet participant)

Jean Fonlupt, University Paris 6

Paolo Franciosa, University La Sapienza, Roma

Andr\'as Frank, Eotvos University, Budapest
         
Bert Gerards, CWI, Amsterdam

Roberto Giaccio, University La Sapienza, Roma

Rebecca Gower, University of Oxford

Willem Haemers, Tilburg University

Matthias Hayer, University of Koeln

Jan van den Heuvel, LSU, London 

Petr Hlin\v en\'y,  Charles University, Prague

Winfried Hochst\"attler, University of Koeln

\hskip .2in (non-Donet participant)

Stan van Hoesel, University of Limburg

Hein van der Holst, CWI Amsterdam

Tibor Jordan, E\"otv\"os University, Budapest

 Anjai Kapoor, University of Padova

Judith Keijsper, University of Amsterdam

Kyriakos Kilakos, LSU, London

Martin Klazar,  Charles University, Prague

Bernhard Korte, University of Bonn

Jan Kratochv\'\i l,  Charles University, Prague

Monique Laurent, LIENS, Paris

Robert Leese,  University of Oxford

Martin Loebl, Charles University, Prague

Andr\'as Luk\'acs, E\"otv\"os University, Budapest

Colin McDiarmid,  University of Oxford

Criel Merino, University of Oxford

Raffaele Mosca, University La Sapienza, Rome

Denis Naddef, University Joseph Fourier, Grenoble

Jaroslav Ne\v set\v ril, Charles University, Prague

Steven Noble, University of Oxford

Rudi Pendavingh, University of Amsterdam

Aline Pennisi, University La Sapienza, Rome

Myriam Preissmann, University Joseph Fourier, Grenoble

Pavel Pudl\'ak, Czech Academy of Sciences

\hskip .2in (non-Donet participant)

Federica Ricca, University La Sapienza, Rome

Andre Rohe, University of Bonn

Irasema Sarmiento, University of Oxford
 
Andr\'as Seb\H o, University Joseph Fourier, Grenoble

Bruce Shepherd, LSU, London

Mark Shepherd, University of Oxford

Bruno Simeone, University La Sapienza, Rome

Stefano Smriglio, University La Sapienza, Rome

Leen Stougie, University of Amsterdam

L\'aszlo Sz\'ekely, E\"otv\"os University, Budapest

Robin Thomas, Georgia Institute of Technology, Atlanta

 \hskip .2in (non-Donet participant)

Carsten Thomassen, Technical University Danemark 

\hskip .2in (non-Donet participant)

Zsolt Tuza, Eotvos University, Budapest

Pavel Valtr, Charles University, Prague

Jens Vygen, University of Bonn

Dominic Welsh, University of Oxford 

\ 
\newpage

\ 
\newpage

\ 

\end{document}
