Arturo Merino ● Profesor Asistente

Combinatorial objects frequently appear in various areas of computer science and discrete mathematics. These objects are central to questions in algorithmic design, where we aim to program a computer to efficiently perform tasks involving them. These tasks may include counting objects based on certain parameters, sampling an object uniformly at random, optimizing with respect to an objective function, searching for objects that satisfy specific properties, or generating all objects exactly once. This project focuses on two of these problems: combinatorial generation and the search for highly distinct combinatorial objects. While many of the aforementioned tasks have general-purpose techniques that allow them to tackle multiple problems simultaneously, the situation becomes less clear when dealing with combinatorial generation or the search for distant objects. Much of the effort in these areas has been devoted to developing ad hoc methods. Despite this, these last two problems can be naturally phrased in the language of flip graphs, which encode the similarity between combinatorial objects. In this context, the problem transforms into the traditional graph problems of Hamiltonicity (finding a path that traverses all the vertices exactly once) and diameter (finding two vertices that are farthest apart). Recent research has highlighted the significant value of exploiting polytopal properties and symmetry of flip graphs, leading to unified frameworks that can address many problems simultaneously. The main objective of this project is to contribute to this perspective. Specifically, it aims to enhance our understanding of the polytopal and symmetric properties of flip graphs and use this knowledge to develop efficient algorithms for tackling Hamiltonicity and diameter problems