International Seminar
In this work-in-progress-seminar, current research results of members of our institute are discussed and further developed.
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, WIL/C115 |
open problems session |
Friday, 8.9.2017, 13:15, |
Free combinations of omega-categorical structures |
Friday, 1.9.2017, 13:45, WIL/C115 |
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 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 NP-hardness 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. 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. |
Friday, 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. |
Friday, 2 June .2017, 13:15, WIL/C115 |
Parking Functions and Noncrossing Partitions |
Friday, 26 May .2017, 13:15, WIL/C115 |
Towards a non-commutative Chevalley-style 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 (Martin-Andersen-Nexö-Gymnasium Dresden) |
Friday, |
Complexity of NP-Complete Constraint Satisfaction Problems |
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 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. |
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 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. |
Friday, |
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. |
Friday, |
Introduction to mean-payoff 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 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. |
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 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. |
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 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. |
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 |
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 |
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. |
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. |
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 ; +). |
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). |
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. |
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. |
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 |