
Using algebra in geometry
Paták, Pavel ; Růžička, Pavel (advisor) ; Šmíd, Dalibor (referee) ; Blagojevic, Pavle (referee)
Using algebra in geometry Pavel Paták Department: Department of Algebra Supervisor: Mgr. Pavel Růžička, Ph.D., Department of Algebra 1 Abstract In this thesis, we develop a technique that combines algebra, algebraic topology and combinatorial arguments and provides nonembeddability results. The novelty of our approach is to examine non embeddability arguments from a homological point of view. We illustrate its strength by proving two interesting theorems. The first one states that kdimensional skeleton of b 2k+2 k + k + 3 dimensional simplex does not embed into any 2kdimensional manifold M with Betti number βk(M; Z2) ≤ b. It is the first finite upper bound for Kühnel's conjecture of nonembeddability of simplices into manifolds. The second one is a very general topological Helly type theorem for sets in Rd : There exists a function h(b, d) such that the following holds. If F is a finite family of sets in Rd such that ˜βi ( G; Z2) ≤ b for any G F and every 0 ≤ i ≤ d/2 − 1, then F has Helly number at most h(b, d). If we are only interested whether the Helly numbers are bounded or not, the theorem subsumes a broad class of Helly types theorems for sets in Rd . Keywords: Homological Nonembeddability, Helly Type Theorem, Kühnel's conjecture of nonembeddability of ske leta of simplices into manifolds


The arity of NU polymorphisms
Draganov, Ondřej ; Barto, Libor (advisor) ; Růžička, Pavel (referee)
This paper deals with an arity of NU polymorphisms of relational structures. The goal is to simplify and clearly describe an already existing example of a relational structure, which has an NU polymorphism, but no NU polymorphisms of low arity in respect to arity of relations and to a number of elements in the relational structure. We explicitly describe mary relational structures with n elements, n ≥ 2, m ≥ 3, which have no NU polymorphisms of arity (m − 1)2n−2 , but have an NU polymorphism of arity (m − 1)2n−2 + 1, which is constructed in the paper, and binary relational structures with n elements, n ≥ 3, which have no NU polymorphisms of arity 22n−3 , but have an NU polymorphism of arity 22n−3 + 1.


Relational Approach to Universal Algebra
Opršal, Jakub ; Barto, Libor (advisor) ; Růžička, Pavel (referee) ; Mayr, Peter (referee)
Title: Relational Approach to Universal Algebra Author: Jakub Opršal Department: Department of Algebra Supervisor: doc. Libor Barto, Ph.D., Department of Algebra Abstract: We give some descriptions of certain algebraic properties using rela tions and relational structures. In the first part, we focus on Neumann's lattice of interpretability types of varieties. First, we prove a characterization of vari eties defined by linear identities, and we prove that some conditions cannot be characterized by linear identities. Next, we provide a partial result on Taylor's modularity conjecture, and we discuss several related problems. Namely, we show that the interpretability join of two idempotent varieties that are not congruence modular is not congruence modular either, and the analogue for idempotent va rieties with a cube term. In the second part, we give a relational description of higher commutator operators, which were introduced by Bulatov, in varieties with a Mal'cev term. Furthermore, we use this result to prove that for every algebra with a Mal'cev term there exists a largest clone containing the Mal'cev operation and having the same congruence lattice and the same higher commu tator operators as the original algebra, and to describe explicit (though infinite) set of identities describing supernilpotence...


Problém realizace von Neumannovsky regulárních okruhů
Mokriš, Samuel ; Růžička, Pavel (advisor) ; Žemlička, Jan (referee)
Title: The realization problem for von Neumann regular rings Author: Samuel Mokriš Department: Department of Algebra Supervisor of the master thesis: Mgr. Pavel Růžička, Ph.D., Department of Algebra Abstract: With every unital ring R, one can associate the abelian monoid V (R) of isomor phism classes of finitely generated projective right Rmodules. Said monoid is a conical monoid with orderunit. Moreover, for von Neumann regular rings, it satisfies the Riesz refinement property. In the thesis, we deal with the question, under what conditions an abelian conical re finement monoid with orderunit can be realized as V (R) for some unital von Neumann regular ring or algebra, with emphasis on countable monoids. Two generalizations of the construction of V (R) to the context of nonunital rings are presented and their interrelation is analyzed. To that end, necessary properties of rings with local units and modules over such rings are devel oped. Further, the construction of Leavitt path algebras over quivers is presented, as well as the construction of a monoid associated with a quiver that is isomorphic to V (R) of the Leavitt path algebra over the same quiver. These methods are then used to realize directed unions of finitely generated free abelian monoids as V (R) of algebras over any given field. A method...


