Original title:
Matice bez zakázaných intervalových minorů
Translated title:
Matrices without forbidden interval minors
Authors:
Surma, David ; Jelínek, Vít (advisor) ; Klazar, Martin (referee) Document type: Bachelor's theses
Year:
2020
Language:
cze Abstract:
[cze][eng] V práci zkoumáme strukturu binárních matic, které neobsahují vzor P jako intervalový minor. Zabýváme se rovněž maticemi kritickými pro P, tedy maticemi neobsahujícími P, které po změně libovolného 0-prvku na 1-prvek zakázaný vzor P obsahují. Nejprve popi- sujeme matice kritické pro libovolný jednořádkový vzor. Dále se zabýváme všemi vzory o dvou řádcích a třech sloupcích, které obsahují nejvýše čtyři 1-prvky. Nakonec charak- terizujeme matice kritické pro střídavý vzor o rozměrech 2 × 4. 1In the thesis, we study the structure of binary matrices which do not contain a pat- tern P as an interval minor. We also deal with matrices that are critical for P, i.e., matrices without P which after changing any 0-entry to 1-entry contain the forbidden pattern P. First, we describe matrices critical for any one-line pattern. Then we deal with all patterns with two rows and three columns which contain at most four 1-entries. Finally, we characterize the matrices critical for the alternating pattern of size 2 × 4. 1
Keywords:
binary matrix; forbidden pattern; interval minor; binární matice; intervalový minor; zakázaný vzor
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/119444