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

Letnji semestar 2019. / Spring semester 2019

12/06/2019
Domingos M. Cardoso (Aveiro): (κ,τ)-regular sets and applications

A (κ,τ)-regular set of a graph is a vertex subset S inducing a κ-regular subgraph such that every vertex out of S has τ neighbors in S. The graphs with classical combinatorial structures, like perfect matchings, Hamilton cycles, efficient dominating sets, etc, are characterized by (κ,τ)-regular sets whose determination is equivalent to the determination of those classical combinatorial structures. The main obtained results on graphs with (κ,τ)-regular sets as well as the the determination of these vertex subsets in a finite number of steps are presented. Several spectral properties of the graphs with (κ,τ)-regular sets are also described.

29/05/2019
Samir Zahirović (PMF Novi Sad): Algebarska i kombinatorna svojstva grafova pridruženih stepeno-asocijativnim grupoidima (prezentacija teme dokstorske disertacije)

15/05/2019
Aleksandar Prokić (FTN Novi Sad): O strukturi komutativnih nil-čistih prstena

U ovom predavanju podrazumevamo da je svaki prsten sa jedinicom. Prsten je čist ako se svaki element prstena može napisati kao zbir idempotentnog elementa i invertibilnog elementa, a nil čist ako se svaki element može napisati kao zbir idempotentnog elementa i nilpotentnog elementa. Posmatraćemo komutativan nil-čist prsten kao dejstvo Bulove algebre na nilpotentan prsten i dokazati neke strukturne osobine komutativnih nil-čistih prstena. Posebno ćemo razmatrati konačan slučaj.

Ovo je zajednički rad sa Petrom Markovićem.

24/04/2019
Stefan Hačko (PMF Novi Sad): O nekim aritmetički interesantnim kolekcijama permutacija

U prvom delu izlaganja bavimo se problemom generisanja takozvanih savršenih nizova i uvodimo pojam optimalnih generatora perioda p, gde je p prost broj. Značajan otvoren problem je karakterizacija svih optimalnih generatora perioda p i u cilju njegovog rešavanja pretstavljamo tri ekvivalentna problema prevedenih u jezik permutacija. Zatim ovaj problem uopštavamo na periode složenih dužina i stižemo do kolekcija permutacija za koje važi da je razlika svaka dva člana kolekcije takođe permutacija. Ispostavlja se da su ove kolekcije ekvivalentne kolekcijama ortogonalnih ortomorfizmima o kojima se ne zna mnogo. Na kraju ovog dela dajemo pregled do sada poznatih rezultata iz ove oblasti.

U drugom delu izlaganja bavimo se srodnim problemom: kolekcijama permutacija za koje važi da je zbir svaka dva člana kolekcije takođe permutacija. Posebno nas interesuju donja i gornja ograničenja kardinalnosti ovih kolekcija u zavisnosti od dužine permutacije. Dajemo konstrukciju koja za slučaj složene dužine permutacija znatno poboljšava dosadašnje rezultate.

17/04/2019
Dragan Mašulović (PMF Novi Sad): Ramsey theory of well-ordered chains

In this talk we consider big Ramsey degrees of finite chains in certain countable ordinals. The first result in this direction is, of course, the infinite version of Ramsey's theorem which claims that finite chains have finite big Ramsey degrees in N, the chain of positive integers. Another important step in this direction was Laver's result on divisibility of scattered chains. Scattered countable chains are of particular interest since the situation with non-scattered chains can be resolved fairly easily: non-scattered countable chains have the same finite big Ramsey degrees as Q, the chain of rationals, where the big Ramsey degrees were explicitly computed by Devlin. Along the way we discuss a result that we see as an infinite analogue of the Finite Product Ramsey Theorem. This is joint work with Branislav Šobot.

20/03/2019
Luka Milićević (MI SANU, Beograd): Deobni rang i analitički rang multilinearnih formi

Deobni rang i analitički rang su dva uopštenja ranga bilinearnih formi za multilinearni slučaj u vektorskim prostorima nad konačnim poljima. Prvi od ova dva je definisan kao najmanji broj multilinearnih formi specijalnog oblika (forme koje se mogu "podeliti", tj. napisati kao proizvod dve forme) koje se sumiraju do date forme, dok je drugi mera toga koliko distribucija vrednosti date forme odudara od ravnomerne. Poznato je da su ova dva ranga povezana, i zapravo je lako pokazati da je analitčki rang ograničen deobnim. U drugom smeru su do skoro ocene bile loše, jer su zavisile od leme o regularnosti. U ovom predavanju ću predstaviti nove, značajno poboljšane, ocene za deobni rang u funkciji analitičkog ranga.

06/03/2019
Boriša Kuzeljević (PMF Novi Sad): Antilanci kopija ultrahomogenih struktura

Na predavanju ćemo prikazati neke rezultate o antilancima u parcijalnom uređenju izomorfnih podstruktura prebrojive ultrahomogene relacijske strukture. Poznato je da u posetu kopija prebojivog kompletnog grafa ne postoje prebrojivi maksimalni antilanci. Kurilić i Marković (2015) su pokazali da u posetu kopija Rado grafa postoje prebrojivi maksimalni antilanci. Posebno ćemo analizirati ovaj problem u klasi svih prebrojivih ultrahomogenih parcijalnih uređenja. Ovo je zajednički rad sa Milošem Kurilićem.