|
| |
|
|
Partial k-trees on surfaces
Vaner, Michal ; Valtr, Pavel (referee) ; Kratochvíl, Jan (advisor)
This work is solving the following problem: A graph G, a partial k-tree embeddable into some surface, is given. Is it possible to complete it to a k-tree in such a way that it is still embeddable? We show that this is always possible for small k (· 2) on any surface. On the contrary, for k ¸ 4, one can find a partial k-tree that is not possible to complete in this way, and for k large enough, there is no partial k-tree that could be completed. The case k = 3 makes the border case, because there is an infinite list of complete 3-trees embeddable into any surface, but not every 3-tree is embeddable. It is known that every partial 3-tree can be completed in the plane. To keep the thesis self-contained we present here the so far unpublished proof of prof. Kratochvíl and prof. Thomas. We extend this result to the projective plane. Other surfaces are still unexplored.
|
|
|
Covering All Lines Intersecting a Convex Domain
Sterzik, Marek ; 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.
|
|
|
Representations and Visualization of Graphs
Štola, Jan ; Kratochvíl, Jan (advisor) ; Valtr, Pavel (referee) ; Wood, David (referee)
The 3D visibility (graph) drawing is a graph drawing in IR3 where vertices are represented by 2D sets placed into planes parallel to xy-plane and the edges correspond to z-parallel visibility among these sets. We continue the study of 3D visibility drawing of complete graphs by rectangles and regular polygons. We show that the maximum size of a complete graph with a 3D visibility drawing by regular n-gons is O(n4). This polynomial bound improves signifficantly the previous best known (exponential) bound 6n3 3n1 3 26n.We also provide several lower bounds. We show that the complete graph K2k+3 (resp. K4k+6) has a 3D visibility drawing by regular 2k-gons (resp.(2k + 1)-gons). We improve the best known upper bound on the size of a complete graph with a 3D visibility drawing by rectangles from 55 to 50. This result is based on the exploration of unimodal sequences of k-tuples of numbers. A sequence of numbers is unimodal if it rst increases and then decreases. A sequence of k-tuples of numbers is unimodal if it is unimodal in each component. We derive tight bounds on the maximum length of a sequence of k-tuples without a unimodal subsequence of length n. We show a connection between these results and Dedekind numbers, i.e., the numbers of antichains of a power set P(1; : : : ; k) ordered by inclusion.
|
|
| |
|
| |
|
|
Ramsey-type theorems in geometry
Stolař, Rudolf ; Kratochvíl, Jan (referee) ; Valtr, Pavel (advisor)
Euclidean Ramsey theory is examining konfigurations of points, for which there exists n such that for every coloring of n-dimensional Euclidean space with r colors we can find translated and/or rotaded copy of our configuration in a single color. Asymetric branch deals with situations when we look for different configurations in every color. In this work we concern about asymetrical ramsey-type theorems and properties of n-cubes, for which we show several new bounds. Major part is dedicated to colorings with more colors and obtained results are closely related to the famous problem of chromatic number of Euclidean space. We will mention possible generalization of the chromatic number and some aspects of such generalization. We also consider problems connected to multi-color configurations and we will introduce upper bound for special case of two-color square.
|
|
|
Ramsey-type results for ordered hypergraphs
Balko, Martin ; Valtr, Pavel (advisor) ; Conlon, David (referee) ; Nešetřil, Jaroslav (referee)
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árolyi 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...
|
|
|
Ramseyova teorie a kombinatorické hry
Valla, Tomáš ; Valtr, Pavel (referee) ; Nešetřil, Jaroslav (advisor)
Ramsey theory studies the internal homogenity of mathematical structures (graphs, number sets), parts of which (subgraphs, number subsets) are arbitrarily coloured. Often, the sufficient object size implies the existence of a monochromatic sub-object. Combinatorial games are 2-player games of skill with perfect information. The theory of combinatorial games studies mostly the questions of existence of winning or drawing strategies. Let us consider an object that is studied by a particular Ramsey-type theorem. Assume two players alternately colour parts of this object by two colours and their goal is to create certain monochromatic sub-object. Then this is a combinatorial game. We focus on the minimum object size such that the appropriate Ramsey-type theorem holds, called Ramsey number, and on the minimum object size such that the rst player has a winning strategy in the corresponding combinatorial game, called game number. In this thesis, we describe such Ramsey-type theorems where the Ramsey number is substantially greater than the game number. This means, we show the existence of rst player's winning strategies, zogether with Ramsey and game numbers upper bounds, and we compare both numbers.
|
|
|
Chromatic invariants in graph drawing
Štola, Jan ; Kratochvíl, Jan (advisor) ; Valtr, Pavel (referee)
This paper studies the question: What is the maximum integer kb,n such that every kb,n-colorable graph has a b-bend n-din1ensional orthogonal box drawing? We give an exact answer for the orthogonal line drawing in all dimensions and for the 3-dimensional rectangle visibility representation. We present an upper and lower bound for the 3-dimensional orthogonal drawing by rectangles and general boxes. Particularly, we improve the best known upper bound for the 3-dimensional orthogonal box drawing from 183 to 42 and the lower bound from 3 to 22. Powered by TCPDF (www.tcpdf.org)
|
guest ::
