The paper Highly connected orientations from edge-disjoint rigid subgraphs by Gamavölgyi, Jordán, Király, and Villányi has been published in Forum of Mathematics Pi! In the paper, they prove a long-standing conjecture of Thomassen, stating that every sufficiently highly connected graph has a $k$-vertex-connected orientation. They also give an affirmative answer to the conjecture of Kriesell…
We have had two more successful defenses: Fekadu Gedefa Tolessa defended his PhD in January, and Lydia Mirabel Mendoza Cadena defended hers in February. The latter was celebrated by a small but enthusiastic team from the research group, in Mexican-Hungarian cooperation, by learning a Moldavian Csángó dance 🙂
Members of the research group took on the Velence 60 challenge, running around Lake Velence twice as a relay team. The Matroad Runners are especially grateful to the Perfect Set Goes for a Random Walk team from the Department of Analysis for lending us a last-minute substitute when one of our teammates dropped out –…
Our paper on Matroid products via submodular coupling has been accepted to the 57th Annual ACM Symposium on Theory of Computing (STOC 2025)! In this paper, inspired by the concept of coupling in probability theory, we introduce the notion of coupling for matroids – or, more generally, for submodular set functions. This operation can be…
Our paper on Matroid secretary via labeling schemes was accepted at IPCO! In this work, we introduce an algorithmic framework for analyzing greedy-like algorithms for the matroid secretary problem by constructing a language associated with the matroid. Using this approach, we improve the state-of-the-art guarantee for laminar matroids by determining the exact probability-competitiveness of the…