On Field Size and Success Probability in Network Coding

Using tools from algebraic geometry and Grobner basis theory the authors solve two problems in network coding. First they present a method to determine the smallest field size for which linear network coding is feasible. Second they derive improved estimates on the success probability of random linear network coding. These estimates take into account which monomials occur in the support of the determinant of the product of Edmonds matrices. Therefore, they finally investigate which monomials can occur in the determinant of the Edmonds matrix.