pipette
ESEspañol

Forbidden graded posets in middle levels: supersaturation, enumeration and randomness

Jiangdong Ai, Mingyu Liu, Zhiyu Song

Preprint

In the authors' words

Let be a fixed finite poset whose maximal chains all have elements, and let be the union of consecutive middle levels of . We prove that the maximum size of a -free subfamily of is for a constant , where , and that the number of -free subfamilies is . For connected we prove supersaturation above and determine, in terms of the coordinate patterns of the copies of in the window, a range of in which the largest -free subfamily of the random family has size and a range in which it has size ; the two ranges meet whenever all copies have the same pattern. For the Boolean poset , which has height , the threshold order in the corresponding window is , and satisfies , where is the vertex Tur\'an density of -dimensional subcubes in the hypercube. Together with a construction of Ellis, Ivan and Leader this gives . For the diamond, known bounds give .

Main resultThe abstract does not state a limitation.

Appeared: Wednesday, October 21. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 20 pages, 1 figure