Classification of Non-redundancy of Boolean Predicates of Arity 4
This work addresses a specific problem in constraint satisfaction theory for researchers in extremal combinatorics and logic, representing an incremental advancement in classification efforts.
The paper tackled the classification of non-redundancy for Boolean predicates of arity 4, achieving a near-complete classification by algorithmically classifying 397 out of 400 predicates and solving two of the remaining three, while identifying the first Boolean predicate with non-polynomial non-redundancy asymptotics.
Given a constraint satisfaction problem (CSP) predicate $P \subseteq D^r$, the non-redundancy (NRD) of $P$ is maximum-sized instance on $n$ variables such that for every clause of the instance, there is an assignment which satisfies all but that clause. The study of NRD for various CSPs is an active area of research which combines ideas from extremal combinatorics, logic, lattice theory, and other techniques. Complete classifications are known in the cases $r=2$ and $(|D|=2, r=3)$. In this paper, we give a near-complete classification of the case $(|D|=2, r=4)$. Of the 400 distinct non-trivial Boolean predicates of arity 4, we implement an algorithmic procedure which perfectly classifies 397 of them. Of the remaining three, we solve two by reducing to extremal combinatorics problems -- leaving the last one as an open question. Along the way, we identify the first Boolean predicate whose non-redundancy asymptotics are non-polynomial.