On a Relation between Schreier-type Sets and a Modification of Turán Graphs

Abstract

Recently, a relation between Schreier-type sets and Turán graphs was discovered. In this note, we give a combinatorial proof and obtain a generalization of the relation. Specifically, for $p,q\ge 1$, let $$\mathcal{A}_q := \{F\subset\mathbb{N}: |F| = 1 \mbox{ or }F\mbox{ is an arithmetic progression with difference } q\}$$ and $$Sr(n, p, q)\ :=\ \#\{F\subset \{1, \ldots, n\}\,:\, p\min F\ge |F|\mbox{ and }F\in \mathcal{A}_q\}.$$ We show that $$Sr(n,p,q)=T(n+1,pq+1,q),$$ where $T(\cdot ,\cdot ,\cdot )$ is the number of edges of an $n$-vertex graph that is a modification of Turán graphs. We also prove that $Sr(n,p,q)$ is the partial sum of certain sequences.

9 pages, 6 figures