Forbidden induced subposets of given height

Let P be a partially ordered set. The function La* (n, P) denotes the size of the largest family F subset of 2([n]) that does not contain an induced copy of P. It was proved by Methuku and Palvolgyi that there exists a constant C-P (depending only on P) such that La*(n,P) < C-P(left perpendicular n/2 right perpendicular n). However, the order of the constant C-P following from their proof is typically exponential in vertical bar P vertical bar. Here, we show that if the height of the poset is constant, this can be improved. We show that for every positive integer h there exists a constant c(h) such that if P has height at most h, then

La* (n, P) <= vertical bar P vertical bar(ch) (left perpendicular n/2 right perpendicular n).

Our methods also immediately imply that similar bounds hold in grids as well. That is, we show that if F subset of k such that F does not contain an induced copy of P and n >= 2 vertical bar P vertical bar, then

vertical bar F vertical bar <=vertical bar P vertical bar(ch) w,

where w is the width of k.

A small part of our proof is to partition 2([n]) (or k) into certain fixed dimensional grids of large sides. We show that this special partition can be used to derive bounds in a number of other extremal set theoretical problems and their generalizations in grids, such as the size of families avoiding weak posets, Boolean algebras, or two distinct sets and their union. This might be of independent interest. (C) 2018 Elsevier Inc. All rights reserved.

WOS:000447961800023

2019-01-01

161

537

562

REVIEWED