Supersaturation and stability for forbidden subposet problems.

Abstract: We address a supersaturation problem in the context of forbidden subposets. A family

m a t h c a l F

of sets is said to contain the poset

P

if there is an injection

i : P i g h t a r r o w m a t h c a l F

such that

p l e_{P} q

implies

i (p) s u b s e t i (q)

. The poset on four elements

a, b, c, d

with

a, b l e c, d

is called butterfly. The maximum size of a family

m a t h c a l F s u b s e t e q 2^{[n]}

that does not contain a butterfly is

as proved by De Bonis, Katona, and Swanepoel. We prove that if

m a t h c a l F s u b s e t e q 2^{[n]}

contains

S i g m a (n, 2) + E

sets, then it has to contain at least

copies of the butterfly provided

E l e 2^{n^{1 - v a r e p s i l o n}}

for some positive

v a r e p s i l o n

. We show by a construction that this is asymptotically tight and for small values of

E

we show that the minimum number of butterflies contained in

m a t h c a l F

is exactly

.

Recommendations

Cites work

Cited in

(7)

This page was built for publication: Supersaturation and stability for forbidden subposet problems.