Entropic matroids and their representation

Emmanuel Abbe, Sophie Spirkl

Research output: Contribution to journalArticlepeer-review

Abstract

This paper investigates entropic matroids, that is, matroids whose rank function is given as the Shannon entropy of random variables. In particular, we consider p-entropic matroids, for which the random variables each have support of cardinality p. We draw connections between such entropic matroids and secret-sharing matroids and show that entropic matroids are linear matroids when p = 2, 3 but not when p = 9. Our results leave open the possibility for p-entropic matroids to be linear whenever p is prime, with particular cases proved here. Applications of entropic matroids to coding theory and cryptography are also discussed.

Original languageEnglish (US)
Article number948
JournalEntropy
Volume21
Issue number10
DOIs
StatePublished - Oct 1 2019

All Science Journal Classification (ASJC) codes

  • Physics and Astronomy(all)

Keywords

  • Coding
  • Combinatorics
  • Entropy function
  • Extremal dependencies
  • Matroids

Fingerprint Dive into the research topics of 'Entropic matroids and their representation'. Together they form a unique fingerprint.

Cite this