Independent Sums of Arithmetic Progressions in $K_m$-free Graphs

Abstract

We establish that for any $m\in \mathbb{N}$ and any $K_m$-free graph $G$ on $\mathbb{N}$, there exist large additive and multiplicative structures that are independent with respect to $G$. In particular, there exists for each $l\in \mathbb{N}$ an arithmetic progression $A_l$ of length $l$ with increment chosen from the finite sums of a prespecified sequence $⟨t_{l,n}{⟩}_{n=1}^{\mathrm{\infty }}$, such that $\bigcup _{i=1}^{\mathrm{\infty }}{A}_l$ is an independent set. Moreover, if $F$ and $H$ are disjoint finite subsets of $\mathbb{N}$, and for each $t\in F\cup H$, $a_t\in A_l$, then $\{{\mathrm{\Sigma }}_{t\in F}{a}_t{\mathrm{\Sigma }}_{t\in H}{a}_t\}$ is not an edge of $G$. If $G$ is $K_{m,m}$-free, one may drop the disjointness assumption on the sets $F$ and $H$. Analogous results are valid for geometric progressions.