International Seminar
Im "International Seminar" werden aktuelle Forschungsergebnisse von Mitarbeiter:innen und Gästen des Instituts für Algebra diskutiert. Zu beiden Vortragsreihen sind interessierte Studierende herzlich willkommen. Ansprechpartner: Prof. Dr. Arno Fehm
Fr, 25.10.2024 13:30 GER/09/U 
Valued Constraints over Infinite Domains Žaneta Semanišinová (TU Dresden) Valued constraint satisfaction problems (VCSPs) provide a framework for many optimization problems. A VCSP is parameterized by a valued structure (template), which consists of a domain and cost functions, each of them defined on finite tuples of elements from the domain. The input to the VCSP consists of a finite set of variables, a finite sum of cost functions applied to these variables, and a threshold u, and the task is to decide whether there exists an assignment to the variables so that the sum of the costs is at most u. VCSPs with finite templates are wellunderstood and exhibit a complexity dichotomy: each of them is in P or NPcomplete. However, many important optimization problems, such as mincorrelationclustering with partial information or the minimum feedback arc set problem cannot be modelled as VCSPs over a finite template. In this talk, we give an introduction to the theory of infinitedomain VCSPs. We then present a complexity classification of VCSPs of all valued structures over the domain Q that are preserved by all orderpreserving permutations. Finally, we sketch how resilience problems from database theory can be viewed as VCSPs and present some complexity classification results that this connection yields. This talk is based on joint work with M. Bodirsky, É. Bonnet and C. Lutz. 
Mo, 14.10.2024 13:00 GER/07/U 
Artin's primitive root conjecture: classically and over Fq[T] 
 Semester Break   
