Forbidden graded posets in middle levels: supersaturation, enumeration and randomness
En palabras de los autores
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 .
Apareció: miércoles, 21 de octubre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 20 pages, 1 figure