Projective planes, coverings and a network problem (Q1404316): Difference between revisions

This article studies a problem concerning packet switched networks which can be translated into a combinatorial design problem involving \(k\)-arcs in projective planes, 3-dimensional linear codes, the theory of fractional matchings and designs which approximate projective planes. The combinatorial design problem concerns coverings \(C(n,k,r)\). A covering \(C(n,k,r)\) is a family of subsets, called blocks, of an \(n\)-set such that: (1) each block has size at most \(k\), (2) each point is on at most \(r\) blocks, and (3) any pair of points is on at least one common block. The number Cov\((k,r)\) is the maximum \(n\) such that there exists a covering \(C(n,k,r)\). Coverings \(C(n,k,q+1)\) can be constructed from non-negative weighted \(k\)-arcs in projective planes of order \(q\). These are weight functions \(w\) assigning non-negative integer weights to the points of the plane such that the sum of the weights of the points of a line is at most \(k\). A covering constructed in this way is called a geometric covering, and if the projective plane is desarguesian, then the covering is called a linear geometric covering. These latter linear geometric coverings are equivalent to linear 3-dimensional codes. The authors determine the largest geometric coverings \(C(n,k,q+1)\) when \(q\) is a prime power and \(k>q\). They also prove that every \(C(n,k,q+1)\), with \(n>qk\), is geometric, and give some exact values for Cov\((k,r)\). In order to obtain good coverings \(C(n,k,q+1)\) for \(k \geq q+1\), with \(q\) not a prime power, they generalize the geometric construction. The projective planes of order \(q\) are replaced by coverings \(C(n,q+1,q+1)\). The coverings \(C(n,q+1,q+1)\) they concentrate on are almost projective planes \(G(q,\delta)\) of defect \(\delta\). These are designs satisfying the following properties: (1) \(G(q,\delta)\) has \(q^2+q+1-\delta\) points and equally many blocks, (2) each block has \(q+1\) points and each point is on \(q+1\) blocks, (3) any two points are on 1 or 2 common blocks, and (4) any two blocks have 1 or 2 points in common.