Fr, 12.07.2024 13:30 WIL C 133 
Approaching local group theory via localities Edoardo Salati (TU Dresden) In the classification of the finite simple groups, the GoreinsteinWalter Dichotomy Theorem implies that not too small finite simple groups either have an involution centralizer of a certain standard form, or are of socalled local characteristic 2. This was the main initial motivation for studying groups of local characteristic p. Building on the geometric approach used by Meierfrankenfeld, Stellmacher and Stroth, we look at how influent is the role of a finite group G over its plocal structure by replacing the group G with fusion systems and localities. This is carried out by focusing on the existing, fundamental result that nearly classifies the normalizers of nontrivial psubgroups of finite groups with a socalled large psubgroup. 
Fr, 05.07.2024 13:30 WIL C 133 
Embedding simply connected 2complexes in 3space Prof. Dr. Johannes Carmesin (TU Freiberg) We characterise the embeddability of simply connected 2dimensional simplicial complexes in 3space in a way analogous to Kuratowski’s characterisation of graph planarity, by excluded minors. This answers questions of Lovasz, Pardon and Wagner. 
Fr, 28.06.2024 13:30 WIL C 133 
Polymorphisms of Topological spaces Sebastian Meyer (TU Dresden) Polymorphisms are a generalization of automorphisms and endomorphisms. They are known to have a close link to the complexity of constraint satisfaction problems. We will give a selfcontained introduction and consider polymorphisms of groups and topological spaces with an application to polymorphisms of graphs and the HellNešetřilTheorem. 
Fr, 21.06.2024 13:30 WIL C 133 
Colloquium for the Master's thesis: On Abstract and Concrete Minions Lukas Juhrich (TU Dresden) For two relational structures A and B with a homomorphism A to B, the set Pol(A, B) of polymorphisms, i.e., homomorphisms A^k to B for arbitrary k>0, carries the structure of a minion. Moreover, if A and B have finite domain and signature, homomorphisms Pol(A, B) to Pol(A', B') respecting this structure give rise to efficient reductions PCSP(A',B') to PCSP(A, B) between the associated promise constraint satisfaction problems, a notion generalizing the classical CSP. Since it is unclear whether the complexity dichotomy of CSPs generalizes to the promise setting, the homomorphism order of polymorphism minions over finite structures is of interest. We investigate when an (abstract) minion – a kind of setvalued functor – is “finitely representable”, i.e. isomorphic to Pol(A, B) where the structures have finite domain, and use constructions known from topos theory to show that the homomorphism order of finitely representable minions is a distributive lattice, and even a biheyting algebra. 
Fr, 14.06.2024 13:30 WIL C 133 
Ultraproducts for multiplicative relations in integral domains Dr. Daniel Windisch (MPI Leipzig) Factorizations of elements of integral domains as products of irreducible elements do not have to be unique: This basic observation lies at the heart of algebraic number theory. We investigate ultraproducts of integral domains with respect to this aspect and show how they can be used to gain further insight to the questions currently asked in the study of nonunique factorizations. 
Fr, 07.06.2024 13:30 WIL C 133 
On clonoids, especially those of Boolean functions Dr. Erkko Lehtonen (Khalifa University) We give a brief introduction to (C1,C2)clonoids, sets of functions of several arguments that are closed under right composition with a clone C1 and under left composition with another clone C2. We mainly focus on clonoids of Boolean functions and present classification results of (C1,C2)clonoids, in the spirit of Post's classification of clones. Moreover, we propose refinements and strengthenings of Sparks's theorem on the cardinalities of clonoid lattices. 
Fr, 31.05.2024 13:30 WIL C 133 
Simplicity of the automorphism group of fields with operators Prof. Dr. Amador MartinPizarro (AlbertLudwigsUniversität Freiburg) In 1992 Lascar proved that the group of field automorphisms of the complex numbers which fix pointwise the algebraic closure of the rationals is simple, assuming the continuum hypothesis. His proof used strongly the topological features of the group of automorphisms of a countable structure, as a Polish group. In 1997 Lascar gave a different proof of the above, without assuming the continuum hypothesis. The new proof needed just the stability of the theory of the field of complex numbers (and particularly stationarity of types as a way to merge two elementary maps) as well as the fact that the field of complex numbers is saturated in its own cardinality. In a recent preprint with T. Blossier, Z. Chatzidakis and C. Hardouin, we have adapted a proof of Lascar to show that certain groups of automorphisms of various theories of fields with operators are simple. It particularly applies to the theory of difference closed fields, which is unstable (yet simple) and hence has possibly no models which are saturated in their uncountable cardinality. 
Fri 24.05.2024   Lecture free period (Pentecost)  
Fri 17.05.2024 13:30 WIL C 133 
Toroidal groups, generalized Jacobians and nontotally real number fields Alessandro Dioguardi Burgio (Università degli studi di Palermo) A toroidal group is a complex Lie group on which every holomorphic function is constant. Under some necessary assumptions, any toroidal group of complex dimension 2 and real rank 3 with extra multiplication is isogenous to a group arising from a nontotally real cubic number field. This correspondence is extended to higher dimension, writing down the relations between the periods defining a toroidal group (such that the complex dimension and the real rank differ by one) and the minimal polynomial of a primitive element of the nontotally real number field. Finally, I introduce the (birationally) isomorphism between a toroidal group and the generalized Jacobian of an elliptic (or hyperelliptic) curve and I give an explicit description of the mtorsion of a toroidal group (arising from a nontotally real number field) in this geometric correspondence. 
Fri 10.05.2024   
Fri 03.05.2024 13:30 WIL C 133 
A localglobal problem for divisibility in algebraic groups Jessica Alessandrì (Università degli Studi dell'Aquila) Localglobal principles have been widely studied during the last century. In this talk, we will present one of them, the socalled LocalGlobal Divisibility Problem for commutative algebraic groups. It was first stated in 2001 by Dvornicich and Zannier as a modified version of the Hasse principle for quadratic forms. We will also see some results, in particular for algebraic tori: a generalization of the GrunwaldWang Theorem to any algebraic tori with bounded dimension and a counterexample for the localglobal divisibility by any power of an odd prime. This is based on a joint work with Rocco Chirivì and Laura Paladino. 
Fri 26.04.2024   
Thu, 12.04.2024 13:30 WIL C 133 
Core field theories and modeltheoretic tilting Margarete Ketelsen (Universität Münster) The tilting construction (as introduced by Fontaine) provides a way to transfer theorems between the worlds of characteristic zero and positive characteristic. Classically, this can be done for perfectoid fields: for each perfectoid field (K,v) of characteristic zero, we can obtain its tilt  a perfectoid field of positive characteristic. A perfectoid field is a complete nondiscretely valued field of rank 1 that satisfies some perfectness condition. Here, rank 1 means that the value group is a subgroup of the reals. In my talk, I will tell you how the tilting construction can be extended to certain valued fields of higher rank, so the value group is not necessarily a subgroup of the reals anymore. This modeltheoretic tilt is only defined up to elementary equivalence, so we tilt the theories rather than the fields themselves. One main strategy to understand a valuation of higher rank is to decompose it into simpler parts which can then be understood separately. One of these simpler parts, a certain rank1valuation of mixed characteristic, is called the core field. In ongoing joint work with Sylvy Anscombe and Franziska Jahnke, we prove that for ℵ_1saturated (K,v), the theory of the core field of (K,v) only depends on the theory of (K,v). This work is crucial for the welldefinedness of the modeltheoretic tilt. 
 Semester Break   
Fri 02.02.2024, 13:30 WIL C133 
Firstorder characterisations of rings Aaron Vollprecht (Institut für Algebra) Most of the rings we work with are given in a way easy to describe and easy to distinguish with algebraic methods such as finite or polynomial rings, the integers or rings of power series (e.g. the padic integers). However, distinguishing rings by firstorder sentences in ring language is hopeless since the LöwenheimSkolem theorem allows to build arbitrary big rings satisfying the same statements, even if we restrict ourselves to commutative unitary rings. A successful approach to overcome this problem was the work of Aschenbrenner, Khélif, Naziazeno and Scanlon (AKNS) that led to an axiomatisation of every finitely generated unitary commutative ring in the class of finitely generated structures in ring language using biinterpretation arguments. Building on this result, Dittmann and Pop could prove that every finitely generated field can be axiomatised within the class of all these fields. We will present key steps of AKNS and sketch a possible generalisation for finitely generated algebras over the padic integers. 
Fri 26.01.2024   
Fri 12.01.2024, 13:30, WIL/C133 
The Collatz map in (Z/pZ)[x] 
Fr, 05.01.2024, 13:30, WIL/C133 
Characterising fields by Galoistheoretic data Philip Dittmann (Institut für Algebra) I will discuss various questions around characterisations of fields by their absolute Galois group, i.e. the Galois group of their separable closure. The first nontrivial result here is the 1927 result of Artin and Schreier characterising those fields whose absolute Galois group is Z/2Z, which is important in the theory of ordered fields. I will also discuss results on padic fields, as well as recent work by myself on how to obtain a satisfactory result for local fields of positive characteristic. Nothing beyond basic Galois theory will be assumed. 
Fr, 17.11.2023, 13:30, WIL/C133 
Higher Commutators and Higher Dimensional Congruences 
Fr, 10.11.2023, 13:30, WIL/C133 
Primitive Elements of Finite Fields Outside of Affine Hyperplanes Philipp Grzywaczyk (Inst. f. Algebra) Primitive Elements in finite fields are of paramount importance for many applications. Finding them deterministically needs lots of computation time. We study smaller subsets of finite fields, in this case, we remove a fixed amount of affine hyperplanes, and want to determine for which parameters this smaller subsets necessarily contain at least one primitive element. We use Vinogradov’s formula, which reduces the problem of finding primitive elements in a subset to the estimation of a character sum over this subset. In this talk, we will present a new estimate for such character sums, and use this estimate to prove new existence results for primitive elements. We will prove existence results for primitive elements outside of affine hyperplanes as well as for sparse primitive elements. 
Fr, 03.11.2023, 13:30, WIL/C133 
Relations with a remarkable property: 
Fr, 20.10.2023, 13:30, WIL/C133 
Conjunctive Table Algebras: Axiomatization Conjunctive table algebras are a databasetheoretic counterpart of cylindric set algebras, where conjunctive queries, with inference based on graph homomorphism, play the role of firstorder formulas. The motivation has been presented in 
Mo 16.10.2023, 13:30, WIL/C133 
Oligomorphic groups, their interactions and generalisations 
 Semester Break   
Fr, 18.08.2023, 13:30, WIL/C115 
Pseudoloop lemmas 
Fr, 16.06.2023, 13:30, WIL/A120/H 
The Pythagoras number of function fields 
Thur, 08.06.2023, 13:30, WIL/C129/H 
Axiomatizing valued difference fields: beyond surjectivity 
Fr 26.05.2023, 13:30, WIL/A120 
Breaking the Barrier: A Computation of the Ninth Dedekind Number 
 Semester Break   
Fr 27.01.2023, 13:30, WIL/C133  Conjunctive Table Algebras Jens Kötters (Institut für Algebra) Conjunctive table algebras are introduced and axiomatically characterized. A conjunctive table algebra is a variant of SPJR algebra (a weaker form of relational algebra), which corresponds to conjunctive queries with equality. The table operations relate to logical operations (e.g. column deletion corresponds to existential quantification). This enables a connection between database theory and algebraic logic, particularly cylindric algebras. A comparison shows which cylindric algebra axioms hold in conjunctive table algebras, which ones are modified, and which ones hold in addition. 
Fr 09.12.2022, 13:30, WIL/C133  Submaximal clones on a threeelement set (modulo minorequivalence) Albert Vucaj (Technische Universität Wien) In 1959 Janov and Mucnik proved that there exists a continuum of clones over a kelement set for k > 2. The goal to achieve a classification à la Post for clones on a threeelement set seemed to falter. Subsequent research in universal algebra therefore focused on understanding particular aspects of clone lattices on finite domains. Remarkable results in this direction are the description of maximal and minimal clones. One might still hope to classify all operation clones on finite domains up to some equivalence relation so that equivalent clones share many of the properties that are of interest in universal algebra. In a recent turn of events, a weakening of the notion of clone homomorphism, known as minorpreserving map, turned out to play an important role in the complexity classification for Constraint Satisfaction Problems. In this talk we focus on the poset that arises by considering clones over a threeelement set with the following order: we set C ≤ D if there exist a minorpreserving map from C to D. In particular, we show that the aforementioned poset has only three submaximal elements. Joint work with Dmitriy Zhuk. 
Fr 02.12.2022, 13:30, WIL/C133 
Definable subsets of the field of real rational functions 
Thur, 01.09.2022, 13:15, GER/09/U 
Quasifinite axiomatizability in the class of finitely generated rings Margarete Ketelsen (master thesis colloquium, supervisor: A. Fehm) A finitely generated ring, i.e., finitely generated as an algebra over ℤ or 𝔽_q, is called quasifinitely axiomatizable (QFA) if within the class of finitely generated rings, it can be axiomatized by a single firstorder sentence. The goal of this talk is to give a sketch of the proof by Aschenbrenner, Khélif, Naziazeno, and Scanlon that every finitely generated integral domain is QFA. It is proven by showing as an intermediate step that every finitely generated integral domain is biinterpretable with ℕ. 
 Semester Break   
Mi 24.08.2022, 13:15, GER/09/U 
Explicit Class Field Theory for Global Function Fields Edwin Weinholtz (master thesis colloquium, supervisor: A. Fehm) Roughly speaking class field theory seeks to classify abelian extensions of a given field by its arithmetical properties. Though this problem is solved for number fields and global function fields, one fails to provide an explicit representation of these abelian extensions in the number field case in general. That is for an arbitrary number field K there is no universal machinery to find a sequence of polynomials whose roots generate the maximal abelian extension of K. However, the American number theorist David Hayes showed that this works for any global function field by a construction similar to the case of imaginary quadratic number fields. This talk provides a brief introduction to the class field theory for global function fields and explains how one obtains this explicit description. 
Fr 1.07.2022 13:30 WIL/C133/H 
A PolynomialTime Algorithm to Check QuantifierElimination in Finite Digraphs 
Fr 22.04.2022 13:30 WIL/C133/H  Introduction to Block Theory Patrick Serwene (Institut für Algebra) We introduce some aspects of Modular Representation Theory of finite groups. We will show how fusion systems arise in the context of blocks, discuss conjectural connections and how those systems tie up with other aspects of the theory. 
Fr. 8.4.2022, 13:30 zoomlink Code: f!Qhut?1 
Komplexität von TVPIErweiterungen temporaler Constraintsprachen 
 Semester Break   
Fr. 25.3.2022, 13:30 
Constraint Satisfaction Probleme mit Parabolischen Relationen 
Fr., 28.01.2022 13:30 
Graph Databases  An Analysis of Joining Technology in Automotive Engineering Martin Voigt (Master colloquium, supervisor: Prof. Schmidt) Joining technology deals with processes for joining components and assemblies to form products. Such processes occur at various points in the manufacturing process of a vehicle. Due to the complexity of the joining technology, the joining components, the assemblies and the vehicle projects, a method is needed to be able to structure and analyze the corresponding data. In this master thesis, which was carried out at Volkswagen AG, a graph database is built to model information about individual joining components in the vehicle and their joining technology as a graph. The data is analyzed using database queries. Furthermore mathematical algorithms are applied to determine central nodes and communities in the graph. The results are used to compare vehicle projects with each other. 
Fr. 7.1.2022, 13:30, zoomlink Code: f!Qhut?1 
A mystery group action (The existence of a cyclic sieving phenomenon for permutations via a bound on the number of border strip tableaux and invariant theory) 
Complexity of Constraint Satisfaction Problems for Unions of Theories 

CSP dichotomy for ωcategorical monadically stable structures 

Fr. 12.11.2021, 13:30, WIL/C133 
Deciding the Joint Embedding Property for Separable Permutation Classes 
Fr. 5.11.2021, 13:30, WIL/C133 
Partial groups: a few categorical properties 
Fr. 22.10.2021, 13:30, WIL/C133 
Selfdual clones collapsed 
Fr. 22.10.2021, 13:30, 
On hardness of deciding the JEP and the AP for universal sentences. Jakub Rydval (Inst. f. Algebra) The finite models of a universal sentence $\Phi$ in a finite relational signature form the age of a structure if and only if $\Phi$ has the \emph{joint embedding property}. They form the age of a homogeneous structure if and only if $\Phi$ has the \emph{amalgamation property}. We prove that the computational problem whether a given universal sentence $\Phi$ has the joint embedding property is undecidable even if $\Phi$ is additionally Horn and the signature is binary. Our proof uses a particular reduction from the universality problem for contextfree grammars that can also be adapted to the analogous problem for the amalgamation property. However, the adaptation requires us to restrict the input to regular grammars only, which leads to PSPACEhardness instead of undecidability. This talk presents the above mentioned reductions as well as some other hardness results for the amalgamation property whose decidability remains open. Jakub Rydval 
Fr. 15.10.2021, 13:30 
Supernilpotent loops Žaneta Semanišinová (Inst. f. Algebra) Commutator theory is a part of universal algebra, which generalizes grouptheoretic definitions such as commutator of two subgroups or nilpotence to arbitrary algebras. Generalizing the definition of the binary commutator, it is possible to define commutators of higher arity and a notion of supernilpotence. Loops are algebras that naturally generalize groups dropping associativity from the axioms. Therefore it is natural to ask what do the mentioned notions yield in loops. Building on three equivalent definitions of supernilpotence due to Aichinger and Mudrinski, Bulatov and Opršal, we derive identities that occur in 1, 2 and 3supernilpotent loops and prove that a ksupernilpotent loop has a knilpotent multiplication group. Moreover, we present results of algorithmic testing of supernilpotence in loops of small orders. 
 Semester Break   
Th., 30.9.2021, 10:00 
Die algebraische Theorie des Measurement Celina Richter (Masterabeitskolloquium, Betreuer: Prof. St. Schmidt) 
Fr. 27.8.2021, 13:30 zoomlink Code: f!Qhut?1 
Submodular piecewise linear functions 
Fr. 23.7.2021, 13:30 zoomlink Code: f!Qhut?1 
Definability in slim pseudoalgebraically closed fields Gavin Elijah Jergensen (Master thesis talk) This talk focuses on the question “in which algebraic extensions of the rational numbers can one define the rational numbers or the integers?” To answer this question, we consider the notion of “slimness,” which describes whether the model theoretic and field theoretic definitions of relative algebraic closure in a particular field coincide, and we investigate pseudoalgebraically closed (PAC) fields – a class of fields related to pseudofinite fields whose model theory is well understood. Along the way, we provide a general classification of PAC fields by slimness and examine definability of subfields in slim PAC fields. The talk culminates with our main result: in almost all algebraic extensions of the rational numbers, one cannot define any proper subfield (including the rational numbers). 
Fr. 16.7.2021, 13:30 zoomlink Code: f!Qhut?1 
Computational problems in Hahn fields Victor Lisinski (U Oxford) For an ordered abelian group G, the Hahn field F_p((t^G)) over the finite field F_p arises naturally as a maximal extension of F_p(t). If G is the integers, this is the field of formal Laurent series over F_p and there is a recursion procedure for approximating elements algebraic over F_p(t). However, if G contains bounded increasing sequences, this approximation method takes the shape of transfinite recursion and some approximations become inaccessible to statements in firstorder logic. Recent results by Kedlaya, generalising work by Christol, shows that there is an alternative way to look at algebraic elements in Hahn fields in terms of deterministic finite automata. In this talk, we will see how Kedlaya's approach can be used to obtain new decidability results for Hahn fields, building on work by Kuhlmann. We will also see how the transfinite approximation method reveals a condition on algebraicity for generalised power series in terms of the order type of the support. 
Mo. 12.7.2021, 13:30 zoomlink Code: f!Qhut?1 
Exotic and blockexotic fusion systems 
Fr. 9.7.2021, 13:30 zoomlink Code: f!Qhut?1 
From Music to Mathematics and backwards: introducing algebra, topology and category theory into computational musicology 
Fr. 11.6.2021, 13:30 zoomlink Code: f!Qhut?1 
Crossmodal activation of primary visual cortex in response to tonal dissonance within a social cognition task 
Fr. 4.6.2021, 13:30 zoomlink Code: f!Qhut?1 
Hochschild lattices and shuffle lattices Henri Mühle (Institut für Algebra) We consider two combinatorially defined lattices: the Hochschild lattice (defined as the componentwise order on certain integer tuples) and the shuffle lattice (defined by some subword order on shuffles of words). These lattices have remarkable properties: the Hochschild lattice is semidistributive and the shuffle lattice is supersolvable. We show that a particular instance of the shuffle lattice arises (surprisingly) as the socalled core label order of the Hochschild lattice. The core label order of a semidistributive lattice is a certain "reordering" of the lattice elements. We strengthen this connection by exhibiting certain enumerative coincidences between these two lattices. If time permits, we compare this situation to the analogous connection between the Tamari lattice and the lattice of noncrossing partitions. 
Fr. 21.5.2021, 13:30 zoomlink Code: f!Qhut?1 
Extremal valued fields Piotr Szewczyk (University of Szczecin) Valued fields for which the image of valuation ring under every polynomial in several variables contains an element of maximum value are called extremal. In this talk we introduce a partial characterization of those fields mainly by use of an AxKochenErshov principle, together with examples why this partial characterization cannot be easily extended. 
Fr. 7.5.2021, 13:30 zoomlink Code: f!Qhut?1 
Digraphs modulo primitive positive constructability Florian Starke (Inst. Algebra) 
Fr. 23.4.2021, 13:30 
Commutative Polymorphisms of Core Triads Michael Wernthaler (defence of Bachelor Thesis, supervisor: Prof. M. Bodirsky) It has been known for a while that for a given finite digraph H the complexity of the constraint satisfaction problem for H only depends on the set of polymorphisms of H. From recent results it follows that the Hcolouring problem is in P if H has a socalled (4ary) Siggers polymorphism, and is NPhard otherwise. In this thesis, we focus on the case where H is a triad, i.e., an orientation of a tree which has a single vertex of degree 3 and otherwise only vertices of degree 2 and 1. We describe an algorithm with various optimisations that checks the existence of Siggers polymorphisms for triads up to a certain number of vertices. 
Fr. 9.4.2021, 13:30, 
The Foundation of Pattern Structures and their Applications 
 Semester Break   
Friday, 28.8.2020, 
Preserving Constraints for Existential Rules Agnes Reuschel (Kolloquium zur Masterarbeit, Betreuer: ...) Query answering is a prominent task for relational databases, in particular the corresponding decision problem of boolean conjunctive queries. This problem becomes undecidable if we consider a database together with a set of existential rules, which can be understood as an extension of datalog rules with existential variables in the head. In this talk we introduce the notion of incidental rules, which can be added to sets of existential rules without changing the answers to queries. We present fundamental properties and introduce an algorithm for detecting some incidental rules. 
Wednesday, 22.7.2020, 10:00, WIL/A317  Nichtkreuzende Partitionen und Einparkfunktionen Rico Mattukat (Kolloquium zur Masterarbeit, Betreuer: JunProf. M. Schneider) Für die Verbände der nichtkreuzenden Partitionen auf n+1 Elementen ist eine Bijektion zwischen deren maximalen Ketten und den Einparkfunktionen der Länge n bekannt. In dieser Arbeit werden Teilordnungen der nichtkreuzenden Partitionen auf n+1 Elementen untersucht, welche durch Einparkfunktionen erzeugt werden, welche ein bestimmtes Element k nicht enthalten. Zum einen wird gezeigt, dass diese Teilverbände die Eigenschaft der Überauflösbarkeit mit den Verbänden der nichtkreuzenden Partitionen teilen. Zum anderen wird eine Formel für die Möbiusfunktion vom kleinsten bis zum größten Element dieser Verbände angegeben. 
Wednesday, 17.6.2020 9:30, online 
Applying Farkas' lemma to valued constraint satisfaction problems. Caterina Viola (PhDdefense, supervisor: Prof. M. Bodirsky) 
Monday, 10.2.2020 13:30, WIL/C129 
Applying Farkas' lemma to valued constraint satisfaction problems. Caterina Viola Valued constraint satisfaction problems (VCSPs) are a class of computational optimisation problems. Given a set D, and a set of cost functions Gamma with domain D, the input of the VCSP for Gamma consists of an objective function, i.e., a sum of finitely many cost functions from Gamma, applied to finitely many variables, and a rational threshold u; the task is to decide whether there exists an assignment of values from D to the variables such that the corresponding cost of the objective function is at most u. 
Friday, 31.1.2020 13:30, WIL/C129 
Proper Jordan schemes exist Sven Reichard (TU Dresden) Association schemes were introduced in the 1930's by Bose et al in the context of the design of statistical experiments. They relate systems of binary relations to algebras of matrices. There have been several generalizations, such as coherent configurations (Higman, WeisfeilerLeman, 196870). If we want to generalize the concept of association schemes while considering only symmetric relations we can replace the matrix product by the Jordan product $A*B=\frac 12 (AB + BA)$, which is symmetric but not associative. This leads to the concept of Jordan schemes, first considered by Shah (1959). Given an association scheme $W$ one can always obtain a Jordan scheme $W'$ by symmetrization. It has been an open question (Cameron 2002, Bailey 2004) whether all Jordan schemes arise in this way, or if there are "proper" Jordan schemes with their own independent theory. Equivalently we can ask if symmetric WeisfeilerLeman stabilization gives the same as ordinary WL followed by symmetrization. We answer these questions by providing two constructions for infinite families of proper Jordan schemes. This is joint work with M. Klin and M. Muzychuk. 
Friday, 24.1.2020 13:30, WIL/C129 
Solving equation systems in omegacategorical algebras Thomas QuinnGregson We study the computational complexity of deciding whether a given set of term equalities and inequalities has a solution in an omegacategorical algebra A. There are omegacategorical groups where this problem is undecidable. We show that if A is an omegacategorical semilattice or an abelian group, then the problem is in P or NPhard. The hard cases are precisely those where Pol(A,\neq) has a uniformly continuous minorpreserving map to the clone of projections on a twoelement set. The results provide information about algebras A such that Pol(A,\neq) does not satisfy this condition, and they are of independent interest in universal algebra. In our proofs we rely on the BartoPinsker theorem about the existence of pseudoSiggers polymorphisms. To the best of our knowledge, this is the first time that the pseudoSiggers identity has been used to prove a complexity dichotomy. 
Friday, 10.1.2020 13:30, WIL/C129 
Posetvalued functions and residuated maps Eszter Horvath (U Szeged) We analyze cuts of posetvalued functions relating them to residuated mappings. Dealing with the latticevalued case we prove that a function μ: X → L induces a residuated map f: L → P(X) whose values are the cuts of μ and we describe the corresponding residual. Conversely, it turns out that every residuated map f from L to the power set of X determines a lattice valued function μ : X → L whose cuts coincide with the values of f. For general posetvalued functions, we give conditions under which the map sending an element of a poset to the corresponding cut is quasiresiduated, and then conditions under which it is also residuated. We prove that without additional conditions, the map analogue to the residual is a partial function hence we get particular weakly residuated maps which, on the power set of the domain, generate centralized systems instead of closures. We show that the main properties of residuated maps are preserved in this generalized case. We apply these results to the canonical representation of posetvalued and latticevalued functions, using the corresponding closures and centralized systems. 
Friday, 13.12.2019 13:30, WIL/C129 
Lattices of idempotent theories Anvar Nurakunov (Akad. d. Wiss, Bishkek, Kirgisien) Abstract 
Friday, 6.12.2019 13:30, WIL/C129 
Constraint Satisfaction Problems in Monadic SecondOrder Logic Johannes Brauer (Kolloquium zur Masterarbeit, Betreuer: Prof. M. Bodirsky) 
Friday, 29.11.2019 13:15, WIL/C129 
Counting points on algebraic varieties over the rational numbers Philip Dittmann (Inst. f. Algebra) For both conceptual and practical reasons it is useful to have estimates on the number of points of algebraic varieties over Q, usually phrased in terms of asymptotics as the height of points increases. I will present a new such estimate obtained in joint work with Wouter Castryck, Raf Cluckers and Kien Huu Nguyen, improving a host of previous results. I will also present some applications of this result. 
Friday, 22.11.2019 13:15, WIL/C129 
Problems and some positive solutions about bounds of nonpsoluble length in finite groups 
Friday, 15.11.2019 13:15, WIL/C129 
Parabolic Cataland  Origins Henri Mühle (Inst. f. Algebra, TU Dresden) We tell the story of the discovery of Parabolic Cataland. The stepping stone in this process is the realization that several Catalan families, as well as the Catalan numbers themselves, are intrinsically related to the symmetric group. Analyzing this connection from the point of view of Coxeter groups made it clear that analogues of Catalan families and Catalan numbers can be defined for every finite Cartan type. Thus, Cataland was found. Most recently, an expansion of Catalandcorresponding to parabolic quotients of finite Coxeter groupswas theorized. We present these constructions, and support them by concrete combinatorial realizations in the symmetric group case. This talk is based on joint work with Cesar Ceballos, Wenjie Fang and Nathan Williams. 
Friday, 8.11.2019 13:15, WIL/C129 
On the lattice of congruence lattices Danica JakubikovaStudenovska (U Košice) For a given finite set A, let E be the system of all congruence lattices of all algebras with the base set A. Then E is a lattice with respect to inclusion. We describe atoms and coatoms in E. Also, meet and join irreducible elements of E are dealt with. 
Friday, 25.10.2019 13:15, WIL/C129 
Comeager conjugacy classes in automorphism groups of linearly ordered structures Aleksandra Kwiatkowska (U Münster) 
 Semester Break   
Friday,20.9.2019 13:15, WIL/C129 
Quasi Jonsson Operations in Highly Transitive Closed Clones Sergej Scheck (Kolloquium zur Masterarbeit, Betreuer: Prof. Manujel Bodirsky) Jonsson terms play an important role in the study of varieties and of constraint satisfaction problems on finite sets. For structures with infinite base sets the idempotency of polymorphisms is a very strong assumption. A generalization of the concept of Jonsson terms that might be useful in the study of infinite structures are quasi Jonsson terms where the idempotency assumption is relaxed. Kazda, Kozik, McKenzie, and Moore (2015) proved that a variety has Jonsson terms if and only if it has directed Jonsson terms. We will show that also locally closed clones on countable sets that contain all permutations have quasi Jonsson operations if and only if they have quasi directed Johnsson operations. It also turns out that if a structure with a finite signature is preserved by all permutations and has quasi Jonsson polymorphisms, it also has a QNU polymorphism. 
Friday,6.9.2019 13:15, WIL/C129 
Constraint Satisfaction Probleme in der Steuererklärung Hanna Möller (Kolloquium zur Masterarbeit, Betreuer: Prof. Manujel Bodirsky) Am Anwendungsbeispiel des deutschen Steuerformulars wird die Komplexität von Constraint Satisfaction Problemen untersucht. Dabei wird insbesondere das von J.C. Lagarias analysierte "TwoVariablesperInequality" Problem (TVPI) betrachtet, welches IntegerProgramming auf zwei Variablen pro Constraint beschränkt. Es wird gezeigt, dass dieses Problem über der unendlichen Grundmenge der ganzen Zahlen NPvollständig ist, selbst wenn Kreisfreiheit des ConstraintGraphen gefordert wird. Beschränkt man sich allerdings auf eine endliche Grundmenge, so lassen sich TVPIs in polynomieller Zeit lösen. Im Steuerformular kommen für die Eingabe nur endlich viele Werte in Frage. Allerdings sind dort auch Multiplikationen von Variablen erlaubt. In meiner MasterArbeit beschäftige ich mich auch damit, wie man mit diesen NichtLinearitäten umgehen kann. 
Friday,12.7.2019 
New Topological Variants of Birkhoff’s Theorem II Manuel Bodirsky 
Friday, 5.7.2019, 13:15, WIL/C129  New Topological Variants of Birkhoff’s Theorem Manuel Bodirsky 
Friday, 28.6.2019, 13:15, WIL/C129  Parabolic Cataland  A TypeA Story Henri Mühle In this talk we embark on a journey through Parabolic Cataland. We first get to know the various families inhabiting the currently explored part of Parabolic Cataland and study their interactions. We then introduce certain natural orders for each of these families and describe how they are related. We then use the infrastructure of Parabolic Cataland to prove a connection between the graded dimensions of a certain Hopf algebra and the number of certain lattice walks in the quarter plane, as well as recover a famous bijection on Dyck paths that combinatorially explains the symmetry of the bigraded Hilbert series of a certain module of diagonal harmonics. In parts, this is joint work with Cesar Ceballos, Wenjie Fang and Nathan Williams 
Monday, 24.6.2019, 15:00, WIL/C129  Convergence of dynamical systems and unique ergodicity Felix Pogorzelski (U Leipzig) 
Monday, 17.6.2019, 13:30, WIL/C129 
Reading group on PCP theorem: Alphabet reduction 
Friday, 7.6.2019, 13:15, WIL/C129  A Fraïssé theorem for IBhomogeneous structures Andres Aranda An Lstructure M is IBhomogeneous if every isomorphism between finite substructures of M extends to a bimorphism (a bijective endomorphism) of M. I will present a version of Fraïssé's theorem relating the finite Lstructures that embed into M, a family of monomorphisms between finite substructures, and the existence of an IBhomogeneous limit. 
Friday, 24.5.2019, 13:15, WIL/C129 
Spectral Methods on Group Rings in a NonCommutative Situation 
17.05.2019 (Fr), 13:15, WIL C 129  A sampling algorithm for valued constraint satisfaction problems Caterina Viola 
Friday, 3.5.2019, 13:15, WIL/C129  Zählspektren von Strukturen mit polynomiell vielen Orbits von nelementigen Teilmengen Julia Grabinsky (diploma defence, supervisor: Prof. Manuel Bodirsky) 
Friday, 12.4.2019, 13:15, WIL/C129 
Isogenybased PostQuantum Cryptography 
Friday, 5.4.2019, 13:15, WIL/C129 
Varieties of PBZ*lattices 
 Semester Break   
Wednesday, 13.3.2019, 13:15, WIL C 115  mutypes and their stabilizers in algebraically closed valued fields Jinhe Ye (University of Notre Dame) In [2], it was proven that to any unbounded curve C ⊆ G in an ominimal theory, where G is a definable group, one can associate a definable, onedimensional subgroup of G. In the language of [1], it is proven that the above group is the μstabilizer of the branch of the curve at infinity. Furthermore, the notion of μstabilizers can be stated in a general context of topological groups. In this talk, we will investigate this problem in the context of linear algebraic groups and give some structral descrptions of the μstabilizers. References: [1] Ya’acov Peterzil and Sergei Starchenko. Topological groups, μtypes and their stabilizers. Journal of the European Mathematical Society, 19(10):2965–2995, 2017. [2] Ya’acov Peterzil and Charles Steinhorn. Definable compactness and definable subgroups of ominimal groups. Journal of the London Mathematical Society, 59(3):769–786, 1999. 
Friday, 15.2.2019, 10:30, WIL/C133 
CSP dichotomy for finite coverings of unary structures 
Friday, 1.2.2019, 13:15, WIL/C133 
Stable Fields 
Friday, 25.1.2019, 13:15, WIL/C133  Cover Problems, Dimensions and the Tensor Product of Complete Lattices Christian Jäkel This talk will treat different dimensional concepts of complete (ortho)lattices and their tensor products. The determination of these dimensions can be translated to certain set cover problems. This yields a sufficient condition for the multiplicativity of various lattice dimensions with respect to the tensor product of complete (ortho)lattices. 
Friday, 18.1.2019, 13:15, WIL/C133 
Lattices with many sublattices 
Friday, 11.1.2019, 13:15, WIL/C133  On an infinite family of highly regular graphs Maja Pech (U Novi Sad) Highly regular graphs for which not all regularities are explainable by symmetries are fascinating creatures. Some of them like, e.g., the line graph of W. Kantor's nonclassical GQ(25,5), are stumbling stones for existing implementations of graph isomorphism tests.They appear to be extremely rare and even once constructed it is difficult to prove their high regularity.Yet some of them, like the McLaughlin graph on 275 vertices and Ivanov's graph on 256 vertices are of profound beauty. This alone makes it an attractive goal to strive for their complete classification or, failing this, at least to get a deep understanding of them.Recently, Ch. Pech discovered new methods for proving high regularity of graphs. Using these techniques, in this talk we report on a family of strongly regular graphs, originally discovered by A.V. Ivanov in 1990. We show that they are (3,5)regular. 
Friday, 14.12.2018, 13:15, WIL/C133 
NazarovWenzl algebras, coideal subalgebras and categorified skew Howe duality 
Wednesday, 28.11.2018, 13:15, WIL/C115 
Large rigid sets of algebras 
Friday, 16.11.2018, 13:15, WIL/C133 
HHhomogeneous graphs with infinite independence number. 
Friday, 9.11.2018, 13:15, WIL/C133  Some very weak height 1 identities Jakub Opršal A strong Maltsev condition is a finite set of identities in a finite algebraic language. Such condition is said to be satisfied in a set of operations (the set of all term operations of an algebra, a clone, a minion) if there is assignment of concrete operations to the symbols of matching arity which universally satisfies all the identities. These conditions are naturally (lattice) ordered by syntactic consequence. The resulting lattice has been studied since 70's. One of the results of Taylor from that time is that there is no such weakest nontrivial condition. Recently, the focus has been shifted to identities of height 1, i.e., identities that have exactly one function symbol on either side. This has been motivated by the study of complexity of CSP. In the talk, we will look into the ordered set of such height 1 conditions and its 'small' elements. 
Friday, 2.11.2018, 13:15, WIL/C115 
The homogeneity of semigroups 
Friday, 26.10.2018, 13:15, WIL/C115  Dissecting Shitpel'man's theorem Nikolaas Verhulst In this talk, we will dissect a classical proof from noncommutative valuation theory. We will introduce the necessary terminology, discuss the proof, and distil its vital parts. We will show how they can be used independently to generalise the original statement. 
Friday, 19.10.2018, 13:15, WIL/C115  Graph algebras and graph varieties Erkko Lehtonen Graph algebras were introduced by Shallon in 1979. To each directed graph G = (V,E), we associate an algebra A(G) of type (2,0), whose universe is the set V∪{∞}, where ∞ is a new element not in V, considered as a nullary operation, and where the binary operation ("product") is defined as xy = x if (x,y)∈E and xy = ∞ otherwise. Encoding graphs as algebras in this way, we can view any algebraic properties of the graph algebra A(G) as properties of the graph G. Although the class of graph algebras does not constitute a variety (as it is not closed under direct products), it makes perfect sense to consider the satisfaction relation between graphs (that is, graph algebras) and identities of type (2,0). With respect to the Galois connection induced by this relation, the closed sets of graphs are called graph varieties and the closed sets of identites are called equational theories of graphs. In this talk, we give a brief overview on different approaches to studying graph varieties. We also report the speaker's recent work with Chaowat Manyuen (Khon Kaen University) on descriptions of graph varieties that are axiomatized by certain groupoid identities that are of general interest in algebra, such as the (left or right) semimedial and medial identities. 
Friday, 12.10.2018, 13:15, WIL/C115 
Multiplicative and implicative derivations on residuated multilattices 
 Semester Break   
Friday 21.9.2018, 13:15, WIL/C115  Temporal constraint satisfaction problems in least fixed point logic Jakub Rydval The constraint satisfaction problem (CSP) for a fixed structure L with finite relational signature is the computational problem of deciding whether a given finite structure of the same signature homomorphically maps to L. A temporal constraint language is a structure over the rational numbers Q whose relations are firstorder definable in (Q;<). In 2009, Bodirsky and Kara presented a complete classification of the computational complexity of CSPs for temporal constraint languages. In contrast to finite domain structures, there are temporal constraint languages whose CSP cannot be solved by any Datalog program but can be expressed in least fixed point logic (LFP). An example is CSP(Q; {(x,y,z)  x>y or x>z}), known as the and/or scheduling problem. I will give a proof of a trichotomy for LFP expressibility of CSPs of temporal constraint languages. For a temporal constraint language L, at least one of the following is true: CSP(L) is expressible in LFP, the relation {(x,y,z)  x>y=z or y>z=x or z>x=y} has a primitive positive definition in L, or the twoelement group has a primitive positive interpretation with parameters in L. In the latter case it is known that CSP(L) cannot be expressed in LFP. We conjecture that the same holds for the second case. 
Friday 14.9.2018, 13:15, WIL/C115  Constraint Satisfaction over the Random Tournament Simon Knäuer The Random Tournament T is the Fraïssé limit of the class of all finite tournament graphs. The talk will introduce this structure and define the Constraint Satisfaction Problem of its firstorder reducts. It will give a proof of the complexity dichotomy for CSPs of firstorder expansions of T by injective relations. 
Friday 20.7.2018, 13:15, WIL/C115  Highly regular graphs Maja Pech (University of Novi Sad) Highly regular graphs appear as a class of graphs with nontrivial degree of regularity that is not induced by symmetries. They are stumble stones for the existing implementations of graph isomorphism tests. So far, there is found just a modest number of examples of such graphs. In this talk, we analyze an infinite family of strongly regular graphs introduced by Brouwer, Ivanov and Klin and uncover certain regularities that are not explainable by their symmetries. This is joint work with Christian Pech. 
Friday 13.7.2018, 13:15, WIL/C115  On the characterization of particular orthogroups by disjunctions of identities Alexander Jende (University of Potsdam) Based on a general result by Clifford, it is a wellknown fact that a semigroup is an orthogroup if and only if it is a semilattice of rectangular groups. In particular, every band is a semilattice of rectangular bands. Classes of semilattices of various particular rectangular groups can be characterized using the concept of disjunctions of identities. This concept, a generalization of the wellknown identities, was introduced by Ljapin in the 1970s. Using disjunctions of identities, we characterize orthogroups which are semilattices of rectangular groups of various exponents. Furthermore, we consider chains of rectangular groups. Finally, we present some applications. For example, we describe several classes of strong semilattices of semigroups. 
Friday 29.6.2018, 13:15, WIL/C115  Complexity of combinations of qualitative constraint satisfaction problems Johannes Greiner In 1979 Nelson and Oppen first presented a result for convex theories T and S, stating that the constraint satisfaction problem (CSP) of the union of T and S can be solved by combining the algorithms for T and S in a blackbox way. We prove for a certain class of structures that convexity is also necessary for polynomialtime tractability of the union of their firstorder theories. In particular, we will look at the generic combination of two relational structures A and B on infinite domains, which is a key idea in the proof. The generic combination of A and B, if it exists, is a structure that has the same CSP as the union of the firstorder theories of A and B, where the signatures of A and B are assumed to be disjoint. Furthermore, its orbits of ntuples are precisely the intersections of the orbits of ntuples of A and of B. We characterize the existence of generic combinations and describe when the generic combination has a binary injective polymorphism, in which case the CSP is polynomialtime tractable. 
Friday 22.6.2018, 13:15, WIL/C115  Twists of hyperelliptic curves without rational points François Legrand In this talk, I shall present several conditional and unconditional results on the lack of rational points on twisted hyperelliptic curves over the rational numbers. Time permitting, I shall also give a conjectural example of a 1parameter family of affine curves over some number field, all with a rational point, but with no generic point, thus relating to an old problem of Schinzel. The talk requires no prior knowledge about rational points on curves. 
Friday 15.6.2018, 13:15, WIL/C115  Stabilization of configurations Sven Reichard One origin of the notion of coherent configurations is the study of the complexity of the graph isomorphism problem. Given an edgecoloring of a complete graph the algorithm by Weisfeiler and Leman constructs a refinement of the coloring using invariants on the edges; the resulting refined coloring has the same automorphisms as the original coloring. The invariant that is used counts colored triangles involving a given edge. Coherent configurations may be defined as colorings that are stable under this procedure. The concepts above can be generalized in several directions. Other invariants can be used by considering subgraphs with more than three vertices (cf. HestenesHigman's tvertex condition}). Instead of graphs we can consider (uniform) hypergraphs; this leads to kary coherent configurations (Babai, ImmermanLander), which play a prominent role in recent advances in the study of the graph isomorphism problem. It is known that the algorithm of WeisfeilerLeman is polynomial in complexity. Twenty years ago two implementations were described which both had their advantages and disadvantages. We will present a new framework that takes into account the generalizations described above as well as advances of modern computer architecture. The programs will be available as open source. 
Friday 8.6.2018, 13:15, WIL/C115  Essential arguments and minors of partial functions Nareupanat Lekkoksung (Khon Kaen University) It is well known that the number of essential arguments of total functions does not increase upon formation of minors. This is no longer true for partial functions. Moreover, in contrast to total functions, it is possible that a nonconstant partial function has no essential argument. From this standpoint, essential arity seems slightly unsatisfactory as a quantity of structural complexity for partial functions. Our goal is to formulate alternative notions that would more accurately describe the dependence of partial functions on some arguments. We consider the question whether the corresponding quantities decrease upon formation of minors. We also investigate the structure of the minor poset of partial functions. M. Couceiro and M. Pouzet showed that the minor poset of Boolean functions is pastfiniteuniversal. This property carries over to minor posets of partial functions on finite sets. We improve this result by showing that certain small fragments of this poset (e.g., partial projections, constant functions) are pastfiniteuniversal. 
Friday, 25.5.2018, 13:15, WIL/C115  A proof of CSP Dichotomy conjecture Dmitriy Zhuk (Lomonosov Moscow State University) Many natural combinatorial problems can be expressed as constraint satisfaction problems. This class of problems is known to be NPcomplete in general, but certain restrictions on the form of the constraints can ensure tractability. The standard way to parameterize interesting subclasses of the constraint satisfaction problem is via finite constraint languages. The main problem is to classify those subclasses that are solvable in polynomial time and those that are NPcomplete. It was conjectured that if a constraint language has a weak near unanimity polymorphism then the corresponding constraint satisfaction problem is tractable, otherwise it is NPcomplete. The hardness result is known since 2001. We present an algorithm that solves Constraint Satisfaction Problem in polynomial time for constraint languages having a weak near unanimity polymorphism, which proves the remaining part of the conjecture. 
Friday, 18.5.2018, 13:15, WIL/C115  Structures with small orbit growth Bertalan Bodor Let C be the class of those countable structures A for which there exist constants c_1 and c<1 so that the number of orbits of A acting on ntuples with pairwise distinct entries is at most c_1n^{cn}. We showed that this class is also equal to the class of finite coverings of firstorder reducts of unary omegacategorical structures. In this talk I will attempt to illustrate the basic ideas of the proof of this theorem, and I will present some interesting consequences. Joint work with Manuel Bodirsky. 
Friday, 11.5.2018, 13:15, WIL/C115  Constraint Satisfaction over the Random Tournament Simon Knäuer The Random Tournament is the Fraïssé limit of the class of all finite tournament graphs. The talk will introduce this structure and define the Constraint Satisfaction Problems of its firstorder reducts. It will also give an idea for the complexity classification of these CSPs. Temporal constraint satisfaction problems in least fixed point logic Jakub Rydval The constraint satisfaction problem (CSP) for a fixed structure L with finite relational signature is the computational problem of deciding whether a given finite structure of the same signature homomorphically maps to L. A temporal constraint language is a structure over the rational numbers Q, where all its relations are first order definable using the usual strict linear order <. In 2009, Bodirsky and Kara presented a complete classification of the computational complexity of CSPs for temporal constraint languages. In contrast to finite domain structures, there are temporal constraint languages whose CSP cannot be solved by Datalog but can be expressed in least fixed point logic (LFP). An example is CSP(Q; {(x,y,z)  x>y or x>z}), known as the and/or scheduling problem. The goal of my master thesis is to classify all CSPs for temporal constraint languages that can be expressed in LFP. In this talk, I present an LFP formula for every temporal constraint language that is preserved by the minimum operation. 
Wednesday, 9.5.2018, 13:15, WIL/C115 
On a Generalization of von Staudt's theorem of crossratios 
Friday, 4.5.2018, 13:15, WIL/C115  The complexity of solving equations and checking identities Michael Kompatscher (Charles University Prague) The equation solvability problem of an algebra A is the computational problem that asks, whether an equation of polynomials f(x_1,…,x_n) = g(x_1,…,x_n) has a solution in A or not. Besides their relevance in algebra, for finite algebras these problems encode many problems in NP, including all CSPs. The identity checking problem of A is the closely related problem that asks, whether an input equation holds for all substitutions of variables or not. In my talk I am first going to discuss some obstacles in classifying the complexity of both problems for all finite algebras. Then I will discuss how commutator theory and tame congruence theory bring us close to a P/NPc (respectively P/coNPc) dichotomy in congruence modular varieties. This is based on joint work with Idziak and Krzaczkowski. 
Friday, 20.4.2018, 13:15, WIL/C115  Surjectivemorphism extension classes of graphs, part 2 Andrés Aranda Two new morphismextension classes were introduced recently for infinite relational structures: HE, the class of all Lstructures such that any homomorphism between finite induced substructures extends to a surjective endomorphism, and MB, the class of all Lstructures such that any monomorphism between finite induced substructures extends to a bijective endomorphism. In this talk, I will show that all MBhomogeneous graphs are HEhomogeneous and all "interesting" (i.e., not a union of finite cliques) HEhomogeneous graphs are MBhomogeneous. In the second talk, I will prove that every MBhomogeneous graph is HEhomogeneous. 
Friday, 13.4.2018, 13:15, WIL/C115  Surjectivemorphism extension classes of graphs Andrés Aranda Two new morphismextension classes were introduced recently for infinite relational structures: HE, the class of all Lstructures such that any homomorphism between finite induced substructures extends to a surjective endomorphism, and MB, the class of all Lstructures such that any monomorphism between finite induced substructures extends to a bijective endomorphism. In this talk, I will show that all MBhomogeneous graphs are HEhomogeneous and all "interesting" (i.e., not a union of finite cliques) HEhomogeneous graphs are MBhomogeneous. 
Friday, 6.4.2018, 13:15, WIL/C115  Splitting fields of central simple algebras of exponent 2 Karim Becher (University of Antwerp) Central simple algebras over fields have been studied for over a century, starting with the work of Cayley, Hamilton, Dickson and Wedderburn. As a crucial result of class field theory, these algebras are completely classified over number fields. Over an arbitrary base field, even though these algebras are abstractly classified by the Brauer group, their structure, or more particularly the structure of finitedimensional division algebras is still a mystery. By Merkurjev’s Theorem every central simple algebra of exponent two is Brauer equivalent to a tensor product of quaternion algebras. In particular, if every quaternion algebra over a given field is split, then there exists no central simple algebra of exponent two over this field. I give an independent elementary proof of the latter fact. While this proof is based on Zorn's Lemma, the statement should also have a constructive proof, leading to an explicit bound of the degree of a splitting 2extension in terms of the degree of the algebra. 
 Semester Break   
Friday, 23.2.2018, 13:15, WIL/C115  Counting relational structures Leopold Schlicht (HansErlweinGymnasium Dresden) Let K be a class of finite, relational structures. This talk is about the following combinatorial function: the *profile* of K takes a natural number n as an argument and yields the number of structures in K of size n (up to isomorphism). Pouzet conjectured for hereditary K satisfying the joint embedding property that if the profile of K is bounded by a polynomial, then the profile is eventually a quasipolynomial. I will give an overview of the current state of research regarding this conjecture. After that I will use the method of generating functions to prove the conjecture for classes of all graphs that embed into the disjoint union of infinitely many copies of a (directed or undirected) path. Finally, a list of open special cases of the conjecture is given. 
Friday, 2.2.2018, 13:15, WIL/C115  The Alternate Order of CongruenceUniform Lattices Henri Mühle A (finite) lattice L is congruenceuniform if and only if it can be obtained from the singleton lattice by a sequence of interval doublings. If we indicate which edge of the poset diagram of L is created at which step in the sequence, we obtain a natural edgelabeling of L. This set of edge labels can be used to define an alternate partial order on the elements of L. The main source of examples for this constructions comes from posets of regions of a real hyperplane arrangement. When such a poset of regions is a congruenceuniform lattice, then the alternate order is a lattice, too. In general, however, it is an open problem to characterize the congruenceuniform lattices whose alternate orders are lattices again. We provide a necessary condition for the lattice property of the alternate order and we discuss constructions that either preserve or destroy the lattice property. 
Friday, 26.1.2018, 13:15, WIL/C115  Linkage of quaternion algebras Parul Gupta A quaternion algebra over a field is given by a pair of nonzero parameters from the field, which we call its slots. We discuss the property for a field F, called strong linkage, that any finite number of quaternion algebras over F have a common slot. The study of this field property is motivated by its relation to quadratic forms and further by the examples of global fields, where it can be shown using Class Field Theory. We study the strong linkage property for the rational function field over quasifinite fields, that is perfect fields having a unique extension of each degree. An interesting example other than finite fields is the field of Laurent series over an algebraically closed field of characteristic 0. In this talk I will discuss relation of the linkage problem to quadratic form theory and different tools which are useful to show strong linkage. 
Friday, 19.1.2018, 13:15, WIL/C115  Morphism extension classes of infinite Lcolored graphs Andrés Aranda An Lstructure M is in HH_L (homomorphismhomogeneous) if every homomorphism between finite induced substructures of M can be extended to an endomorphism of M; similarly, M is in MH_L if every local monomorphism can be extended to an endomorphism of M. It is known that for some languages L (for example, graphs), MH_L and HH_L coincide, while for others HH_L is a proper subclass of MH_L. If L is a finite partial order, an Lcolored graph is a graph in which elements of L are assigned to the edges. Hartman, Hubička and Mašulović proved that in the case of finite graphs colored by linear orders, MH=HH even when colorings of the vertices were allowed, and that MH=HH for vertexuniform (all vertices of the same color) finite graphs colored by a diamond (an antichain enriched by a bottom element and a top element), but differ when vertex colorings are allowed. In this talk, I will show that MH=HH for countable Lcolored graphs when L is a linear order, give an example of an infinite MH Lcolored graph that is not HH when L is a diamond, and prove that if MH=HH for infinite vertexuniform Lcolored graphs, then L is a joinsemilattice. This is joint work with David Hartman. 
Wednesday 17.1.2018, 13:15, WIL/C115  CDindependent subsets Eszter Horváth (University of Szeged) A subset X of a finite lattice L is called CDindependent if the meet of any two incomparable elements of X equals 0. Czédli, Hartmann and Schmidt has an important result about CDbases (maximal CDindependent subsets) of distributive lattices. In the talk, we define CDindependent subsets in an arbitrary poset in a natural way. Actually, CDindependence is in close relationship with trees. More precisely, if we have a CDindependent subset in a poset and we remove its possible 0, then we obtain a forest. We show that the CDbases of any poset can be characterized as maximal chains in a related poset. We use this result to investigate CDbases in semilattices and in more general lattice classes. Finally, I give some overview about other results, in particular about some combinatorial aspects of CDindependence. 
Friday 12.1.2018, 13:15, WIL/C115 
Solution sets of systems of equations 
Friday 5.1.2018, 13:15, WIL/C115  The undecidability of joint embedding for hereditary graph classes, and related problems Sam Braunfeld (Rutgers University) A class of structures has the joint embedding property if for any two structures in the class, there is a third structure in the class embedding both. We will sketch a proof of the undecidability of joint embedding for finitelyconstrained hereditary graph classes. Time permitting, we will discuss the analogous question in other classes of structures. 
Friday 15.12.2017, 13:30, WIL/C204  εhomomorphisms and complexity reduction Alexandr Kazda (Charles University) 
Friday 8.12.2017, 13:15, WIL/C115  The promise(d) land of constraint satisfaction Jakub Opršal The promise constraint satisfaction problem can be viewed as a generalization of CSP. The domain of a PCSP is not one, but two relational structures A and B in the same language. PCSP(A, B) refer to the decision problem which on input gets a ppsentence φ in the common language of A and B, and decides between two cases: * (Completeness) A satisfies φ, or * (Soundness) B does not satisfy φ. An important instance of this problem is approximate graph coloring (the corresponding structures are a dclique and a eclique for fixed e>d): the goal is to decide whether a given graph is dcolorable or not even ecolorable. The complexity of this graph coloring is mostly open, but believed to be NPhard for all constants e>d. Recently, Brakensiek and Guruswami rediscovered a Galois correspondence between pairs of relational structures and minor closed sets of functions which is a key ingredient of the algebraic approach. We will discuss the natural followup, the full algebraic approach to PCSP and how it relates to the fact that the complexity of CSP depends only on the height 1 (linear) identities satisfied by the corresponding polymorphism clone. This opens a new possibility of applying algebra in several approximation problems. 
Friday, 1.12.2017, 13:15, WIL/C115  Counting rational points on definable sets Margaret Thomas (Universität Konstanz) The results outlined in this talk are part of a wider, flourishing interaction between diophantine geometry and model theory. The central aim is to bound the density of rational and algebraic points lying on certain `transcendental' subsets of the reals. Following influential work by Pila and Wilkie in this area, our focus is on sets which are firstorder definable in various ominimal expansions of the real field. We shall survey background and some results in this area, in particular concerning possible improvements to the Pila–Wilkie bound. These include instances of a conjecture of Wilkie, which proposes an improvement for the real exponential field, and some recent progress made towards finding an effective version of the Pila–Wilkie Theorem. 
Friday, 24.11.2017, 13:15, WIL/C115 
The homomorphism order: monounary algebras 
Friday, 17.11.2017, 13:15, WIL/C115 
Time Complexity of NPHard CSPs 
Friday, 10.11.2017, 13:15, WIL/C115 
Profiniteness in finitely generated varieties is undecidable 
Friday, 3.11.2017, 13:15, WIL/C115 
Homogeneous structures and a new poset 
Friday, 27.10.2017, 13:15, WIL/C115 
Twisting the zerodivisors away 
Tuesday, 24.10.2017, 11:00, WIL/C115 
A Dichotomy Theorem for the Inverse Satisfiability Problem 
Friday, 20.10.2017, 13:15, WIL/C115 
Ultraproducts preserve finite subdirect reducibility 
Friday, 13.10.17, 13:15, WIL/C115 
open problems session 
 Semester Break   
Friday, 8.9.2017, 13:15, 
Free combinations of omegacategorical structures 
Friday, 1.9.2017, 13:45, WIL/C115 
Monotone Monadic SNP 2: proof of the universalalgebraic dichotomy conjecture Antoine Mottet (joint work with Manuel Bodirsky) The forbidden patterns problem of the set of vertexcoloured graphs {H1,…,Hk} is the decision problem of the form: given a finite graph G as input, is it possible to colour the vertices of G in a way that none of H1, …, Hk homomorphically maps to the resulting coloured graph. The logic MMSNP can be seen as a complexity class whose problems are forbidden patterns problems of finite sets of coloured relational structures. It was conjectured by Feder and Vardi that this complexity class exhibits a complexity dichotomy (i.e., that every forbidden patterns problem is in P or NPcomplete). Feder and Vardi showed that every problem in MMSNP reduces in probabilistic polynomialtime to the CSP of a structure with finite domain, and Kun later derandomized this reduction. Thus, MMSNP and finitedomain CSPs are computationally equivalent. Following up on Manuel's talk, I will present a completely new reduction from MMSNP to finitedomain CSPs that uses recent techniques and results from universal algebra, model theory, and Ramsey theory. This proves a stronger form of the FederVardiKun result, and shows in particular that the BodirskyPinsker tractability conjecture holds for all CSPs in MMSNP. 
Friday, 1.9.2017, 13:15, WIL/C115 
Monotone Monadic SNP 1: classical results and applications 
Friday, 14 July .2017, 13:15, WIL/C115 
Submodular Semilinear Valued Constraint Languages Caterina Viola I will present some new results on the characterisation of submodular semilinear functions and an algorithm solving the VCSP for an interesting subclass of them. I will also show a generalisation of the NPhardness condition for semilinear VCSPs. This is joint work with M. Bodirsky and M. Mamino. 
Friday, 30 June 2017, 9:30, WIL/C207 
Polynomial growth of concept lattices, canonical bases and generators: extremal set theory in Formal Concept Analysis 
Friday, 23 June 2017, 13:15, WIL/C115 
Practically efficient algorithms for coherent configurations Sven Reichard In complexity theory we study the /theoretical/ complexity of algorithms, that is, the asymptotic behaviour of the amount of required resources (time, space, energy) as a function of the input size. For the practitioner who uses the algorithms it may be more interesting to know the /practical/ complexity, the resources required for specific instances of the problem on given hardware. Here, the size of the constants does matter. It turns out that in this case the simple model of computation with one processing unit and uniform memory access is not adequate. We look at two algorithmic problems related to coherent configurations, which are relational systems with a strong algebraic flavour. WeisfeilerLeman (WL) stabilization computes the coarsest coherent refinement of a given configuration. It features in the recent improvements to the solution of the graph isomorphism problem. Its twodimensional variant is of interest in algebraic graph theory. Two implementations were developed in the 1990's, with diverse theoretical and practical characteristics. We describe a few ways to outperform both classical implementations. Srings are twodimensional coherent configurations which admit a regular group of automorphisms. They play a role in the theory of Cayley graphs. The set of Srings over a given group G is related to the set of twoclosed overgroups of the regular action of G. Knowledge of their structure helps us solve the isomorphism problem for Cayley graphs over G. Enumeration of Srings is hard, but it provides plenty of opportunity for efficient implementation. 
Friday, 9 June .2017, 13:15, WIL/C115 
Reflectionclosed varieties of multisorted algebras and minor identities Erkko Lehtonen, Reinhard Pöschel Reflections (as introduced by L. Barto, J. Opršal, M. Pinsker) generalize the classical operators of taking subalgebras and homomorphic images. We generalize this notion to multisorted algebras. We ask for a characterization of reflectionclosed varieties (RPvarieties) and consider the Galois connection ModmId between multisorted algebras and minor identities. Analogously to the classical Birkhoff theorem, it turns out that the Galois closed sets of algebras are just the reflectionclosed varieties of multisorted algebras, i.e., Mod mId K = RP K. Similarly, we characterize the minorequational theories of multisorted algebras, i.e., the closed sets of minor identities. We also discuss how RPvarieties and usual varieties of multisorted algebras are related to each other. This is joint work with Tamás Waldhauser. 
Friday, 2 June .2017, 13:15, WIL/C115 
Parking Functions and Noncrossing Partitions 
Friday, 26 May .2017, 13:15, WIL/C115 
Towards a noncommutative Chevalleystyle algebraic geometry 
Friday 12 May 2017, 13:15, WIL/C115 
Complexity of term representations of functions 
Friday, 
Residuated multilattices: the first glimpse into their structure 
Friday, 21 April 2017, 13:15, WIL/C115 
Primitive positive definability over complex numbers Sebastian Meyer (MartinAndersenNexöGymnasium Dresden) 
Friday, 
Complexity of NPComplete Constraint Satisfaction Problems 
 Semester Break   
Friday, 3 Feb 2017, 13:15, WIL/C115 
Extremal lattices: where we go from here Bogdan Chornomaz (V.N. Karazin Kharkiv National University) In 2015 Alexandre Albano and I managed to prove an exact upper bound on the number of elements in a lattice with bounded VCdimension. In this talk I'll try to show that, instead of closing the topic, this result may be considered as a starting point for deeper, more challenging, but in the same time natural studies. 
Friday, 27 Jan 2017, 13:15, WIL/C115 
Majors of functions Erkko Lehtonen We consider the minor ordering of functions of several arguments. A function is said to be a minor of another function, if the former can be obtained from the latter by permutation of arguments, identification of arguments, and introduction of inessential arguments. The very definition of minor provides a natural way of going downwards in the minor order. In this talk, we are interested in going upwards in the minor order, i.e., in majors of functions, and, in particular, in upper covers of functions. This talk is based on joint work with Miguel Couceiro. 
Friday, 20 Jan 2017, 13:15, WIL/C115 
Supersingular Isogeny DiffieHellman Key Exchange Juliane Prochaska (TU Dresden) The DiffieHellman key exchange is a wellknown and important protocol in modern cryptographic applications. It is, however, vulnerable to quantum algorithms. A promising candidate for postquantum cryptography is the supersingular isogeny DiffieHellman key exchange, which has been introduced by de Feo, Jao and Plût in 2011. This talk presents the protocol and its underlying mathematical concepts, including an introduction to elliptic curves and their use in cryptography. 
Friday, 
Upper bounds for the number of Galoisclosed sets arising from finite binary relations Alexandre Albano We will do a gentle and short introduction to Formal Concept Analysis and give a minisurvey of results associated to the FCAmotivated question: how many closed sets does a Galois connection induced by a binary relation have? The general perspective here is that of complete lattices, but the focus will be combinatorial. 
Friday, 
Introduction to meanpayoff games 
Wednesday 30 Nov 2016, 13:15, WIL/C115 
Representation problems for monoids of endomorphisms Danica JakubíkováStudenovská (U Košice) The present talk deals with the following representation problems: (A) ABSTRACT: (i) Is every monoid isomorphic to the monoid of all endomorphisms of some algebraic structure? (ii) Is every group isomorphic to the group of all automorphisms of some algebraic structure? (B) CONCRETE: (i) Is every monoid of transformations of a nonempty set U equal to (not just isomorphic to) the monoid of all endomorphisms of some algebraic structure? (ii) Is every group of permutations of a nonempty set U equal to (not just isomorphic to) the group of all automorphisms of some algebraic structure? We will consider also different types of the algebraic structures. 
Friday, 
Submodular semilinear valued constraint satisfaction problems Caterina Viola Submodular functions are an important class of cost functions in optimisation theory. Given a totally ordered domain D, we say that a rationalvalued function f on D^n is submodular if, for all x, y in D^n, it holds that f(x)+f(y) ≥ f(max(x,y))+f(min(x,y)), where max and min are applied componentwise. I focus on submodular cost functions f that are semilinear, that is, the underlying domain D is the set of rational numbers and f is firstorder definable in (Q;<,+,1). Let us consider a (finite) set Gamma of submodular semilinear cost functions. An instance of the valued constraint satisfaction problem (VCSP) for Gamma is specified by a finite set of variables and by an objective function which is given as the sum of applications of the cost functions in Gamma to some of the variables. The goal is to find an assignment to the variables minimising the objective function. Our strategy to obtain a polynomialtime algorithm solving the VCSP for submodular semilinear cost functions is as follows. In a first step, we show that all submodular semilinear functions have an explicit syntactic characterisation. In a second step, we show how to reduce the problem to submodular VCSPs over finite domains, which are known to be polynomialtime solvable. 
Friday, 18 Nov 2016, 13:15, WIL/C115 
open problems session 
Friday., 11 Nov 2016, 13:15, WIL/C115 
Indecomposabilty of two equational theories We will discuss the indecomposability of two Mal'cev conditions—namely the conditions describing congruence modular varieties, and varieties that are congruence npermutable for some n—in the following strong sense: Suppose that we have two sets of identities in disjoint languages such that their union implies the Mal'cev condition, then one of the sets implies the Mal'cev condition. 
Friday., 
On Noncrossing Partitions In this survey talk I will try to follow the timeline of this evolution, emphasize properties and connections to other objects, and outline potential generalizations. 
Friday., 28 Oct 2016, 13:15, WIL/C115 
Local Movement and Jordan Groups Robert Barham I will explain what a Jordan Group is, what it means for it to be locally moving, and how this relates to Reconstruction from Automorphism Groups and the complexity of certain CSPs. This work builds on the results I presented last time I spoke at the International Seminar, but I will not assume any prior specialist knowledge. 
Friday., 21 Oct 2016, 13:15, WIL/C204 
problems presented by participants 
Friday., 14 Oct 2016, 13:15, WIL/C207 
Minors of functions and permutations, reconstruction problems, and the order of first occurrence Erkko Lehtonen 
 Semester Break   
Fr., 15.7.2016, 13:15 Uhr, WIL/C115  Enumeration of Srings over the elementary abelian group of order 64 Sven Reichard Srings, as introduced by Schur and Wielandt, are certain subrings of the group ring C[G] for a finite group G. There is a onetoone correspondence between Srings over G and association schemes invariant under a regular action of G. Hence they provide a link between Group Theory and Combinatorics. They have been successfully utilized for example in the study of the complexity of the isomorphism problem for circulants. Srings have been classified over all groups of order less than 64. The case of the elementary abelian group $Z_2^{^6}$ poses particular challenges. We report on progress toward the enumeration of Srings over this group. 
Di., 12.7.2016, 10:00 Uhr, WIL/C115  Generalized Concepts of Distance, Proximity and Betweenness in Comparison Mosadak Al Salamat (Vortrag zur Masterarbeit, Betreuer: Prof. Stefan Schmidt) 
Fr., 8.7.2016, 13:15 Uhr, WIL/C115 
Decidable and undecidable properties of universal firstorder theories André Schrottenloher (École polytechnique, TU Dresden) We study the decidability of various properties that one might ask for finite universal firstorder theories T. On the one hand, for example, the equivalence of T to a universal Horn theory is decidable. On the other hand, it is an open problem whether one can effectively decide the Joint Embedding Property for the class of models of T. Finally, we show that the following problem is undecidable: are the universalnegative consequences of T finitely axiomatisable? All these questions have applications in the study of constraint satisfaction problems (CSPs) that are given by such finite universal firstorder theories, since properties of the CSP can be reformulated as properties of its theory. 
Do., 7.7.2016, 13:15 Uhr, WIL/C115  Subdirectly and almost subdirectly irreducible monounary algebras Danica JakubíkováStudenovská (Pavol Jozef Šafárik University in Košice) 
Fr., 1.7.2016, 13:15 Uhr, WIL/C115  Lower bounds and reconstruction algorithms for sums of affine powers Timothée Pécatte (École normale supérieure de Lyon) A sum of affine powers is an expression of the form f(x) = a_1 * (x  b_1)^e_1 + ... + a_s * (x  b_s)^e_s. Although quite simple, this model is a generalization of two wellstudied models: Waring decomposition and sparsest shift. For these three models there are natural extensions to several variables, but this talk will be focused on univariate polynomials. We will present efficient algorithms for reconstructing the smallest expression for an input polynomial f. These algorithms build on techniques developed for proving lower bounds on the number of terms s needed to represent a polynomial. 
Fr., 24.06.2016, 13:15 Uhr, WIL/C115 
Submaximal Strong Partial Clones Victor Lagerqvist 
Fr., 10.06.2016, 13:15 Uhr, WIL/C115  On products of amalgams and amalgams of products Maja Pech We study amalgamated free sums in strict amalgamation classes of finite relational structures that are closed with respect to finite products. Examples of such classes are the class of finite partial orders, the class of nonempty finite metric spaces, the class of finite simple graphs, … In particular, we are interested in the interaction between amalgamated free sums and direct products. It turns out that there is a canonical homomorphism between the amalgamated free sum of products and the product of amalgamated free sums. When is this canonical homomorphism an embedding? In this talk we will present results toward the general answer to this question. 
Fr., 3.6.2016, 13:15 Uhr, WIL/C115  Constraint Propagation and Pebble Games Christoph Berkholz (HumboldtUniversität zu Berlin) A generic method for solving the constraint satisfaction problem is "constraint propagation" where one iteratively derives new constraints in order to shrink the search space or to detect inconsistencies in the instance. A classical and very basic algorithm in this area is the socalled kconsistency test that iteratively derives local constraints involving only k variables. In this talk I will give an introduction to this method and show that the kconsistency test is tightly connected to a simple combinatorial pebble game originally introduced in the context of finite model theory. Afterwards I will present some results on the structure and complexity of the kconsistency test that have been obtained via this pebble game in the last years. 
 Semester Break   
Fr., 18.3.2016, 13:15 Uhr, WIL/C115  Strong Partial Clones and the Complexity of Constraint Satisfaction Problems Victor Lagerqvist This seminar is concerned with properties of strong partial clones and their applicability to study the computational complexity of constraint satisfaction problems. Loosely, the approach boils down to the wellknown fact that sets of relations invariant under partial functions can be characterized by primitive positive definitions without existential quantification. These quantifierfree primitive positive definitions provides a method to study the complexity of problems where the normal Galois connection between clones and relational clones does not result in reductions that are finegrained enough. We are going to see applications of partial clone theory to study the worstcase time complexity of NPcomplete Boolean constraint satisfaction problems, and also touch upon some unavoidable complications with this strategy, which somewhat limits its applicability in practice. 
Fr., 5.2.2016, 13:15 Uhr, WIL/C115  Unifying Tone System Definitions: Ordering Chromas Tobias Schlemmer The talk describes the background of a musical tone system definition that has been proposed [1] in the proceedings of the MCM2015 in London.[2] This definition uses abstract ordered groups as interval groups. The common operation of octave identification is replaced by a folding operation for ordered sets that is based on the factorisation of groups by normal subgroups. The resulting structure is used to provide a chroma system definition that can preserve a certain amount of the order relation. Additionally, a path is shown that allows the integration of the David Lewin's theory of Generalized Interval Systems into the extensional language that has been proposed by Rudolf Wille and Wilfried Neumaier. 
Mo., 1.2.2016, 16:40 Uhr, WIL/C207  Mathematische Morphologie und ihre Fuzzyfizierung Lars Lumpe (Diplomverteidigung, Betreuer: Prof. S. Schmidt) 
Fr., 29.1.2016, 13:15 Uhr, WIL/C115  Laws for finite groups Andreas Thom 
Fr., 22.1.2016, 13:15 Uhr, WIL/C115  Latticevalued functions Eszter Horvath (Universität Szeged) 
Fr., 15.1.2016, 13:15 Uhr, WIL/C115  The complexity of CSPs for reducts of the random partial order Trung Van Pham The random partial order is defined as the Fraissé limit of the class of finite partial orders. In this talk, we will give a full complexity classification for the constraint satisfaction problems (CSPs) on the class of reducts of the random partial order. This result confirms a dichotomy conjecture on infinite CSPs. 
Fr., 18.12.2015, 13:15 Uhr, WIL/C/115  On permutation groups and permutation pattern classes Erkko Lehtonen 
Fr., 4.12.2015, 13:15 Uhr, WIL/C/115  Mashups algebras and constraint satisfaction problems Antoine Mottet Abstract: We study the class of locally closed function clones whose unary operations are all injections that fix a given finite set of elements. For such a clone C, we prove that either there exists a uniformly continuous map from C to the clone of projections that preserves equations of height one and left composition with unary operations, or there is a canonical operation in C which is a Siggers operation modulo left composition with unaries. In the context of constraint satisfaction problems, this implies that every CSP whose constraint language is definable with parameters and equality is in P or NPcomplete if and only if the FederVardi conjecture for finitedomain CSPs holds. 
Fr., 20.11.2015, 13:00 Uhr, WIL/C/207  Topologische Charakterisierung und endliche Repräsentation nominaler Mengen Albrecht Schmidt (Kolloquium zur Diplomarbeit, Betreuer: Jun.Prof. M. Schneider) 
Fr., 13.11.2015, 13:15 Uhr, WIL/C/115  Ratio Quantiles Daniel Gburek (Fak. Informatik) In this talk we show that socalled ratio quantiles for finite Markov chains with rewards can be efficiently computed. That is, the exact computation of optimal thresholds, which are almost surely or with positive probability exceeded by the ratio between two reward functions, can be done in polynomial time. We also provide polynomialtime algorithms solving related decision problems on ratio objectives. This is joint work with Christel Baier, Clemens Dubslaff, and Jana Schubert. 
Fr., 6.11.2015, 13:15 Uhr, WIL/C/206  CSPs or Orientations of Trees  Computational Experiments on their Tractability via Polymorphisms Jana Fischer (Verteidigung der Diplomarbeit; Betreuer: Prof. Manuel Bodirsky) In der Theorie der ConstraintSatisfactionProbleme (CSP) dreht sich derzeit alles um die Tractability Conjecture. Diese von Bulatov/Jeavons/Krokhin im Jahr 2000 aufgestellte Vermutung beschreibt eine algebraische Eigenschaft, von der man glaubt, dass sie ein CSP im Fall Ihres Vorliegens tractable ("leicht lösbar") und im Fall ihres Nichtvorliegens NPvollständig ("schwer lösbar") macht. Für einige Klassen von CSPs ist die Richtigkeit der Vermutung bereits bewiesen worden, doch zu einem allgemeinen Beweis ist es noch ein weiter Weg. In meiner Arbeit habe ich mich auf experimentelle Weise mit der Tractability Conjecture für eine weitere Klasse von CSPs, definiert durch Orientierungen von Bäumen, beschäftigt. In diesem Vortrag stelle ich die Ergebnisse meiner Diplomarbeit vor. 
Fr., 30.10.2015, 13:15 Uhr, WIL/C/115  A homogenisable fragment of existential secondorder logic Manuel Bodirsky 
Fr., 23.10.2015, 13:15 Uhr, WIL/C/115  Locally Moving Clones Robert Barham A locally moving group is a group that acts on a complete atomless Boolean algebra in a special way. These were introduced by M. Rubin to study reconstruction from automorphism groups. A locally moving clone is a clone where: 1. the group of invertible elements is a locally moving group; and 2. there are enough `algebraically canonical' elements. After defining these things fully, I will prove that every locally moving polymorphism clone has automatic homeomorphicity with respect to all polymorphism clones, and that if (Q,L) is a reduct of the rationals such that: 1. Aut(Q,L) is not the symmetric group; and 2. End(Q,L)=Emb(Q,L), then Pol(Q,L) is locally moving. 
Fr., 16.10.2015, 13:15 Uhr, WIL/C/115  Lattices generated by the chipfiring game model Trung Van Pham Chipfiring game (also known under the name Sandpile model) is a discrete dynamical model which is defined on graphs. In this talk we will discuss about the lattices generated by this model, and give a necessary and sufficient condition for that class of lattices. Based on that condition we give a polynomial time algorithm for determining whether a given lattice is generated by a chipfiring game. 
Mi., 14.10.2015, 15:00 Uhr, WIL/C/115  Über sofische Monoide Johannes Hüsam (Kolloquiumsvortrag zur Masterarbeit, Betreuer: Jun.Prof. M. Schneider) 
Fr., 9.10.2015, 13:15 Uhr, WIL/C/115  The Model Companions of Permutation Pattern Avoidance Classes Lisa Hutschenreiter (Kolloquium zur Masterarbeit, Betreuer: Prof. M. Bodirsky) 
Fr., 9.10.2015, 10:00 Uhr, WIL/C/115  Topologische Charakterisierung und endliche Repräsentation nominaler Mengen Albrecht Schmidt (Kolloquium zur Diplomarbeit, Betreuer: Jun.Prof. M. Schneider) 
Do., 8.10.2015, 13:15 Uhr, WIL/C/115  CSPs of Orientations of Trees: Computational Experiments on their Tractability via Polymorphisms Jana Fischer (Kolloquium zur Diplomarbeit, Betreuer: Prof. M. Bodirsky) This is the inofficial talk of my Diploma thesis. 
 Semester Break   
Fr., 25.09.2015, 13:15 Uhr, WIL/C/115  Pattern structures and their morphisms Lars Lumpe & Stefan Schmidt In 2001, Bernhard Ganter and Sergei Kuznetsov published the paper Pattern Structures and Their Morphisms, which started a research domain on its own. Here, a pattern structure consists of a map from a set of objects into a partially ordered set of patterns such that every subset of objects possesses a greatest common subpattern. Their investigation was inspired by methods from formal concept analysis. 
Fr., 11.9.2015, 13:15 Uhr, WIL/C/115  Every simple compact semiring is finite Martin Schneider A Hausdorff topological semiring is called simple if every nonzero continuous homomorphism into another Hausdorff topological semiring is injective. A classical result due to Anzai and Kaplansky states that every compact Hausdorff topological ring is profinite, i.e., representable as a projective limit of finite discrete rings. Hence, every simple compact Hausdorff topological ring is finite. Of course, the profiniteness theorem does not generalize to arbitrary compact semirings: in fact, there are numerous examples of connected compact semirings, which therefore cannot be profinite. However, we show that any simple compact Hausdorff topological semiring is finite. 
Fr., 4.9.2015, 13:15 Uhr, WIL/C/115 
The Countably Infinite Boolean Vector Space and Constraint Satisfaction Problems Francois Bossiere Given a relational structure Gamma, the problem CSP(Gamma) takes as an argument a primitive positive sentence phi and asks whether Gamma satisfies phi. Let (V ; +) be the countably infinite vector space over the twoelement field. A firstorder definable structure over (V ; +) with domain V is called a reduct of (V ; +). This talk presents a method combining universal algebra, model theory and Ramsey theory in order to classify the complexity of CSPs over reducts of (V ; +). 
Fr., 21.8.2015, 16:15 Uhr, WIL/C/129  Zu formalen Kontexten mit gegebener FerrerskKodimension Anna Thurm (Verteidigung der Diplomarbeit, Betreuer: Prof. B. Ganter) 
Fr., 14.8.2015, 16:15 Uhr, WIL/C/129  Automatic Construction of Implicative Theories for Mathematical Domains Artem Revenko Implication is a logical connective corresponding to the rule of causality "if ... then ...". Implications allow one to organize knowledge of some field of application in an intuitive and convenient manner. This thesis explores possibilities of automatic construction of all valid implications (implicative theory) in a given field. As the main method for constructing implicative theories a robust active learning technique called Attribute Exploration was used. Attribute Exploration extracts knowledge from existing data and offers a possibility of refining this knowledge via providing counterexamples. In frames of the project implicative theories were constructed automatically for two mathematical domains: algebraic identities and parametrically expressible functions. This goal was achieved thanks both pragmatical approach of Attribute Exploration and discoveries in respective fields of application. The two diverse application fields favourably illustrate different possible usage patterns of Attribute Exploration for automatic construction of implicative theories. 
Fr., 24.7.2015, 13:15 Uhr, WIL/C/115  On simple compact topological semirings Jens Zumbrägel 
Fr., 17.7.2015, 13:15 Uhr, WIL/C/115  Bipartite Kneser graphs are Hamiltonian, Dr. Torsten Muetze (ETH Zuerich) For integers k>=1 and n>=2k+1, the bipartite Kneser graph H(n,k) is defined as the graph that has as vertices all kelement and all (nk)element subsets of {1,2,...,n}, with an edge between any two vertices (=sets) where one is a subset of the other. It has long been conjectured that all bipartite Kneser graphs have a Hamilton cycle, i.e., a cycle that visits every vertex exactly once. The special case of this conjecture concerning the Hamiltonicity of the graph H(2k+1,k) became known as the 'middle levels conjecture' or 'revolving door conjecture', and has attracted particular attention over the last 30 years. One of the motivations for tackling these problems is an even more general conjecture due to Lovász, which asserts that in fact every connected vertextransitive graph (as e.g. H(n,k)) has a Hamilton cycle (apart from five exceptional graphs). 
Fr., 3.7.2015, 13:15 Uhr, WIL/C/115  Higher commutators: Results and open problems Dr. Nebojša Mudrinski (U Novi Sad) 
Fr., 19.6.2015, 13:15 Uhr, WIL/C/115  Structures with a Maltsev Polymorphism Christoph Glinzer (Vorstellung der Bachelorarbeit; Betreuer: Manuel Bodirsky) Constraint Satisfaction Problems over the Integers with Successor Antoine Mottet Abstract: I will present a dichotomy result for the complexity of constraint satisfaction problems whose templates are firstorder definable in (Z;succ), the integers with the successor function. This structure is neither finite nor omegacategorical, and therefore the classical universal algebraic approach cannot be used in this case. We will see how to adapt this approach in our setting, using the modeltheoretic notion of saturation. This is joint work with Manuel Bodirsky and Barnaby Martin. 
Fr., 29.5.2015, 13:15 Uhr, WIL/C/115  Profinite algebras and affine boundedness Martin Schneider Profinite algebras are topological algebras that are isomorphic to a projective limit of finite discrete algebras. In general this property concerns both the topological and algebraic characteristics of a topological algebra. However, for topological groups, rings, semigroups, and distributive lattices, profiniteness turns out to be a purely topological property as it is is equivalent to the underlying topological space being a Stone space, i.e. a totally disconnected compact Hausdorff space. 
Fr., 22.5.2015, 13:15 Uhr, WIL/C/115  On the reconstructibility of functions from identification minors Erkko Lehtonen (University of Lisbon) We consider functions of several arguments from $A$ to $B$, i.e., mappings $f \colon A^n \to B$ for some $n \geq 1$. For any $I = \{i, j\} \subseteq \{1, \dots, n\}$ with $i < j$, let $f_I \colon A^{n1} \to B$ be the function given by the rule $f_I(a_1, \dots, a_{n1}) = f(a_1, \dots, a_{j1}, a_i, a_j, \dots, a_{n1})$ for all $a_1, \dots, a_{n1} \in A$. (Note that $a_i$ occurs twice on the right side of the above equality: both at the $i$th and the $j$th position.) Such a function $f_I$ is called an \emph{identification minor} of $f$. We present some results  both positive and negative  and open problems concerning the following reconstruction problem: Is a function $f \colon A^n \to B$ uniquely determined, up to permutation of arguments, by the collection of its identification minors? A related open problem is to determine which functions have a unique identification minor. The speaker conjectures that for sufficiently large arity, the only functions with a unique identification minor are those which are 2settransitive or determined by the order of first occurrence, up to permutation of arguments. This talk is partly based on joint work with Miguel Couceiro and Karsten Schölzel. 
Fr., 8.5.2015, 13:15 Uhr, WIL/C/115  Finding pindecomposable Functions Artёm Revenko Parametric expressibility of functions is a generalization of expressibility via composition. All parametrically closed classes of functions form a lattice. For finite domains the lattice is shown to be finite, however straightforward iteration over all functions is infeasible, and so far the indecomposable functions are only known for domains with two and three elements. In this work we show how pindecomposable functions can be computed more efficiently by means of an extended version of attribute exploration  a robust active learning technique. Under certain assumptions it is possible to complete the lattice of parametrically closed classes of functions for a finite domain. 
Fr., 24.4.2015, 13:15 Uhr, WIL/C/115  Complexity Bounds For Arithmetic Nets And Some Related Problems Thomas Olschewski (TU Dresden) Determining the number of rational operations it takes to evaluate polynomials is a classical problem of algebraic complexity theory. Many lower and (somewhat fewer) upper bounds have been derived since the early 1970s which differ in coefficient field K, set of operations (division free or not ...), cost measure (nonscalar, multiplicative, additive, timespace tradeoff ...). For several types of polynomials evaluation complexity has been determined up to some constant factor, for some even exactly. For algebraically closed fields K the known methods for deriving lower bounds are mostly of an algebraic nature. In case of the binary field, counting methods and advanced proof methods have been employed for deriving lower and upper bounds. Subject of this talk are methods for proving lower bounds for arithmetic nets and some more recent results. 
Fr., 17.4.2015, 13:15 Uhr, WIL/C/115  Endomorphisms monoids of omegacategorical structures Michael Kompatscher (TU Wien) Two omegacategorical structures are biinterpretable iff their automorphism groups are isomorphic as topological groups. For a lot of wellknown omegacategorical structures this theorem still holds, if we ignore the topology. Is this true in general? The answer is no: In 1990 Evans and Hewitt constructed two omegacategorical structures with isomorphic, but not topologically isomorphic automorphism groups. In my talk I want to discuss their example and show that also the endomorphism monoids of the structures are isomorphic, but not topologically isomorphic. 
Mi., 1.4.2015, 14:00 Uhr, WIL/C/207  Konstruktion und Validierung von Wissensstrukturen mit den Methoden der Formalen Begriffsanalyse Matthias Lange (Verteidigung der Diplomarbeit; Betreuer: Prof. B. Ganter) 
 Semester Break   
Fr., 27.3.2015, 13:15 Uhr, WIL/C/115  Generated Groups, Shellability and Transitivity of the Hurwitz Action Henri Mühle (U Paris 7) Abstract: Let G be a group generated by a conjugation closed set A. There is a natural action of the braid group on k strands on the set of reduced Adecompositions of any group element of length k, the Hurwitz action. It can informally be described as ``shifting letters to the right, and conjugating as you go''. Whenever this action is transitive, we can deduce important geometric and representationtheoretic consequences. Moreover, in the given setting we can naturally define a subword order on G, and it is immediate the reduced Adecompositions of any group element are in bijection with the maximal chains in the principal order ideal generated by this element. Using this perspective, we present a new approach to proving the transitivity of the Hurwitz action, in that we establish a connection between the shellability of this subword order and the Hurwitz transitivity. This work, which is joint work with Vivien Ripoll from the University of Vienna, culminates in the observation that these two properties (whose proofs are in general far from being trivial) follow from a simple local criterion, namely the existence of a wellbehaved total order of A. 
Mo., 23.3.2015, 13:00 Uhr, WIL/C/115  translation invariant maxclosed semilinear constraints over the reals, and connections to stochastic games Marcello Mamino 
Fr., 13.3.2015, 14:00 Uhr, WIL/C/129  Forbidden Permutation Patterns and Constraint Satisfaction Problems Verteidigung der Diplomarbeit von Tom Hanika (Betreuer: Manuel Bodirsky) 
Fr., 20.2.2015, 13:15 Uhr, WIL/C/115  Forbidden Permutation Patterns and Constraint Satisfaction Problems Tom Hanika 
Do., 12.2.2015, 13:15 Uhr, WIL/C/115  GAP  Groups, Algorithms, Programming  a System for Computational Discrete Algebra Sven Reichard 
Fr., 6.2.2015, 13:15 Uhr, WIL/C/115  Group extensions as binary relation orbifolds Tobias Schlemmer 
Fr., 30.1.2015, 13:15 Uhr, WIL/C/102  Extremely amenable groups Martin Schneider 
Fr., 16.1.2015, 13:15 Uhr, WIL/C/102  Some enumerative and lattice theoretic aspects of islands and related investigations Eszter K. Horvath (Szeged) 
Fr., 9.1.2015, 13:15 Uhr, WIL/C/102  Centralizer clones Reinhard Pöschel 
Fr., 19.12.2014, 13:15 Uhr, WIL/C/207  Homomorphic Signatures for Network Coding Johannes Greiner 
Fr., 12.12.2014, 13:15 Uhr, WIL/C/207  The Discrete Logarithm Problem in finite fields of small characteristic Jens Zumbrägel 
Fr., 5.12.2014, 13:15 Uhr, WIL/C/102  Homomorphic Signatures for Network Coding Johannes Greiner 
Fr., 21.11.2014, 13:15 Uhr, WIL/C/102  On an algorithmic problem of weighted Markov chains Daniel Krähmann (Fak. Informatik) 
Fr., 14.11.2014, 13:15 Uhr, WIL/C/102  Galois theory for semiclones Mike Behrisch (U Linz) 
Fr., 7.11.2014, 13:15 Uhr, WIL/C/102  Reconstructing cyclefree partial orders from their abstract automorphism groups Robert Barham 
Fr., 17.10.2014, 13:15 Uhr, WIL/C/102  Concepts of Connection in Directed Hypergraphs Paul Mittelstädt 