Abelian groups yield many large families for the diamond problem

摘要

There is much recent interest in excluded subposets. Given a fixed poset (P), how many subsets of ([n]) can be found without a copy of (P) realized by the subset relation? The hardest and most intensely investigated problem of this kind is when (P) is a diamond, i.e. the power set of a two-element set. In this paper, we show infinitely many asymptotically tight constructions using random set families defined from posets based on Abelian groups. They are provided by the convergence of Markov chains on groups. Such constructions suggest that the diamond problem is hard.