[DMANET] PhD studentship in Algorithms & Complexity, Uni of Edinburgh

There is the funding for an EU PhD student with an excellent
Mathematical background to study within the Algorithms & Complexity
group at the University of Edinburgh. The proposed research topic
is below (though there is some flexibility with regard to topic).
The deadline is noon on Friday, 6th March. Please contact me
(Mary Cryan) in the first instance.


Measuring, Counting and Sampling in Polytopes
supervisor: Mary Cryan

The project proposes to study some algorithmic and combinatorial
questions regarding a special class of high-dimensional polytopes
called transportation polytopes - we will be interested in the
diameter of these polytopes, the (number of, and shape of) vertices
of the polytopes, and the number of lattice points inside these
polytopes (the lattice points are also known as contingency tables).
In recent years, there has been a bustle of activity concerning the
diameter of general multi-dimensional polytopes - the big result
being Francisco Santos' counterexample disproving the "Hirsch
conjecture". Despite this, the question of the diameter of
special classes of polytopes remains open, and there is a
possibility (for example) that the class of transportation
polytopes does satisfy that conjecture.

Apart from diameter the question of counting/sampling contingency
tables remains open for the general case, and we would plan to spend
some time re-examining that problem. In that case our concern is in
obtaining polynomial-time algorithms. We may alternatively spend
time considering different counting and sampling questions. Our
early results will influence the later direction of the project.

--
Mary Cryan, Phone: 0131 6505153
School of Informatics, Fax: 0131 6511426
University of Edinburgh Office: IF 5.16




--
The University of Edinburgh is a charitable body, registered in
Scotland, with registration number SC005336.

**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************