Original title: Möbiova funkce maticových uspořádání
Translated title: Möbius function of matrix posets
Authors: Medek, Michal ; Jelínek, Vít (advisor) ; Kantor, Ida (referee)
Document type: Bachelor's theses
Year: 2023
Language: eng
Abstract: 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 .
Keywords: Sparse matrix|Submatrix|Möbius function; Řídká matice|Podmatice|Möbiova funkce

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/183053

Permalink: http://www.nusl.cz/ntk/nusl-532289


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Bachelor's theses