\documentstyle{article}
\sloppy
\textwidth=105mm
\textheight=160mm

\def\kb{Krystyna T. Bali\'{n}ska: An Algorithmic Approach to a Random Process
for Graphs with Bounded Degree}

\def\pb{Peter Brass: On Lattice-like Extremal Sets for
Combinatorial Geometry Problems}

\def\gb{Graham Brightwell: Recent Results in Partially Ordered Sets}

\def\jd{Josep Diaz: Approximation of \#P Problems in RNC}

\def\wde{Walter Deuber: TBA}

\def\gel{Gyorgy Elek\'es: Metric Combinatorics and Combinatorial Algebra}

\def\sf{S\'andor P.~Fekete: A New Exact Algorithm for General Orthogonal
                     d-dimensional Knapsack Problems and
                     a New Lower Bound for Bin Packing Problems}

\def\mf{Mike Fellows: The Shortest Vector Problem and the Prospects for
               Cryptosystems Based on NP-Hard Problems}

\def\af{Andr\'as Frank: Algorithms for Increasing the Connectivity of
Graphs}

\def\rg{Ronald L. Graham: TBA}

\def\jg{Jerry Griggs: The Distribution of Subset Sums in $R^m$ and in Finite
                Abelian Groups}

\def\hg{Harald Gropp: On the Upper Chromatic Number of Configurations}

\def\ag{Arvind Gupta: Monadic Second Order Logic and Complement Problems}

\def\mi{Mary Inaba: Geometric Clustering Problem}

\def\mk{Martin Klazar: Extremal Problems for Colored Trees}

\def\ak{Alexander Kostochka: On Colour-critical Graphs and Hypergraphs with
Few Edges}

\def\bk{Bernhard Korte: TBA}

\def\jk{Jan Kraj\'{\i}\v{c}ek: Proof Complexity and Some Related Algebraico -
                        combinatorial Problems}

\def\hk{Jan Kratochv\'{\i}l: List Colorings and Choosability of Graphs}

\def\lk{Lud\v ek Ku\v cera: Fast Deflection Routing of Long Messages}

\def\ll{L\'aszlo Lov\'asz: Random Walks, Mixing, and Sampling}

\def\tl{Tomasz Luczak: Random Trees and Random Graphs}

\def\el{Eugene Luks: Algorithmic Applications of the Simple Groups
Classification}

\def\wm{Wolfgang Mader: An Extremal Problem for Subdivisions of $K_5$ and
Topological Subgraphs in Graphs of Large Girth}

\def\jm{Ji\v r\'{\i} Matou\v sek: Upper Bounds in Geometric and Combinatorial
                           Discrepancy}

\def\fm{Franti\v sek Mat\'u\v s: Entropy Functions and Matroids (On
Entropic Polymatroids)}

\def\pmi{Peter Mih\'ok: The Structure of Hereditary Properties of Graphs
                     and Minimal Reducible Bounds}

\def\jn{Jaroslav Ne\v set\v ril: The Structure of Graph Homomorphisms}

\def\pp{Petr Pan\v co\v ska: Proteins, Graphs and Spectra - Selected
Problems}

\def\pp{Pavel Pudl\'{a}k : New algorithms for satisfiability}

\def\fr{Fred S. Roberts: Meaningless Statements}

\def\mr{M. Rosenfeld: Three Problems in Combinatorial Number Theory}

\def\gr{G\"unter Rote: Convex 3-polytopes Can Be Realized with Linearly
Many Bits per Coordinate}

\def\jsg{Ji\v r\'{\i} Sgall: On Pairs of Intersecting Families}

\def\ms{Mikl\'os Simonovits: General Methods to Prove Exact Results in
Extremal Graph Theory}

\def\gs{G\'abor Simonyi: Information Theory in Combinatorics}

\def\ws{William F. Smyth:  Periodicity in Strings}

\def\es{Eric Sopena: Acyclic Improper Colorings}

\def\vs{Vera S\'os: TBA}

\def\js{Joel Spencer: Sophisticated Probability}

\def\rt{Robin Thomas: Permanents, Pfaffian Orientations, and Even Directed
Circuits}

\def\wt{William T. Trotter: Ramsey Theory and Sequences of Random
Variables}

\def\pv{Pavel Valtr: Several Recent Results on Geometric Graphs}









\title{\bf DIMATIA-DIMACS conference\\[10pt]
The Future of Discrete Mathematics\\[10pt]
\v Sti\v r\'{\i}n, May 19-25, 1997}

\date{\empty}
\begin{document}
\maketitle

\vspace{-\bigskipamount}
\input{stir}$$\setstir$$
\bigskip

\tableofcontents
\thispagestyle{empty}



\newpage
\section{Foreword}

It is a great pleasure to welcome you at the Future of Discrete Mathematics meeting held at \v Sti\v r\'{\i}n castle on May
19--25, 1997. This is the 
first meeting organized by the newly created center DIMATIA. It is organized jointly with DIMACS, which provided not only a necessary expertise but
also essentially contributed to the success of the meeting through the Czech
-- NSF joint grant No. 055/1997. The conference is further supported
by our Czech grants GA\v CR 0194/1996, GAUK 194/1996 and FR M\v SMT, and by
DIMATIA associated members LaBRI Bordeaux, Pacific Institute of Mathematical
Sciences, Sobolev Institute of Mathematics Novosibirsk and Mathematical 
Institute Budapest. This is our first joint project, and we all believe this is
the first out of many. Thus we included in this brochure a brief description
of the DIMATIA center, its scope, its goals (and its dreams).

We thank all speakers and participants for joining us for the inauguration of
DIMATIA and we wish you pleasant and fruitful time in \v Sti\v r\'{\i}n.

\begin{flushright}
Jan Kratochv\'{\i}l, Jaroslav Ne\v set\v ril (DIMATIA)\\
Ronald L. Graham, Fred S. Roberts (DIMACS)\\
for the organizing committee
\end{flushright}




\newpage
\section{Few words about DIMATIA}

The {\bf Center for Discrete Mathematics, Theoretical Computer Science and
Applications} was established in September 1996 at Charles University in
Prague as a joint project of Charles University,
Academy of Sciences of the
 Czech Republic
and Institute of Chemical Technology, Prague.
 The center is open and actively seeks
partners from all parts of the world.

\bigskip
\noindent
{\bf 1. Overview and goals.}
The purpose of the center is to foster research in all fields of discrete mathematics and its modern applications
and relationship to computer science, operations research and fields as
diverse as biology, chemistry and social sciences. Towards this end the center
will organize a continuing program of workshops, conferences and research
visits both in Prague and other places together with cooperating
institutions. The project will concentrate on research topics that are on
the forefront of current research in discrete mathematics and theoretical
computer science.

\bigskip
\noindent
{\bf 2. Activities.} The activities of DIMATIA are planned to stimulate
research in the most promising areas of discrete mathematics and its
applications. The program seeks to involve senior scientists and
outstanding young researchers both from Czech Republic and outside. The
following are considered to be the most important activities:
\begin{itemize}
\item DIMATIA will organize research workshops  focused
on specific topics to reflect recent trends in discrete mathematics and
theoretical computer science (e.g., a workshop on probabilistic method
is planned
jointly with DIMACS for 1997, a joint DIMACS-DIMATIA workshop on
 computational geometry is planned for 1998).
DIMATIA will take over the organization of problem oriented Midsummer
 combinatorial workshops, which
were  organized by the Department of Applied Mathematics in the past 4
years and which have built up a successful tradition. Workshops are
organized in an informal way which stresses the working atmosphere. They
usually involve 20 - 30 researchers.
\item DIMATIA will also organize larger conferences on more general topics
for more general audience (the DIMATIA-DIMACS conference "The Future of
Discrete Mathematics" is organized in May 1997,
the 5th International Czecho-Slovak
Symposium
on Combinatorics and Graph Theory is planned for 1998).
\item DIMATIA will continue the tradition of publishing KAM Preprint Series,
which will be published and distributed on a larger scale.
\item DIMATIA will serve as an international center, encouraging wide
international contacts and cooperation by supporting short-term visits of
researchers on the base of invitations and bilateral cooperation. For this
purpose, DIMATIA has created and refurnished new office spaces, including
 the basic computer equipment.
\item DIMATIA will also encourage long-term visits of senior researchers
and young scientists. Postdoctoral positions are announced and supported
jointly with our partner institutions. (E.g., following a contract with
Humboldt Fellowship we are offering one visiting position from September
1997.)
\end{itemize}

\bigskip\noindent
{\bf 3.
Organizational structure and personnel.}
DIMATIA is a corporate structure founded by three leading Prague research
groups working in discrete mathematics, theoretical computer science and
their applications. The research team includes 14 permanent members, mostly
mathematicians and computer scientists, but some members of the research team
are physicists and chemists. All these members are staff members of the
founding institutions -- Faculty of Mathematics and Physics of the Charles
University (V. Janota, M. Klazar, J. Kratochv\'{\i}l, L. Ku\v cera, M. Loebl,
J. Matou\v sek, J. Ne\v set\v ril, P. Pan\v co\v ska,
P. Valtr), Mathematical Institute of the Academy of Sciences of the Czech Republic (I. Havel, J. Kraj\'{\i}\v cek, P. Pudl\'ak, J. Sgall) and
Faculty of Chemical Engineering of the Institute of Chemical Technology, Prague
(D. Turz\'{\i}k).
This number does not include  associated
researchers, foreign associates and graduate students.

The center has a Director (J. Ne\v set\v ril) to provide scientific leadership
and day-to-day operation of the center. In that he is assisted by Deputy
Director (J. Kratochv\'{\i}l) and Scientific
Secretary (V. Janota). Charles University
provides the center with a full time secretary position.

The center has an International Scientific Advisory Board consisting of
representatives of DIMATIA participating organizations. DIMATIA (as opposed
to e.g. DIMACS) is an open institution, directed to the cooperation on the whole
European scale and open to further collaboration. This is a very special feature
 of the DIMATIA concept and
key to its intended activities. Presently the foreign associates are
Sobolev Institute of Mathematics, Novosibirsk, LaBRI Institute, Bordeaux,
Pacific Institute of Mathematical Sciences and DIMACS, New Jersey. We
expect that further institutions will join DIMATIA shortly (among them
Bielefeld and Budapest).
The open character of DIMATIA is also expressed by its International
Advisory Board. The role of this board is to foster the international
character of DIMATIA  as a whole European center with close links
to the top American institutions. Presently, the foreign members
of the board include
Prof. V. Beresnev (Sobolev Institute of Mathematics),
Prof. R.L.Graham (AT\&T Bell Labs),
Prof. B. Korte (Universit\"at Bonn),
Dr. D. Pappenfuss (Alexander von Humboldt Stifftung),
Prof. F.S.Roberts (DIMACS),
Prof. E. Sopena (University Bordeaux).


\bigskip
\noindent
{\bf 4. Budget.}
As it is usual an institution of this kind is only partially supported by its
host institution. Charles University provides rooms and offices (in one of the
most attractive historical districts of Prague). It also supports the center
by a secretary position. In addition, each of the founding institutions
(Charles University,
Academy of Sciences of the
 Czech Republic
and Institute of Chemical Technology, Prague)
contribute equally to the operation costs (\$ 2000 annually).
Also the foreign associates support the activities of DIMATIA.
The funds for larger activities
(scholarships, conferences, workshops, visits) are supported by our
grants and  cooperation contracts and are budgeted usually for 2-3 year
periods.



\newpage
To obtain more information about DIMATIA, application forms etc., contact
us by e-mail or regular mail at the address given below. Also visit our
web page at\\
\centerline{{\tt http://www.ms.mff.cuni.cz/acad/kam/dimatia/}}


\bigskip\bigskip
\input{dimgb}$$\setdimgb$$


\bigskip\bigskip\noindent
\begin{center}{\sl
DIMATIA,
Charles University\\
Malostransk\'e n\'am. 25\\
118 00 Praha 1,
Czech Republic\\
phone: 420-2-21914230,  420-2-57320726\\
fax: 420-2-57320726\\
e-mail: {\tt dimatia@kam.ms.mff.cuni.cz}}
\end{center}



\newpage


\section{Preliminary Program \\ of the Conference}

{\parindent=5mm \narrower
 \parindent=-5mm \parskip=1mm


\medskip{\bf Monday May 19, 1997}

14:00 departures of buses from Malostransk\'e n\'am.

15:00 expected arrival to \v St\i\v r\'{\i}n

15:30-16:00 coffee

16:00  \mr

17:00  \rt

19:00  dinner

\medskip\noindent{\bf Tuesday May 20, 1997}

9:00  \ll

10:00-10:30  coffee break

10:30  \wt

11:30  \fr

12:30  lunch

14:00  \jm

15:00  \gr

16:00-16:30 coffee break

16:30  \pv

17:00  \mi

17:30  \pb

19:00 dinner

\medskip\noindent{\bf Wednesday May 21, 1997}

9:00  \js

10:00-10:30 coffee break

10:30  \tl

11:30  \kb

12:30 lunch

14:00  \el

15:00  \lk

15:45-16:15 coffee break

16:15  \mf

16:45  \jsg

17:15  \pp

19:00 conference banquet

\medskip\noindent{\bf Thursday May 22, 1997}

9:00  \jn

10:00-10:30 coffee break

10:30  \hk

11:15  \ak

12:30 lunch

15:00 afternoon excursion

19:00 dinner

\medskip\noindent{\bf Friday May 23, 1997}

9:00  \vs

10:00-10:30 coffee break

10:30  \gb

11:30  \es

12:30 lunch

14:00  \jk

15:00 pm \ag

16:00-16:30 coffee break

16:30  \jd

17:00  \gel

17:30  \gs

19:00 dinner

\medskip\noindent{\bf Saturday May 24, 1997}

9:00  \wde

10:00  \af

11:00-11:30 coffee break

11:30 \wm

14:00 lunch

15:30  \mk

16:00  \ms

17:00  \pmi

17:30  \ws

19:00 dinner

\medskip\noindent{\bf Sunday May 25, 1997}

9:00  \jg

10:00-10:30 coffee break

10:30  \bk

11:30 lunch


13:00  departure of buses for Prague


}




\newpage
\section{Preliminary List of Participants}

\mbox{\quad}

%\noindent\hbox{
%\vtop{\hsize=40mm

Robert Babilon,
~ Praha

{Krystyna T. Bali\'{n}ska},
~ Poznan, Poland

Josef Balogh, 
~ Szeged, Hungary

{Peter Brass},
~ Berlin, Germany

{Graham Brightwell},
~ London, U.K.

{Walter Deuber},
~ Bielefeld, Germany

{Josep Diaz},
~ Barcelona, Spain

{Gyorgy Elek\'es},
~ Hungary

{S\'andor P.~Fekete},
~ Koeln, Germany

{Mike Fellows},
~ Victoria, Canada

{Andr\'as Frank},
~ Budapest, Hungary

Hubert de Fraysseix,
~ Paris, France

{Ronald L. Graham},
~ DIMACS, U.S.A.

{Jerry Griggs},
~ Columbia, U.S.A.

{Arvind Gupta},
~ Burnaby, Canada

Penny Haxell,
~ Waterloo, Canada

Petr Hlin\v en\'y,
~ Praha

{Mary Inaba},
~ Tokyo, Japan

{Martin Klazar},
~ Praha

{Alexander Kostochka},
~ Novosibirsk, Russia

{Bernhard Korte},
~ Bonn, Germany

{Jan Kraj\'{\i}\v{c}ek},
~ Praha

{Jan Kratochv\'{\i}l},
~ Praha

{Lud\v ek Ku\v cera},
~ Praha

{L\'aszlo Lov\'asz},
~ New Haven, U.S.A.

{Tomasz Luczak},
~ Poznan, Poland

{Eugene Luks},
~ Eugene, U.S.A.



%}\hspace{8mm}\vtop{\hsize=45mm



{Wolfgang Mader},
~ Hannover, Germany

{Ji\v r\'{\i} Matou\v sek},
~ Praha

{Franti\v sek Mat\'u\v s},
~ Bielefeld, Germany

Patrice Ossona de Mendez,
~ Paris, France

{Peter Mih\'ok},
~ Kosice, Slovakia

{Jaroslav Ne\v set\v ril},
~ Praha

{Petr Pan\v co\v ska},
~ Praha

G\'abor Pete,
~ Szeged, Hungary

Victor Pollara,
~ Braunschweig, Germany

{Pavel Pudl\'{a}k},
~ Praha

{Fred S. Roberts},
~ Rutgers, U.S.A.

{M. Rosenfeld},
~ Seattle, U.S.A.

{G\"unter Rote},
~ Graz, Austria

{Ji\v r\'{\i} Sgall},
~ Praha

{Mikl\'os Simonovits},
~ Budapest, Hungary

{G\'abor Simonyi},
~ Budapest, Hungary

{William F. Smyth},
~ Hamilton, Canada

{Eric Sopena},
~ Bordeaux, France

{Vera S\'os},
~ Budapest, Hungary

{Joel Spencer},
~ New York, U.S.A.

Claude Tardiff,
~ Bielefeld, Germany

{Robin Thomas},
~ Atlanta, U.S.A.

{William T. Trotter},
~ Tempe, U.S.A.

{Pavel Valtr},
~ Praha

Paola Vocca,
~ Rome, Italy

Shiyu Zhou,
~ U.S.A.

%}}






\newpage

\section{Abstracts}





\bigskip\bigskip
\noindent
{\bf Krystyna T. Bali\'{n}ska (Pozna\'{n}): An algorithmic approach to a
random process for graphs with bounded degree} \\
(joint work with Louis V.
Quintas)

\medskip\noindent
  Graphs with bounded degree are simple graphs having no vertex of
degree greater than a given positive integer $f$. These are called
({\em f- graphs})
([J.W. Kennedy and L.V. Quintas, Probability models for random
$f$-graphs, {\em Combinatorial Mathematics} (New York, 1985),
{\em Ann. N.Y. Acad. Sci., }{\bf 555} (1989) 248-261]).
The probability model for $f$-graphs on
$n$ vertices that generalizes the random graph process
(i.e. with $f = n - 1$) is known as the random $f$-graph process
(R$f$GP) of order $n$
([K.T. Bali\'{n}ska and L.V. Quintas, The random $f$-graph
process, {\em Quo Vadis, Graph Theory?} (Fairbanks, Alaska, 1990)
{\em Ann. Discrete Math., }{\bf 55} (1993) 333-340]).

  The main difficulty encountered in the study of the R$f$GP is that
choosing edges for a random $f$-graph from the set of available edges
is dependent on the process.

  A general method called $RGA$ (Random Graph Algorithms)
([K.T. Bali\'{n}ska, Algorithms for random graphs with bounded
degree, {\em Politechnika Pozna\'{n}ska, Rozprawy}, {\bf 314},
Pozna\'{n} (1996)]) for
obtaining an insight into deterministic and probabilistic problems
for the R$f$GP is presented. The method is based on the
{\em transition digraph} $D(n,f)$ of the process and consists of the
following classes of algorithms.

  {\em Class} ${\cal A}$: Exact algorithms generating all nodes of
$D(n,f)$ and calculating corresponding state probabilities. The
distribution of any random variable on $f$-graphs in the R$f$GP can
be obtained and enumeration problems for $f$-graphs and $D(n,f)$ can
be solved
([K.T. Bali\'{n}ska and L.V. Quintas, Degrees in a digraph whose
nodes are graphs, (Keszthely, 1993) {\em Discrete Math.} {\bf 150}
(1996) 17-29]).

  The main algorithm, IMAGE$f$, uses the BFS (Breadth First Search)
method for generating and visiting nodes of $D(n,f)$. Its time
complexity at step $t$, corresponding to $f$-graphs of size $t$ of
the R$f$GP, depends on the number of nodes of $D(n,f)$ and on the
complexity of the algorithm for testing the isomorphism of two
graphs. In general, this algorithm is exponential in $n$, however
for the case $f = 2$ there exists a $O(n^3)$ polynomial algorithm.
IMAGE$f$ has also been extended for constructing the underlying
(undirected) graph of $D(n,f)$ and calculating some of its
properties (e.g. its diameter).

  {\em Class} ${\cal B}$: Simulation algorithms for generating and
identifying graphs up to large orders to solve probabilistic
problems for the R$f$GP. Algorithms of this class are polynomial
in $n$. This method can be regarded as using a sample of random
walks along $D(n,f)$ from the initial state to a terminal state of
the R$f$GP. These have been combined with approximation functions
for studying some properties of the R$f$GP as functions of $n$ and
$f$.

\bigskip\bigskip\noindent
{\bf Peter Brass (FU Berlin):
 On lattice-like extremal sets
                for combinatorial geometry problems }

\medskip\noindent
Only in very few cases the structure of the extremal sets
for  Erd\H os-like combinatorial geometry problems is known,
but many of Erd\H os' conjectures are motivated by the belief
that lattice sections and related sets have many
extremal properties. A structural approach to these problems
may be preferable to direct counting, since the
importance of lattice-constructions shows the connection to
number-theoretic problems which are difficult to handle
by purely combinatorial methods (e.g. in the many-unit-distances
problem).

In this talk we will give a survey of lattice-like constructions
and present some new results to their extremality,
especially connected with the maximum number of unit distances,
of translates of a given pattern, and of point-line-incidences.



\bigskip\bigskip\noindent
{\bf Josep Diaz (Barcelona): Approximation of \#P problems in RNC}\\
(joint work with P. Spirakis and M.J. Serna)

\medskip\noindent
Using genetic systems we analize the rapid mixing of Markov chains
for approximate counting and almost uniform generation of
matching and perfect matching problems.

\bigskip\bigskip\noindent
{\bf G. Elekes (Budapest): Metric Combinatorics and Combinatorial Algebra}\\
(joint work with L. Ronyai)


\medskip\noindent
We study the structure of polynomials (and rational functions)
of two real variables which take few distinct values
on large (finite) Cartesian products.
As an application, a problem of G.~Purdy is solved on finite subsets
of the plane which determine few distinct distances.




\bigskip\bigskip\noindent
{\bf S\'andor P.~Fekete (K\"oln):
A new exact algorithm for general orthogonal d-dimensional knapsack problems
and
a new lower bound for bin packing problems}\\
(joint work with J\"org Schepers)

\medskip\noindent
The {\em $d$-dimensional orthogonal knapsack problem}
(OKP) has a wide range
of practical applications, including packing, cutting and scheduling.
We present a new approach to this problem,
using a graph-theoretical characterization of feasible packings.
This characterization allows us to deal with whole classes of packings
that share a certain combinatorial structure,
instead of single packings. Combining the use of this structure with
other heuristics, we develop a two-level tree search algorithm
for finding exact solutions for the $d$-dimensional OKP.
Computational results are reported, including optimal
solutions for all two--dimensional test
problems from recent literature.

We also describe a general method to obtain good lower bound
for packing problems. In particular, we establish a good new
lower bound for bin packing problems.


\bigskip\bigskip\noindent
{\bf Michael R. Fellows (Victoria):
The Shortest Vector Problem and the Prospects for Cryptosystems
Based on NP-Hard Problems}\\
(joint work with Rod Downey, Neal Koblitz, Alex Vardy and Geoff Whittle)

\medskip\noindent
In 1996 Ajtai showed that hard instances of the SHORTEST VECTOR
problem concerning integer lattices can be efficiently generated.
This is a major breakthrough in the fundamental problem of key generation
in cryptography, and even in our understanding of the nature of
computational intractability --- but wait: is SHORTEST VECTOR a hard problem?
This question has remained open for nearly 20 years.  Problems about
integer lattices seem to be closely related to problems about linear codes.
In particular, the SHORTEST VECTOR problem is formally very close to the
MINIMUM DISTANCE problem about linear codes, also conjectured for more than
20 years to be NP-hard.  Using deep coding theory arguments, Vardy has
recently shown that the MINIMUM DISTANCE problem is NP-hard.  The talk
will describe a fresh attack on this collection of fundamental problems
using the techniques of parameterized complexity.  Among the results:
MAXIMUM LIKELIHOOD DECODING and THETA SERIES FOR INTEGER LATTICES are
hard for the parameterized complexity class W[1].
The talk will describe some of the basics of
the parameterized complexity framework, some of the broader issues
concerning prospects for cryptosystems based on NP-hard problems,
and address some general remarks to the future of continued
fruitful collaborations between algebra and combinatorics in work
such as this.

\bigskip\bigskip\noindent
{\bf Andr\'as Frank (Budapest): Algorithms for increasing the connectivity
of digraphs}

\medskip\noindent
 In an earlier paper, co-authored by
T. Jord\'an, we proved a min-max formula for the necessary number of
new edges to be added to a digraph in order to increase its
connectivity.  The original proof is not algorithmic and our present
goal is to exhibit a constructive proof that gives rise to a
combinatorial polynomial time algorithm.  The same method yields a
simple algorithmic proof of Gy{\H o}ri's theorem on intervals. We
also describe a two-phase greedy algorithm to increase the rooted
connectivity of a digraph at minimum cost.


\def\midn#1{{{#1}\choose{\left\lfloor{{#1}\over2}\right\rfloor}}}
\def\sumai{\sum_{i\in I}a_i}
%%%%%%%%%%%

\bigskip\bigskip\noindent
{\bf Jerrold R. Griggs (University of South Carolina):
The Distribution of Subset Sums in $R^m$ and in Abelian Groups}

%%%%%%%%%%%
\medskip\noindent
We consider two separate problem areas that concern the distribution
of the $2^n$ subset sums $\sumai$, over all index sets $I$.
The first problem concerns maximizing the number of subset sums equal to
the same target point $t$, over all choices of $n$  vectors
$a_1, \ldots, a_n\in {\bf R}^m$ and all $t\in {\bf R}^m$, where some additional
condition on the $a_i$'s must be satisfied.
Such situations
arise naturally in connection with a certain model of database security:
The goal is to maximize the number of queries of a statistical
database that are answerable without compromising the database.
Well-known problems that arise in this way include the Littlewood-Offord
problem and the Erd\H os-Moser problem.
We shall focus on the problem of maximizing the concentration of subset
sums when each $m$ of the vectors $a_i$ form a basis.

The second subset sum project is joint work with Bjorn Poonen on
spanning sets in finite abelian groups $G$.
Let $a_1,\ldots,a_n$ be distinct nonzero elements of $G$.
We prove that if $n> |G|/2 $,  then the set of nontrivial
subset sums of the $a_i$'s includes every element of $G$.
Our main result is that this remains true,
when $n$ is reduced to $|G|/2$,
for groups $G$ of even order $>8$,  where it is best-possible.
For groups $G$ of odd order, the minimum required size $n$ remains open.
Dias da Silva and Hamidoune have solved the case that
$G={\bf Z}_p$, $p$ prime, settling an old problem of
Erd\H os and Heilbronn.
In that case, the answer is $\left\lfloor 2(p-2)^{1/2} \right\rfloor$.


\bigskip\bigskip\noindent
{\bf Arvind Gupta (Simon Fraser University): Monadic Second Order Logic and
Complement Problems}\\
(joint work with Damon Kaller and Tom Shermer)

\medskip\noindent
Graphs of bounded tree-width have an underlying tree-like structure
that often allows tree-based algorithms for problems to also work on
this larger class.  This class is the  same as the partial $k$-trees
for fixed $k$ and includes such well-studied graph families as
outerplanar graphs, series-parallel graphs and Halin graphs.
Since 1985 a concerted effort by many researchers has lead to a logical
characterization of those graph properties that have linear time
algorithms on this class; many of these properties are $\cal NP$-complete
for general graphs.  One of the most common characterization is the
Counting Monadic Second Order Logic (CMS).
Indeed many well known problems can be expressed in CMS or one of its
variants.

Succinctly, the theory states that any problem expressible in CMS will
have a linear time solution on bounded tree-width graphs.
That is, for some problem, let $\Pi$ be the set of yes-instances of the
problem and suppose $\Pi$ is CMS-definable.
Then for any constant $k$ and $G_k$ the class of partial $k$-trees, the
intersection $\Pi\cap G_k$ can be recognized by a {\em tree automaton}.
The tree-automaton is similar to a finite automaton except it works up
a tree (from leaves to root) with state changes dependent on child
labels and child states.
The resulting algorithm then takes a dynamic-programming approach similar
to the solution of the problem on a tree.

Despite the elegance of the CMS formalism, it is not always clear
which naturally-stated graph problems are CMS-definable.
This is an important issue because the ability of CMS logic to define
a problem is intimately related to the power of dynamic programming in
solving the problem.  This talk discusses the role of {\em complement}
problems in elucidating the structure of CMS-definable graph problems.
Again consider the set $\Pi$ of yes-instances and define
$\overline{\Pi}$ to consist of the graph-theoretic complements of all
graphs in $\Pi$.
We are interested in answering the following question:  {\em If $\Pi$ is
CMS-definable, when is $\overline{\Pi}$ CMS-definable?}
We show that in some cases $\overline{\Pi}$ is CMS-definable, but in
other cases $\overline{\Pi}\cap G_k$ is CMS-definable but not
$\overline{\Pi}$.
Furthermore, using a pumping lemma we show that in some cases not
even $\overline{\Pi}\cap G_k$ is CMS-definable.







\newcommand{\boldx}{{\hbox{$\boldmath x$}}}
\bigskip\bigskip\noindent
{\bf Mary Inaba (Tokyo): Geometric clustering problem}\\
(joint work with Hiroshi Imai)

\medskip\noindent
Clustering is a very important problem in statistics, image understanding,
computer graphics, etc.  There are two types of clustering problem, one
is clustering on a weighted graph (or a (dis)similarity matrix),
and the other is a geometric one.
Geometric clustering has nicer structures than the graph version
due to constraints induced by geometry.

This talk  first points out combinatorial optimization aspects
of the geometric clustering problem,
and summarizes recent results by our group
on the $k$-clustering problem for a set $S$ of
$n$ points $p_i=(\boldx_i)$ $(i=1,\ldots,n)$ in the $d$-dimensional space with
variance-based errors as clustering criteria.
A main problem is to find a $k$-clustering of $S$ into
$S_j$ $(j=1,\ldots,k)$ minimizing
$$
\sum_{j=1}^k\sum_{p_i\in S_j} \|\boldx_i-\bar \boldx (S_j)\|^2
$$
where $\|\cdot\|$ is the $L_2$ norm and $\bar \boldx (S_j)$
is the centroid of points in $S_j$, i.e.,
${1\over|S_j|}\sum_{p_i\in S_j} \boldx_i$.


Next,  relations of those results with the existing local improvement
technique, called $k$-means, are described, together with results of
computational experiments and its application to the
color quantization problem.
We also relate it to some mathematical programming
problem called geographic optimization problem by Iri, Murota, Ohya.
We further consider an improvement of the $k$-means
algorithm via overrelaxation, motivated from the viewpoint
of mathematical programming.


\bigskip\bigskip\noindent
{\bf Martin Klazar (Praha):
Extremal problems for colored trees}\\

\medskip\noindent
We discuss a generalization of the extremal problems connected
with {\em Davenport-Schinzel sequences\/} to trees. For example, in the case
of
has no immediate repetition of a symbol. For this particular problem the
maximu
What is the maximum number of vertices of a tree that can be vertex colored
by
at most $n$ colors so that (1*) no subgraph is a subdivision of the 6-vertex
path with color pattern $aabbab$, (2*) the coloring is proper and (3*) no
subgraph is a subdivision of the 4-vertex star with the (unique) proper
coloring pattern. Condition (3*), which is void for paths (i.e. DS
sequences),
We do not know if for the tree generalization the maximum size remains
$O(n)$.



\bigskip\bigskip\noindent
{\bf Alexander Kostochka (Novosibirsk):
On colour-critical graphs and hypergraphs with few edges}\\
(joint work with M.~Stiebitz)

\medskip\noindent
The aim of the talk is to describe the currently known
bounds for $f(r,k,n)$---the minimum possible number of edges
in $r$-uniform $k$-critical hypergraphs on $n$ vertices.
In particular,
it is proved that $f(r,k,n)=(k+o(k))n$  for each $r>2$ and new
lower bounds for $f(2,k,n)$ improving recent results by
M.~Krivelevich are given.


\bigskip\bigskip\noindent
{\bf Jan Kraj\'{\i}\v{c}ek (Oxford and Praha):
Proof complexity and some related
algebraico - combinatorial problems}

\medskip\noindent
We give some assorted examples of results
(recent as well as not so recent) on complexity
of proof systems, and of open problems they
motivate.

A proof system (tacitly for propositional logic here)
is a non - deterministic algorithm such that the property of being
an accepting computation is polynomial - time, and that
accepts exactly the set of propositional tautologies
in some complete language (or some other closely related
coNP-complete set like polynomial systems over a finite field
unsolvable in that field).

The statement that there is no polynomial - time proof system is
just the statement that NP~$\neq$~coNP. A research in proof complexity
aims currently at proving lower bounds for stronger and stronger
natural proof systems.
For example, it is open whether every tautology has a polynomial -
size
proof in the usual text - book calculus based on modus ponens.
In fact, no non - trivial lower bounds are known for this calculus
at all.

The topics we plan to discuss include: provability
and unprovability
(by short proofs) of counting principles in  propositional
calculi in various languages working with bounded depth formulas
only, related algebraic proof systems (systems manipulating
polynomials),
and various open problems of algebraico - combinatorial nature
motivated by these results.


\bigskip\bigskip\noindent
{\bf Jan Kratochv\'{\i}l (Praha): List colorings and choosability of graphs}\\
(joint work with Zs. Tuza and M. Voigt)

\medskip\noindent
Given a graph $G$ and a system $L:V(G)\to B$ of lists $L(u)$ of admissible
colors for particular vertices, we say that $(G,L)$ is {\em list colorable}
if there is a proper coloring choosing for every vertex $u$ a color from
$L(u)$. A graph is called {\em $k$-choosable} if it is list colorable for
every system of lists of sizes $\ge k$.

It is well known that determining the choosability of a given graph is a
PSPACE-complete problem, and deciding list colorability is NP-complete. We
will investigate the complexity of restricted variants of list colorings
and choosability, also for a more general notion of $(p,q,r)$-choosability.

In particular, we will consider list colorings nearly disjoint lists
adjacent vertices having nearly disjoint lists and we will prove bounds for
this variant of choosability, which are tight upto a multiplicative
constant.


\bigskip\bigskip\noindent
{\bf Lud\v ek Ku\v cera (Lyon and Praha):
Fast deflection routing of long messages}

\medskip\noindent
In order to obtain lowest possible latency, routing algorithms should try
to avoid message waiting for resources (network links) blocked by other
messages and multiplexing of more messages over one physical channel.
This requirement becomes an imperative in the case of long messages.
The only type of protocols able to guarantee this type of routing under
heavy load are algorithms based on deflection (also called nonminimal
adaptive or hot potato) routing.

The paper deals with problems connected with the use of deflection
algorithms. In contrast the case of nonadaptive or partially adaptive
routing, it is very infrequent that a deflection routing becomes deadlocked
and similarly livelock is not a serious problem. On the other hand, there
are two other phenomena, called together a {\em deflection jam}, that limit
throughput of deflection algorithms used to route long messages. They have
been observed for many deflection heuristics, interconnection network
topologies and both virtual cut-through and wormhole routing.

Under a light load orthodox deflection algorithms rou\-te messages in an
almost optimal way, but if the load reaches a certain threshold value, which
is still relatively low, it might happen that the communication suddenly
breaks down almost completely after thousands or even millions of steps of
smooth information exchange. A low load deflection jam need not to lock
messages for ever, but the network throughput decreases to a very small
fraction of the original value and the saturation tends to be persistent.

An analysis presented in the paper shows how to modify naive deflection
algorithm to preserve their very low latency while extending the range of
a sustainable load well beyond the above threshold. The throughput of such
algorithms is usually limited by a high load deflection jam, which occurs
when the subnetwork of free channels becomes highly disconnected and
represent the ultimate bound for efficient deflection-type routing.

\bigskip\bigskip\noindent
{\bf L\'aszl\'o Lov\'asz (Yale and Budapest):
Random walks, mixing, and sampling}\\
(joint work with Peter Winkler)

\medskip\noindent
Random walk techniques have many applications to the problem of
sampling, i.e., to the problem of generating a random element from a
given distribution. Applications of such methods include
simulation in statistical mechanics, combinatorial
enumeration, integration, volume computation, generation of
contingency tables, and optimization over convex bodies.

The basis of these methods is the fact that if we do random walk on a
(non-bipartite, connected) graph, the distribution of the current node
after $t$ steps will tend to a limit distribution
(as $t$ tends to infinity) in which the
probabilities of nodes are proportional to the degrees.  Crucial in
these applications is the question of how long we have to walk before
getting close to the limit distribution.

It is not necessary that every walk stops after the same number of steps.
In fact, making the stopping rule dependent on the history, any
prescribed distribution can be achieved exactly.
There exist optimal stopping rules
(minimizing the expected number of steps before stopping) of a rather
simple kind. The time used by an optimal stopping rule is a
relatively well-behaved and easily computable value. While an
optimal rule to the stationary distribution
may be impossible to implement in practice, there is a
very simple, easily implementable rule that gives a good approximation
and is only a (decent) constant factor slower than the optimal rule.

Various algorithmic situations suggest a number of other
``mixing measures''. One of these is the
"reset time", which may be defined as the minimum mean length of
a stopping rule that, when started from the stationary distribution,
generates a node that has the same distribution but is independent
from the starting node. Another one is the "forget time": this is defined
as the minimum mean length of any stopping rule that yields the same
distribution, independently from the starting node.

A surprising (and not quite easy) fact is that the forget time of a chain
is equal to the reset time of the time-reversed chain.  In particular,
the forget time and the reset time of a time-reversible chain are
equal. There are a number of unexpected further identities and ``approximate
identities'' between mixing measures.

\bigskip\bigskip\noindent
{\bf Tomasz Luczak (Poznan): Random trees and random graphs}

\medskip\noindent
 We describe some simple self-similarity arguments
   which can be used to study random trees. In particular,
   we find the asymptotic number of trees of large height,
   which immediately leads to a precise estimate of the diameter
   of the random graph in the subcritical phase.


\bigskip\bigskip\noindent
{\bf Eugene Luks (Eugene):
Algorithmic Applications of the Simple Groups Classification}

\medskip\noindent
The Classification of Finite Simple Groups stands as a monumental
mathematical achievement, its implications far-reaching, and
occasionally surprising.  We survey several applications to the
computational complexity of problems that have seemingly elementary
formulations.  In some instances, the Classification is currently
needed just to attain polynomial time, in others to establish
parallelizability.  There are also significant consequences in
low-level complexity, facilitating speedups of an order-of-magnitude
or more for much of the group-theoretic machinery.  This includes the
very basic, and well-worked, problem of testing membership in a
permutation group.  Particularly useful tools stem from
Classification-dependent observations of Cameron about the structure
of primitive permutation groups; such groups frequently occur as the
base case of combinatorial divide-and-conquer algorithms.  There is
even an impact on the best result for testing graph-isomorphism as a
result of a sharpening of Babai's combinatorial bounds on the orders
of primitive groups.  It is noteworthy that the Classification is most
often invoked via succinct, uncomplicated corollaries.  However,
some algorithms demand a case-by-case analysis of the classes of
simple groups.

\bigskip\bigskip\noindent
{\bf Wolfgang Mader (Hannover): An extremal problem for subdivisions of
$K_5$ and topological
subgraphs in graphs of large girth}

\medskip\noindent
We prove that every graph with $n\ge  3$ vertices and
$3n - 5$ edges contains a subdivision of $K_5$. This is best possible
for every $n$ and had been conjectured by Dirac in 1964. We shall
also characterize the graphs with $3n - 6$ edges without a
subdivision of $K_5$. A key result in the proof is that every
graph with $n\ge 6$ vertices, $2n -5$ edges, and girth at
least 5, but the Petersen graph, contains a subdivision of
$K_5 - e$ ( $e$ an edge ). So we will study also the interrelation
between the existence of subdivisions and girth.


\bigskip\bigskip\noindent
{\bf Ji\v{r}\'{\i} Matou\v sek (Praha): Upper bounds in geometric and
combinatorial discrepancy}

\medskip\noindent
Geometric discrepancy theory studies the question ``How uniformly
can an $n$-point set be distributed in a given region of
space?''. Combinatorial discrepancy is concerned with 2-coloring points
of a set system in such a way that the colors on each set are
as balanced as possible. We discuss a technique (the so-called
entropy method) that leads to asymptotically optimal bounds
in several problems from both areas. We also point out some open
problems where new methods seem to be called for.



\newcommand{\g}{$G$ }
\newcommand{\cp}{$\cal P$ }
\newcommand{\ci}{$\cal I$ }
\newcommand{\pn}{${\cal P}_1,{\cal P}_2,\dots ,{\cal P}_n$ }
\newcommand{\pnb}{${\cal P}_1.{\cal P}_2.\dots .{\cal P}_n$ }
\newcommand{\ppn}{$({\cal P}_1,{\cal P}_2,\dots ,{\cal P}_n)$ }
\newcommand{\vn}{$(V_1,V_2,\dots ,V_n)$ }
\newtheorem{probl}{Problem}
\newtheorem{rem}{Remark}
\newcommand{\text}{\mbox}


\bigskip\bigskip\noindent
{\bf P. Mih\'ok (Ko\v{s}ice):
Additive and monotone properties of graphs are uniquely
factorizable into irreducible factors}


\medskip\noindent
Let us denote by \ci the class of all mutually nonisomorphic
finite simple graphs. If $\emptyset \not = {\cal P}\subset{\cal
I}$ be a nonempty isomorphism-closed subset of \ci, then \cp denote
the property of
graphs. A property \cp is said to be {\it monotone} whenever
$H\subseteq G \text { and } G\in{\cal P}$ implies  $H\in {\cal P}$ and
{\it additive} if it is closed under the disjoint union of
graphs. (For more details see~[M.Borowiecki, I.Broere, M.Frick, P.Mih\' ok
and G.Semanisin:
{\it Survey of hereditary properties of graphs}
Discussiones Math. - Graph Theory, {\bf 17}, 1997, to appear] and~
[T.R.Jensen and B.Toft: {\it Graph Colouring
Problems}, Wiley - Interscience Publications, New
York, 1995]).

Let \pn be properties of graphs, a vertex \ppn-
partition of a graph $G$ is a partition \vn of the vertex set
$V(G)$ such that the induced subgraph $G[V_i]\in{\cal P}_i$ for
$i=1,2,\dots ,n$.

Let us denote by $U$\ppn the set of all
graphs which posses unique vertex \ppn- partition and
${\cal R}=$\pnb the set of all vertex \ppn- partitionable graphs. It
is easy to see, that if \pn are additive and monotone
properties of graphs, then ${\cal R}=$\pnb is additive and
monotone,too. The property ${\cal R}=$\pnb, $n\geq 2$ is said to be
reducible,
i.e. \cp is reducible if there exist ${\cal P}_1,{\cal P}_2$ such
that ${\cal R}={\cal P}_1.{\cal P}_2$ and irreducible otherwise.

A graph $G$ is said to be \cp-maximal if $G \in {\cal P}$ but for
any edge $e$ of its complement $G+e \notin {\cal P}$.

To characterize the reducible properties of graphs the
following problems seems to be natural.

{\bf Problem 1} UNIQUE FACTORIZATION PROBLEM
[T.R.Jensen and B.Toft: {\it Graph Colouring
Problems}, Wiley - Interscience Publications, New
York, 1995]
\newline
Let ${\cal R}$ be a reducible property of graphs and ${\cal R}=$\pnb,
$n\geq 2$
be a factorization of ${\cal R}$ into irreducible factors. Is the
factorization unique (apart from the order of factors)?

This basic question is related to the following problems:

Let ${\cal R}=$\pnb, $n\geq 2$ be a factorization of the property $R$
into irreducible factors. Do the following statements hold?

{\bf Problem 2} THE STRUCTURE OF MAXIMAL GRAPHS
\newline
If the property ${\cal R}$ is reducible, then all ${\cal
R}$-maximal graphs are joins of at least n graphs. Is this
necessary condition also sufficient?

{\bf Problem 3} THE EXISTENCE OF UNIQUELY
PARTITIONABLE GRAPHS
\newline
$U({\cal P}_1.{\cal P}_2.\dots .{\cal P}_n)\not = \emptyset$,
moreover $U({\cal P}.{\cal P}.\dots .{\cal P})\not =
\emptyset$ if and only if ${\cal P}$ is irreducible.

We shall present an affirmative solution of all of above presented
problems.


\bigskip\bigskip\noindent
{\bf Jaroslav Ne\v set\v ril (Praha): The Structure of Graph Homomorphisms}

\medskip\noindent
Graph homomorphisms appear naturally in the context of various combinatorial
problems, especially related to coloring and construction (and
reconstruction) algebraical problems. On the other hand, homomorphisms
yield a ``minimal calculus" for graphs, thus providing a natural setting
for seemingly isolated problems.

In the talk, we want to list some of the recent results and open problems
in this area related to the structure of color classes, universality and
duality theorems.



\bigskip\bigskip\noindent
{\bf Petr Pan\v{c}o\v{s}ka (Chicago and Praha):
Spectra, graphs and proteins. Towards understanding of protein folding}\\
(joint work with V. Janota and J. Ne\v set\v ril)

\medskip\noindent
With proper transformation of protein three-dimensional structures known
from x-ray crystallography, various features of protein conformation can be
encoded into mathematical objects (vectors, matrices, graphs, strings,
fractals and others). Examples of novel graph representations of segment
topology of globular proteins and polypeptide backbone distance matrix will
be shown together with practical applications in analysis of protein optical
spectra and protein fold classification.  Problems related to the analysis
of mathematical properties of the resulting graphs will be formulated. When
the chemical composition of the sets of edges of graph representation of the
backbone distance matrix was analyzed using the basic theorems of coding
theory, a simple method for identification of structurally correlated parts
of protein primary structure was formulated. Examples of structural
interpretation of this result will be given for a representative set of
nohomologous protein structures. Example of application for analysis of
protein function will be demonstrated using the database of somatic
mutations of protein p53 in human tumors.


\bigskip\bigskip\noindent
{\bf Pavel Pudl\'{a}k : New algorithms for satisfiability}\\
(joint work with Ramamohan Paturiand Francis Zane)

\medskip\noindent
We present and analyze two simple algorithms for finding satisfying assignments
of
$k$-CNFs (Boolean formulae in conjunctive normal form with at most $k$ literals
per clause).  The first is
a randomized algorithm which, with probability approaching 1,
finds a satisfying
assignment of a satisfiable $k$-CNF formula $F$ in time $O(n^2 |F| 2^{n-n/k})$.
The second algorithm is deterministic, and its
running time approaches $2^{n-n/2k}$ for large $n$ and $k$.  The
randomized algorithm is the best known algorithm for $k>3$;
the deterministic algorithm is the best
known deterministic algorithm for $k>4$. The key idea
used in these upper and lower bounds is what we call the {\em Satisfiability\
Coding\ Lemma}.
This basic lemma shows how to encode satisfying solutions of a $k$-CNF
succinctly.




\bigskip\bigskip\noindent
{\bf Fred S. Roberts
(Rutgers): Meaningless Statements}

\medskip\noindent
A statement involving scales of measurement is called meaningless if
its truth or falsity can depend upon the particular versions of scales
which are used in the statement.  This is an idea which is closely
related to the theme of invariance, which has played such a central
role in the history of the mathematical sciences, for instance in the
Erlanger Program of Felix Klein, in geometry, in physics, and so on.
We develop the theory of meaningful and meaningless statements.  This
theory has had a wide variety of applications and we concentrate here
on examples relevant to fundamental ideas in discrete mathematics:
limitations on conclusions in combinatorial optimization, and in
particular in graph coloring and scheduling; limitations on
conclusions in linear programming and game theory; and limitations on
the possible consensus functions which are appropriate in group
decisionmaking.

\bigskip\bigskip\noindent
{\bf Moshe Rosenfeld (Tacoma):
3 problems in combiatorial number theory}

\medskip\noindent
Let $n$ be a positive integer. The Factor-Difference-Set, $D(n)$ of $n$,
is defined by: $D(n) = \{|a-b| : ab = n\}$. We conjecture that for
every integer $k$, there are $k$ integers $n_1 < n_2 < \ldots < n_k$
such that $|\bigcap_{i=1}^k D(n_i) | \geq k$. In the first part I'll trace
the origin of this problem and discuss some related results. This
work was done with Paul Erd\H{o}s.


Let $(A,B)$ be a partition of $\{1,2,\ldots,2n\}$ into two disjoint $n$-sets.
We say that $A$ and $B$ are gracefully matched if one can sequence $A$ and
$B$
so that all differences $\pm(a_i - b_i)\mbox{ mod }(2n + 1)$ will be distinct.
We conjecture that for $n \geq 4$ all partitions of $\{1,2,\ldots,2n\}$
admit a graceful matching. We use a theorem of Weil to prove that
if $A = Q(q), B = N(q)$ where $q = p^r$, $r$ an odd prime, $Q(q)$
the quadratic
residues in $GF(q)$, $N(q)$ the non-residues in $GF(q)$ can be gracefully
matched. Applications and related open problems will be discussed.
This is joint work with J. Kratochv\'{\i}l, J, Ne\v set\v ril and Tamas Szonyi.



Consider an $n \times n$ square chess board. Select randomly a set of
squares and "cover" it. We say that the covered set $A$ can be doubled
if there is a translation of $A$ that will occupy only uncovered squares.
Suppose you start with a set $A$ consisting of a single square, double
$A$ then continue doubling the new set. How many times can we repeat the
doubling before we run out of space? This problem is related to the
Shannon Capacity of cycles, and special subspaces of $GF^n(q)$. We discuss
this problem and a nice uniqueness proof communicated to me by
Rafael Robinson.


\bigskip\bigskip\noindent
{\bf G\"unter Rote (Graz): Convex 3-polytopes can be realized with
linearly many bits per coordinate}
\newif\ifKURZ \KURZtrue

%% IF THE ABSTRACT IS TOO LONG,
%% DELETE THE FOLLOWING LINE TO OBTAIN A SHORTER VERSION OF THE ABSTRACT.
\KURZfalse

\medskip\noindent
By a theorem of Ernst Steinitz~(1922),
every 3-connected planar graph with $n$ vertices can be realized as a convex
polytope.
We can do this with integer vertex coordinates between $-C$ and~$C$, where
$C=43^n$.

Onn and Sturmfels~(1994) have shown this for $C=2^{169 n^3}$.
\ifKURZ\else

Das and Goodrich~(1995) have given an algorithm that works for triangulated
3-polytopes and selects rational vertex-coordinates with polynomially many
bits for the numerator and the denominator, i.e., $C=2^{n^{O(1)}}$.
However, their algorithm takes only a linear number of steps (including
arithmetic operations on numbers of size at most~$C$).

The approach of Das and Goodrich is more closely related to the original proof
of Steinitz, who builds up the polytope from simpler polytopes by making
local changes.
\fi
(Steinitz's original proof yields a doubly-exponential bound for~$C$.)

We follow the approach of Onn and Sturmfels, who exploit the connection
between 3-polytopes and {\it stresses\/} on the edges of a plane projection of
a polytope, which goes back to Maxwell (1864).
We fix a triangular face as exterior face, interpret all
remaining edges as springs with elasticity $w=1$, and compute the
equilibrium of this mechanical system.
\ifKURZ\else
This amounts to solving a system
of linear equations, and leads to vertex coordinates of size at most~$42^n$.
The same procedure was also used by Tutte (1960) for obtaining a nice drawing
of a planar graph.

\fi
The next step calculates the polytope which projects onto this drawing.
\ifKURZ
We can
\else
In contrast to Onn and Sturmfels, who find such a polytope by solving a
system of inequalities for the $z$-coordinates, we
\fi
do this directly by exploiting the
geometric significance of the edge weights.
\ifKURZ
Finally, in case the graph contains no triangle,
\else

Finally, the case that the graph contains no triangles
is not treated by realizing
the dual graph and then going to the polar polytope. Instead,
\fi
we carefully select the shape of a 4-sided or 5-sided face to ensure that an
equilibrium on the interior vertices can be extended to the whole graph.

The question whether the bound $C$ can be improved to a polynomial is open.

\bigskip\bigskip\noindent
{\bf Ji\v r\'{\i} Sgall (Praha): On Pairs of Intersecting Families}\\
(joint work with Pavel Pudl\'ak)

\medskip\noindent

We study pairs of families ${\cal A},{\cal B}\subseteq 2^{\{1\ldots r\}}$ such
that $|A\cap B|\in L$ for any $A\in{\cal A}$, $B\in{\cal B}$. We are
interested in the maximal product $|{\cal A}|\cdot|{\cal B}|$, given $r$ and
$L$.

We give tight bounds for $L=\{1\ldots k\}$ and partial results for
$L=\{k,k+1\}$.

This latter case is motivated by a conjecture about the relation
between communication complexity and rank of a matrix.






\vfill
\def\L{{\cal L}}
\def\ext{{\rm ext}}
\bigskip\bigskip\noindent
\vbox{
{\bf Mikl\'os Simonovits (Budpest): 
General methods to prove exact results
in extremal graph theory}
}\nopagebreak

\medskip\noindent
In the talk I will present a few general methods to prove {\bf exact} results
in extremal graph theory.

Given a family $\L$ of -- so called -- forbidden graphs, denote by
$\ext(n,\L)$ the maximum number of edges a graph $G_n$ of
order $n$ can have under the conditions that $G_n$ contains no
forbidden subgraphs $L\in \L$. Generally we wish to determine $\ext(n,\L)$,
or at least get good asymptotics as $n\rightarrow\infty$. Besides, it is
important also to determine the (asymptotical) structure of the graphs
attaining the maximum.

Mostly we can get good asymptotics but not exact results in such cases.
Here we shall regard cases where for $n>n_0(\L)$ we have the exact values
of the function $\ext(n,\L)$.

Some of the results presented here are joint with J. Griggs and Thomas Rubin.




\bigskip\bigskip\noindent
{\bf G\'abor Simonyi (Budapest): Information theory in combinatorics}

\medskip\noindent
Information theoretic concepts and methods
helped to solve some combinatorial problems during the last
decade. Two outstanding examples are Kahn and Kim's sorting
algorithm in [J. Kahn and J. H. Kim, Entropy and sorting, {\it Proc. 24th
Annual ACM Symposium on the Theory of Computing}, 178--187] and the solution of R\'enyi's qualitative
2-independence problem by Gargano, K\"orner, and Vaccaro, cf.
[L. Gargano, J. K\"orner, U. Vaccaro, Capacities: from
information theory to extremal set theory, {\it J. Comb. Theory, ser A},
{\bf 61} (1992), 173--192].  The key role in both of the above cases is played
by a graph functional that also depends on a probability
distribution on the vertex set of the graph at hand. In the first case
this functional is K\"orner's notion of graph entropy, a
probabilistic refinement of the chromatic number, cf.
[G. Simonyi, Graph entropy: a survey,
{\it in} ''Combinatorial Optimization'', DIMACS Series
in Discrete Math. and Theoretical Comp. Sci., Vol. 20
(W Cook, L. Lov\'asz, and P. D. Seymour eds.), 399--441].
In the second case it is an analogous notion for
the clique number which has very close connections to the
Shannon capacity of graphs.  The talk is intended to describe
these and other connections between information theory and
combinatorics and also formulate some open problems.



\bigskip\bigskip\noindent
{\bf W. F. Smyth (McMaster): Periodicity in strings}
\nopagebreak

\medskip\noindent
Periodicity in strings can be generalized in various interesting ways,
some of which have applications, to molecular biology, for example.
In this talk I discuss some of these generalizations: covers, k-covers,
weak repetitions, nontandem repetitions, approximate repetitions.
Some algorithms that compute approximate periodicity are described,
and some open problems are indicated.

\bigskip\bigskip\noindent
{\bf Eric Sopena (Bordeaux): Acyclic Improper Colorings}\\
(joint work with Pierre Boiron and Laurence Vignal)

\medskip\noindent
Many variations and extensions of graph colorings have been considered
in the literature (see [Jensen, T.R. and Toft, B.:
{\em Graph Coloring Problems.}
Wiley Interscience, 1995] for a general overview). In particular,
{\em improper} colorings (sometimes called {\em genreralized}, {\em defective}
or {\em relaxed} colorings) have been extensively studied. A coloring of a
graph $G$ is said to be improper whenever two adjacent vertices may be
assigned the same color. In such colorings, the adjacency constraint is thus
replaced by some constraint on the structure of {\em monochromatic
subgraphs}. We will say that such an improper coloring is {\em acyclic}
if for every two colors $i$ and $j$, the subgraph induced by the edges
whose endpoints are respectively $i$- and $j$-colored is acyclic.
This notion generalizes the usual notion of acyclic coloring.

Our motivation when introducing such colorings was the study of
homomorphisms of oriented graphs [Kostochka, A.V., Sopena, E. and Zhu, X.:
Acyclic and oriented chromatic numbers of graphs.
{\em J. Graph Theory}, to appear],
[Ne\v set\v ril, J., Raspaud, A. and Sopena, E.:
Colorings and girth of oriented planar graphs.
{\em Discrete Math.}, to appear],
[Raspaud, A. and Sopena, E.:
Good and semi-strong colorings of oriented planar graphs.
{\em Inform. Processing Letters} 51:171--174, 1994],
[Sopena, E.
The chromatic number of oriented graphs.
{\em J. Graph Theory}, to appear]. We prove that the existence
of some special acyclic improper colorings of a graph allows to derive
an upper bound on its oriented chromatic number [Sopena, E.
The chromatic number of oriented graphs.
{\em J. Graph Theory}, to appear]. Acyclic improper
coloring are also related, in a similar way, to homomorphisms of
edge-colored graphs, recently introduced by Alon and Marshall
[Alon, N. and Marshall, T.H.:
Homomorphisms of edge-coloured graphs and Coxeter groups.
{\em Manuscript}, 1996].

We shall review some results on acyclic improper colorings of
outerplanar graphs, planar graphs and graphs with bounded degree
and mention some open questions.



\bigskip\bigskip\noindent
{\bf Joel Spencer (New York): Sophisticated Probability}

\medskip\noindent
It wasn't too many decades ago that the probability needed for
random structures and/or probabilistic methods was quite elementary:
expectation, variance and the Chernoff bounds could carry one a long long
way.  No longer.  We discuss some examples:
Large deviation results using  inequalities of Janson and
Talagrand. Martingales in surprising forms.  Entropy arguments.
Asymptotic approximation of random processes by continuous time branching
processes. Most recently, Fourier Analysis to characterize coarse
threshold behavior.


\bigskip\bigskip\noindent
{\bf Robin Thomas (Atlanta):
Permanents, Pfaffian orientations, and even directed circuits}\\
(joint work with N. Robertson and P.D. Seymour)

\medskip\noindent
   Given an $n$ by $n$ 0-1 matrix $A$, when can some of the 1's be changed to
$-1$'s in such a way that the permament of $A$ equals the determinant of the
modified matrix? When does a real $n$ by $n$ matrix $A$ have the property that
every real matrix $B$ with the same sign pattern (that is, the corresponding
entries either have the same sign, or are both zero) is non-singular?
When is a hypergraph with $n$ vertices and $n$
hyperedges minimally non-bipartite?
When does a bipartite graph have a "Pfaffian orientation"? Given a digraph,
does it have a directed circuit of even length? Given a digraph, does it have
a subdivision with no even directed circuit?

  It is known that all the above problems are equivalent. We prove a
structural characterization of the feasible instances, which implies a
polynomial-time algorithm to solve all of the above problems. The structural
characterization says, roughly speaking, that a bipartite graph has a
Pfaffian orientation if and only if it can be obtained by piecing together
(in a specified way) planar bipartite graphs and one sporadic non-planar
bipartite graph.

 The structural
characterization was independently obtained by W. McCuaig.


\def\Prob{\mbox{Prob}}
\def\eps{\varepsilon}
\bigskip\bigskip\noindent
{\bf W.T.Trotter (Tempe):
 Ramsey theory and sequences of random variables}\\
(joint work with Peter Winkler)

\medskip\noindent
We consider probability spaces
which contain a family $\{E_A:A\subseteq \{1,2,\dots,n\}, |A|=k\}$
of events indexed by the $k$--element subsets of $\{1,2,\dots,n\}$.
Our goal, albeit one which is not precisely defined, is to
develop a ``Ramsey theory'' for probability spaces.  We begin
by studying notions of patterns and uniformity.  This line
of research was originally motivated by a question of
Brightwell and Scheinerman involving the fractional
dimension of partially ordered sets, and we set out to
develop a theoretical base sufficient to settle their
question.  This approach led naturally to the following
question:

A pair $(A,B)$ of $k$--element subsets of $\{1,2,\dots,n\}$
is called a {\em shift pair} if the largest $k-1$
elements of $A$ coincide with the smallest $k-1$ elements of $B$.
For a shift pair $(A,B)$, $\Prob[A\overline{B}]$ is the
probability that event $E_A$ is true and $E_B$ is false.
We investigate how large the minimum value of $\Prob[A\overline{B}]$,
taken over all shift pairs, can be.  As $n\rightarrow\infty$,
this value converges to a number $\lambda_k$, with $\frac{1}{2}-
\frac{1}{2k+2}\le\lambda_k\le\frac{1}{2}-\frac{1}{4k+2}$.
We show that $\lambda_k$
is a strictly increasing function of $k$, with
$\lambda_1=\frac{1}{4}$ and $\lambda_2=\frac{1}{3}$.

For $k=1$, our results have the following natural interpretation.
If a fair coin is tossed repeatedly, and event
$E_i$ is true when the $i^{\underline{th}}$ toss is heads, then
for all $i$ and $j$ with $i<j$, $\Prob[E_i\overline{E_j}]=
\frac{1}{4}$. Furthermore, as we show in this paper,
for any $\eps>0$, there is an $n$ such that for any sequence
$E_1,E_2,\dots,E_n$ of events in an arbitrary probability
space, there are indices $i<j$ with
$\Prob[E_i\overline{E_j}]<\frac{1}{4}+\eps$.
The results and techniques we develop in this research,
together with further applications of Ramsey theory,
are then used to answer Brightwell and Scheinerman's
question by showing that the supremum of fractional dimensions
of interval orders is exactly 4.

Generalizing the $\frac{1}{4}+\eps$ result to random variables
$X_1,X_2,\dots,X_n$ with values in an $m$--element set, we obtain a
finite version of de Finetti's theorem without the exchangeability
hypothesis: for any fixed $m$, $k$ and $\eps$, every sufficiently
long sequence of such random variables has a length-$k$ subsequence
at variation distance less than $\eps$ from an i.i.d.\ mix.


\bigskip\bigskip\noindent
{\bf Pavel Valtr (Rutgers and Praha):
Several recent results on geometric graphs}

\medskip\noindent
A {\em geometric graph\/}  is a graph $G=(V,E)$ drawn in the
plane so that the vertex set $V$ consists of points in general
position and the edge set $E$ consists of some of the straight line
segments between points of $V$. We will talk about
recent extremal-type results on geometric graphs. E.g.,
we will discuss upper bounds on the maximum number of
edges in a geometric graph on $n$ vertices
with no $k$ pairwise disjoint (pairwise crossing) edges.


%\newpage
%\section{Few words about \v Sti\v r\'{\i}n}
%
% Stirin is a small, high-baroque castle which has
%recently been renovated as a conference center and a stylish hotel. The
%castle is situated in a beautiful park which includes a golf course
%and tennis courts.  The common facilities include 2 conference rooms,
%2 smaller banquet rooms and a chapel (used for concerts).















\end{document}

