|
| |
|
| |
|
|
The combinatorics of pattern-avoiding matrices
Mikšaník, David ; Jelínek, Vít (advisor) ; Klazar, Martin (referee)
A permutation matrix P partially avoids a quasi-permutation matrix A (i.e., a 01- matrix such that each column and row of A contains at most one nonzero entry) if there is no submatrix P′ of P of the same size as A satisfying Ai,j ≤ P′ i,j for all possible indices i and j. Two quasi-permutation matrices A and B are partially Wilf-equivalent if, for every n ∈ N, the number of permutation matrices of order n partially avoiding A is the same as the number of permutation matrices of order n partially avoiding B. This generalizes the well-known concept of avoidance and Wilf equivalence of permutations. One of the central topics in this area is the classification of permutations of order k into Wilf equivalence classes. The complete classification is known for k = 1, 2, . . . , 7. In our thesis, we study the same problem for quasi-permutation matrices. Namely, we classify all 371 quasi-permutation matrices of size at most 4 × 4 into partial Wilf equivalence classes (two quasi-permutation matrices belong to the same class if and only if they are partially Wilf-equivalent). Along the way, we prove several general results showing how to construct from one or two quasi-permutation matrices more quasi-permutation matrices that are pairwise partially Wilf-equivalent. 1
|
|
|
Structural aspects of aesthetic visualinformation processing
Douchová, Veronika ; Nešetřil, Jaroslav (advisor) ; Klazar, Martin (referee) ; Vlček, Tomáš (referee)
Univerzita Karlova Filozofická fakulta Katedra logiky Obor: Logika Strukturální aspekty zpracování vizuální informace s estetickou složkou Structural aspects of aesthetic visual information processing Abstract Mgr. Veronika Douchová vedoucí (supervisor): prof. RNDr. Jaroslav Nešetřil, DrSc., 2022 Abstract In the thesis, we investigate and formulate a framework for analyzing certain aspects of aesthetics from a structural and mathematical perspective. We build on the results of neuroaesthetics-a (relatively new) field in neurol- ogy introduced by S. Zeki in 1990's-which links the process of seeing, and evaluating information with an aesthetic component, with the structure of the human brain. Several principles influencing aesthetic judgements were identified by neuroaesthetics and connected with the structure of the human brain, such as the notions of modularity, symmetry, harmony, or balance. We argue that these results provide an objective interpretative framework for an- alyzing certain aspects of visual information with an aesthetic component by means of mathematical methods. We apply these results to Birkhoff's aes- thetic measure, providing objective foundations for his theoretical methods, based on algebraic invariants for aesthetics. We follow up with a discussion of the theory of J. Nešetřil-which...
|
|
|
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 ; Klazar, Martin (advisor) ; Nešetřil, Jaroslav (referee)
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.
|
|
|
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
|
|
|
Specialni bezbodove prostory
Novák, Jan ; Pultr, Aleš (advisor) ; Klazar, Martin (referee)
1 This thesis concerns separation axioms in point-free topology. We introduce a notion of weak inclusion, which is a relation on a frame that is weaker than the relation ≤. Weak inclusions provide a uniform way to work with standard separation axioms such as subfitness, fitness, and regularity. Proofs using weak inclusions often bring new insight into the nature of the axioms. We focus on results related to the axiom of subfitness. We study a sublocale which is defined as the intersection of all the codense sublocales of a frame. We show that it need not be subfit. For spacial frames, it need not be spacial.
|
|
|
Additive combinatorics and number theory
Hančl, Jaroslav ; Klazar, Martin (advisor)
We present several results for growth functions of ideals of different com- binatorial structures. An ideal is a set downward closed under a containment relation, like the relation of subpartition for partitions, or the relation of induced subgraph for graphs etc. Its growth function (GF) counts elements of given size. For partition ideals we establish an asymptotics for GF of ideals that do not use parts from a finite set S and use this to construct ideal with highly oscillating GF. Then we present application characterising GF of particular partition ideals. We generalize ideals of ordered graphs to ordered uniform hypergraphs and show two dichotomies for their GF. The first result is a constant to linear jump for k-uniform hypergraphs. The second result establishes the polynomial to exponential jump for 3-uniform hypergraphs. That is, there are no ordered hypergraph ideals with GF strictly inside the constant-linear and polynomial- exponential range. We obtain in both dichotomies tight upper bounds. Finally, in a quite general setting we present several methods how to generate for various combinatorial structures pairs of sets defining two ideals with iden- tical GF. We call these pairs Wilf equivalent pairs and use the automorphism method and the replacement method to obtain such pairs. 1
|
guest ::
