Original title: Dědičné třídy binárních matic
Translated title: Hereditary classes of binary matrices
Authors: Kučera, Stanislav ; Jelínek, Vít (advisor) ; Klazar, Martin (referee)
Document type: Master’s theses
Year: 2017
Language: eng
Abstract: [eng] [cze]
Interval minors of binary matrices were introduced by Jacob Fox in the study of Stanley-Wilf limits. We study what can be implied from their relation to the theory of pattern avoidance of submatrices, which is a very popular area of discrete mathematics. We start by characterizing matrices avoiding small interval minors. We then consider classes of matrices closed under interval minors and we find classes of matrices that cannot be described by a finite number of forbidden interval minors. We also define and study a variant of a classical extremal Tur'an- type question studied in the area of combinatorics of permutations and binary matrices and in combinatorial geometry. 1 Intervalové minory binárních matic byly zavedeny Jacobem Foxem při vý- zkumu Stanleyho-Wilfových limit. Prozkoumáme, co se dá odvodit z jejich vztahu s teorií neobsahování podmaticových vzorů, což je velmi populární oblast diskrétní matematiky. Začneme charakterizací matic neobsahujících malé intervalové mi- nory. Poté se podíváme na třídy matic uzavřené na intervalové minory a najdeme takové třídy, které nelze popsat pomocí konečně mnoha zakázaných intervalových minorů. Také zadefinujeme a prozkoumáme variantu klasické Turánovské otázky zkoumané v oblastech kombinatoriky permutací a binárních matic a kombinato- rické geometrie. 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/85642

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


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