Set families with a forbidden pattern

Research output: Contribution to journalArticlepeer-review

Authors

Colleges, School and Institutes

External organisations

  • Hebrew University of Jerusalem

Abstract

A balanced pattern of order 2d is an element P ∈ {+, −}2d, whereboth 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 AP [n] is P-free if pat(A, B) ≠ P for all A, B ∈ A. Weconsider the following extremal question: how large can a family AP [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 ad-balanced pattern with d < c log log n then |A|= o(2n). Wethen 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(2n). In the case of (i), thisis tight.

Details

Original languageEnglish
Pages (from-to)183-196
Number of pages14
JournalEuropean Journal of Combinatorics
Volume62
Early online date16 Jan 2017
Publication statusPublished - 1 May 2017

Keywords

  • Extremal set theory, patterns