|
|
Ramsey-type results for ordered hypergraphs
Balko, Martin ; Valtr, Pavel (advisor)
Ramsey-type 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 3-regular 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˝os-Szekeres conjecture to ordered hypergraphs. We obtain the exact formula for the minimum number of crossings in simple x-monotone 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 VC-dimension of a set P of n-element permutations is the largest integer k such that the set of restrictions of the permutations in P on some k-tuple 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 n-element permutations with VC-dimension 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 1-entries an n × n M-avoiding matrix can have. For example, for every even k, we give a construction of a matrix with k2 n/2 1-entries that avoids one specific k-permutation matrix. We also give almost tight bounds on the maximum number of 1-entries 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.
|
|
|
Grid representations of graphs and the chromatic number
Balko, Martin ; Valtr, Pavel (advisor) ; Kratochvíl, Jan (referee)
Grid Representations and the Chromatic Number Martin Balko August 2, 2012 Department: Department of Applied Mathematics Supervisor: doc. RNDr. Pavel Valtr Dr. Supervisor's email address: valtr@kam.mff.cuni.cz Abstract In the thesis we study grid drawings of graphs and their connections with graph colorings. A grid drawing of a graph maps vertices to distinct points of the grid Zd and edges to line segments that avoid grid points representing other vertices. We show that a graph G is qd -colorable, d, q ≥ 2, if and only if there is a grid drawing of G in Zd in which no line segment intersects more than q grid points. Second, we study grid drawings with bounded number of columns, introducing some new NP- complete problems. We also show a sharp lower bound on the area of plane grid drawings of balanced complete k-partite graphs, proving a conjecture of David R. Wood. Finally, we show that any planar graph has a planar grid drawing where every line segment contains exactly two grid points. This result proves conjectures of D. Flores Pe˝naloza and F. J. Zaragoza Martinez. Keywords: graph representations, grid, chromatic number, plane
|
|
|
Pokrývání sečen konvexní oblasti
Sterzik, Marek ; Matoušek, Jiří (referee) ; Valtr, Pavel (advisor)
For a given covnex body we try to find the shortest possible set (optionally admitting some prescribed properties) meeting all lines meeting the given body. The size of the covering set is measured by the Hausdorff 1-dimensional measure 1. In the first chapter there is given an introduction to the problem. In the second chapter we discuss the upper bound for the minimal covering set. In the third chapter we discuss the existence and properties of the minimal covering. In the fourth chapter we show some lower bounds for the size of a covering. In the fifth chapter we study some related topics and a generalization of the problem.
|
|
| |
guest ::
