Seminar Geometrija i primene, 28. decembar 2022.

Naredni sastanak Seminara biće održan u četvrtak, 28. decembra 2022, u sali 301f Matematičkog instituta SANU sa početkom u 17.15 časova.

Predavač: Ivan Limonchenko, HSE University, Russia

Naslov predavanja: THE AANDERAA-KARP-ROSENBERG CONJECTURE AND TORIC TOPOLOGY (part 2/2)

Apstrakt: By property of a graph we mean a boolean function on the set of all graphs; it is called invariant if relabelling of vertices of a graph does not change the value of the property on it. In order to check a certain property of a graph, one needs to ask a number of questions about edges of a graph. If a (simple) graph has n vertices, then m=n(n-1)/2 is the maximal possible number of its edges. The Aanderaa-Rosenberg conjecture (now proved) states that there exists a positive constant C such that at least $Cm$ questions are needed to check any (non-trivial) monotonic invariant property. A stronger Aanderaa-Karp-Rosenberg conjecture (still open) asserts that one can always assume C=1 above. The topological approach developed to attack the last conjecture relates it to the study of fixed point sets of finite group actions on cellular spaces.

In this talk, we'll be interested in a version of the Aanderaa-Karp-Rosenberg conjecture, in which one considers all non-trivial monotonic properties. We're going to interpret a monotonic boolean function of m variables as a simplicial complex with m vertices, and then apply the results of Bjorner-Lovasz on algorithmic complexity of polyhedra to the corresponding polyhedral products. Finally, we'll deduce a version of the original Aanderaa-Rosenberg conjecture for non-invariant monotonic properties from the version of the Toral Rank Conjecture proved for moment-angle complexes by Ustinovskii. This new perspective provides new connections between toric topology, theoretical informatics, and probably even artificial intelligence.

The talk is based on the ongoing research project j.w. Anton Ayzenberg and Fedor Vylegzhanin.

Napomena: Sastanke seminara je moguće pratiti i onlajn. Registracija za učešće je dostupna na sledećem linku:
https://miteam.mi.sanu.ac.rs/asset/5vJy5i44YQbMdSuDZ

Ukoliko ste već registrovani, predavanje možete pratiti na sledećem linku (nakon sto se ulogujete):
https://miteam.mi.sanu.ac.rs/asset/jJPbbrZF9BLD73r5m

Neulogovani korisnici mogu pratiti prenos predavanja na ovom linku, ali ne mogu postavljati pitanja (osim putem poruka) i ne ulaze u evidenciju prisustva:
https://miteam.mi.sanu.ac.rs/call/cngMrxTa7WoFSKZJn/ddPssjwsP40vEFRiLjVYEt-bWXLwl-VPYEEFMQjMOG1


 Ostavite vaš komentar 

Komentari(0)

Nažalost nije moguće ostaviti komentar.