
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 1amalgamable 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 1amalgamability and splittability of permutation classes. It was previously shown that unsplittability implies 1amalgamability. We prove that unsplittability and 1amalgamability are not equivalent properties of permutation classes by showing that there is a permutation class that is both splittable and 1amalgamable. Moreover, we show that there are infinitely many such classes. Our construction is based on the concept of LRinflations or more generally on hereditary 2colorings, which we both introduce here and which may be of independent interest. 1


On the interior of a minimal convex polygon
Šplíchal, Ondřej ; Valtr, Pavel (advisor) ; Rataj, Jan (referee)
Zvolme konečnou množinu bod· P v rovině v obecné poloze, tj. žádné 3 body neleží na přímce. Konvexní núhelník je minimální, pokud v jeho konvexním obalu neleží jiný konvexní núhelník s vrcholy v P. Erd®s a Szekeres (1935) ukázali, že pro každé n ≥ 3 existuje minimální číslo ES(n) takové, že mezi libovolnými ES(n) body v rovině v obecné poloze lze vybrat n bod·, které tvoří vrcholy konvexního núhelníku. Z jejich tvrzení vyplývá, že v topologic kém vnitřku minimálního konvexního núhelníku m·že ležet jen omezený po čet bod· P pro libovolnou volbu P. Označíme maximální takový počet jako mci(n). V práci ukážeme horní odhad mci(n) ≤ ES(n) − n a spodní odhad 2n−3 − n + 2 ≤ mci(n) pro n ≥ 3.


Problems in discrete geometry
Patáková, Zuzana ; Matoušek, Jiří (advisor) ; Bárány, Imre (referee) ; Valtr, Pavel (referee)
of doctoral thesis Problems in discrete geometry Zuzana Patáková This thesis studies three different questions from discrete geometry. A common theme for these problems is that their solution is based on algebraic methods. First part is devoted to the polynomial partitioning method, which par titions a given finite point set using the zero set of a suitable polynomial. However, there is a natural limitation of this method, namely, what should be done with the points lying in the zero set? Here we present a general version dealing with the situation and as an application, we provide a new algorithm for the semialgebraic range searching problem. In the second part we study Ramsey functions of semialgebraic predi cates. Conlon, Fox, Pach, Sudakov, and Suk constructed the first examples of semialgebraic predicates with the Ramsey function bounded from below by a tower function. We reduce the dimension of the ambient space in their construction and as a consequence, we provide a new geometric Ramseytype theorem with a large Ramsey function. Last part is devoted to reptile simplices. A simplex S is kreptile if it can be tiled by k simplices with disjoint interiors that are all mutually congruent and similar to S. We show that fourdimensional kreptile simplices can exist only for k = m2 , where m ≥ 1...


Ramseytype results for ordered hypergraphs
Balko, Martin ; Valtr, Pavel (advisor)
Ramseytype results for ordered hypergraphs Martin Balko Abstract We introduce ordered Ramsey numbers, which are an analogue of Ramsey numbers for graphs with a linear ordering on their vertices. We study the growth rate of ordered Ramsey numbers of ordered graphs with respect to the number of vertices. We find ordered match ings whose ordered Ramsey numbers grow superpolynomially. We show that ordered Ramsey numbers of ordered graphs with bounded degeneracy and interval chromatic number are at most polynomial. We prove that ordered Ramsey numbers are at most polynomial for ordered graphs with bounded bandwidth. We find 3regular graphs that have superlinear ordered Ramsey numbers, regardless of the ordering. The last two results solve problems of Conlon, Fox, Lee, and Sudakov. We derive the exact formula for ordered Ramsey numbers of mono tone cycles and use it to obtain the exact formula for geometric Ramsey numbers of cycles that were introduced by K'arolyi et al. We refute a conjecture of Peters and Szekeres about a strengthening of the fa mous Erd˝osSzekeres conjecture to ordered hypergraphs. We obtain the exact formula for the minimum number of crossings in simple xmonotone drawings of complete graphs and provide a combinatorial characterization of these drawings in terms of colorings of ordered...


Extremal Polyominoes
Steffanová, Veronika ; Valtr, Pavel (advisor) ; Cibulka, Josef (referee)
Title: Extremal Polyominoes Author: Veronika Steffanová Department: Department of Applied Mathematics Supervisor: Doc. RNDr. Pavel Valtr, Dr. Abstract: The thesis is focused on polyominoes and other planar figures consisting of regular polygons, namely polyiamonds and polyhexes. We study the basic geometrical properties: the perimeter, the convex hull and the bounding rectangle/hexagon. We maximise and minimise these parameters and for the fixed size of the polyomino, denoted by n. We compute the extremal values of a chosen parameter and then we try to enumerate all polyominoes of the size n, which has the extremal property. Some of the problems were solved by other authors. We summarise their results. Some of the problems were solved by us, namely the maximal bounding rectan gle/hexagon and maximal convex hull of polyiamonds. There are still sev eral topics which remain open. We summarise the literature and offer our observations for the following scientists. Keywords: Polyomino, convex hull, extremal questions, plane 1


