|
|
Linear codes and a projective plane of order 10
Liška, Ondřej ; Drápal, Aleš (advisor) ; Vojtěchovský, Petr (referee)
Projective plane of order 10 does not exist. Proof of this assertion was finished in 1989 and is based on the nonexistence of a binary code C generated by the incidence vectors of the plane's lines. As part of the proof of the nonexistence of code C, the coefficients of its weight enumerator were studied. It was shown that coefficients A12, A15, A16 and A19 have to be equal to zero, which contradicted other findings about the relationship among the coefficients. Presented diploma thesis elaborately analyses the phases of the proof and, in several places, enhances them with new observations and simplifications. Part of the proof is generalized for projective planes of order 8m + 2. 1
|
|
|
Geometric and algebraic properties of discrete structures
Rytíř, Pavel ; Loebl, Martin (advisor) ; Serra, Oriol (referee) ; Kaiser, Tomáš (referee)
In the thesis we study two dimensional simplicial complexes and linear codes. We say that a linear code C over a field F is triangular representable if there exists a two dimensional simplicial complex ∆ such that C is a punctured code of the kernel ker ∆ of the incidence matrix of ∆ over F and dim C = dim ker ∆. We call this simplicial complex a geometric representation of C. We show that every linear code C over a primefield is triangular representable. In the case of finite primefields we construct a geometric representation such that the weight enumerator of C is obtained by a simple formula from the weight enumerator of the cycle space of ∆. Thus the geometric representation of C carries its weight enumerator. Our motivation comes from the theory of Pfaffian orientations of graphs which provides a polynomial algorithm for weight enumerator of the cut space of a graph of bounded genus. This algorithm uses geometric properties of an embedding of the graph into an orientable Riemann surface. Viewing the cut space of a graph as a linear code, the graph is thus a useful geometric representation of this linear code. We study embeddability of the geometric representations into Euclidean spaces. We show that every binary linear code has a geometric representation that can be embed- ded into R4 . We characterize...
|
|
|
Geometric and algebraic properties of discrete structures
Rytíř, Pavel ; Loebl, Martin (advisor) ; Serra, Oriol (referee) ; Kaiser, Tomáš (referee)
In the thesis we study two dimensional simplicial complexes and linear codes. We say that a linear code C over a field F is triangular representable if there exists a two dimensional simplicial complex ∆ such that C is a punctured code of the kernel ker ∆ of the incidence matrix of ∆ over F and dim C = dim ker ∆. We call this simplicial complex a geometric representation of C. We show that every linear code C over a primefield is triangular representable. In the case of finite primefields we construct a geometric representation such that the weight enumerator of C is obtained by a simple formula from the weight enumerator of the cycle space of ∆. Thus the geometric representation of C carries its weight enumerator. Our motivation comes from the theory of Pfaffian orientations of graphs which provides a polynomial algorithm for weight enumerator of the cut space of a graph of bounded genus. This algorithm uses geometric properties of an embedding of the graph into an orientable Riemann surface. Viewing the cut space of a graph as a linear code, the graph is thus a useful geometric representation of this linear code. We study embeddability of the geometric representations into Euclidean spaces. We show that every binary linear code has a geometric representation that can be embed- ded into R4 . We characterize...
|
|
|
Linear codes and a projective plane of order 10
Liška, Ondřej ; Drápal, Aleš (advisor) ; Vojtěchovský, Petr (referee)
Projective plane of order 10 does not exist. Proof of this assertion was finished in 1989 and is based on the nonexistence of a binary code C generated by the incidence vectors of the plane's lines. As part of the proof of the nonexistence of code C, the coefficients of its weight enumerator were studied. It was shown that coefficients A12, A15, A16 and A19 have to be equal to zero, which contradicted other findings about the relationship among the coefficients. Presented diploma thesis elaborately analyses the phases of the proof and, in several places, enhances them with new observations and simplifications. Part of the proof is generalized for projective planes of order 8m + 2. 1
|
guest ::
