8 papers
Measurable Matroids: Foundations and Min--Max Theorems
Kristóf Bérczi, András Imolay, Ádám Schweitzer
We develop a measure-theoretic analogue of matroid theory on standard atomless measure spaces. Motivated by the quotient-convergence framework for submodular set functions, our aim…
Fixed-parameter tractability and hardness for Steiner rooted and locally connected orientations
Kristóf Bérczi, Florian Hörsch, András Imolay +1
Finding a Steiner strongly -arc-connected orientation is particularly relevant in network design and reliability, as it guarantees robust communication between a designated set…
Interaction between skew-representability, tensor products, extension properties, and rank inequalities
Kristóf Bérczi, Boglárka Gehér, András Imolay +3
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, optim…
Matroid products via submodular coupling
Kristóf Bérczi, Boglárka Gehér, András Imolay +3
The study of matroid products traces back to the 1970s, when Lovász and Mason studied the existence of various types of matroid products with different strengths. Among these, the…
Monotonic Decompositions of Submodular Set Functions
Kristóf Bérczi, Boglárka Gehér, András Imolay +2
Submodular set functions are undoubtedly among the most important building blocks of combinatorial optimization. Somewhat surprisingly, continuous counterparts of such functions ha…
Problems on Group-labeled Matroid Bases
Florian Hörsch, András Imolay, Ryuhei Mizutani +2
Consider a matroid equipped with a labeling of its ground set to an abelian group. We define the label of a subset of the ground set as the sum of the labels of its elements. We st…
Multicolor Turán numbers
András Imolay, János Karl, Zoltán Lóránt Nagy +1
We consider a natural generalisation of Turán's forbidden subgraph problem and the Ruzsa-Szemerédi problem by studying the maximum number of edge-disjoint copies of a f…
Clique number of Xor products of Kneser graphs
András Imolay, Anett Kocsis, Ádám Schweitzer
In this article we investigate a problem in graph theory, which has an equivalent reformulation in extremal set theory similar to the problems researched in "A general 2-part Erdős…