M.Sc Thesis

M.Sc StudentHooker Niv
SubjectOn the Existence of the q-Fano Planes
DepartmentDepartment of Computer Science
Supervisor PROF. Tuvi Etzion
Full Thesis textFull thesis text - English Version


Network coding is a networking technique in which transmitted data is encoded and decoded to increase network throughput, reduce delays and make the network more robust. In network coding, algebraic algorithms are applied to the data to accumulate the various transmissions. The received transmissions are decoded at their destinations. This means that fewer transmissions are required to transmit all the data, but this requires more processing at intermediary and terminal nodes.

The set of nodes’ combinations that resulted from those algebric algorithm is a solution of the network. We will focus on the case where our messages will be linear vectors, and the coefficients in the combinations will be linear subspaces. We might require that all subspaces will be of the same dimension, for convenience, and that the minimal distance between two subspaces will be of certain value, to allow for error correction properties. One possible code with equal weight codewords, a given minimal distance and maximal size could be the family of q-analog of Steiner systems, known also as q-Steiner systems.

The existence question of an infinite family of q-Steiner systems, (spreads not included) in general, is one of the most intriguing problems, in q-analogs of designs. In particular, we are interested in the existence question for the q-analog of the Fano plane, known also as the q-Fano plane, smallest possible structure in that family. These questions are in the front line of open problems in block design. There was a common belief and a conjecture that such structures do not exist. Only recently, q-Steiner systems were found for one set of parameters.

In this work, a definition for the q-analog of the residual design is presented. This new definition is different from previous known definition, but its properties reflect better the q-analog properties. The existence of a design with the parameters of the residual q-Steiner system in general and the residual q-Fano plane in particular are examined. We start by constructing different residual q-Fano planes for all q, where q is a prime power. The constructed structure is just one step from a construction of a q-Fano plane. Then, we use the structures we find, for construction of other q-Steiner system. The constructed structure is just one step from a third construction that will provide a family of constructions of q-Fano planes.