|
|
Roth's theorem on arithmetic progressions
Krkavec, Michal ; Klazar, Martin (advisor) ; Kráľ, Daniel (referee)
Title: Roth's theorem on arithmetic progressions Author: Michal Krkavec Department: Department of Applied Mathematics Supervisor: doc. RNDr. Martin Klazar, Dr., Department of Applied Mathematics Abstract: In the presented summary work we study sets of natural numbers not containing arithmetic progressions. The aim of this thesis is to provide an overview and comparison of both analytical and combinatorial proofs of Roth's theorem, which states that every set of positive upper asymptotic density contains arithme- tic progression of length three. We also focus on the Erd˝os-Turán conjecture and Szemerédi's theorem, which finally settled the conjecture for arithmetic progres- sions of arbitrary length k. In the end, we introduce the bounds for the number r3(n), which corresponds to the largest size of a subset A ⊆ [n], which contains no arithmetic progressions of length three. At the end we present two constructions of progression-free sets. Keywords: Additive number theory, Arithmetic progressions, Roth's theorem, Elkin's construction 1
|
|
|
Datové struktury pro setříděné ukládání dat
Bulánek, Jan ; Koucký, Michal (advisor) ; Kráľ, Daniel (referee)
In this work we study two variants of a bucketing game. This game is used for the lower bound proof of time complexity of item insertion into a sorted array, a data structure for the order maintenance problem. We show that these two variants of the bucketing game have the same time complexity up to a constant factor. Then we show that sorted arrays can use cache efficiently for certain operations. Finally, we present one implementation of the order maintenance data structure using the array of size n1+e.
|
|
|
Szemerédi Regularity Lemma a jeho aplikace v kombinatorice
Hladký, Jan ; Kráľ, Daniel (advisor) ; Dvořák, Zdeněk (referee)
In the thesis we provide a solution of the Loebl-Komlós-Sós Conjecture (1995) for dense graphs. We prove that for any q > 0 there exists a number n0 N such that for any n > n0 and k > qn the following holds. Let G be a graph of order n with at least n/2 vertices of degree at least k. Then any tree of order k+1 is a subgraph of G. This improves previous results by Zhao (2002), and Piguet and Stein (2007). A strengthened version of the above theorem together with a lower bound for the problem is discussed. As a corollary a tight bound on the Ramsey number of two trees is stated. The proof of the main theorem combines a Regularity-Lemma based embedding technique with the Stability Method of Simonovits. Results presented here are based on joint work with Diana Piguet.
|
|
|
Algebraické vlastnosti barevnosti grafů
Bulánek, Jan ; Jelínek, Vít (referee) ; Kráľ, Daniel (advisor)
We study algebraic tools for proving the existence of graph colorings and focus a classical method of Alon-Tarsi from this area. In particular, we prove Alon-Tarsi Theorem, provide examples of some known applications and give a new application to colorings of squares of cycles.
|
|
|
Varianty problému obarvení
Lidický, Bernard ; Kráľ, Daniel (referee) ; Fiala, Jiří (advisor)
The choice number is a graph parameter that generalizes the chromatic number. In this concept vertices are assigned lists of available colors. A graph is k-choosable if it can be colored whenever the lists are of size at least k. It is known that every planar graph without triangles is 4-choosable and there is an example of a non-3-choosable planar graph without triangles. In this work we study the choice number of planar graph without triangles and other short cycles.
|
|
|
Zakázané minory pro apexové třídy grafů
Klimošová, Tereza ; Dvořák, Zdeněk (referee) ; Kráľ, Daniel (advisor)
In the present work we search for the minimal forbidden minors (also called obstructions) for the class of apexes of partial 2-trees. Because this class is minor closed, by Robertson-Seymour's theorem it has a nite set of obstructions. The set of obstructions is one of the possible characterizations of every minor closed class. We analyze a structure of possible obstructions for the class of apexes of partial 2-trees and thanks to this knowledge, we can classify all the obstructions for the class of apexes of partial 2-trees except for some special type of them with pathwidth three. We use the knowledge of obstructions for related classes of graphs.
|
|
| |
|
|
Rozklady grafů
Škoda, Petr ; Fiala, Jiří (referee) ; Kráľ, Daniel (advisor)
The notion of submodular partition functions generalizes many of well-known tree decompositions of graphs. For fixed k, there are polynomialtime algorithms to determine whether a graph has tree-width, branch-width, etc. at most k. Contrary to these results, we show that there is no subexponential algorithm for determining whether the width of a given submodular partition function is at most two. In addition, we also develop another dual notion for submodular partition functions which is analogous to loose tangles for connectivity functions.
|
|
| |
|
|
Paramterized complexity in graph theory
Suchý, Ondřej ; Kráľ, Daniel (referee) ; Kratochvíl, Jan (advisor)
Seidel's switching of a set of vertices of a graph is an operation which deletes the edges leaving this set from the graph and adds those edges between the set and the rest of graph that weren't in the original graph. Other edges remain untouched by this operation. Parameterized complexity asks if the exponential part of algorithms for hard problems can be bounded by some function only of selected parameters, which we assume small. In this thesis, we study the complexity of a question if the given graph can be turned into a graph with some property P using Seidel's switching, from the parameterized point of view. First we give an overview of known results. Then we show fixed-parameter tractability of switching to a regular graph, a graph with bounded degree of vertices, bounded number of edges and a graph without a forbidden subgraph. We briefly introduce basic definitions and techniques of parameterized complexity.
|
guest ::
RSS feed.