Mřížky a kódy

Abstract

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.