
Enumeration of polyomino fillings
Karpilovskij, Mark ; Jelínek, Vít (advisor) ; Klazar, Martin (referee)
We prove two new results about 01fillings of skew diagrams avoiding long increasing and decreasing chains. In the first half of the thesis, we show that for a large class of skew diagrams, there is a bijection between sparse fillings avoiding an increasing chain of fixed length and sparse fillings avoiding a decreas ing chain of the same length. In the second half, we extend a known inequality between the number of sparse 01fillings of skew diagrams avoiding an increasing chain of length 2 and a decreasing chain of length 2 to all 01fillings. 1


Hereditary classes of binary matrices
Kučera, Stanislav ; Jelínek, Vít (advisor) ; Klazar, Martin (referee)
Interval minors of binary matrices were introduced by Jacob Fox in the study of StanleyWilf limits. We study what can be implied from their relation to the theory of pattern avoidance of submatrices, which is a very popular area of discrete mathematics. We start by characterizing matrices avoiding small interval minors. We then consider classes of matrices closed under interval minors and we find classes of matrices that cannot be described by a finite number of forbidden interval minors. We also define and study a variant of a classical extremal Tur'an type question studied in the area of combinatorics of permutations and binary matrices and in combinatorial geometry. 1


Patternavoiding permutation classes
Opler, Michal ; Jelínek, Vít (advisor) ; Klazar, Martin (referee)
For a permutation π, the major index of π is the sum of all indices i such that πi > πi+1. In this thesis, we study the distribution of the major index over patternavoiding permutations of length n. We focus on the number Mm n (Π) of permutations of length n with major index m and avoiding the set of patterns Π. First, we are able to show that for a singleton set Π = {σ} other than some trivial cases, the values Mm n (Π) are monotonic in the sense that Mm n (Π) ≤ Mm n+1(Π). Our main result is a study of the asymptotic behaviour of Mm n (Π) as n goes to infinity. We prove that for every fixed m, Π and n large enough, Mm n (Π) is equal to a polynomial in n and moreover, we are able to determine the degrees of these polynomials for many sets of patterns. 1


Enumeration of compositions with forbidden patterns
Dodova, Borjana ; Klazar, Martin (advisor) ; Jelínek, Vít (referee)
Enumeration of pattern avoiding compositions of numbers Abstract The aim of this work was to find some new results for 3regular compositions, i.e., for those compositions which avoid the set of patterns {121, 212, 11}. Those compositions can be regarded as a generalization of Carlitz composition. Based on the generating function of compositions avoiding the set of patterns {121, 11} and {212, 11} we derive an upper bound for the coefficients of the power series of the generating function of 3regular compositions. Using the theory of finite automata we derive its lower bound. We develop this result further by defining 3block compositions. For the generating function of 3regular compositions we prove a recursive ralation. Besides that we also compute the generating function of compositions avoiding the set of patterns {312, 321} whose parts are in the set [d]. In the last section we prove that the generating function of Carlitz compositions is transcendental.


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˝osTurá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 progressionfree 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 = 2Aj  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  cA. 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 wellknown graphtheoretical interpretation of the determinant as a signed weighted sum over cycle covers. In Chapter 4, we nd a multiset generalization of the graphtheoretical...
