Narayanan and Fujishige showed the existence of the principal partition sequence of a submodular function, a structure with numerous applications in areas such as clustering, fast algorithms, and approximation algorithms. In our recent paper $\{s,t\}$-Separating Principal Partition Sequence of Submodular Functions, motivated by two applications, we develop a theory of $\{s,t\}$-separating principal partition sequence of…
Our paper on the Interaction between skew-representability, tensor products, extension properties, and rank inequalities was accepted to SODA! The paper explores skew-representable matroids, a fundamental class connecting combinatorics and linear algebra with applications in coding theory, optimization, and geometry. Since deciding skew-representability is computationally hard, we study it through a new perspective: tensor products. This…
Our paper on splitting-off operations in hypergraphs was accepted to JCTB! In this work, we introduce a splitting-off operation in hypergraphs, prove the existence of a local connectivity-preserving complete splitting-off, and give a strongly polynomial-time algorithm to compute it in weighted hypergraphs.
In the paper Quotient-convergence of submodular setfunctions, we developed a limit theory for matroids, and more generally for submodular setfunctions. We later showed in Cycle Matroids of Graphings: From Convergence to Duality that the theory is in line with the notion of local-global convergnece of bounded-degree graphs. In a new paper titled Convergent sequences of…
Skew-representable matroids form a fundamental class in matroid theory, bridging combinatorics and linear algebra. They play an important role in areas such as coding theory, optimization, and combinatorial geometry, where linear structure is crucial for both theoretical insights and algorithmic applications. Since deciding skew-representability is computationally intractable, much effort has been focused on identifying necessary…