Скачать или смотреть Arturo Merino: how to enumerate combinatorial objects fast

Kolmogorov seminar on computational and descriptional complexity (founded by Kolmogorov around 1979) meeting October 6, 2025

If we want to enumerate combinatorial objects (say, permutations) with minimal delay between objects, they should be enumerated in a special order (it is convenient if two permutations differ by a neighbor's transposition). Trying to do this for other objects, we need to find a Hamiltonian path in a graph where vertices are objects and edges are objects that are "close enough". The following result (and its algorithmic proof) is useful for this: a convex hull of a subset of the Boolean cube, considered as a polyhedron, always has a Hamiltonian path. (This result was explained in details and some possible applications are surveyed.)