|
|
Structural properties of hereditary permutation classes
Opler, Michal ; Jelínek, Vít (advisor) ; Valtr, Pavel (referee)
A permutation class C is splittable if it is contained in a merge of its two proper subclasses, and it is 1-amalgamable if given two permutations σ, τ ∈ C, each with a marked element, we can find a permutation π ∈ C containing both σ and τ such that the two marked elements coincide. In this thesis, we study both 1-amalgamability and splittability of permutation classes. It was previously shown that unsplittability implies 1-amalgamability. We prove that unsplittability and 1-amalgamability are not equivalent properties of permutation classes by showing that there is a permutation class that is both splittable and 1-amalgamable. Moreover, we show that there are infinitely many such classes. Our construction is based on the concept of LR-inflations or more generally on hereditary 2-colorings, which we both introduce here and which may be of independent interest. 1
|
|
|
An algorithm for extending partial planar drawings
Hora, Martin ; Jelínek, Vít (advisor) ; Šámal, Robert (referee)
This thesis studies the problem of partially embedded planarity. The input of the problem is a graph G and a planar drawing of a subgraph of G. The goal is to decide whether the drawing of the subgraph can be extended to a planar drawing of the entire graph G. It has already been proved that the partially embedded planarity problem can be solved in linear time. However, all known linear algorithms are relatively complicated. This is probably the reason that no implementation has yet been published. We will introduce a new, simpler linear algorithm that solves the problem and we will prove its correctness. Next, we will enclose an implementation of this algorithm in the C++ programming language. 1
|
|
|
Hereditary classes of binary matrices
Kučera, Stanislav ; Jelínek, Vít (advisor) ; Klazar, Martin (referee)
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
|
|
|
Intersection representations of graphs
Töpfer, Martin ; Jelínek, Vít (advisor) ; Šámal, Robert (referee)
We investigate intersection graphs of axis-aligned L-shapes (L-graphs) and their subclass, when all L- shapes have one of their endpoints on the same line - let us call this class outer-L-graphs. In the beginning we introduce some known facts about L-graphs. Then we show, that interval, circular and outerplanar graphs are subclasses of outer-L-graphs. We also characterise outer-L-graphs using ordering without forbidden patterns. Powered by TCPDF (www.tcpdf.org)
|
|
|
Generating random pattern-avoiding matrices
Kučera, Stanislav ; Jelínek, Vít (advisor) ; Šámal, Robert (referee)
Binary matrices not containing a smaller matrix as a submatrix have become an interesting topic recently. In my thesis, I introduce two new algorithms to test whether a big square binary matrix contains a smaller binary matrix together with a process using randomness, which approximates a uniformly random matrix not containing a given matrix. The reason to create such algorithms is to allow researchers test their conjectures on random matrices. Thus, my thesis also contains an effective cross- platform implementation of all mentioned algorithms. Powered by TCPDF (www.tcpdf.org)
|
|
|
Structure and enumeration of permutation classes
Karpilovskij, Mark ; Jelínek, Vít (advisor) ; Balko, Martin (referee)
We define the operation of composing two hereditary classes of permutations using the standard composition of permutations as functions and we explore properties and structure of permutation classes considering this operation. We mostly concern ourselves with the problem of whether permutation classes can be composed from their proper subclasses. We provide examples of classes which can be composed from two proper subclasses, classes which can be composed from three but not from two proper subclasses and classes which cannot be composed from any finite number of proper subclasses. Powered by TCPDF (www.tcpdf.org)
|
|
|
Cops and robber game on directed complete graphs
Slívová, Veronika ; Gavenčiak, Tomáš (advisor) ; Jelínek, Vít (referee)
BACHELOR THESIS - ABSTRACT Veronika Slívová This thesis focuses on the game Cops and robber on tournaments (a graph we gain by orienting each edge of undirected complete graph). We show that tournaments containing a vertex with large outdegree have small cop number. On the other hand we prove that the number of cops we need to capture the robber on any tournament is not bounded. Then we study circulant tournaments and graphs obtained by cyclically orienting each triple of Steiner triple system. We disprove the conjecture made by Geňa Hahn that the cop number of any graph obtained by orientation Steiner triple system is bounded. We also show that the cop number of circulant tournaments cannot be bounded. Then we focus on the 2-fast cop and the 2-fast robber variant of the game. We prove that one 2-fast cop wins on any tournament. On the contrary in case that the game is played on tournament whose vertices have the same outdegree, the 2-fast robber is captured trivially or runs away indefinitely.
|
|
| |
|
|
Pattern-avoiding permutation classes
Opler, Michal ; Jelínek, Vít (advisor) ; Klazar, Martin (referee)
For a permutation π, the major index of π is the sum of all indices i such that πi > πi+1. In this thesis, we study the distribution of the major index over pattern-avoiding permutations of length n. We focus on the number Mm n (Π) of permutations of length n with major index m and avoiding the set of patterns Π. First, we are able to show that for a singleton set Π = {σ} other than some trivial cases, the values Mm n (Π) are monotonic in the sense that Mm n (Π) ≤ Mm n+1(Π). Our main result is a study of the asymptotic behaviour of Mm n (Π) as n goes to infinity. We prove that for every fixed m, Π and n large enough, Mm n (Π) is equal to a polynomial in n and moreover, we are able to determine the degrees of these polynomials for many sets of patterns. 1
|
|
|
Enumeration of compositions with forbidden patterns
Dodova, Borjana ; Klazar, Martin (advisor) ; Jelínek, Vít (referee)
Enumeration of pattern avoiding compositions of numbers Abstract The aim of this work was to find some new results for 3-regular compositions, i.e., for those compositions which avoid the set of patterns {121, 212, 11}. Those compositions can be regarded as a generalization of Carlitz composition. Based on the generating function of compositions avoiding the set of patterns {121, 11} and {212, 11} we derive an upper bound for the coefficients of the power series of the generating function of 3-regular compositions. Using the theory of finite automata we derive its lower bound. We develop this result further by defining 3-block compositions. For the generating function of 3-regular compositions we prove a recursive ralation. Besides that we also compute the generating function of compositions avoiding the set of patterns {312, 321} whose parts are in the set [d]. In the last section we prove that the generating function of Carlitz compositions is transcendental.
|
guest ::
RSS feed.