{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T08:19:53Z","timestamp":1761293993109,"version":"build-2065373602"},"reference-count":37,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2019,9,27]],"date-time":"2019-09-27T00:00:00Z","timestamp":1569542400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.3390\/e21100948","type":"journal-article","created":{"date-parts":[[2019,9,27]],"date-time":"2019-09-27T11:14:35Z","timestamp":1569582875000},"page":"948","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Entropic Matroids and Their Representation"],"prefix":"10.3390","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8014-5706","authenticated-orcid":false,"given":"Emmanuel","family":"Abbe","sequence":"first","affiliation":[{"name":"Department of Mathematics, \u00c9cole polytechnique f\u00e9d\u00e9rale de Lausanne, 1015 Lausanne, Switzerland"}]},{"given":"Sophie","family":"Spirkl","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Princeton University, Princeton, NJ 08540, USA"}]}],"member":"1968","published-online":{"date-parts":[[2019,9,27]]},"reference":[{"key":"ref_1","unstructured":"Oxley, J.G. (2006). Matroid Theory, Oxford University Press."},{"key":"ref_2","unstructured":"Woodall, D.R. (2019, September 23). Matroid Theory: Types of Matroids Lecture Notes. Available online: https:\/\/www.maths.nottingham.ac.uk\/personal\/drw\/PG\/matroid.ch3.pdf."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/S0019-9958(78)91063-X","article-title":"Polymatroidal dependence structure of a set of random variables","volume":"39","author":"Fujishije","year":"1978","journal-title":"Inf. Control"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Bachem, A., Gr\u00f6tschel, M., and Korte, B. (1982). Submodular functions and convexity. Mathematical Programming-The State of the Art, Springer.","DOI":"10.1007\/978-3-642-68874-4"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Edmonds, J. (2003). Submodular Functions, Matroids and Certain Polyhedra, Springer. Lecture Notes in Computer Science.","DOI":"10.1007\/3-540-36478-1_2"},{"key":"ref_6","first-page":"320","article-title":"A uniqueness of shannon\u2019s information distance and related nonnegativity problems","volume":"6","author":"Han","year":"1981","journal-title":"J. Comb. Inf. Syst. Sci."},{"key":"ref_7","unstructured":"Li, C., Walsh, J.M., and Weber, S. (2013, January 2\u20134). Matroid bounds on the region of en- tropic vectors. Proceedings of the 2013 51st Annual Allerton Conference on Communication, Control, and Computing (Allerton), Monticello, IL, USA."},{"key":"ref_8","first-page":"1140","article-title":"On characterization of entropy function via information inequalities","volume":"44","author":"Zhang","year":"1998","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_9","unstructured":"Yeung, R.W. (2008). Information Theory and Network Coding, Springer."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"745","DOI":"10.2307\/3214910","article-title":"On Equivalence of Markov Properties over Undirected Graphs","volume":"29","year":"1992","journal-title":"J. Appl. Probab."},{"key":"ref_11","first-page":"185","article-title":"Probabilistic conditional independence structures and matroid theory: Background","volume":"22","year":"1994","journal-title":"Int. J. Gen. Syst."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"2388","DOI":"10.1109\/TIT.2015.2410253","article-title":"Randomness and dependencies extraction via polarization, with applications to Slepian-Wolf coding and secrecy","volume":"61","author":"Abbe","year":"2015","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_13","unstructured":"Abbe, E. (2010). Mutual information, matroids and extremal dependencies. arXiv."},{"key":"ref_14","first-page":"437","article-title":"On forbidden minors for GF(3)","volume":"102","author":"Kahn","year":"1988","journal-title":"Proc. Am. Math. Soc."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1006\/jctb.2000.1963","article-title":"The excluded minors for GF(4)-representable matroids","volume":"79","author":"Geelen","year":"2000","journal-title":"J. Comb. Theory Ser. B"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1112\/blms\/20.1.5","article-title":"On the uniqueness of matroid representations over GF(4)","volume":"20","author":"Kahn","year":"1988","journal-title":"Bull. Lond. Math. Soc."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1007\/BF01864171","article-title":"Combinatorial geometries representable over GF(3) and GF(q). ii. dowling geometries","volume":"4","author":"Kung","year":"1988","journal-title":"Gr. Comb."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/BF02187781","article-title":"Combinatorial geometries representable over GF(3) and GF(q). i. the number of points","volume":"5","author":"Kung","year":"1990","journal-title":"Discret. Comput. Geom."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"579","DOI":"10.1090\/S0002-9947-97-01893-X","article-title":"On matroids representable over GF(3) and other fields","volume":"349","author":"Whittle","year":"1997","journal-title":"Trans. Am. Math. Soc."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Apte, J., Li, C., and Walsh, J.M. (July, January 29). Algorithms for computing network coding rate regions via single element extensions of matroids. Proceedings of the 2014 IEEE International Symposium on Information Theory, Honolulu, HI, USA.","DOI":"10.1109\/ISIT.2014.6875245"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Salimi, A., M\u00e9dard, M., and Cui, S. (October, January 29). On the representability of integer poly- matroids: Applications in linear code construction. Proceedings of the 2015 53rd Annual Allerton Conference on Communication, Control, and Computing (Aller- ton), Monticello, IL, USA.","DOI":"10.1109\/ALLERTON.2015.7447046"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Chan, T., Grant, A., and Kern, D. (2010, January 13\u201318). Existence of new inequalities for repre- sentable polymatroids. Proceedings of the 2010 IEEE International Symposium on Information Theory, Austin, TX, USA.","DOI":"10.1109\/ISIT.2010.5513542"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"6364","DOI":"10.1109\/TIT.2011.2165133","article-title":"Truncation technique for charac- terizing linear polymatroids","volume":"57","author":"Chan","year":"2011","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1007\/s00493-017-3534-y","article-title":"Classes of matroids closed under minors and principal extensions","volume":"38","year":"2018","journal-title":"Combinatorica"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/0095-8956(92)90007-K","article-title":"On secret-sharing matroids","volume":"56","author":"Seymour","year":"1992","journal-title":"J. Comb. Theory Ser. B"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Beimel, A., Livne, N., and Padro, C. (2008). Matroids can be far from ideal secret sharing. Theory of Cryptography Conference, Springer.","DOI":"10.1007\/978-3-540-78524-8_12"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"599","DOI":"10.1109\/TIT.2015.2500232","article-title":"Secret sharing, rank inequalities, and information inequalities","volume":"62","author":"Martin","year":"2015","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1007\/BF00196772","article-title":"On the classification of ideal secret sharing schemes","volume":"4","author":"Brickell","year":"1991","journal-title":"J. Cryptol."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Blakley, G.R. (1979, January 4\u20137). Safeguarding Cryptographic Keys. Proceedings of the 1979 AFIPS National Computer Conference, Monval, NJ, USA.","DOI":"10.1109\/MARK.1979.8817296"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"612","DOI":"10.1145\/359168.359176","article-title":"How to share a secret","volume":"22","author":"Shamir","year":"1979","journal-title":"Commun. ACM"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Mart\u00ed-Farr\u00e9, J., and Padr\u00f3, C. (2007). On secret sharing schemes, matroids and polymatroids. Theory of Cryptography Conference, Springer.","DOI":"10.1007\/978-3-540-70936-7_15"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1023\/A:1008244215660","article-title":"Almost affine codes","volume":"14","author":"Simonis","year":"1998","journal-title":"Des. Codes Cryptogr."},{"key":"ref_33","first-page":"144","article-title":"A homotopy theorem for matroids II","volume":"88","author":"Tutte","year":"1958","journal-title":"Trans. Am. Math. Soc."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/0095-8956(79)90055-8","article-title":"Matroid representation over GF(3)","volume":"26","author":"Seymour","year":"1979","journal-title":"J. Comb. Theory Ser. B"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1016\/0095-8956(79)90056-X","article-title":"On Reid\u2019s characterization of the ternary matroids","volume":"26","author":"Bixby","year":"1979","journal-title":"J. Comb. Theory Ser. B"},{"key":"ref_36","unstructured":"Pegg, E. (2019, September 23). Math Games: The Fano Plane. Available online: http:\/\/www.mathpuzzle.com\/MAA\/47-Fano\/mathgames_05_30_06.html."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"5437","DOI":"10.1109\/TIT.2012.2201374","article-title":"Polar codes for the m-user multiple access channel","volume":"58","author":"Abbe","year":"2012","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/21\/10\/948\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:25:19Z","timestamp":1760189119000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/21\/10\/948"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,27]]},"references-count":37,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2019,10]]}},"alternative-id":["e21100948"],"URL":"https:\/\/doi.org\/10.3390\/e21100948","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2019,9,27]]}}}