In the Properly Colored Spanning Tree problem, we are given an edge-colored undirected graph and the goal is to find a properly colored spanning tree, i.e., a spanning tree in which any two adjacent edges have distinct colors. The problem is interesting not only from a graph coloring point of view, but is also closely…
We are organizing a Workshop on “Matroid-Constrained Optimization Problems” at the Institut Henri Poincaré (IHP) in Paris, France April 2-3, 2024. We intend to bring together a small group (25-35) of people working on matroid-related optimization problems for two half days, with keynote talks given by Britta Peis (RWTH Aachen) and Rico Zenklusen (ETH Zurich). Further, we plan to have…
In our recent paper titled Reconfiguration of basis pairs in regular matroids, we verify conjectures of White and of Gabow for the class of regular matroids. White’s conjecture aims at characterizing two basis sequences being reachable from each other by symmetric exchanges, which received a significant interest also in algebra due to its connection to…
Several postdoc positions are available in Budapest in various research groups in discrete mathematics and probability theory. To make the application process more efficient and joyful, we are organizing a drafting workshop for young researchers interested in these positions, with the dates Jan 29 – 31, 2024, at the Rényi Institute. The application due date…
In a recent paper titled Hypergraph Splitting-off and Covering Skew-Supermodular Functions in Strongly Polynomial Time, we consider hypergraph network design problems where the goal is to construct a hypergraph satisfying certain properties. The central theme of this work is to show that certain hypergraph network design problems admit solutions with polynomial number of hyperedges and…