National Institute of the Republic of Serbia

ὅδε οἶκος, ὦ ἑταῖρε, μνημεῖον ἐστιν ζωῶν τῶν σοφῶν ἀνδρῶν, καὶ τῶν ἔργων αὐτῶν

**PROGRAM**

ODELJENJE ZA MATEMATIKU MATEMATIČKOG INSTITUTA SANU |

Registracija za učešće na seminaru je dostupna na sledećem linku:

https://miteam.mi.sanu.ac.rs/asset/tz97w4Hu4c3unsJ7N.

Ukoliko ste vec registrovani predavanje možete pratiti na sledećem linku (nakon sto se ulogujete):

https://miteam.mi.sanu.ac.rs/asset/J6zEMJyMSoAbTMMX7.

Neulogovani korisnici mogu pratiti prenos predavanja na ovom linku (ali ne mogu postavljati pitanja osim putem chata i ne ulaze u evidenciju prisustva):

https://miteam.mi.sanu.ac.rs/call/T9XDGChhq8aDcNqmz/qw7wIwci2jv2rdg9I9CrXkm7OJhF_LB8DfjXZp4jTFV.

**PROGRAM ZA NOVEMBAR 2023.**

**Petak, 03.11.2023. u 14:15, Kneza Mihaila 36, sala 301f i**** On-line**

*Melanija Mitrović, Mašinski fakultet, Niš*

**CONSTRUCTIVE SEMIGROUPS WITH APARTNESS: BASICS AND POTENTIAL APPLICATIONS**

This talk aims to provide a clear and understandable picture of constructive semigroups with apartness. Our theory is partly inspired by the classical case, but it is distinguished from it in two significant aspects: we use intuitionistic logic rather than classical throughout; our work is based on the notion of apartness (between elements of the set, and, later, between elements and its subsets). To have a structure, we need a set, a relation, and rules establishing how we will put them together, that is, working within classical or intuitionistic logic, in order to analyze algebraic structures it is necessary to start with study on sets and ordered sets, relational systems, etc. A comparative analysis between presented constructive and known classical results is also a part of this talk.

Joint work with M.N. Hounkonnou and P. Catarino.

Extremal Graph Theory is one of the fastest developing areas in Discrete Mathematics. It started in the 1940's (by Turán theorem) and was in strong connection with two other important areas of Discrete Mathematics, namely, to Ramsey Theory and to to Combinatorial Number Theory. Soon, Extremal Graph Theory and Ramsey Theory became the sources of several further important research areas.

In Extremal Graph Theory we fix some kind of objects, some parameter of these objects, and try to maximize or minimize some other parameters.

Stability methods mean that the extremal structures are very similar to some simple structure, and that the almost extremal structures are similar to the extremal strucures. For that part of Extremal Graph Theory when we consider simple graphs (no loops, neither multiple edges) and the minimum chromatic number of excluded subgraphs is at least 3, the Erdős-Simonovits theorem asserts that the stability holds. To prove sharp results in Extremal Graph Theory we mostly use stability results. We shall explain this approach, on the other hand, we shall show cases where the stability does not hold.

Further, we shall sketch several approaches to prove the stability, several proofs of the Erdős-Simonovits theorem.

The Constraint Satisfaction Problem was defind 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.

Prvi netrivijalan rezultat o približnim algebarskim strukturama u aditivnoj kombinatorici je Frajmanova teorema. U kontekstu Furijeove analize višeg reda, sledeća opštija verzija te teoreme pojavljuje se prirodnije: kada god skup A ⊆ (F^n)_p ima bar c|A|^3 aditivnih četvorki, onda postoji potprostor U, veličine |U| ≤ O𝑐(|A|), takav da je |U ∩ A| ≥ Ω𝑐(|A|). (Kao što je uobičajeno, pod aditivnom četvorkom nazivamo četvorku elemenata (a₁, a₂, a₃, a₄) ∈ ((F^n)_p)^4 takvu da je a₁ + a₂ = a₃ + a₄) Dakle, o skupu A sa ovim svojstvom možemo razmišljati kao o približnom potprostoru. Motivisani drugim približnim algebarskim strukturama koje se pojavljuju u Furijeovoj analizi višeg reda, u ovom predavanju ćemo se baviti kvadratnom verzijom ove teoreme. Naime, razmatraćemo koji bi to kombinatorni uslovi bili adekvatni za definiciju približnih kvadratnih varijeteta, a koji bi nam pritom omogućili da dokažemo kvadratnu Frajmanovu teoremu.

We give a survey of algorithmic complexity results for theories of algebraic structures including Kleene star. Those include Kleene algebras, Kleene lattices, and their extensions with division operations, also called action algebras / lattices. We focus on equational and Horn theories, since already on this level of expressivity we get high levels of undecidability. The talk includes both well-known old results (following Kozen 2002 and Buszkowski 2007), as well as new ones recently obtained by the speaker. The latter include undecidability and complexity of the logic of action algebras, both non-commutative and commutative, and that of the logic of Kleene algebras with commutativity conditions.

Odeljenje za matematiku je opsti matematicki seminar namenjen sirokoj publici. Predavanja su prilagodjena matematicarima i onima koji zele da to postanu.

Zoran Petrić, Odeljenje za matematiku Matematickog instituta SANU