Exact Forbidden Subposet Results using Chain Decompositions of the Cycle

  • Abhishek Methuku
  • Casey Tompkins
Keywords: Forbidden subposet, Extremal set theory, Cycle method, Sperner theory


We introduce a method of decomposing the family of intervals along a cyclic permutation into chains to determine the size of the largest family of subsets of $[n]$ not containing one or more given posets as a subposet.   De Bonis, Katona and Swanepoel determined the size of the largest butterfly-free family. We strengthen this result by showing that, for certain posets containing the butterfly poset as a subposet, the same bound holds. We also obtain the corresponding LYM-type inequalities.
Article Number