In the Properly Colored Spanning Tree problem, we are given an edge-colored undirected graph and the goal is to find a spanning tree in which any two adjacent edges have distinct colors. Since finding such a tree is NP-hard in general, previous work often relied on minimum color degree conditions to guarantee the existence of…
The year kicked off in the same great way the last one finished: our research group’s paper on $\{s,t\}$-separating principal partition sequences has been accepted to IPCO 2026!
The end of 2025 has been very successful for the research group in terms of publications: several of our submitted papers have been accepted by leading journals, including JCTB, Combinatorica, and SIDMA. It has been a challenging period with a lot of hard work, but we are happy to share the good news that, thanks…
The multiple exchange property for matroid bases states that for any bases $A$ and $B$ of a matroid and any subset $X\subseteq A\setminus B$, there exists a subset $Y\subseteq B\setminus A$ such that both $A-X+Y$ and $B+X-Y$ are bases. This classical result has not only found applications in matroid theory, but also in the analysis…
The Matroid Secretary Problem is a central question in online optimization, modeling sequential decision-making under combinatorial constraints. Despite significant progress, the Matroid Secretary Conjecture — which asks whether every matroid admits a constant-competitive algorithm — remains open. In the paper Free-Order Secretary for Two-Sided Independence Systems, we introduce a bipartite graph framework that unifies and…