2022arXiv (Cornell University)Open access

Entropic Weighted Rank Function

Mohammad A Rashid, Elahe Ghasemi, Javad B. Ebrahimi

Open full text 0 citations

Abstract

It is known that the entropy function over a set of jointly distributed random variables is a submodular set function. However, not any submodular function is of this form. In this paper, we consider a family of submodular set functions, called weighted rank functions of matroids, and study the necessary or sufficient conditions under which they are entropic. We prove that weighted rank functions are located on the boundary of the submodularity cone. For the representable matroids over a characteristic 2 field, we show that the integer valued weighted rank functions are entropic. We derive a necessary condition for constant weight rank functions to be entropic and show that for the case of graphic matroids, this condition is indeed sufficient. Since these functions generalize the rank of a matroid, our findings generalize some of the results of Abbe et. al. about entropic properties of the rank function of matroids.

Open-access reader

About this research paper

What this paper is about

It is known that the entropy function over a set of jointly distributed random variables is a submodular set function. However, not any submodular function is of this form. In this paper, we consider a family of submodular set functions, called weighted rank functions of matroids, and study the necessary or sufficient conditions under which they are entropic. We prove that weighted rank functions are located on the boundary of the submodularity cone. For the representable matroids over a characteristic 2 field, we show that the integer valued weighted rank functions are entropic. We derive a necessary condition for constant weight rank functions to be entropic and show that for the case of graphic matroids, this condition is indeed sufficient. Since these functions generalize the rank of a matroid, our findings generalize some of the results of Abbe et. al. about entropic properties of the rank function of matroids.

Why it matters

A significance statement is not available in the OpenAlex record.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

It is known that the entropy function over a set of jointly distributed random variables is a submodular set function. However, not any submodular function is of this form. In this paper, we consider a family of submodular set functions, called weighted rank functions of matroids, and study the necessary or sufficient conditions under which they are entropic. We prove that weighted rank functions are located on the boundary of the submodularity cone. For the representable matroids over a characteristic 2 field, we show that the integer valued weighted rank functions are entropic. We derive a necessary condition for constant weight rank functions to be entropic and show that for the case of graphic matroids, this condition is indeed sufficient. Since these functions generalize the rank of a matroid, our findings generalize some of the results of Abbe et. al. about entropic properties of the rank function of matroids.

Key concepts: Matroid, Submodular set function, Mathematics, Rank (graph theory), Set function, Combinatorics, Function (biology), Discrete mathematics

Related papers

Back to paper searchBrowse research topicsOriginal source
Entropic Weighted Rank Function — Research Paper | ScholarLens