Viditelnostní grafy
Král, Karel ; Valtr, Pavel (advisor) ; Balko, Martin (referee)
In the thesis we study visibility graphs focusing on the Big Line Big Clique conjecture. For a given finite point set P in real plane we say that two points see each other if and only if the open line segment between them contains no point from P. Points from P are vertices of the visibility graph, and two points are connected by an edge if and only if they see each other. Kára et al. conjectured that for every finite big enough point set there are at least ℓ collinear points, or the clique number of its visibility graph is at least k. In the thesis we generalize the conjecture, and thus provide an alternative proof for k = ℓ = 4. We also review related known results. We strengthen an observation about occurrence of a Hamiltonian cycle in visibility graphs. We characterize the asymptotic behavior of the edge chromatic number of visibility graphs. We show that for given n, ℓ, k the original conjecture is decidable by a computer. We also provide computer experiments both for the generalized and for the original conjecture. 1


Extremal combinatorics of matrices, sequences and sets of permutations
Cibulka, Josef ; Valtr, Pavel (advisor) ; Füredi, Zoltán (referee) ; Jelínek, Vít (referee)
Title: Extremal combinatorics of matrices, sequences and sets of permutations Author: Josef Cibulka Department: Department of Applied Mathematics Supervisor: Doc. RNDr. Pavel Valtr, Dr., Department of Applied Mathematics Abstract: This thesis studies questions from the areas of the extremal theory of {0, 1}matrices, sequences and sets of permutations, which found many ap plications in combinatorial and computational geometry. The VCdimension of a set P of nelement permutations is the largest integer k such that the set of restrictions of the permutations in P on some ktuple of positions is the set of all k! permutation patterns. We show lower and upper bounds quasiexponential in n on the maximum size of a set of nelement permutations with VCdimension bounded by a constant. This is used in a paper of Jan Kynčl to considerably improve the upper bound on the number of weak isomorphism classes of com plete topological graphs on n vertices. For some, mostly permutation, matrices M, we give new bounds on the number of 1entries an n × n Mavoiding matrix can have. For example, for every even k, we give a construction of a matrix with k2 n/2 1entries that avoids one specific kpermutation matrix. We also give almost tight bounds on the maximum number of 1entries in matrices avoiding a fixed layered...

 

Konvexně nezávislé podmnožiny konečných množin bodů
Zajíc, Vítězslav ; Valtr, Pavel (advisor) ; Cibulka, Josef (referee)
Let fd(n), n > d ≥ 2, be the smallest positive integer such that any set of fd(n) points, in general position in Rd , contains n points in convex position. Let hd(n, k), n > d ≥ 2 and k ≥ 0, denote the smallest number with the property that in any set of hd(n, k) points, in general position in Rd , there are n points in convex position whose convex hull contains at most k other points. Previous result of Valtr states that h4(n, 0) does not exist for all n ≥ 249. We show that h4(n, 0) does not exist for all n ≥ 137. We show that h3(8, k) ≤ f3(8) for all k ≥ 26, h4(10, k) ≤ f4(10) for all k ≥ 147 and h5(12, k) ≤ f5(12) for all k ≥ 999. Next, let fd(k, n) be the smallest number such that in every set of fd(k, n) points, in general position in Rd , there are n points whose convex hull has at least k vertices. We show that, for arbitrary integers n ≥ k ≥ d + 1, d ≥ 2, fd(k, n) ≥ (n − 1) (k − 1)/(cd logd−2 (n − 1)) , where cd > 0 is a constant dependent only on the dimension d. 1


Competitive filling of a plane region
Slabý, David ; Valtr, Pavel (advisor) ; Valla, Tomáš (referee)
Two players take alternating turns filling a rectangular board with unit squares without rotation, but may be otherwise arbitrary. Squares may not overlap and the game ends when there is no space for the next one. The result of the game is the number of turns. The constructor aims to maximize this quantity while the destructor wants to minimize it. We would like to get close to this value, provided that both players use their optimal strategy. We prove some new lower and upper bound for the game. This thesis extends results given by Tamás Hubai in his paper Competitive rectangle filling. Furthermore, we have a look at other board shapes and shapes to fill with.
