Zoom link: https://princeton.zoom.us/j/92116764865

Passcode: 114700

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 estimate its algorithmic complexity in terms of the topological characteristics of the corresponding polyhedral products. This new perspective provides new connections between toric topology and theoretical informatics.

The talk is based on the ongoing research project joint with Anton Ayzenberg and Fedor Vylegzhanin.