Set families with a forbidden pattern

Journal article

A balanced pattern of order 2d is an element P ∈ {+, −}2d , where both signs appear d times. Two sets A, B ⊂ [n] form a P-pattern, which we denote by pat(A, B) = P, if A△B = {j1, . . . , j2d} with 1 ≤ j1 < · · · < j2d ≤ n and {i ∈ [2d] : Pi = +} = {i ∈ [2d] : ji ∈ A \ B}. We say A ⊂ P [n] is P-free if pat(A, B) ̸= P for all A, B ∈ A. We consider the following extremal question: how large can a family A ⊂ P [n] be if A is P-free? We prove a number of results on the sizes of such families. In particular, we show that for some fixed c > 0, if P is a d-balanced pattern with d < c log log n then | A |= o(2 n ). We then give stronger bounds in the cases when (i) P consists of d+ signs, followed by d− signs and (ii) P consists of alternating signs. In both cases, if d = o( √ n)then | A |= o(2 n ). In the case of (i), this is tight.

Authors: Karpas, I; Long, E

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Elsevier
• Journal: European Journal of Combinatorics
• Volume: 62
• Pages: 183-196
• Publication date: 2017-01-16
• Acceptance date: 2016-11-15
• DOI: 10.1016/j.ejc.2016.11.005
• ISSN: 0195-6698