In 2008, Bodirsky and Grohe showed that for every \Pi_n^P-level of the Polynomial Hierarchy (PH) there are omega-categorical Constraint Satisfaction Problems (CSPs) complete for this level. We show that, in fact, there are omega-categorical CSPs complete for any level of the PH. To this end, we use a recent result of Bodirsky, Kn\"{a}uer, and Rudolph for constructing omega-categorical CSPs from sentences of Monadic Second-Order logic (MSO) with certain preservation properties. As a secondary contribution, we develop a new tool for producing MSO sentences satisfying said preservation properties. In the present talk, I give an overview of the above-mentioned results and motivate several new questions. This is joint work with Santiago Guzman-Pro.
The polynomial hierarchy and omega-categorical CSPs
Tue, Apr. 21 2:30pm (MATH 3…
Lie Theory
Richard Green (CU)
X
A pair (g,k) of Lie algebras is a symmetric pair if k is the set of fixed points of an automorphism of g of order 2. We will show that when g and k are simply laced Lie algebras of equal rank, the pair gives rise to some combinatorial structures whose numerical invariants can be predicted in terms of matroids that are representable over the field with two elements.
This is based on joint work with Tianyuan Xu (University of Richmond).
The polynomial hierarchy and omega-categorical CSPs