|
Letnji semestar 2018. / Spring semester 2018 06/06/2018 (12:00) Razmatramo sledeći problem: potrebno je odrediti najmanji broj tačaka koje se mogu
izabrati u datom n × n kvadratu ABCD na takav način da ne preostane nijedan jedinični kvadrat u kvadratu ABCD koji u svojoj
unutrašnjosti ne sadrži nijednu od uočenih tačaka. Drugim rečima, zanima nas kako najefikasnije "uništiti" objekat oblika kvadrata stranice n,
gde se "uništavanje" sprovodi bušenjem što manjeg broja malih rupa, a kvadrat se smatra "uništenim" ako se ne može spasti nijedno kvadratno parče stranice 1. 23/05/2018 Generalizing the classical results of F.P.Ramsey from the
late 1920's, the structural Ramsey theory originated at the beginning of 1970s. We say that a class
K of fiite structures has the Ramsey property if the following holds: for any number
k≥2 of colors and all A,B∈K such that A embeds
into B there is a C∈K such that no matter how we color
the copies of A in C with k colors, there is a monochromatic copy
B' of B in C (that is, all the copies of A that fall within
B' are colored by the same color). 16/05/2018 The Wagner-Preston theorem says that any inverse semigroup may be embedded in the so-called symmetric inverse semigroup consisting of all injective partial maps between subsets of some set X . This is a very good representation theorem: it illuminates, for example, all the order properties important in the study of inverse semigroups. On the other hand, the embedding of the proof is neither unique nor necessarily optimal. So it is desirable to be able to describe and classify all representations of inverse semigroups in a symmetric one. A theorem of Schein does exactly that, and works of Munn and Ponizovskii do likewise for linear (or matrix) representations of inverse semigroups. Beyond the symmetric inverse semigroups, there are many concrete inverse semigroups (made up of partial automorphisms of various structures, for example) which may serve as useful models of inverse semigroups. Yet our means of constructing good representations of this nature is embarrassingly limited: we are mostly reliant on Cayley's theorem in semigroup theory, and its modifications, to make representations by injective partial maps, matrices and the like. (This may be contrasted with the situation in group theory, where notable groups have been described as automorphism groups of geometries, graphs, spaces, etc.) This talk will illustrate some of these remarks, and set out a partial description and classification of representations of arbitrary inverse semigroups in members of a fairly broad class of (what can be thought of as) partial automorphism monoids. (Thus it may be seen as a generalisation of Schein's approach.) We have to consider the meaning of transitivity and effectiveness in this more general setting, and we pay some particular attention to the Boolean inverse monoids and the dual symmetric inverse monoids as receivers for representations. 09/05/2018 P-ideal dihotomija je kombinatorni princip koji
sledi iz Proper forsing aksiome. Neke važnije posledice P-ideal dihotomije su Suslinova hipoteza, Hipoteza o singularnim
kardinalima i Projektivna determinisanost. Poznato je da Proper forsing aksioma implicira da se svako Aronszajnovo drvo
može utopiti u racionalnu liniju, što je vrlo jaka forma Suslinove hipoteze. Na predavanju ćemo ispitati odnos
P-ideal dihotomije i ove verzije Suslinove hipoteze. 25/04/2018 (12:00) In threshold-based distributed algorithms, a process has to wait until the number of messages it receives reaches a certain threshold, in order to perform an action. I will present an automated method for synthesizing these thresholds, given a sketch of a distributed algorithm and specifications. In this way we synthesize distributed algorithms that are correct for every number n of processes and every number t of faults, provided some resilience condition holds, e.g. n>3t. This is joint work with Igor Konnov, Josef Widder and Roderick Bloem. Josef Widder (TU Wien, Austria): Communication-closed layers as paradigm for distributed systems Distributed computations are characterized by a partial order over events: two concurrent events at different processes may be re-ordered without changing the outcome of the computation. For systems that are composed of so-called communication-closed layers, this partial-order argument has been used to reduce the reasoning about distributed systems to a specific sequential form. I will discuss existing techniques for communication-closed layers, and applications to automated verification of state-of-the-art distributed systems. This is joint work with Marijana Lazić and Cezara Drăgoi. 11/04/2018 U izlaganju ćemo prezentovati rezultate iz rada: L. Barto, The collapse of the bounded width hierarchy. Instanca Problema zadovoljenja uslova (kraće CSP, od eng. Constraint Satisfaction Problem) se sastoji od promenljivih i uslova, gdje je svaki od uslova skup dozvoljenih evaluacija za neke od promenljivih. Jedan od načina kako da definišemo neku CSP podklasu je da ograničimo relacije uslova na tzv. jezik uslova, tj. fiksiran skup relacija na konačnom skupu. Definišemo relacijsku širinu za jezik uslova preko (k,l)-minimalne instance, a oni jezici uslova sa ograničenom relacijskom širinom se mogu urediti u odnosu na najmanju relacijsku širinu koju imaju. Međutim, ispostavlja se da, na osnovu glavne teoreme pomenutog rada i par ranijih rezultata, ova hijerarhija značajno kolapsira. Za kraj ćemo navesti i neke primene koje je glavna teorema našla u univerzalnoj algebri. 28/03/2018 U izlaganju uopštavamo dobro poznate veze između operatora zatvaranja, sistema zatvaranja i potpunih mreža. Uvodimo posebnu vrstu parcijalnog operatora zatvaranja, koji nazivamo oštar parcijalni operator zatvaranja, i pritom svaki oštar parcijalni operator zatvaranja jedinstveno korespondira parcijalnom sistemu zatvaranja. Dalje uvodimo posebnu vrstu parcijalnog sistema zatvaranja, nazvan glavni parcijalni sistem zatvaranja, a zatim navodimo teoremu reprezentacije za posete u odnosu na uvedene parcijalne operatore zatvaranja i parcijalne sisteme zatvaranja. Dalje, s obzirom na dobro poznatu vezu između matroida i geometrijskih mreža, a budući da se pojam matroida može na prirodan način uopštiti na parcijalne matroide (definišući ih preko parcijalnih operatora zatvaranja umesto preko operatora zatvaranja), definišemo geometrijske uređene skupove i pokazujemo da su povezani sa parcijalnim matroidima na isti način kao što su povezani i matroidi i geometrijske mreže. Osim toga, definišemo polumodularne uređene skupove, koji su uopštenje polumodularnih mreža, i takođe postoji ista veza između polumodularnih i geometrijskih poseta kao što imamo između polumodularnih i geometrijskih mreža. Ovo je zajednički rad sa B. Šešeljom i A. Tepavčević. 14/03/2018 A typical question in extremal graph theory concerns finding sufficient
conditions for a certain property to hold. In the recent years a lot of focus has been directed into questions regarding whether a random
graph satisfies a certain property. An even more recent trend, initiated by Sudakov and Vu in 2008, is to study how robust such properties are.
For instance, local resilience measures how many edges incident to every vertex an
adversary is allowed to remove arbitrarily in order to destroy the property. In this talk we report on some of the developments in
the field. In particular, we generalise the notion of local resilience and demonstrate its usefulness on an example of the square of a Hamilton cycle
in random graphs. 27/02/2018 (utorak / Tuesday) 14/02/2018
P vs NP je jedan od najpoznatijih Milenijumskih problema Klejevog instituta. Intuitivno,
P je klasa problema koji se mogu
"brzo" rešiti, a NP klasa problema za koje možemo "brzo" proveriti da li je neka ponuđena vrednost jedno od rešenja.
Pitanje (doslovno) vredno milion dolara je: da li su klase P i NP iste?
01/02/2018 (četvrtak / Thursday)
Two fundamental finiteness properties in group theory are those of being finitely generated and of being finitely presented.
These two properties were generalised to higher dimensions by C. T. C. Wall in 1965. A group G is said to be of type
Fn if it has an Eilenberg-MacLane complex K(G,1) with finite n-skeleton.
(Here K(G,1) is a certain nice topological space with fundamental group G.)
It may be shown that a group is finitely generated if and only if it is of type F1
and is finitely presented if and only if it is of type F2. Related to this is a certain
homological finiteness property called FPn. This property is defined for a monoid S
in terms of the existence of certain resolutions of free left ZS-modules.
The property FPn was introduced for groups by Bieri in 1976. In monoid and semigroup theory
the property FPn arises naturally in the study of string rewriting systems.
The connection between complete rewriting systems and homological finiteness properties
is given by a result of Anick (1986) which shows that a monoid that admits such a presentation must be of type
FPn for all n. The properties Fn and
FPn are closely related. In particular, for finitely presented groups they are equivalent.
|
