velikost textu

Geometric and algebraic properties of discrete structures

Upozornění: Informace získané z popisných dat či souborů uložených v Repozitáři závěrečných prací nemohou být použity k výdělečným účelům nebo vydávány za studijní, vědeckou nebo jinou tvůrčí činnost jiné osoby než autora.
Název:
Geometric and algebraic properties of discrete structures
Název v češtině:
Geometrické a algebraické vlastnosti diskrétních struktur
Typ:
Disertační práce
Autor:
Mgr. Pavel Rytíř, Ph.D.
Školitel:
prof. RNDr. Martin Loebl, CSc.
Oponenti:
Oriol Serra
RNDr. Tomáš Kaiser, Dr.
Id práce:
44523
Fakulta:
Matematicko-fyzikální fakulta (MFF)
Pracoviště:
Katedra aplikované matematiky (32-KAM)
Program studia:
Informatika (P1801)
Obor studia:
Diskrétní modely a algoritmy (4I4)
Přidělovaný titul:
Ph.D.
Datum obhajoby:
1. 8. 2013
Výsledek obhajoby:
Prospěl/a
Jazyk práce:
Angličtina
Klíčová slova:
simpliciální komplex, lineární kód, váhový polynom, geometrické reprezentace
Klíčová slova v angličtině:
simplicial complex, linear code, weight enumerator, geometric representations
Abstrakt:
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é mají geometrickou reprezentaci v R3. Ukážeme, že váhový polynom každého binárního lineárního kódu je polynomiálně pře- veditelný na permanent troj-rozměrné nezáporné matice. Dále studujeme Pfaffiánovské troj-rozměrné matice a ukážeme aplikaci našich výsledků ve statistické fyzice.
Abstract v angličtině:
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 binary linear codes that have a geometric representation embeddable into R3. We further show that the weight enumerator of any binary linear code is polynomial reducible to the permanent of a non-negative three dimensional matrix. We give some applications of our results to statistical physics, by studying the Pfaffian three dimensional matrices.
Dokumenty
Stáhnout Dokument Autor Typ Velikost
Stáhnout Text práce Mgr. Pavel Rytíř, Ph.D. 841 kB
Stáhnout Abstrakt v českém jazyce Mgr. Pavel Rytíř, Ph.D. 18 kB
Stáhnout Abstrakt anglicky Mgr. Pavel Rytíř, Ph.D. 14 kB
Stáhnout Posudek vedoucího prof. RNDr. Martin Loebl, CSc. 34 kB
Stáhnout Posudek oponenta Oriol Serra 121 kB
Stáhnout Posudek oponenta RNDr. Tomáš Kaiser, Dr. 153 kB
Stáhnout Záznam o průběhu obhajoby 177 kB