Matroidal entropy functions (Part 1)

Abstract: A matroidal entropy function is an entropy function in the form log v · r_M , where v is an integer exceeding one and r_M is the rank function of a matroid M. For a matroid M, the characterization of matroidal entropy functions induced by M is to determine its probabilistic-characteristic set Χ_M, i.e., the set of integers v such that log v · r_M is entropic. When M is a connected matroid with rank not less than 2, such characterization also determines the entropic region on the extreme ray of the polymatroidal region containing log v · r_M.

To characterize matroidal entropy functions, variable-strength orthogonal arrays (VOA) is defined, which can be considered as special cases of classic combinatorial structure orthogonal arrays (OA). It can be proved that whether log v · r_M is entropic depends on whether a VOA(M, v) is constructible. The constructibility of VOA(M, v) is also equivalent to the partition-representability of M over an alphabet with cardinality v, defined by Fero Matúš, which generalize the linear representability of a matroid over a field.

In this part, we characterize all matroidal entropy functions with ground set size not exceeding 5 except for log v · r_{U_{2,5}} and log v · r_{U_{3,5}} for some v. We also briefly discuss the application of matroidal entropy functions to network coding and secret sharing.

Computer scienceMathematics

Audience: researchers in the discipline

Seminar on Algorithmic Aspects of Information Theory

Series comments: This online seminar is a follow up of the Dagstuhl Seminar 22301, www.dagstuhl.de/en/program/calendar/semhp/?semnr=22301.