1,720,964 research outputs found
Codes, arrangements, matroids, and their polynomial links
Get PDFCodes, arrangements, matroids, and their polynomial links Many mathematical objects are closely related to each other. While studying certain aspects of a mathematical object, one tries to find a way to "view" the object in a way that is most suitable for a specific problem. Or, in other words, one tries to find the best way to model the problem. Many related fields of mathematics have evolved from one another this way. In practice, it is very useful to be able to transform a problem into other terminology: it gives a lot more available knowledge and that can be helpful to solve a problem. This thesis deals with various closely related fields in discrete mathematics, starting from linear error-correcting codes and their weight enumerator. We can generalize the weight enumerator in two ways, to the extended and generalized weight enumerators. The set of generalized weight enumerators is equivalent to the extended weight enumerator. Summarizing and extending known theory, we define the two-variable zeta polynomial of a code and its generalized zeta polynomial. These polynomials are equivalent to the extended and generalized weight enumerator of a code. We can determine the extended and generalized weight enumerator using projective systems. This calculation is explicitly done for codes coming from finite projective and affine spaces: these are the simplex code and the first order Reed-Muller code. As a result we do not only get the weight enumerator of these codes, but it also gives us information on their geometric structure. This is useful information in determining the dimension of geometric designs. To every linear code we can associate a matroid that is representable over a finite field. A famous and well-studied polynomial associated to matroids is the Tutte polynomial, or rank generating function. It is equivalent to the extended weight enumerator. This leads to a short proof of the MacWilliams relations for the extended weight enumerator. For every matroid, its flats form a geometric lattice. On the other hand, every geometric lattice induces a simple matroid. The Tutte polynomial of a matroid determines the coboundary polynomial of the associated geometric lattice. In the case of simple matroids, this becomes a two-way equivalence. Another polynomial associated to a geometric lattice (or, more general, to a poset) is the Möbius polynomial. It is not determined by the coboundary polynomial, neither the other way around. However, we can give conditions under which the Möbius polynomial of a simple matroid together with the Möbius polynomial of its dual matroid defines the coboundary polynomial. The proof of these relations involves the two-variable zeta polynomial, that can be generalized from codes to matroids. Both matroids and geometric lattices can be truncated to get an object of lower rank. The truncated matroid of a representable matroid is again representable. Truncation formulas exist for the coboundary and Möbius polynomial of a geometric lattice and the spectrum polynomial of a matroid, generalizing the known truncation formula of the Tutte polynomial of a matroid. Several examples and counterexamples are given for all the theory. To conclude, we give an overview of all polynomial relations
Weight enumeration of codes from finite spaces
No full textWe study the generalized and extended weight enumerator of the q-ary Simplex code and the q-ary first order Reed-Muller code. For our calculations we use that these codes correspond to a projective system containing all the points in a finite projective or affine space. As a result from the geometric method we use for the weight enumeration, we also completely determine the set of supports of subcodes and words in an extension code
Relations between Möbius and coboundary polynomials
Get PDFIt is known that, in general, the coboundary polynomial and the Möbius polynomial of a matroid do not determine each other. Less is known about more specific cases. In this paper, we will investigate if it is possible that the Möbius polynomial of a matroid, together with the Möbius polynomial of the dual matroid, define the coboundary polynomial of the matroid. In some cases, the answer is affirmative, and we will give two constructions to determine the coboundary polynomial in these cases
Codes, arrangements and matroids
No full textThis chapter treats error-correcting codes and their weight enumerator as the center of several closely related topics such as arrangements of hyperplanes, graph theory, matroids, posets and geometric lattices and their characteristic, chromatic, Tutte, Möbius and coboundary polynomial, respectively. Their interrelations and many examples and counterexamples are given. It is concluded with a section with references to the literature for further reading and open questions
Truncation formulas for invariant polynomials of matroids and geometric lattices
Get PDFThis paper considers the truncation of matroids and geometric lattices. It is shown that the truncated matroid of a representable matroid is again representable. Truncation formulas are given for the coboundary and Möbius polynomial of a geometric lattice and the spectrum polynomial of a matroid, generalizing the truncation formula of the rank generating polynomial of a matroid by Britz.
Keywords: Matroid theory – Geometric lattice – Invariant polynomial
On defining generalized rank weights
No full textThis paper investigates the generalized rank weights, with a definition implied by the study of the generalized rank weight enumerator. We study rank metric codes over L, where L is a finite extension of a field K. This is a generalization of the case where K = Fq and L = Fqm of Gabidulin codes to arbitrary characteristic. We show equivalence to previous definitions, in particular the ones by Kurihara-Matsumoto-Uyematsu [12, 13], Oggier-Sboui [16] and Ducoat [6]. As an application of the notion of generalized rank weights, we discuss codes that are degenerate with respect to the rank metric
The extended coset leader weight enumerator
No full textThis paper is a report on the ongoing research concerning the extended coset
leader weight enumerator using the theory of arrangements of hyperplanes, geo-
metric lattices and characteristic polynomials
The extended and generalized rank weight enumerator of a code
No full textThis paper investigates the rank weight enumerator of a code over L, where L is a finite extension of a field K. This is a generalization of the case where K = F_q and L = F_{q^m} of Gabidulin codes to arbitrary characteristic. We use the notion of counting polynomials, to define the (extended) rank weight enumerator, since in this generality the set of codewords of a given rank weight is no longer finite. Also the extended and generalized rank weight enumerator are studied in analogy with previous work on codes with respect to the Hamming metric
Extended and generalized weight enumerators
No full textThis paper gives a survey on extended and generalized weight enumerators of a linear code and the Tutte polynomial of the matroid of the code [16]. Furthermore ongoing research is reported on the coset leader and list weight enumerator and its extensions using the derived code and its arrangement of hyperplanes
- …
