International Seminar

In this work-in-progress-seminar, current research results of members of our institute are discussed and further developed.

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
Eszter K. Horváth (U Szeged)
For every natural number n ≥ 5, we prove that the number of subuniverses of an n-element lattice is 2^n, 13 · 2^(n−4) , 23 · 2^(n−5) , or less than 23 · 2^(n−5). By a subuniverse, we mean a sublattice or the emptyset. Also, we describe the n-element lattices with exactly 2^n, 13 · 2^(n−4) , or 23 · 2^(n−5) subuniverses. In the talk, some other related results will be mentioned.

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 non-classical 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

Nazarov-Wenzl algebras, coideal subalgebras and categorified skew Howe duality
Catharina Stroppel  (U Bonn)

Wednesday, 28.11.2018, 13:15, WIL/C115

Large rigid sets of algebras
Danica Jakubikova-Studenovska  (U Košice, Slovakia)
Let $\tau$ be a nonempty similarity type of algebras. A set $H$ of $\tau$-algebras is called  rigid with respect to embeddability, if whenever $A,B\in H$ and $\varphi:A\to B$ is an embedding, then $A=B$ and $\varphi$ is the identity map. We prove that if $\tau$ is a nonempty similarity type and $\mathfrak m$ is a cardinal such that no inaccessible cardinal is smaller than or equal to $\mathfrak m$, then there exists a set $H$ of $\tau$-algebras such that $H$ is rigid with respect to embeddability and $|H|=\mathfrak m$.

Friday, 16.11.2018, 13:15, WIL/C133

