1 citations · 2 across the 19 of their papers we have counts for
11 papers · 1 filter
Rainbow Arborescence Conjecture
Kristóf Bérczi, Tamás Király, Yutaro Yamaguchi +1
The famous Ryser--Brualdi--Stein conjecture asserts that every Latin square contains a partial transversal of size . Since its appearance, the conjecture has attr…
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…
Quotient-convergence of Submodular Setfunctions
Kristóf Bérczi, Márton Borbényi, László Lovász +1
We introduce the concept of quotient-convergence for sequences of submodular set functions, providing, among others, a new framework for the study of convergence of matroids throug…
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…
Cycle Matroids of Graphings: From Convergence to Duality
Kristóf Bérczi, Márton Borbényi, László Lovász +1
A recent line of research has concentrated on exploring the links between analytic and combinatorial theories of submodularity, uncovering several key connections between them. In…
Partitioning into common independent sets via relaxing strongly base orderability
Kristóf Bérczi, Tamás Schwarcz
The problem of covering the ground set of two matroids by a minimum number of common independent sets is notoriously hard even in very restricted settings, i.e.\ when the goal is t…
Matroid Horn functions
Kristóf Bérczi, Endre Boros, Kazuhisa Makino
Hypergraph Horn functions were introduced as a subclass of Horn functions that can be represented by a collection of circular implication rules. These functions possess distinguish…
On the complexity of packing rainbow spanning trees
Kristóf Bérczi, Gergely Csáji, Tamás Király
One of the most important questions in matroid optimization is to find disjoint common bases of two matroids. The significance of the problem is well-illustrated by the long list o…
On approximating the rank of graph divisors
Kristóf Bérczi, Hung P. Hoang, Lilla Tóthmérész
Baker and Norine initiated the study of graph divisors as a graph-theoretic analogue of the Riemann-Roch theory for Riemann surfaces. One of the key concepts of graph divisor theor…
Hypergraph characterization of split matroids
Kristóf Bérczi, Tamás Király, Tamás Schwarcz +2
We provide a combinatorial study of split matroids, a class that was motivated by the study of matroid polytopes from a tropical geometry point of view. A nice feature of split mat…
Approximation by Lexicographically Maximal Solutions in Matching and Matroid Intersection Problems
Kristóf Bérczi, Tamás Király, Yutaro Yamaguchi +1
We study how good a lexicographically maximal solution is in the weighted matching and matroid intersection problems. A solution is lexicographically maximal if it takes as many he…