[ Home ]   [ Current ]   [ Archive ]



Seminar za Logiku, Algebru, DIskretnu Matematiku i teorijsko računarstvo
Logic, Algebra, DIscrete Mathematics and Theoretical Computer Science Seminars

Školska 2023/24. / Academic year 2023/24

09/02/2024

Kristina Asimi (University of Durham, UK): (Promise) Constraint Satisfaction Problem

In this lecture, I will present the basics of the Constraint Satisfaction Problem (CSP) and one of its generalizations, the Promise Constraint Satisfaction Problem (PCSP). In the final part, I will present some special classes of PCSP, the so called not finitely tractable PCSPs. Namely, all the currently known tractable (i.e., solvable in polynomial time) PCSPs over finite templates can be reduced to tractable CSPs and I will present some classes of PCSPs for which that CSP has to be over an infinite domain (unless P=NP).

17/01/2024

Boriša Kuzeljević (DMI PMF NS): Lower bounds of P-point ultrafilters

The Rudin-Keisler ordering was introduced in the early seventies of the twentieth century. In the talk, we will give some historical background of this notion, and then focus on the structure of P-point ultrafilters under this ordering. Since P-points form a downward closed subset of the set of all ultrafilters on the set of natural numbers, this provides some global information about the lower part of this class. We will present some recent results on the existence of lower bounds of sets of P-points, obtained in a joint work with Dilip Raghavan and Jonathan Verner.

08/12/2023

Petar Marković (DMI PMF NS): The Constraint Satisfaction Dichotomy Conjecture: History, proofs and generalizations

The Constraint Satisfaction Problem was defined in the 1990s inspired by certain topics in Descriptive Complexity. At that time, the Dichotomy Conjecture on the complexity of the Constraint Satisfaction Problem was posed. The Dichotomy Conjecture was proved a quarter of a century later, in 2017, independently by Andrei Bulatov and Dmitriy Zhuk. In this lecture I will define the Constraint Satisfaction Problem, motivate the Dichotomy Conjecture, and survey the main ideas in the proofs by Bulatov and Zhuk. In the final part, I will briefly describe the two most popular generalizations which are a focus of research by numerous teams since the proof of the Dichotomy Conjecture, introduce a third possibility of generalizing the Dichotomy Conjecture and argue why this third topic should also be in the focus of research.

17/11/2023

Edward T. Dobson (University of Primorska, Koper, Slovenia): Towards inductive proofs in algebraic combinatorics

One of the main obstacles to solving problems concerning automorphism groups of vertex-transitive graphs and digraphs is that the natural factors of the automorphism group do not necessarily give groups that are automorphism groups of vertex-transitive graphs or digraphs (or even 2-closed groups). Thus using induction can be difficult. We find a class of transitive permutation groups, which properly contains the automorphism groups of vertex-transitive graphs and digraphs, and call them 5/2-closed, as, using Wielandt's hierarchy of permutation groups, the class is larger than 2-closed but contain groups which are not 3-closed. We give a sufficient condition for the natural quotients of transitive groups in this class to remain in this class, in effect giving a sufficient condition for natural inductive proofs to work. We will then give examples of results that have been proven for this new class, solving several problems concerning isomorphisms between combinatorial objects, automorphism groups of combinatorial objects, and more.

Ademir Hujdurović (University of Primorska, Koper, Slovenia): Erdős-Ko-Rado property of transitive permutation groups

The Erdős-Ko-Rado theorem is one of the central results in extremal combinatorics. It gives a bound on the size of a family of intersecting k-subsets of a set and classifies the families satisfying the bound. In this presentation I will talk about the classical Erdős-Ko-Rado theorem and its extension to transitive permutation groups. I will present some known and some new results on the maximum sizes of intersecting sets in certain permutation groups. We will see how the construction of certain cyclic codes was used for disproving a recent conjecture regarding transitive groups of degree a product of two primes. Several open problems will be presented.

[ Home ]   [ Current ]   [ Archive ]