Projective planes, coverings and a network problem
type: Item
instance of: scholarly article
title: Projective planes, coverings and a network problem
zbMATH Open document ID: 1027.51014
DOI: 10.1023/A:1024140122167
author: Stefano Marcugini
author: Fernanda Pambianco
author: Jürgen Bierbrauer
published in: Designs, Codes and Cryptography
publication date: 2003-08-21T00:00:00Z
review text: 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 t…
Mathematics Subject Classification ID: 51E22
Mathematics Subject Classification ID: 94B05
Mathematics Subject Classification ID: 51E21
Mathematics Subject Classification ID: 94C30
Mathematics Subject Classification ID: 51E15
zbMATH DE Number: 1968857
zbMATH Keywords: congestion-free networks
zbMATH Keywords: coverings
zbMATH Keywords: projective planes
zbMATH Keywords: arcs
zbMATH Keywords: designs
zbMATH Keywords: codes
zbMATH Keywords: fractional matchings
zbMATH Keywords: fractional covers
zbMATH Keywords: almost projective planes
reviewed by: Leo Storme
MaRDI profile type: Publication
full work available at URL: a:1024140122167
OpenAlex ID: W1568426568
description: scientific article; zbMATH DE number 1968857