Семинар Геометрија и примене, 28. децембар 2022.

Наредни састанак Семинара биће одржан у четвртак, 28. децембра 2022, у сали 301ф Математичког института САНУ са почетком у 17.15 часова.

Предавач: Ivan Limonchenko, HSE University, Russia

Наслов предавања: THE AANDERAA-KARP-ROSENBERG CONJECTURE AND TORIC TOPOLOGY (part 2/2)

Апстракт: 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.

Напомена: Састанке семинара је могуће пратити и онлајн. Регистрација за учешће је доступна на следећем линку:
https://miteam.mi.sanu.ac.rs/asset/5vJy5i44YQbMdSuDZ

Уколико сте већ регистровани, предавање можете пратити на следећем линку (након сто се улогујете):
https://miteam.mi.sanu.ac.rs/asset/jJPbbrZF9BLD73r5m

Неулоговани корисници могу пратити пренос предавања на овом линку, али не могу постављати питања (осим путем порука) и не улазе у евиденцију присуства:
https://miteam.mi.sanu.ac.rs/call/cngMrxTa7WoFSKZJn/ddPssjwsP40vEFRiLjVYEt-bWXLwl-VPYEEFMQjMOG1


Нажалост није могуће оставити коментар.

Вести и дешавања


Активности на семинарима

све вести