On the Theory of Linear Rank Inequalities

Abstract

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.

En este trabajo estudiamos los polimatroides lineales y las desigualdades rango lineales. Nos enfocamos en el problema de determinar si elMétodo de la Información Común puede generar todas las desigualdades rango lineales, que son las desigualdades satisfechas por todos los polimatroides lineales. Se sabe que existen conexiones profundas entre la Teoría de desigualdades rango lineales y el Problema de Repartición Lineal de Secretos. En este texto estudiamos estas conexiones. Primero, estudiamos el problema de estimar las ratas de información que pueden ser alcanzadas por soluciones lineales al Problema de Repartición de Secretos. Luego, llegamos a la nueva noción de Repartición Abeliana de Secretos. Probamos que si las soluciones abelianas al Problema de Repartición de Secretos superan a las soluciones lineales, entonces el Método de la Información Común es incompleto. Por lo tanto, nos enfocamos en el problema de comparar las representaciones de esquemas abelianos y lineales. Nosotros probamos que este último problema está relacionado con la Teoría de Representación de Matroides.