HH-homogeneous graphs with infinite independence number.
Andrés Aranda
It is a well-known fact that any infinite graph G containing the Rado graph as a spanning subgraph is HH-homogeneous, meaning that any homomorphism between finite substructures can be extended to an endomorphism of G. In this talk, I will connect the seemingly unrelated property of having infinite independence number with the property of having the Rado graph as a spanning subgraph, and show as a corollary that all but four MB-homogeneous graphs H have the Rado graph as a spanning subgraph of both H and its complement.

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 non-trivial 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
Thomas Quinn-Gregson
A semigroup S is called homogeneous if every isomorphism between finitely generated subsemigroups of S extends to an automorphism of S. This work was motivated by the desire to construct interesting examples of omega-categorical semigroups. Indeed, a homogeneous structure which has the finiteness condition of being uniformly locally finite is necessarily omega-categorical.
In this talk we give an overview of how homogeneous semigroups may be built from homogeneous groups and labelled bipartite graphs. In particular, a complete description of all finite regular semigroups is given, which extends the group case given by Cherlin in 2000. We also discuss the importance of our choice of signature; be it semigroups, completely regular semigroups or inverse semigroups. This gives rise to the following open question: Is a homogeneous group a homogeneous semigroup?

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 non-commutative 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.
The result we will discuss is Shtipel'man's theorem, which states that every valuation on the first Weyl-field is abelian. The Weyl field is the skewfield of fractions of the ring of quantum mechanics and plays an important role in (some version of) non-commutative geometry.

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
Celestin Lele (University of Dschang, Cameroon)
The primary goal of this work is to extend the study of derivations to residuated multilattices, formulating the definitions and studying their first properties. In particular, we define the notions of multiplicative and implicative derivations on residuated multilattices. The connections between the existence of these derivations and existing algebraic properties of residuated multilattices are investigated. Moreover, given that residuated multilattices are fairly new, the derivations introduced here offer a different tool and prospective into their studies. It goes without saying that all the results obtained here will generalize both those from lattices by M. Kondo 2017 and also residuated lattices by J. Rachunek and D. Salounava 2017.

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 first-order 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 two-element 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 first-order reducts. It will give a proof of the complexity dichotomy for CSPs of first-order 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 well-known 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 well-known 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 black-box way. We prove for a certain class of structures that convexity is also necessary for polynomial-time tractability of the union of their first-order 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 first-order theories of A and B, where the signatures of A and B are assumed to be disjoint. Furthermore, its orbits of n-tuples are precisely the intersections of the orbits of n-tuples 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 polynomial-time 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 1-parameter 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 edge-coloring 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. Hestenes-Higman's t-vertex condition}). Instead of graphs we can consider (uniform) hypergraphs; this leads to k-ary coherent configurations (Babai, Immerman-Lander), which play a prominent role in recent advances in the study of the graph isomorphism problem.
It is known that the algorithm of Weisfeiler-Leman 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 past-finite-universal. 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 past-finite-universal.
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 NP-complete 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 NP-complete. 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 NP-complete. 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 n-tuples 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 first-order reducts of unary omega-categorical 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 first-order 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 cross-ratios
Yatir Halevi (Hebrew University of Jerusalem)
I will present a generalization of von Staudt's theorem that every permutation of the projective line that preserves harmonic quadruples is a projective semilinear map. From that I will conclude that any proper supergroup of permutations of the projective semilinear group over an algebraically closed field of transcendence degree at least 1 is 4-transitive.
Joint work with Itay Kaplan.

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/NP-c (respectively P/coNP-c) dichotomy in congruence modular varieties. This is based on joint work with Idziak and Krzaczkowski.
Friday, 20.4.2018, 13:15, WIL/C115 Surjective-morphism extension classes of graphs, part 2
Andrés Aranda
Two new morphism-extension classes were introduced recently for infinite relational structures: HE, the class of all L-structures such that any homomorphism between finite induced substructures extends to a surjective endomorphism, and MB, the class of all L-structures such that any monomorphism between finite induced substructures extends to a bijective endomorphism. In this talk, I will show that all MB-homogeneous graphs are HE-homogeneous and all "interesting" (i.e., not a union of finite cliques) HE-homogeneous graphs are MB-homogeneous. In the second talk, I will prove that every MB-homogeneous graph is HE-homogeneous.
Friday, 13.4.2018, 13:15, WIL/C115 Surjective-morphism extension classes of graphs
Andrés Aranda
Two new morphism-extension classes were introduced recently for infinite relational structures: HE, the class of all L-structures such that any homomorphism between finite induced substructures extends to a surjective endomorphism, and MB, the class of all L-structures such that any monomorphism between finite induced substructures extends to a bijective endomorphism. In this talk, I will show that all MB-homogeneous graphs are HE-homogeneous and all "interesting" (i.e., not a union of finite cliques) HE-homogeneous graphs are MB-homogeneous.
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 finite-dimensional 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 2-extension in terms of the degree of the algebra.
Friday, 23.2.2018, 13:15, WIL/C115 Counting relational structures
Leopold Schlicht (Hans-Erlwein-Gymnasium 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 quasi-polynomial.

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 Congruence-Uniform Lattices
Henri Mühle
A (finite) lattice L is congruence-uniform 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 edge-labeling 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 congruence-uniform lattice, then the alternate order is a lattice, too.  In general, however, it is an open problem to characterize the congruence-uniform 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 quasi-finite 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 L-colored graphs
Andrés Aranda
An L-structure M is in HH_L (homomorphism-homogeneous) 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 L-colored 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 vertex-uniform (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 L-colored graphs when L is a linear order, give an example of an infinite MH L-colored graph that is not HH when L is a diamond, and prove that if MH=HH for infinite vertex-uniform L-colored graphs, then L is a join-semilattice. This is joint work with David Hartman.
Wednesday 17.1.2018, 13:15, WIL/C115 CD-independent subsets
Eszter Horváth (University of Szeged)
A subset X of a finite lattice L is called CD-independent if the meet of any two incomparable elements of X equals 0. Czédli, Hartmann and Schmidt has an important result about CD-bases (maximal CD-independent subsets) of distributive lattices. In the talk, we define CD-independent subsets in an arbitrary poset in a natural way. Actually, CD-independence is in close relationship with trees. More precisely, if we have a CD-independent subset in a poset and we remove its possible 0, then we obtain a forest.  We show that the CD-bases of any poset can be characterized as maximal chains in a related poset. We use this result to investigate CD-bases in semilattices and in more general lattice classes. Finally, I give some overview about other results, in particular about some combinatorial aspects of CD-independence.
Friday 12.1.2018, 13:15, WIL/C115

Solution sets of systems of equations
Tamás Waldhauser (University of Szeged)
Solution sets of systems of homogeneous linear equations over fields are characterized as being subspaces, i.e., sets that are closed under linear combinations. But what can we say about the "shape" of the set of all solutions of systems of equations over arbitrary algebras? We prove that if such solution sets can be characterized as sets being closed under "something", then this "something" must be the centralizer of the clone of term operations of the algebra. For two-element algebras, such a characterization does indeed work, but this is not the case for larger algebras. This naturally raises the problem of describing those clones C for which solution sets of systems of equations over C are exactly the invariant relations of the centralizer clone C*. We present some results of ongoing work on this problem that were obtained together with Endre Tóth, an MSc student at the university of Szeged.

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 finitely-constrained 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 pp-sentence φ 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 d-clique and a e-clique for fixed e>d): the goal is to decide whether a given graph is d-colorable or not even e-colorable. The complexity of this graph coloring is mostly open, but believed to be NP-hard 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 follow-up, 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 first-order definable in various o-minimal 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
Danica Jakubíková-Studenovská (P.J. Šafárik University, Košice)
A class of algebraic structures can be ordered with respect to homomorphisms (B. Davey, SSAOS 2017): A<B if there is a homomorphism of A into B. This is a quasiorder; for equivalence classes we get a lattice, where join is a direct product and meet is a disjoint sum of structures. We will deal with the class of connected monounary algebras. A disjoint sum of connected monounary algebras fails to be connected and also a direct product of connected algebras can be non-connected. However, it will be proved that the class L of all connected monounary algebras ordered with respect to homomorphisms (factorized by the corresponding equivalence) is a bounded lattice. Further, L is glued from two parts: the upper part is a countable and distributive lattice, from below bounded by the largest element of the second part, and the second part is a lattice (not a set, but a proper class). Each antichain in L is a set containing at most continuum elements. Moreover, there exists an antichain having exactly continuum elements.

Friday, 17.11.2017, 13:15, WIL/C115

Time Complexity of NP-Hard CSPs
Victor Lagerqvist
The constraint satisfaction problem over a constraint language Gamma (CSP(Gamma)) is the computational decision problem of checking whether a set of constraints over Gamma is satisfiable. Recently, two independent results have settled the long-standing conjecture that CSP(Gamma) is always either tractable or NP-complete for constraint languages over finite domains. In this seminar we will look at the related question of studying the variance of time complexity NP-hard CSP(Gamma) problems. More concretely, fix a finite domain D. Is it then possible to describe all NP-hard CSP(Gamma) such that CSP(Gamma) is solvable in O(c^n) time, where c < |D|, and n denotes the number of variables? In other words we are interested in classifying NP-hard CSPs that can be solved strictly faster than the naive algorithm of enumerating all assignments over the domain. We will see that the algebraic approach can play a significant role in this pursuit if one considers partial operations arising from strong Maltsev conditions.

Friday, 10.11.2017, 13:15, WIL/C115

Profiniteness in finitely generated varieties is undecidable
Michał M. Stronkowski (Warsaw University of Technology)
Joint work with Anvar M. Nurakunov (Institute of mathematics, National Academy of Sciences, Kyrgyzstan).
Profinite algebras are exactly those that are isomorphic to inverse limits of finite algebras. Such algebras are naturally equipped with Boolean topologies. A variety V is standard if every Boolean topological algebra with the algebraic reduct in V is profinite. We show that there is no algorithm which takes as input a finite algebra A of a finite type and decide whether the variety V(A) generated by A is standard. We also show the undecidability of some related properties. In particular, this allowed us to solve one of the problems posed by Clark, Davey, Freese and Jackson.

Friday, 3.11.2017, 13:15, WIL/C115

Homogeneous structures and a new poset
Bertalan Bodor
In 1991 Thomas conjectured that every homogeneous countable structure over a finite relational language has finitely many reducts. This has been solved for several individual structures, but we still don't know much in general. In this talk I will talk about a possible generalization of Thomas' conjecture involving a new poset of structures.

Friday, 27.10.2017, 13:15, WIL/C115

Twisting the zero-divisors away
Nikolaas Verhulst
In this talk, we will explore the wonderful world of classical algebra, more precisely of field arithmetic. Here, division algebras, i.e., finite dimensional associative algebras without zero-divisors, play a crucial role. The goal is to get a better understanding of these beasts. We will see how finite dimensional algebras, like most things in life, can be understood with linear algebra. This will allow us to talk about determinants of elements which, in turn, allows us to compute zero-divisors. I will explain how an algebra can be twisted and why this (sometimes) eliminates zero-divisors. Some interesting, and possibly not too hard, open problems will be stated.

Tuesday, 24.10.2017, 11:00, WIL/C115

A Dichotomy Theorem for the Inverse Satisfiability Problem
Biman Roy (Linköping University)
The inverse satisfiability problem over a set of Boolean relations Γ (Inv-SAT(Γ)) is the computational decision problem of, given a relation R, deciding whether there exists a SAT(Γ) instance with R as its set of models. This problem is co-NP-complete in general and a dichotomy theorem for finite Γ containing the constant Boolean relations was obtained by Kavvadias and Sideri. In this paper we remove the latter condition and prove that Inv-SAT(Γ) is always either tractable or co-NP-complete for all finite sets of relations Γ, thus solving a problem open since 1998. Very few of the techniques used by Kavvadias and Sideri are applicable and we have to turn to more recently developed algebraic approaches based on partial polymorphisms. We also consider the case when Γ is infinite, where the situation differs markedly from the case of SAT. More precisely, we show that there exists infinite Γ such that Inv-SAT(Γ) is tractable even though there exists finite ∆ ⊂ Γ such that Inv-SAT(∆) is co-NP-complete.

Friday, 20.10.2017, 13:15, WIL/C115

Ultraproducts preserve finite subdirect reducibility
Anvar Nurakunov (Institute of mathematics, National Academy of Sciences, Kyrgyzstan)
An algebraic structure A is said to be finitely subdirectly reducible if A is not finitely subdirectly irreducible. We show that for any signature providing only finitely many relation symbols, the class of finitely subdirectly reducible algebraic structures is closed with respect to the formation of ultraproducts. We provide some corollaries and examples for axiomatizable classes that are closed with respect to the formation of finite subdirect products, in particular, for varieties and quasivarieties.

Friday, 13.10.17, 13:15,

open problems session

Friday, 8.9.2017, 13:15,

Free combinations of omega-categorical structures
Johannes Greiner
In order to analyze the tractability of constraint satisfaction problems of omega-categorical structures, we introduce the notion of a free combination. The new notion describes a combination of the constraint satisfaction problem over a structure A with the constraint satisfaction problem over a structure B. In this talk, we provide a necessary and sufficient condition for the existence of a free combination of two omega-categorical structures and present a new classification result using the notion.

Friday, 1.9.2017, 13:45,
Monotone Monadic SNP 2: proof of the universal-algebraic dichotomy conjecture
Antoine Mottet (joint work with Manuel Bodirsky)
The forbidden patterns problem of the set of vertex-coloured 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 NP-complete). Feder and Vardi showed that every problem in MMSNP reduces in probabilistic polynomial-time to the CSP of a structure with finite domain, and Kun later derandomized this reduction. Thus, MMSNP and finite-domain CSPs are computationally equivalent.

