Logic Seminar
Kevin Zhou
UIC
Hereditary Properties and Weighted Model Counting
Abstract: Hereditary properties of graphs, which are classes of finite graphs closed under isomorphism and induced subgraph, are well-studied objects in combinatorics. Of particular interest are the possible asymptotic growth rates of the number of graphs with vertex set [n] in a hereditary property. In the 2000’s, a series of papers gave a classification into only four discrete growth rates, which was later generalized by Laskowski and Terry to hereditary properties in any finite relational language. The problem is of particular model-theoretic interest because hereditary properties are precisely the classes of models of universal theories.
A closely related problem related to statistical relational learning is that of weighted model counting, in which weights are assigned to each relation in the language and the goal is to efficiently compute the weighted count of the models of a given sentence. The advantage of working in the weighted setting is the existence of a Skolemization procedure - for any weighted model counting problem, there is an equivalent problem where the sentence is universal, while still staying in the finite relational setting. I will discuss some new connections between the work on classifying the growth rates of hereditary properties and efficient weighted model counting.
Wednesday April 10, 2024 at 4:00 PM in 712 SEO