In this paper, we prove a $1/e$ guarantee for the matroid secretary problem on linear matroids (each element of a fixed optimal basis is selected with probability at least $1/e), which settles the strong secretary conjecture for that class. The result holds in the online-representation model too, where a representation over a finite field arrives…
The equitability theorem for matroids says that if the ground set of a matroid can be partitioned into $k$ bases, then the elements of any prescribed subset can be distributed almost equally among the bases. In our paper Weighted Equitability and Matroid-Constrained Discrepancy, we prove a weighted analogue: for arbitrary nonnegative weights, there is a…
Frank’s min–max theorem gives an exact relation between maximum joins and optimal ear decompositions in graphic matroids. In our paper Joins and ear decompositions beyond graphic matroids, we investigate how far this relation extends beyond the graphic setting. The exact equality already fails for cographic matroids, and computing a maximum join is NP-hard even in…
Our paper Fixed-Parameter Tractability and Hardness for Steiner Rooted and Locally Connected Orientations was accepted to FOCS 2026! The paper studies the Steiner Rooted Orientation problem introduced by Király and Lau at FOCS 2006. Given an undirected graph, a root vertex, a set of $t$ terminals, and a connectivity requirement $k$, the goal is to…
Motivated by the exact weight perfect matching problem and recent parameterized algorithms for finding an $\ell$-th smallest perfect matching, in the paper A hierarchy of edge-weight symmetries in perfect matchings we study structural properties of edge-weight symmetries in graphs. Recent work by El Maalouly et al. (ESA 2025) showed that excluding all perfect matchings whose…