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 \(\langle t_{l,n}\rangle _{n=1}^{\infty}\), such that \(\bigcup_{i=1 }^\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 \(\{\Sigma_{t \in F}a_t\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.