Combinatorics and Computation of the Permanent (Christmas lecture)
Abstract:
The permanent is a matrix function that is much less known
than its big brother, the determinant. Originally introduced by
Cauchy and Binet in 1812, it was studied more systematically
by Muir in 1882. However, only after the Dutch mathematician
Van der Waerden conjectured that the permanent attains its
minimum (over all doubly stochastic matrices) in the constant
double stochastic matrix, research on properties of the
permament started to flourish. A book by Minc solely devoted
to the permament is a classic in this area.
After the Van der Waerden Conjecture became a theorem in
1979, the main feature of the permanent that remained, is its
efficient computation. Indeed, a polynomial time algorithm for
evaluating the permanent would prove that P=NP.
In this lecture we will describe elementary properties and
applications of the permanent and pay attention to algorithms
for its computation.
12.12.14
09:00
Prof. RNDr. Michal Křížek, DrSc. Ing. Jakub Šístek, Ph.D. Doc. RNDr. Tomáš Vejchodský, Ph.D. chairman (chairmen)