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...

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

Neste trabalho calculamos o peso e a dimensão de todos os códigos cíclicos de comprimento pn na álgebra de grupo FqCpn, onde p é um número primo e Fq é um corpo finito de característica q. Também calculamos o peso do código dado pela soma de dois códigos abelianos minimais em Fq(Cp × Cp), dessa forma foi possível fazer uma breve comparação entre códigos cíclicos e abelianos não cíclicos de comprimento p2. / In this work we compute the weight and the dimension of all cyclic codes of length pn in the group algebra FqCpn, where p is a prime number and Fq is a finite field of characteristic q. Furthermore, we compute the weight of codes which are given by the sum of two minimal abelian codes in Fq(Cp × Cp). In this way, it was possible to compare briefly cyclic codes and non-cyclic abelian codes of length p2.

One of the basic streams of modern statistical physics is an effort to understand the frustration and chaos. The basic model to study these phenomena is the finite dimensional Edwards-Anderson Ising model. We present a generalization of this model. We study set systems which are closed under symmetric differences. We show that the important question whether a groundstate in Ising model is unique can be studied in these set systems. Kreweras' conjecture asserts that any perfect matching of the $n$-dimensional hypercube $Q_n$ can be extended to a Hamiltonian cycle. We prove this conjecture. The {\it matching graph} $\mg{G}$ of a graph $G$ has a vertex set of all perfect matchings of $G$, with two vertices being adjacent whenever the union of the corresponding perfect matchings forms a Hamiltonian cycle. We prove that the matching graph $\mg{Q_n}$ is bipartite and connected for $n \ge 4$. This proves Kreweras' conjecture that the graph $M_n$ is connected, where $M_n$ is obtained from $\mg{Q_n}$ by contracting all vertices of $\mg{Q_n}$ which correspond to isomorphic perfect matchings. A fault-free path in $Q_n$ with $f$ faulty vertices is said to be \emph{long} if it has length at least $2^n-2f-2$. Similarly, a fault-free cycle in $Q_n$ is long if it has length at least $2^n-2f$. If all faulty vertices are...

In this thesis, we describe linear codes over prime fields obtained from incidence designs of iterated line graphs of complete graphs Li(Kn) where i = 1, 2. In the binary case, results are extended to codes from neighbourhood designs of the line graphs Li+1(Kn) using certain elementary relations. Codes from incidence designs of complete graphs, Kn, and neighbourhood designs of their line graphs, L1(Kn) (the so-called triangular graphs), have been considered elsewhere by others. We consider codes from incidence designs of L1(Kn) and L2(Kn), and neighbourhood designs of L2(Kn) and L3(Kn). In each case, basic parameters of the codes are determined. Further, we introduce a family of vertex-transitive graphs 􀀀n that are embeddable into the strong product L1(Kn) ⊠ K2, of triangular graphs and K2, a class which at first sight may seem unnatural but, on closer look, is a repository of graphs rich with combinatorial structures. For instance, unlike most regular graphs considered here and elsewhere that only come with incidence and neighbourhood designs, 􀀀n also has what we have termed as 6-cycle designs. These are designs in which the point set contains vertices of the graph and every block contains vertices of a 6-cycle in the graph. Also, binary codes from incidence matrices of these graphs have other minimum words in addition to incidence vectors of the blocks. In addition, these graphs have induced subgraphs isomorphic to the family Hn of complete porcupines (see Definition 4.11). We describe codes from incidence matrices of 􀀀n and Hn and determine their parameters.

In this thesis, we describe linear codes over prime fields obtained from incidence designs of iterated line graphs of complete graphs Li(Kn) where i = 1, 2. In the binary case, results are extended to codes from neighbourhood designs of the line graphs Li+1(Kn) using certain elementary relations. Codes from incidence designs of complete graphs, Kn, and neighbourhood designs of their line graphs, L1(Kn) (the so-called triangular graphs), have been considered elsewhere by others. We consider codes from incidence designs of L1(Kn) and L2(Kn), and neighbourhood designs of L2(Kn) and L3(Kn). In each case, basic parameters of the codes are determined. Further, we introduce a family of vertex-transitive graphs 􀀀n that are embeddable into the strong product L1(Kn) ⊠ K2, of triangular graphs and K2, a class which at first sight may seem unnatural but, on closer look, is a repository of graphs rich with combinatorial structures. For instance, unlike most regular graphs considered here and elsewhere that only come with incidence and neighbourhood designs, 􀀀n also has what we have termed as 6-cycle designs. These are designs in which the point set contains vertices of the graph and every block contains vertices of a 6-cycle in the graph. Also, binary codes from incidence matrices of these graphs have other minimum words in addition to incidence vectors of the blocks. In addition, these graphs have induced subgraphs isomorphic to the family Hn of complete porcupines (see Definition 4.11). We describe codes from incidence matrices of 􀀀n and Hn and determine their parameters.

