Triangle Free Sets and Arithmetic Progressions – Two Pisier Type Problems

Abstract

Let ${\cal P}_f({\bf N})$ be the set of finite nonempty subsets of ${\bf N}$ and for $F,G\in{\cal P}_f({\bf N})$ write $F < G$ when $\max F < \min G$. Let $X=\{(F,G):F,G\in{\cal P}_f({\bf N})$ and $F < G\}$. A triangle in $X$ is a set of the form $\{(F\cup H,G),(F,G),(F,H\cup G)\}$ where $F < H < G$. Motivated by a question of Erdős, Nešetríl, and Rödl regarding three term arithmetic progressions, we show that any finite subset $Y$ of $X$ contains a relatively large triangle free subset. Exact values are obtained for the largest triangle free sets which can be guaranteed to exist in any set $Y\subseteq X$ with $n$ elements for all $n\leq 14$.