Following up on Manuel's talk, I will present a completely new reduction from MMSNP to finite-domain CSPs that uses recent techniques and results from universal algebra, model theory, and Ramsey theory. This proves a stronger form of the Feder-Vardi-Kun result, and shows in particular that the Bodirsky-Pinsker tractability conjecture holds for all CSPs in
Friday, 1.9.2017, 13:15, WIL/C115

Monotone Monadic SNP 1: classical results and applications
Manuel Bodirsky (joint work with Antoine Mottet; 30 min. workshop talk for QuantLA)
The logic MMSNP is a restricted fragment of existential second-order logic which allows to express many interesting queries in graph theory, database theory, and finite model theory. The logic was introduced by Feder and Vardi who showed that every MMSNP sentence is polynomially equivalent to a finite-domain constraint satisfaction problem (CSP); the clever probabilistic reduction was derandomized by Kun using explicit constructions of expander structures. Several authors have recently announced proofs that every finite-domain CSP is either in P or NP-complete; hence, the same is true for MMSNP.

We present a new proof of the complexity dichotomy for MMSNP. Our new proof has the advantage that it confirms a tractability conjecture by Pinsker and myself that we have made for a much larger class of computational problems. Another advantage is that it does not rely on the intricate expander constructions of Kun (but we do use the finite domain CSP dichotomy). Our approach is based on the fact that every MMSNP sentence can be effectively rewritten into a finite union of CSPs for countably infinite omega-categorical structures; moreover, by a recent result of Hubička and Nešetřil, these structures can be expanded to homogeneous structures with finite relational signature and the Ramsey property. This allows us to use the universal-algebraic approach to study the computational complexity of MMSNP.

