Personal tools
You are here: Home Graduate Study Measuring, Counting and Sampling in Polytopes

Measuring, Counting and Sampling in Polytopes

Research project on algorithmic and combinatorial aspects of diameter, lattice points and vertices of simplified polytopes.


Measuring, Counting and Sampling in Polytopes

Potential 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. 

That would be our starting point for the research.

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.

There is a possibility of funding for an EU student to work on this project; deadline is noon, Friday 6th March, 2015. 

Document Actions