|
| |
|
| |
|
|
Ramseyovské otázky v euklidovském prostoru
Cibulka, Josef ; Valtr, Pavel (advisor) ; Černý, Jakub (referee)
One of the problems in Euclidean Ramsey theory is to determine the chromatic number of the Euclidean space. The chromatic number of a space is the minimum number of colors with which the whole space can be colored so that no two points of the same color are at unit distance. We prove that the chromatic number of the six-dimensional real space is at least 11 and that the chromatic number of the seven-dimensional rational space is at least 15. In addition we give a new proof of the lower bound 9 for the chromatic number of the five-dimensional real space. We also simplify the proof of the lower bound 7 for the four-dimensional real space. It is known that the chromatic number of the n-dimensional real space grows exponentially in n. We show some of its subspaces, in which the growth is slower than exponential. We also summarize previous results for normed spaces in general and for some interesting non-Euclidean spaces.
|
|
|
Generating simple drawings of graphs
Čermák, Filip ; Balko, Martin (advisor) ; Valtr, Pavel (referee)
In this thesis, we study the crossing numbers of complete graphs. After introducing a long history of the old problem of determining the crossing number of Kn, we survey the recent progress on the Harary-Hill conjecture by compiling proofs of this conjecture for special classes of drawings of Kn. We also create a program for generating a database of all simple drawings of Kn with n ≤ 8. We implement another program that visualizes these drawings and allows the user to create its own simple drawings of general graphs. The visualizer also captures the structure of crossings of the displayed drawings. We use our programs to verify a conjecture by Balko, Fulek, and Kynčl for small cases and we find a mistake in a paper by Mutzel and Oettershagen. 1
|
|
|
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.
|
|
|
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...
|
|
|
Bounds of number of empty tetrahedra and other simplices
Reichel, Tomáš ; Valtr, Pavel (advisor) ; Balko, Martin (referee)
Let M be a finite set of random uniformly distributed points lying in a unit cube. Every four points from M make a tetrahedron and the tetrahedron can either contain some of the other points from M, or it can be empty. This diploma thesis brings an upper bound of the expected value of the number of empty tetrahedra with respect to size of M. We also show how precise is the upper bound in comparison to an approximation computed by a straightforward algorithm. In the last section we move from the three- dimensional case to a general dimension d. In the general d-dimensional case we have empty d-simplices in a d-hypercube instead of empty tetrahedra in a cube. Then we compare the upper bound for d-dimensional case to the results from another paper on this topic. 1
|
|
|
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
|
|
|
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 Ramsey-type theorem with a large Ramsey function. Last part is devoted to reptile simplices. A simplex S is k-reptile if it can be tiled by k simplices with disjoint interiors that are all mutually congruent and similar to S. We show that four-dimensional k-reptile simplices can exist only for k = m2 , where m ≥ 1...
|
guest ::
