Leírás
Kedves Kombinatorikusok!
A Kombinatorika szemináriumom következő előadása november 14-én 14:15-kor lesz (Rényi, Nagyterem)
Előadó:
Bérczi Kristóf (Rényi)
Title: Matroid Products via Submodular Coupling
Abstract:
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 tensor product is arguably the
most important, which can be considered as an extension of the tensor
product from linear algebra. However, Las Vergnas showed that the tensor
product of two matroids does not always exist. Over the following four
decades, matroid products remained surprisingly underexplored, regaining
attention only in recent years due to applications in tropical geometry
and the limit theory of matroids.
In this talk, inspired by the concept of coupling in probability theory,
we introduce the notion of coupling for matroids -- or, more generally,
for submodular set functions. This operation can be viewed as a
relaxation of the tensor product. Unlike the tensor product, however, we
prove that a coupling always exists for any two submodular functions and
can be chosen to be increasing if the original functions are increasing.
As a corollary, we show that two matroids always admit a matroid
coupling, leading to a novel operation on matroids. Our construction is
algorithmic, providing an oracle for the coupling matroid through a
polynomial number of oracle calls to the original matroids. We apply
this construction to derive new necessary conditions for matroid
representability and establish connection between tensor products and
Ingleton’s inequality. Additionally, we verify the existence of set
functions that are universal with respect to a given property, meaning
any set function over a finite domain with that property can be obtained
as a quotient.
Joint work with Boglárka Gehér, András Imolay, László Lovász,
Balázs Maga, and Tamás Schwarcz.