Original title:
Mřížky a kódy
Translated title:
Lattices and Codes
Authors:
Rytíř, Pavel ; Loebl, Martin (advisor) ; Pangrác, Ondřej (referee) Document type: Master’s theses
Year:
2007
Language:
cze Abstract:
[cze][eng] Diplomová práce zkoumá trojúhelníkové kon gurace, binární matroidy a mřížky generované binárními kódy. Zkoumáme domněnku, zdali mřížka generovaná kódovými slovy binárního kódu má bázi skládající se pouze z kódových slov. Domněnku dokážeme pro matroidy s dobrou uchovou dekompozicí. Prostudujeme operaci hranové kontrakce trojúhelníkové kon gurace. Hlavní dopad kontrakce na cyklus a acyklickou trojúhelníkovou kon guraci. Dokážeme, že pro každý graf existuje trojúhelníková kon gurace s kostrou která obsahuje tento graf jako minor. Pro každý binární matroid sestrojíme trojúhelníkovou kon guraci, která obsahuje tento matroid jako minor. Navíc dokážeme, že mezi prostory cyklů kon gurace a matroidu existuje bijekce. Tato bijekce zobrazuje kružnice matroidu na kružnice kon gurace.This thesis studies triangular con gurations, binary matroids, and integer lattices generated by the codewords of a binary code. We study the following hypothesis: the lattice generated by the codewords of a binary code has a basis consisting only of the codewords. We prove the hypothesis for the matroids with the good ear decomposition. We study the operation of edge contraction in the triangular con gurations. Especially in cycles and acyclic triangular con gurations. For an arbitrary graph we nd a triangular con guration with the skeleton containing this graph as a minor. For every binary matroid we construct a triangular con guration such that the matroid is a minor of the con guration. We prove that between the cycle spaces of the matroid and the con guration exists a bijection. The bijection maps the circuits of the matroid to the circuits of the con guration.
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/9350