On the representability of the biuniform matroid (Q2870516)

The existence of efficient methods to find a representation for every given biuniform matroid has not been proved. The interest in this problem is due to its connections with secret-sharing. In this paper the existence of efficient methods to find representations for all biuniform matroids is proved for the first time and the proposed constructions provide in many cases representations over smaller finite fields.NEWLINENEWLINENEWLINE Among other things it is proved that the biuniform matroid of rank \(k\) and subranks \(m\) and \(l\) with \(d=m+l-k=2\) is representable over \(\mathbb{F}_{q}\) if \(q\) is odd and \(\max \{|E_1|,|E_2|\}\leq (q-1)/2\), and for \(d\geq 2\) this matroid is representable over the same field if \(q=q_{0}^{s}\) for some \(s>d(d-1)/2\) and some prime power \(q_{0}>\max \{|E_1|,|E_2|\}\). Moreover, such a representation can be obtained in time polynomial in the size of the ground set of the matroid. Here \(E_1\) and \(E_2\) arise in the partition of the ground set \(E=E_1\cup E_2\) of the matroid, where \(|E_1|\geq m\) and \(|E_2|\geq l\).