|
|
Dissections of triangles and distances of groups
Szabados, Michal ; Drápal, Aleš (advisor) ; Klazar, Martin (referee)
Denote by gdist(p) the least number of cells that have to be changed to get a latin square from the table of addition modulo prime p. A conjecture of Drápal, Cavenagh and Wanless states that there exists c > 0 such that gdist(p) ≤ c log(p). In this work we prove the conjecture for c ≈ 7.21, and the proof is done by constructing a dissection of an equilateral triangle of side n into O(log(n)) equilateral triangles. We also show a proof of the lower bound c log(p) ≤ gdist(p) with improved constant c ≈ 2.73. At the end of the work we present computational data which suggest that gdist(p)/ log(p) ≈ 3.56 for large values of p.
|
|
|
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
|
|
|
Obecná enumerace číselných rozkladů
Hančl, Jaroslav ; Klazar, Martin (advisor) ; Jelínek, Vít (referee)
Název práce: Obecná enumerace číselných rozklad· Autor: Jaroslav Hančl Katedra: Katedra aplikované matematiky Vedoucí diplomové práce: doc. RNDr. Martin Klazar, Dr., KAM MFF UK Abstrakt: Předložená diplomová práce se zabývá asymptotikami počítacích funkcí ideál· číselných rozklad·. Jejím hlavním cílem je zjistit největší možný asympto- tický r·st počítací funkce rozkladového ideálu, která je nekonečněkrát rovna nule. Autor se na základě znalosti asymptotik vybraných rozkladových ideál· snaží po- mocí kombinatorických a základních analytických metod odvodit odhady hledané asymptotiky. Výsledkem je za prvé slabší horní odhad, za druhé poměrně silný dolní odhad a za třetí, pro speciální třídu rozkladových ideál· je nalezen největší asymptotický r·st. Klíčová slova: íselné rozklady, asymptotika rozklad·, rozkladové ideály, počítací funkce, kombinatorická enumerace. 1
|
|
| |
|
|
Freiman's theorem in additive combinatorics
Hančl, Jaroslav ; Nešetřil, Jaroslav (referee) ; Klazar, Martin (advisor)
In the presented summary work we study the inverse problem in additive number theory. More speci cally, we try to characterize sets A of positive integers if we know some information about their sumsets 2A = A + A. At the beginning we devote some time to nite sets with the property |2A| = 2|Aj| - 1, then we solve a generalized problem for such abelian groups G in whose order of all elements is bounded by a constant rand their subsets A satisfying j2Aj cjAj. At the end we present the famous Freiman theorem, which describes sets of positive integers A small in the sense |2A| - c|A|. We prove this theorem and give some corollaries and applications.
|
|
|
Discrete and Linear Structures in Enumeration
Teimoori Faal, Hossein ; Loebl, Martin (advisor) ; Klazar, Martin (referee) ; Kang, Mihyun (referee)
The central theme of this thesis is to nd the multiset version of the combinatorial identities arising from the cyclic decomposition of permutations of nite sets. The main contributions of author's work are as follows. In Chapter 1, we nd the appropriate multiset version of the Stirling cycle number. Then, using these new Stirling numbers, we give a new equivalent statement of the coin arrangements lemma which is an important trick in Sherman's proof of Feynman conjecture on two dimensional Ising model. We also present a new proof of the coin arrangements lemma. Finally, we show several relations of the coin arrangements lemma with various concepts in enumerative combinatorics. In Chapter 2, we rst give a new proof of the Witt identity which is an algebraic identity in the context of Lyndon words using the Bass' identity for zeta function of nite graphs. Then, we present a new proof of the Bass' identity by only slight modi cations to the approach that has been developed by Feynman and Sherman as the path method for combinatorial solution of two dimensional Ising problem. In Chapter 3, we give a multiset generalization of the well-known graph-theoretical interpretation of the determinant as a signed weighted sum over cycle covers. In Chapter 4, we nd a multiset generalization of the graph-theoretical...
|
|
| |
|
| |
|
| |
|
|
Non-negative linear operators and their use in econometric and statistic models
Horský, Richard ; Arlt, Josef (advisor) ; Vrabec, Michal (referee) ; Klazar, Martin (referee)
Non-negative operators, in special case non-negative matrices, are an interesting topics for many scientists and scientific teams from the beginning of the 20th century. It is not suprising because there are a lot of applications in different areas of science like economy, statistics, linear programming, computer science and others. We can give as the particular example the theory of the Markov chains in which we deal with non-negative matrices, so called transition matrices. They are of the special form and we called them stochastic matrices. Another example is given by the non-negative operator on spaces of infinite dimension which is employed in the theory of stochastic processes. It is the backward shift operator called the lag operator as well. The non-negativity in these examples is considered as the piecewise non-negativity. Another type of non-negativity is that in the sense of inner products. In the case of matrices we talk about positive-definite or positive-semidefinite matrices. A typical example is the covariance matrix of a random vector or symmetrization of any linear operator, for instance the symmetrization of the difference operator. The terms inverse problem or ill-posed problem have been gaining popularity in modern science since the middle of the last century. The subjects of the first publications in this area were related to quantum scattering theory, geophysics, astronomy and others. Thanks to powerful computers the chances for applications of the theory of inverse and ill-posed problems has extended in almost all fields of science which use mathematical methods. Ill-posed problems bear the feature of instability and there is the need of regularization if we want to get some reasonable solution. A typical example of the regularization is the differencing of stochastic process with the purpose to obtain a stationary process. Another concept of regularization used for solving e.g. integral equations with compact operators consists in application of regularization method as truncated singular value decomposition, Tichonov regularization method or Landweber iteration method. Mathematical tools employed in this work are those of the functional analysis. It is the area of mathematics in which distinct mathematical structures meet each other. They are structures built within different mathematical disciplines as mathematical analysis, topology, theory of sets, algebra (mainly linear algebra) and theory of measure (probability). The functional analysis framework enables us to obtain right formulations of definitions and problems providing the general view on the notions and problems of the theory of stochastic processes.
|
guest ::
