Original title:
Geometrické a algebraické vlastnosti diskrétních struktur
Translated title:
Geometric and algebraic properties of discrete structures
Authors:
Rytíř, Pavel ; Loebl, Martin (advisor) ; Serra, Oriol (referee) ; Kaiser, Tomáš (referee) Document type: Doctoral theses
Year:
2013
Language:
eng Abstract:
[eng][cze] 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...V práci se zabýváme dvou-dimenzionálními simpliciálními komplexy a lineárními kódy. Řekneme, že lineární kód C nad tělesem F je trojúhelníkově reprezentovatelný, pokud exis- tuje dvou-dimenzionální simpliciální komplex ∆ takový, že kód C je propíchnutým kódem jádra ker ∆ incidenční matice simpliciálního komplexu ∆ nad F a dim C = dim ker ∆. Tento simpliciální komplex nazveme geometrickou reprezentací kódu C. Dokážeme, že každý lineární kód nad prvotělesem je trojúhelníkově reprezentovatelný. Pro konečná prvotělesa sestrojíme geometrickou reprezentaci takovou, že váhový polynom kódu C je dán jednoduchou formulí váhového polynomu prostoru cyklů simpliciálního kom- plexu ∆. Tedy geometrická reprezentace kódu C určuje jeho váhový polynom. Naše motivace pochází z teorie pfaffiánovských orientací grafů, která poskytuje polyno- miální algoritmus pro výpočet váhového polynomu prostoru řezů grafu s omezeným rodem. Tento algoritmus využívá geometrických vlastností nakreslení grafu na orientovatelnou ri- emannovskou plochu. Prostor řezů je lineární kód a odpovídající graf je jeho užitečnou geometrickou reprezentací. Dále studujeme vnořitelnost geometrických reprezentací do euklidovských prostorů. Ukážeme, že každý binární lineární kód má geometrickou reprezentaci v R4 . Charakte- rizujeme binární lineární kódy, které...
Keywords:
geometric representations; linear code; simplicial complex; weight enumerator; geometrické reprezentace; lineární kód; simpliciální komplex; váhový polynom
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/53317