Triangle free sets and arithmetic progressions---two Pisier type problems

Dennis Davenport ; Neil Hindman ; Dona Strauss

The electronic journal of combinatorics, Tome 9 (2002)

Résumé

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$.

Détail

DOI : 10.37236/1639

Classification : 05D10
Mots-clés : arithmetic progression, triangle free sets