Philosophiae Doctor - PhD (Mathematics) / The main theme of this thesis is the construction of linear codes from adjacency matrices or sub-matrices of adjacency matrices of regular graphs. We first examine the binary codes from the row span of biadjacency matrices and their transposes for some classes of bipartite graphs. In this case we consider a sub-matrix of an adjacency matrix of a graph as the generator of the code. We then shift our attention to uniform subset graphs by exploring the automorphism groups of graph covers and some classes of uniform subset graphs. In the sequel, we explore equal codes from adjacency matrices of non-isomorphic uniform subset graphs and finally consider codes generated by an adjacency matrix formed by adding adjacency matrices of two classes of uniform subset graphs.

Philosophiae Doctor - PhD / In this thesis, we describe linear codes over prime fields obtained from incidence designs of iterated line graphs of complete graphs Li(Kn) where i = 1, 2. In the binary case, results are extended to codes from neighbourhood designs of the line graphs Li+1(Kn) using certain elementary relations. Codes from incidence designs of complete graphs, Kn, and neighbourhood designs of their line graphs, L1(Kn) (the so-called triangular graphs), have been considered elsewhere by others. We consider codes from incidence designs of L1(Kn) and L2(Kn), and neighbourhood designs of L2(Kn) and L3(Kn). In each case, basic parameters of the codes are determined. Further, we introduce a family of vertex-transitive graphs Γn that are embeddable into the strong product L1(Kn)⊠  K2, of triangular graphs and K2, a class which at first sight may seem unnatural but, on closer look, is a repository of graphs rich with combinatorial structures. For instance, unlike most regular graphs considered here and elsewhere that only come with incidence and neighbourhood designs, Γn also has what we have termed as 6-cycle designs. These are designs in which the point set contains vertices of the graph and every block contains vertices of a 6-cycle in the graph. Also, binary codes from incidence matrices of these graphs have other minimum words in addition to incidence vectors of the blocks. In addition, these graphs have induced subgraphs isomorphic to the family Hn of complete porcupines (see Definition 4.11). We describe codes from incidence matrices of Γn and Hn and determine their parameters. / South Africa

Philosophiae Doctor - PhD / In this thesis, we describe linear codes over prime fields obtained from incidence designs of iterated line graphs of complete graphs Li(Kn) where i = 1,2. In the binary case, results are extended to codes from neighbourhood designs of the line graphs Li+l(Kn) using certain elementary relations. Codes from incidence designs of complete graphs, Kn' and neighbourhood designs of their line graphs, £1(Kn) (the so-called triangular graphs), have been considered elsewhere by others. We consider codes from incidence designs of Ll(Kn) and L2(Kn), and neighbourhood designs of L2(Kn) and L3(Kn). In each case, the basic parameters of the codes are determined. Further, we introduce a family of vertex-transitive graphs Rn that are embeddable into the strong product Ll(Kn) ~ K2' of triangular graphs and K2' a class that at first sight may seem unnatural but, on closer look, is a repository of graphs rich with combinatorial structures. For instance, unlike most regular graphs considered here and elsewhere that only come with incidence and neighbourhood designs, Rn also has what we have termed as 6-cycle designs. These are designs in which the point set contains vertices of the graph and every block contains vertices of a 6-cycle in the graph. Also, binary codes from incidence matrices of these graphs have other minimum words in addition to incidence vectors of the blocks. In addition, these graphs have induced subgraphs isomorphic to the family Hn of complete porcupines (see Definition 4.11). We describe codes from incidence matrices of Rn and Hn and determine their parameters. The discussion is concluded with a look at complements of Rn and Hn, respectively denoted by Rn and Hn. Among others, the complements rn are contained in the union of the categorical product Ll(Kn) x Kn' and the categorical product £1(Kn) x Kn (where £1(Kn) is the complement of the iii triangular graph £1(Kn)). As with the other graphs, we have also considered codes from the span of incidence matrices of Rn and Hn and determined some of their properties. In each case, automorphisms of the graphs, designs and codes have been determined. For the codes from incidence designs of triangular graphs, embeddings of Ll(Kn) x K2 and complements of complete porcupines, we have exhibited permutation decoding sets (PD-sets) for correcting up to terrors where t is the full error-correcting capacity of the codes. For the remaining codes, we have only been able to determine PD-sets for which it is possible to correct a fraction of t-errors (partial permutation decoding). For these codes, we have also determined the number of errors that can be corrected by permutation decoding in the worst-case.