|
|
Möbius function of matrix posets
Medek, Michal ; Jelínek, Vít (vedoucí práce) ; Kantor, Ida (oponent)
In this work, we focus on the M¨obius function µ(X, Y ) of four variants of containment posets of sparse matrices, for which the M¨obius function has not been studied before. A sparse matrix is a binary matrix containing at most one 1-cell in each row and column. We focus mainly on the dominated scattered containment, where X ≤ Y if X can be created from Y by removing some rows and columns and by changing some 1-cells to 0-cells. We consider this poset to be a generalization of the permutation poset, as for permutations σ and π, if σ ≤ π, then the permutation matrices Mσ and Mπ satisfy Mσ ≤ Mπ. For the dominated scattered containment, we study the values of the M¨obius function on intervals of the form [1, Y ], where 1 is the 1 × 1 matrix consisting of a single 1-cell. We show that the situation when Y contains a zero row or column can be reduced to a situation when Y has no such zero line, that is, Y is a permutation matrix. For a permutation matrix Y , we derived a theorem expressing µ(1, Y ) in terms of the blocks of the sum decomposition of Y .
|
|
|
Möbiova funkce kombinatorických uspořádání
Kopfová, Lenka ; Jelínek, Vít (vedoucí práce) ; Kantor, Ida (oponent)
V této práci se zabýváme částečně uspořádanou množinou znaménkových permutací. Uspořádání na permutacích je zde definováno pomocí obsahování jako podpermutace. Znaménková permutace je taková permutace, ve které má každý prvek zvolené plus nebo mínus znaménko. Znaménkové permutace jsou tak zobecněním neznamínkových permutací, protože ty můžeme dostat tak, že každému prvku zvolíme plus znaménko. Ukážeme několik výsledků týkající se Möbiovy funkce znaménkových permutací, některá z nich jsou zobecněním už dříve dokázaných vět pro neznaménkové permutace. Práce se také zabývá izomorfismem částečně uspořádaných množin znaménkových permutací. Izomor- fismus pak mimo jiné zaručuje, že dané dva intervaly mají stejnou hodnotu Möbiovy funkce.
|
host ::
RSS.