#матлог #учёба #спецсеминар

Kolmogorov seminar on complexity (for receive the zoom link, please email nikolay.vereshchagin@gmail.com)

6 October, 18:30 MSK

Arturo Merino (Universidad de O'Higgin, https://amerino.cl/).

0,1-polyhedra.

A 0-1 polyhedron is a polyhedron whose vertices are 0,1 vectors. For example, for a given graph G, one can define a 0,1-polyhedron whose vertices are matchings of G.
There is a classical result that any 0,1-polyhedron admits a Hamiltonian path along its edges. The idea is to first try to understand this result, and then discuss what is known about efficient generation of the vertices of 0,1-polyhedra.

➰ ВК