In this first part of the talk we will give an introduction to MMSNP with many examples and the classical results, including the Feder-Vardi reduction to finite-domain CSPs, but also usages of MMSNP to classify the complexity of problems that arose in the context of descriptions logics (by Bienvenu, ten Cate, Lutz, Wolter). In the second part, Antoine presents our new analysis of MMSNP sentences using the universal-algebraic approach and Ramsey theory.

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 NP-hardness condition for semilinear VCSPs.
This is joint work with M. Bodirsky and M. Mamino.
30 June 2017, 9:30, WIL/C207

Polynomial growth of concept lattices, canonical bases and generators: extremal set theory in Formal Concept Analysis
Alexandre Albano (disputation of the dissertation., supervisor: Prof. B. Ganter)

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. Weisfeiler-Leman (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 two-dimensional 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.
S-rings are two-dimensional coherent configurations which admit a regular group of automorphisms. They play a role in the theory of Cayley graphs. The set of S-rings over a given group G is related to the set of two-closed overgroups of the regular action of G. Knowledge of their structure helps us solve the isomorphism problem for Cayley graphs over G. Enumeration of S-rings is hard, but it provides plenty of opportunity for efficient implementation.
9 June .2017,
13:15, WIL/C115
Reflection-closed 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 reflection-closed varieties (RP-varieties) and consider the Galois connection Mod-mId 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 reflection-closed varieties of multisorted algebras, i.e., Mod mId K = RP K. Similarly, we characterize the minor-equational theories of multisorted algebras, i.e., the closed sets of minor identities. We also discuss how RP-varieties and usual varieties of multisorted algebras are related to each other.

This is joint work with Tamás Waldhauser.
2 June .2017,
13:15, WIL/C115

Parking Functions and Noncrossing Partitions
Henri Mühle
A sequence of integers (a_1,a_2,...,a_n) is a parking function of length n if its nondecreasing rearrangement (b_1,b_2,...,b_n) satisfies b_i ≤ i.  It is well known that there are precisely (n+1)n-1 parking functions of length n.  Perhaps most prominently, parking functions show up in the study of the space of diagonal harmonics; in fact they index a basis of this space. The Shuffle Conjecture asserts that the bigraded Frobenius characteristic of this space can be expressed combinatorially as a sum over all parking functions.  This conjecture was recently generalized to involve a sum over parking functions with undesired spaces.  Richard Stanley gave a bijection between parking functions of length n-1 and maximal chains in the lattice of noncrossing partitions of an n-element set.  It is only natural to study the subposet of noncrossing partitions coming from parking functions with undesired spaces.  We outline the constructions mentioned above and present recent results on the structure and topology of these posets. 

26 May .2017,
13:15, WIL/C115

Towards a non-commutative Chevalley-style algebraic geometry
Nikolaas Verhulst
In the commutative case, there exists a kind of translation mechanism between algebra and geometry. This mechanism relies heavily on the concept of valuation rings. Therefore, when one wants to generalise it to a non-commutative setting, one needs a convenient notion of non-commutative valuation rings. I will introduce G-valuation rings and explain why these are logical candidates and, time permitting, briefly sketch some connections with previously suggested generalisations of valuation rings.

12 May 2017, 13:15, WIL/C115

Complexity of term representations of functions
Jakub Opršal
One way to measure complexity of terms of a finite algebra is to count how many symbols are needed to write down a term describing a particular n-ary term operation, and taking the maximum of these values among all n-ary term operations of the algebra. We will talk about several results about the asymptotics of this sequence.
(This is a joint work with E. Aichinger and N. Mudrinski.)

28 April 2017,

Residuated multilattices: the first glimpse into their structure
Line N. N. Maffeu
We prove that when either divisibility or prelinearity is added to a residuated multilattice, this causes the multilattice structure to collapse down to a residuated lattice. In addition semi-divisibility and regularity are studied on residuated multilattices. The ordinal sum construction is also applied to residuated multilattices as a way to construct new examples of both residuated multilattices and consistent filters. Finally, it is also established that the smallest residuated multilattice that is not a residuated lattice has order 7.

21 April 2017,
13:15, WIL/C115
Primitive positive definability over complex numbers
Sebastian Meyer (Martin-Andersen-Nexö-Gymnasium Dresden)

7 April 2017
13:15 WIL/C115 .

Complexity of NP-Complete Constraint Satisfaction Problems
Victor Lagerqvist
In this talk we will look at some recent developments in analyzing the time complexity of NP-complete constraint satisfaction problems, and algebraic methods to study this question. In particular we will study properties of partial operations definable by sets of equations, and see that such operations share several properties with the corresponding total operations, which can be exploited in for example kernelization algorithms and when constructing exponential-time algorithms better than brute force search.    .

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 VC-dimension. 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.
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.
20 Jan 2017, 13:15, WIL/C115
Supersingular Isogeny Diffie-Hellman Key Exchange
Juliane Prochaska (TU Dresden)
The Diffie-Hellman key exchange is a well-known and important protocol in modern cryptographic applications. It is, however, vulnerable to quantum algorithms. A promising candidate for post-quantum cryptography is the supersingular isogeny Diffie-Hellman 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.

9 Dec 2016,
13:15, WIL/C115

Upper bounds for the number of Galois-closed sets arising from finite binary relations
Alexandre Albano
We will do a gentle and short introduction to Formal Concept Analysis and give a mini-survey of results associated to the FCA-motivated 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.

2 Dec 2016, 13:15, WIL/C115

Introduction to mean-payoff games
Marcello Mamino

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:
(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?
(i) Is every monoid of transformations of a non-empty 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 non-empty 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.

25 Nov 2016, 13:15, WIL/C115

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 rational-valued 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 first-order 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 polynomial-time 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 polynomial-time solvable.
18 Nov 2016, 13:15, WIL/C115
open problems session
11 Nov 2016, 13:15, WIL/C115

Indecomposabilty of two equational theories
Jakub Opršal

We will discuss the indecomposability of two Mal'cev conditions—namely the conditions describing congruence modular varieties, and varieties that are congruence n-permutable 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.

4 Nov 2016, 13:15, WIL/C115

On Noncrossing Partitions
Henri Mühle
Noncrossing partitions are, in their original form, the set partitions whose blocks have a certain "noncrossing" property.  Equipped with (dual) refinement, they form a lattice with a rich combinatorial structure.  Somewhat surprisingly this lattice has appeared in different guises in many different disciplines, such as group theory, algebraic topology, free probability, representation theory, and combinatorics. In the late 1990s several mathematicians made the striking observation that the lattice of noncrossing set partitions arises in a natural way as a structure on the symmetric group, and that analogous structures can be defined for other reflection groups, too.  In particular, these "generalized" noncrossing partition lattices possess most of the (structural and enumerative) properties of the original.  A whole branch of combinatorics, usually called Coxeter-Catalan combinatorics, is nowadays dedicated to the study of these objects and their interplay with other equinumerous objects.

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.

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.
21 Oct 2016, 13:15, WIL/C204

open problems session

problems presented by participants

14 Oct 2016, 13:15, WIL/C207

Minors of functions and permutations, reconstruction problems, and the order of first occurrence

Erkko Lehtonen
Fr., 15.7.2016, 13:15 Uhr, WIL/C115 Enumeration of S-rings over the elementary abelian group of order 64
Sven Reichard
S-rings, as introduced by Schur and Wielandt, are certain subrings of the group ring C[G] for a finite group G. There is a one-to-one correspondence between S-rings 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.
S-rings 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 S-rings 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 first-order theories
André Schrottenloher (École polytechnique, TU Dresden)
We study the decidability of various properties that one might ask for finite universal first-order 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 universal-negative 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 first-order 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 well-studied 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
A strong partial clone is a set of partial functions which (1) is closed under functional composition and (2) contains all partial projection functions. We will study the following question: given a strong partial clone, how can one describe its maximal strong partial subclones? We will see that for many interesting cases which are relevant for constraint satisfaction problems, this question is likely at least as difficult as describing all submaximal strong partial clones; a question which despite intense research has not been fully answered even for the Boolean domain.

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 non-empty 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 (Humboldt-Universitä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 so-called k-consistency 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 k-consistency 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 k-consistency test that have been obtained via this pebble game in the last years.
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 well-known fact that sets of relations invariant under partial functions can be characterized by primitive positive definitions without existential quantification. These quantifier-free 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 fine-grained enough. We are going to see applications of partial clone theory to study the worst-case time complexity of NP-complete 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 Lattice-valued 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 NP-complete if and only if the Feder-Vardi conjecture for finite-domain 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 so-called 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 polynomial-time 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 Constraint-Satisfaction-Probleme (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 NP-vollstä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 second-order 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 chip-firing game model
Trung Van Pham

Chip-firing 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 chip-firing 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.
The Tractability Conjecture, formulated by Bulatov/Krokhin/Jeavons 2000 states that Constraint Satisfaction Problems are tractable if they have certain algebraic properties and if they do not have these properties, they are NP-complete. This can be reformulated in terms of the existence of certain polymorphisms. It has been confirmed for several classes of finite structures, but is still open for CSPs of digraphs and even orientations of trees. To systematically verify the conjecture for orientations of trees by computational means was one goal of my work, and in the talk I will present my results on this task.
Some types of polymorphisms are related in a way that the existence of one type implies the existence of another. Types that are not related in general structures can become related when the structures are special. For example, Malcev polymorphisms and majority polymorphisms are not related in the general case, but if the structure is a digraph, the existence of the former implies the existence of the latter. To look for this kind of emerging connections in orientations of trees was another goal of my work and the results will be presented as well.

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 sub-pattern. Their investigation was inspired by methods from formal concept analysis.
For the purpose of being able to reduce complexity, they introduced projections of pattern structures, which were modeled as kernel operators on the poset of patterns. They assumed that projections are infimum preserving, however this is not always the case. Subsequently, this concept of projection led to some confusion and errors, which could only partially being fixed.
Only this year, we provided an example where a certain projection of a pattern structure is not again a pattern structure.  For residual projections however, the answer is always positive. Independently, Buzmatov et alii considered projections and restricted the codomain of a projection to its image. These restrictions of projections they called o-projections and proved that o-projections of pattern structures are again pattern structures.
In our talk we give a definition of morphism between pattern structures that includes residual projections and o-projections as special instances. From a general reasoning about morphisms between poset adjunctions we derive some interesting insights, which in particular justify our concept of morphism between pattern structures.

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 non-zero 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 two-element field. A first-order 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 ; +).
Besides establishing P/NP-complete dichotomy results for the complexity of the CSPs for nearly every reduct of (V ; +), this approach yields on the way an algebraic description of the lattices of automorphism groups and monoids of self-embeddings of reducts of (V ; +). A sizeable part of the lattice of endomorphism monoids of reducts of (V ; +) is then described. Lastly, endomorphism monoids of model-complete cores of reducts of (V ; +) are fully classfiied, foraying toward a dichotomy classication result for CSPs.

Fr., 21.8.2015, 16:15 Uhr, WIL/C/129 Zu formalen Kontexten mit gegebener Ferrers-k-Kodimension
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 counter-examples. 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 k-element and all (n-k)-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 vertex-transitive graph (as e.g. H(n,k)) has a Hamilton cycle (apart from five exceptional graphs).
Last year I presented a rather technical proof of the middle levels conjecture in the seminar. In this talk I present a simple and short proof that all bipartite Kneser graphs H(n,k) have a Hamilton cycle, assuming that H(2k+1,k) has one. No prior knowledge will be assumed for this talk.

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 first-order definable in (Z;succ), the integers with the successor function. This structure is neither finite nor omega-categorical, 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 model-theoretic 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.
I will introduce the concept of affine boundedness for an arbitrary algebra and show that for an affinely bounded topological algebra over a compact signature profiniteness is equivalent to the underlying topological space being a Stone space. Since groups, semigroups, rings, and distributive lattices are indeed affinely bounded algebras over finite signatures, all these known cases arise as special instances of the presented result. Furthermore, I will discuss some additional examples.

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^{n-1} \to B$ be the function given by the rule $f_I(a_1, \dots, a_{n-1}) = f(a_1, \dots, a_{j-1}, a_i, a_j, \dots, a_{n-1})$ for all $a_1, \dots, a_{n-1} \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 2-set-transitive 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 p-indecomposable 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 straight-forward 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 p-indecomposable 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.
Attribute exploration relies on the routine of finding counter-examples to attribute implications. This routine will be the focus of the talk.

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 (non-scalar, multiplicative, additive, time-space 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 omega-categorical structures
Michael Kompatscher (TU Wien)

Two omega-categorical structures are bi-interpretable iff their automorphism groups are isomorphic as topological groups. For a lot of well-known omega-categorical 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 omega-categorical 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)
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 A-decompositions 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 representation-theoretic consequences. Moreover, in the given setting we can naturally define a subword order on G, and it is immediate the reduced A-decompositions 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 well-behaved total order of A.

Mo., 23.3.2015, 13:00 Uhr, WIL/C/115 translation invariant max-closed 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 cycle-free 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

Zu dieser Seite

Letzte Änderung: 08.01.2019