Set families with a forbidden pattern

Abstract

A balanced pattern of order $2d$ is an element $P\in \{+,-{\}}^{2d}$, where both signs appear $d$ times. Two sets $A,B\subset [n]$ form $P$-pattern, which we denote by $\mathrm{pat}(A,B)=P$, if $A△B=\{j_1,\dots ,j_{2d}\}$ with $1\le j_1<\cdots <j_{2d}\le n$ and $\{i\in [2d]:P_i=+\}=\{i\in [2d]:j_i\in A\setminus B\}$. We say $\mathcal{A}\subset \mathcal{P}[n]$ is $P$-free if $\mathrm{pat}(A,B)\ne P$ for all $A,B\in \mathcal{A}$. We consider the following extremal question: how large can a family $\mathcal{A}\subset \mathcal{P}[n]$ be if $\mathcal{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 $|\mathcal{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(\sqrt{n})$ then $|\mathcal{A}|=o(2^n)$. In the case of (i), this is tight. .

15 pages

References in corpus (1)

• A note on tilted Sperner families with patterns