On the Theory of Linear Rank Inequalities

Abstract. In this work, we study linear polymatroids and linear rank inequalities. We focus on the problem of determining if the Common Information Method can generate all the linear inequalities satisfied by all linear polymatroids. It is well known that there exist deep connections between the Theory of Linear Rank Inequalities and Linear Secret Sharing. We study those connections. First, we study the problem of estimating the information rates that can be achieved by Linear Secret Sharing. Then, we arrive to the novel notion of Abelian Secret Sharing. We prove that if Abelian Secret Sharing outperforms Linear Secret Sharing, then the Common Information Method is incomplete. Therefore, we focus on the problem of comparing the performances of abelian and linear schemes. We show that the last problem is related to the Representation Theory of Matroids.

• Autores: Mejía Moreno, Carolina
• Tipo de recurso: Doctoral thesis
• Fecha de publicación: 2016
• Institución: Universidad Nacional de Colombia
• Repositorio: Universidad Nacional de Colombia
• Idioma: spa
• OAI Identifier: oai:repositorio.unal.edu.co:unal/56999
• Acceso en línea: https://repositorio.unal.edu.co/handle/unal/56999; http://bdigital.unal.edu.co/53062/
• Palabra clave: 51 Matemáticas / Mathematics; Linear polymatroids; Linear rank inequalities; Secret sharing; Linear schemes; Abelian polymatroids; Matroids; Polimatroides lineales; Desigualdades rango lineales; Repartición de Secretos; Esquemas lineales; Polimatroides abelianos; Matroides
• Rights: openAccess
• License: Atribución-NoComercial 4.0 Internacional