An algebra is called minimal Taylor if its clone satisfies a non-trivial minor condition, but no proper subclone does so. Recently, Barto, Brady, Bulatov, Kozik and Zhuk initiated the systematic study of minimal Taylor algebras, intending to build a unified theory to understand the complexity of constraint satisfaction problems. They conjecture that every minimal Taylor algebra is finitely related, which we disprove by giving a counterexample.
This result can be interpreted as follows: there is an infinite sequence of tractable finite domain CSPs, such that every CSP harder than all problems in the sequence, is already NP-complete.
The q,t-Catalan numbers can be described elegantly in terms of pairs of statistics on Dyck paths: area and bounce, or area and dinv. Mahonian permutation statistics, such as coinversion, disorder, and the sorting index, are some of the most thoroughly studied statistics on permutations. Using bijective methods, we prove new expressions of the q,t-Catalan numbers over subsets of permutations in terms of at least one Mahonian statistic. In the process, we develop new Catalan subsets of permutations, new bijections from Dyck paths to these subsets, and new permutation statistics.
Mahonian Statistics and the q,t-Catalan Numbers
Tue, Nov. 19 3:30pm (MATH 3…
Topology
Andrew Doumont
X
We will construct Lagrangian Floer homology. Time permitting, we will also discuss Fukaya categories and the homological mirror symmetry conjecture.
A non-finitely related minimal Taylor algebra