L3

Static vacuum data and their conformal classes play an important role in the discussion of the smoothness of gravitational fields at null infinity. We study the question under which conditions such data admit non-trivial conformal rescalings which lead again to such data. Some of the restrictions implied by this requirement are discussed and it is shown that there exists a 3-parameter family of static vacuum data which are not conformally flat and which admit non-trivial rescalings.

I will discuss ongoing work to provide a proof for the following

conjecture: if the development of a time symmetric, conformally flat

initial data set admits a smooth null infinity, then the initial data

is Schwarzschildean in a neighbourhood of infinity. The strategy

to construct a proof consists in a detailed analysis of a

certain type of expansions that can be obtained using H. Friedrich's

"cylinder at infinity" formalism. I will also discuss a toy model for

the analysis of the Maxwell field near the

spatial infinity of the Schwarzschild spacetime

By classical results of Tarski and Artin-Schreier, the elementary theory of the field of real numbers can be axiomatized in purely Galois-theoretic terms by describing the absolute Galois group of the field. Using work of Ax-Kochen/Ershov and a p-adic analogue of the Artin-Schreier theory the same can be proved for the field $\mathbb{Q}_p$ of p-adic numbers and for very few other fields.

Replacing, however, the absolute Galois group of a field K by that of the rational function field $K(t)$ over $K$, one obtains a Galois-theoretic axiomatiozation of almost arbitrary perfect fields. This gives rise to a new approach to longstanding decidability questions for fields like

$F_p((t))$ or $C(t)$.

Hypergraph Transversals have been studied in Mathematics for a long time (e.g. by Berge) . Generating minimal transversals of a hypergraph is an important problem which has many applications in Computer Science, especially in database Theory, Logic, and AI. We give a survey of various applications and review some recent results on the complexity of computing all minimal transversals of a given hypergraph.

Phylogenetics is the reconstruction and analysis of 'evolutionary'

trees and graphs in biology (and related areas of classification, such as linguistics). Discrete mathematics plays an important role in the underlying theory. We will describe some of the ways in which concepts from combinatorics (e.g. poset theory, greedoids, cyclic permutations, Menger's theorem, closure operators, chordal graphs) play a central role. As well as providing an overview, we also describe some recent and new results, and outline some open problems.

The transportation problem (TP) is a classic problem in operations research. The problem was posed for the first time by Hitchcock in 1941 [Hitchcock, 1941] and independently by Koopmans in 1947 [Koopmans, 1948], and appears in any standard introductory course on operations research.

The mxn TP has m supply points and n demand points. Each supply Point i holds a quantity r_i, and each demand point j wants a quantity c_j, with the sum of femands equal to the sum of supplies. A solution to the problem can be written as a mxn matrix X with entries decision x_{ij} having value equal to the amount transported from supply point i to demand point j. The objective is to minimize total transportation costs when unit transporation costs between each supply and each demand point are given.

The set of feasible solutions of TP, is called the transportation polytope.

The 1-skeleton (edge graph) of this polytope is defined as the graph with vertices the vertices of the polytope and edges its 1-dimensional faces.

In 1957 W.M. Hirsch stated his famous conjecture cf. [Dantzig, 1963]) saying that any d-dimensional polytope with n facets has diameter at most n-d. So far the best bound for any polytope is O(n^{\log d+1}) [Kalai and Kleitman, 1992]. Any strongly polynomial bound is still lacking. Such bounds have been proved for some special classes of polytopes (for examples, see [Schrijver, 1995]). Among those are some special classes of transportation polytopes [Balinski, 1974],[Bolker, 1972] and the polytope of the dual of TP [Balinski, 1974].

The first strongly polynomial bound on the diameter of the transportation polytope was given by Dyer and Frieze [DyerFrieze, 1994]. Actually, they prove a bound on the diameter of any polytope {x|Ax=b} where A is a totally unimodular matrix. The proof is complicated and indirect, using the probabilistic method. Moreover, the bound is huge O(m^{16}n^3ln(mn))3) assuming m less than or equal to n.

We will give a simple proof that the diameter of the transportation polytope is less than 8(m+n-2). The proof is constructive: it gives an algorithm that describes how to go from any vertex to any other vertex on the transportation polytope in less than 8(m+n-2) steps along the edges.

According to the Hirsch Conjecture the bound on the TP polytope should be

m+n-1. Thus we are within a multiplicative factor 8 of the Hirsch bound.

Recently C. Hurkens refined our analysis and diminished the bound by a factor 2, arriving at 4(m+n-2). I will indicate the way he achieved this as well.