Multivariate cryptography
Jančaříková, Irena ; Žemlička, Jan (advisor) ; Růžička, Pavel (referee)
This thesis deals with multivariate cryptography. It includes specifically a description of the MQ problem and the proof of it's NPcompletness. In the part of the MQ problem there is a description of a general pattern for the creation of the public part of asymetric cryptosystems based on the MQ problem. It this part the thesis describes the QMLE problem, which is important for the figure of the cryptosystem private key based on the MQ problem. Further, the thesis includes a description of the influence of the structure display, which appears in the QMLE problem, on time solution complexity of QMLE problem. The influence of time complexity has been detected by means of experimental measurement with programed algorithm. At the end of the thesis there is specified description of selected multivariety cryptosystems based on the MQ problem. Selected cryptosystems are provided with detailed description of encryption and decryption by means of selected cryptosystems and time estimations of these operations. The thesis includes estimations of memory requirements on saving of private and public key of the selected cryptosystems. Powered by TCPDF (www.tcpdf.org)


An algorithmic approach to resolutions in representation theory
Ivánek, Adam ; Šťovíček, Jan (advisor) ; Růžička, Pavel (referee)
In this thesis we describe an algorithm and implement a construction of a projective resolution and minimal projective resolution in the representation the ory of finitedimensional algebras. In this thesis finitedimensional algebras are KQ /I where KQ is a path algebra and I is an admissible ideal. To implement the algorithm we use the package QPA [9] for GAP [2]. We use the theory of Gröbners basis of KQmodules and the theory described in article Minimal Pro jective Resolutions written by Green, Solberg a Zacharia [5]. First step is find a direct sum such that i∈Tn fn∗ i KQ = i∈Tn−1 fn−1 i KQ ∩ i∈Tn−2 fn−2 i I. Next important step to construct the minimal projective resolution is separate nontri vial Klinear combinations in i∈Tn−1 fn−1 i I + i∈Tn fn i J from fn∗ i . The Modules of the minimal projective elements are i∈Tn (fn i KQ)/(fn i I). 1

 

Constraint satisfaction, graphs and algebras
Bulín, Jakub ; Barto, Libor (advisor) ; Růžička, Pavel (referee) ; Bulatov, Andrei (referee)
Constraint satisfaction, graphs and algebras Jakub Bulín Abstract This thesis consists of three papers in the area of algebraic approach to the constraint satisfaction problem. In the first paper, a joint work with Deli'c, Jackson and Niven, we study the reduction of fixed template CSPs to digraphs. We construct, for every relational structure A, a digraph D(A) such that CSP(A) and CSP(D(A)) are logspace equivalent and most rele vant properties carry over from A to D(A). As a consequence, the algebraic conjectures characterizing CSPs solvable in P, NL and L are equivalent to their restrictions to digraphs. In the second paper we prove that, given a core relational structure A of bounded width and B ⊆ A, it is decidable whether B is an absorbing subuniverse of the algebra of polymorphisms of A. As a byproduct, we show that Jónsson absorption coincides with the usual absorption in this case. In the third paper we establish, using modern algebraic tools (e.g. absorption theory and pointing operations), the CSP dichotomy conjecture for socalled special oriented trees and in particular prove that all tractable core special trees have bounded width. Keywords: constraint satisfaction problem, algebra of polymorphisms, absorbing subuniverse, bounded width, oriented tree.


Maximal Orders
Tlustá, Stanislava ; Příhoda, Pavel (advisor) ; Růžička, Pavel (referee)
Maximal Orders Stanislava Tlustá Abstract This thesis summarizes basic properties of lattices and orders over Dedekind domain in separable algebras. The concepts of reduced norm and reduced trace are introduced and applied to few examples of rational algebras. By that the maximal orders are found. The properties of maximal orders are stated and used to explore new types of ideals: normal ideals and Λideals. At the end of this thesis the isomorphisms of lattices are examined and the JordanZassenhaus theorem is proved. 1


Generalized injectivity and approximation
Sahinkaya, Serap ; Trlifaj, Jan (advisor) ; Jirásko, Josef (referee) ; Růžička, Pavel (referee)
Title: Generalized injectivity and approximations Author: Serap S¸ahinkaya Department:Algebra Faculty of Mathematics and Physics, Charles University Supervisor: Prof. RNDr. Jan Trlifaj, DSc, Faculty of Mathematics and Physics, Charles University Abstract: Injective modules form a basic class studied in contemporary module theory. One of their generalizations, inspired by tilting theory, is the notion of a cotilting module. While tilting modules behave well with respect to localization, we show that colocalization is the correct approach when comparing the struc ture of cotilting modules over commutative noetherian rings R with the structure of cotilting modules over their localizations Rm where m runs over the maximal spectrum of R. This is done in Chapter 2 of this Dissertation whose main results were published in the paper [33]. In Chapter 3, we investigate approximation properties of other classic generalizations of injective modules, the Ci and quasi injective modules, introduced by Harada et al. Suprisingly, we prove that these classes provide for approximations only in exceptional cases (when all Ci mod ules are injective, or pureinjective). The Dissertation ends with a set of open problems. Keywords: Commutative noetherian ring, (co)tilting module, (generalized) injec tive module. 1
