
\documentclass[12pt]{article}
\usepackage{e-jc}

\usepackage{amssymb,amsmath,amsthm}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}
\DeclareMathAlphabet{\Sss}{U}{bbmss}{m}{n}
\def\Ex{{\Sss E}}
\def\Z{{\Sss Z}}


\newcommand{\dR}{\mathbb R}
\newcommand{\de}{\mbox{d}}
\newcommand{\hm}[1]{\leavevmode{\marginpar{\tiny%
$\hbox to 0mm{\hspace*{-0.5mm}$\leftarrow$\hss}%
\vcenter{\vrule depth 0.1mm height 0.1mm width \the\marginparwidth}%
\hbox to 0mm{\hss$\rightarrow$\hspace*{-0.5mm}}$\\\relax\raggedright #1}}}

\def\N{N}

\begin{document}

\title{Graphs on  Affine and Linear Spaces and Deuber Sets}

\author{David S. Gunderson\\
\small Department of Mathematics\\[-0.8ex]
\small University of Manitoba\\[-0.8ex]
\small Winnipeg, Manitoba R3T 2N2, Canada\\
\small \tt gunderso@cc.umanitoba.ca\\
\and
 Hanno Lefmann\\
\small Fakult\"at f\"ur Informatik\\[-0.8ex]
 \small TU Chemnitz\\[-0.8ex]
\small 09107 Chemnitz, Germany\\
\small \tt lefmann@informatik.tu-chemnitz.de
}
\date{\dateline{September 19, 2012} {May 17, 2013}\\
\small Mathematics Subject Classifications: 05D10}



\maketitle

\begin{abstract}
If $G$ is a large $K_k$-free graph, by Ramsey's theorem, a large
set of vertices is independent. For graphs whose vertices are positive
integers, much recent work has been done to identify what arithmetic structure
is possible in an independent set. This paper addresses  similar
problems: for graphs whose vertices are affine or linear spaces
over a finite field, and when the vertices of the graph are elements
of an arbitrary Abelian group.
\end{abstract}

\section{Introduction and Notation}
For a set $X$ and a positive integer $i$, the collection of all 
$i$-element subsets
of $X$ is denoted $[X]^i=\{Y\subseteq X : |X|=i\}$. For integers $a<b$, let
$[a,b]=\{z\in \mathbb{Z}:a\leq z\leq b\}$. Let $[n]=[1,n]=\{1,2,\ldots,n\}$
and let $[n]^i$ be an abbreviation for $[[n]]^i$.
Let $G = (V,E)$ denote a (simple) graph with vertex-set $V=V(G)$ and edge-set $E=E(G)$,
where $E \subseteq [V]^2$.  The complete graph on $k$ vertices
is denoted by $K_k$, and a graph $G$ is called $K_k$-free if
$G$ contains no copy of $K_k$ as a subgraph. 
A subset $I \subseteq V(G)$ is called
{\em independent} in $G$ if and only if $I$ does not contain any edges from $E$,
{\it i.e.}, $[I]^2\cap E=\emptyset$.

One form of Ramsey's theorem \cite{Ram:30} says that for any
integers $k,\ell\in \mathbb{Z}^{+}$,
there exists an $n$ so that any $K_k$-free graph on $n$ vertices contains an
independent set with at least $\ell$ vertices. In 1995, Erd\H{o}s asked if
$G$ is triangle-free graph on $\mathbb{Z}^{+}$, does there exist a Schur triple
$\{x,y,x+y\}$, that is independent? This was answered affirmatively
by {\L}uczak,  R\"odl, and  Schoen \cite{LRS:96} by a
much more general theorem for $K_k$-free graphs on
$\mathbb{Z}^{+}$.
Similarly, it was found by Gunderson, Leader, Pr\"omel, and
R\"odl \cite{GLPR:01} that there are arbitrarily long
finite arithmetic progressions that are independent in $K_k$-free graphs
on $\mathbb{Z}^{+}$.  Motivated by a question from Deuber, both results were
generalized in  \cite{GLPR:03} by the aforementioned 
authors  to provide a characterization of those 
arithmetic structures
that can be found in an independent set. These and more such generalizations are considered
in detail in Section \ref{se:pr}.

Here, similar questions about the richness of structure in independent sets
are investigated for $K_k$-free graphs whose vertices are either points
in a finite vector space (see Theorem \ref{theo2a}) or linear
lines in a finite vector space
(see Theorem \ref{theo5}). In each case, entire subspaces (resp., affine or
linear) are found in independent sets.  We also show that there are no
higher dimensional analogues of Theorems~\ref{theo2a} and~\ref{theo5}.
As an application,  in Section \ref{se:pr} we consider $K_k$-free graphs $G$
whose vertices are elements of an
Abelian group $\mathcal{G}$, and we show the existence of  
solutions $\mathbf{x} = (x_1, \ldots , x_\ell)^T\in 
(\mathcal{G} \setminus \{ 0 \})^\ell$ 
to any given partition regular system $M\mathbf{x} = \mathbf{0}$
of equations over 
$\mathcal{G}\setminus\{0\}$, where $\{ x_1, \ldots , x_\ell \}$ 
is an independent set in the graph $G$.
It turns out that for the countably infinite direct sum
$G = \mathbb{Z}_p^{< \omega}$ the considerations are
easier than in the case $G = \mathbb{Z}$.

\section{Affine and Linear Spaces}
In this section we introduce some useful notation.

When $q$ is a power of a prime, let $\mathbb{F}_q$ denote
the Galois field with $q$ elements, and let $\mathbb{F}_q^n$ denote
the $n$-dimensional linear vector space over $\mathbb{F}_q$. An $m$-dimensional
linear subspace $W\subseteq \mathbb{F}_q^n$ is a set of vectors for which
there exists $m$ (basis) vectors
$\mathbf{v}_1,\ldots, \mathbf{v}_m\in \mathbb{F}_q^n$ that are
linearly independent (over $\mathbb{F}_q$) and for which
$W=\mbox{span}\{\mathbf{v}_1,\ldots,\mathbf{v}_m\}$.
For any vector  $\mathbf{a}\in \mathbb{F}_q^n$,
the set
$U=\mathbf{a}+W=\{\mathbf{a}+\mathbf{w}:\mathbf{w}\in W\}$ is
called an {\em affine subspace}, and the vector $\mathbf{a}$ is called the {\em translation
vector} or {\em initial vector} of $U$. The dimension of $U=\mathbf{a}+W$ is the
dimension of $W$.

A vector $\mathbf{v}\in \mathbb{F}_q^n$ is written with respect to the standard
basis vectors $\mathbf{e}_1=(1,0,0,\ldots,0)$, $\mathbf{e}_2=(0,1,0,\ldots,0)$, \ldots,
$\mathbf{e}_n=(0,\ldots,0,1)$, so the notation $\mathbf{v}=(v_1,\ldots,v_n)$ means
$\mathbf{v}=\sum_{i=1}^nv_i\mathbf{e}_i$. Each $v_i\in \mathbb{F}_q$ is called
the $i$-th coordinate of $\mathbf{v}$, also denoted $\mathbf{v}(i)=v_i$.

For any (linear or affine) subspace $W$ of  $\mathbb{F}_q^n$, there is a certain kind
of basis for $W$ that is convenient to work with here.
By elementary linear algebra, for any $m$-dimensional (linear) subspace
$W$ of $\mathbb{F}_q^n$,
there is a unique ordered basis $(\mathbf{w}_1,\ldots, \mathbf{w}_m)$ 
satisfying:

(i) the first non-zero coordinate of each $\mathbf{w}_i$ is equal to $1$,

(ii) for each $i$, if the first non-zero coordinate of $\mathbf{w}_i$ occurs at position $c_i$,
then $c_1<c_2<\cdots <c_m$, and

(iii) for each $i$ and each $j\neq i$, $\mathbf{w}_j(c_i)=0$.

\noindent
Such an ordered basis satisfying (i)--(iii) is said to be the
{\em Schur normal form} (SNF) basis for $W$.
If $(\mathbf{w}_1,\ldots, \mathbf{w}_m)$ is
the SNF basis for a linear subspace $W$, write
\[W=\langle \mathbf{w}_1,\ldots, \mathbf{w}_m\rangle.\]
For an affine space $U=\mathbf{a}+W$, the translation vector $\mathbf{a}$ is not unique,
however, if $W$ is in SNF as above,
there is a unique initial vector $\mathbf{a}_0$ so that for 
$i=1,\ldots, m$, the
$c_i$-th coordinate is zero, that is, $\mathbf{a}_0(c_i)=0$. In this case,
\[U=\langle \mathbf{a}_0;\mathbf{w}_1,\ldots, \mathbf{w}_m\rangle\]
is the (unique) SNF for $U$.

To illustrate the notation, consider the space
$V=\mathbb{F}_5^3$. The set  $A=\{(x,y,z):y=3\}$ of points is an
affine plane with translation vector $\mathbf{a}_0=(0,3,0)$, and so
$A=\langle (0,3,0); (1,0,0), (0,0,1)\rangle$.

The 1-dimensional affine subspace $B=\{(x,y,z):x+3z=1,y=3\}$ of $A$
%is
%\[B=\{(0,3,2),(1,3,0),(2,3,3),(3,3,1),(4,3,4)\}\]
%and
has SNF
$B=\langle(0,3,2); (1,0,3)\rangle$.
If the above affine line $B$ is written as $\langle\mathbf{a}_0; \mathbf{a}_1\rangle$
in SNF, the $t$'th point  $\mathbf{a}_0 +t \cdot \mathbf{a}_1$ on the line
is uniquely determined.

\section{Affine Points}
In this section we consider graphs with vertices being  points in a vector space
over some finite field. Here is the first main result in this paper.

\begin{theorem} \label{theo2a}
Fix a prime power $q$ and let $k, m$ with $k \geq 3$
be  positive integers. Then, there exists a positive
integer $n_1 =  n_1(q,k,m)$ such that for every integer $n \geq n_1$, every $K_k$-free
graph $G$ on the vertex-set $\mathbb{F}_q^n$ contains an $m$-dimensional affine
subspace  whose set of points forms an independent set in the graph $G$.
\end{theorem}

To prove Theorem~\ref{theo2a}, we use a higher-dimensional partition result. 
Such
a strategy turned out to be fruitful in Canonizing Ramsey Theory.
Here we use the following
result of Graham, Leeb, and Rothschild \cite{GLR:72}.
\begin{theorem} \label{theo1}
Let  $q$ be a prime power, and let $\ell, m, r$ be nonnegative integers
with $\ell \leq m$. Then, there exists a positive
integer $n_2 = n_2(q,\ell,m,r)$ such that for every integer $n \geq n_2$ and
every $r$-coloring of the $\ell$-dimensional affine subspaces of $\mathbb{F}_q^n$
there exists an $m$-dimensional affine subspace
$S\subseteq \mathbb{F}_q^n$ such that all
$\ell$-dimensional affine subspaces in $S$ are colored the same.
\end{theorem}

\begin{proof} (of Theorem \ref{theo2a})
Assume, without loss of generality, that $k\leq m$, for then the
case for smaller $m$ follows directly.

From Theorem~\ref{theo1}, we set $n_2= n_2(q,1,m, 2^{q(q-1)/2})$. We claim that
$n_1 = n_1(q,k,m) \leq n_2$ for each $k \leq m$. Let $n\geq n_2$, and
let
$G = (V, E)$ be a  $K_k$-free graph  on the vertex-set $V =
\mathbb{F}_q^n$. It remains to find an $m$-dimensional affine subspace
whose vertices form an independent set in $G$.

Color the $1$-dimensional affine subspaces $L$ of $\mathbb{F}_q^n$
(affine lines) according to the pattern of the edges in $L$, {\em i.e.}, 
color
the line   $\langle \mathbf{a}_0; \mathbf{a}_1\rangle$ in SNF
by the set of all unordered pairs $\{ g, h\}$, $g,h \in \mathbb{F}_q$, 
for which
$\{ \mathbf{a}_0 +g \cdot \mathbf{a}_1, \ \mathbf{a}_0 +h 
\cdot \mathbf{a}_1 \} \in E$. Hence, at most $ 2^{q(q-1)/2}$ colors are used.

By Theorem \ref{theo1} there exists an $m$-dimensional
affine subspace $S$ of $\mathbb{F}_q^n$  such that all its
$1$-dimensional affine subspaces are colored the same, hence they all
have the same pattern with respect to the occurring edges.
Let the $m$-dimensional affine subspace $S= \langle \mathbf{a}_0; \mathbf{a}_1, \dots , \mathbf{a}_m
\rangle $ be in SNF, where $\mathbf{a}_0$ is the initial vector.

We show that the points in $S$ form an independent set in $G$.
For a contradiction first
 assume that in the  $1$-dimensional affine subspace given by
$\langle \mathbf{a}_0; \mathbf{a}_1 \rangle$ in SNF,
 for some $i \neq j$, 
\begin{eqnarray} \label{otto1a}
\{ \mathbf{a}_0 +i \cdot \mathbf{a}_1, \mathbf{a}_0 +j \cdot \mathbf{a}_1 \} \in E.
\end{eqnarray}
We claim that the following $k$  points in $S$
yield a complete graph $K_k$ in the graph $G$:
\begin{eqnarray*}
&& \mathbf{a}_0 + i \cdot \mathbf{a}_1,\\
&& \mathbf{a}_0 + j \cdot \mathbf{a}_1 + i \cdot \mathbf{a}_2, \\
&& \mathbf{a}_0 + j \cdot \mathbf{a}_1 + j \cdot \mathbf{a}_2 + i \cdot \mathbf{a}_3,\\
&& \vdots \\
&& \mathbf{a}_0 + j \cdot \mathbf{a}_1 + \dots + j \cdot \mathbf{a}_{k-1} + i \cdot \mathbf{a}_k.
\end{eqnarray*}
To see this,  for $1 \leq r < s \leq k$ consider the $1$-dimensional
affine subspaces given by $\langle \mathbf{x}_{r,s}; \mathbf{y}_{r,s} \rangle$ of  $S$
in SNF with initial vector $\mathbf{x}_{r,s}$, where
\begin{eqnarray}
\mathbf{x}_{r, s} &=& \mathbf{a}_0 + j \cdot \sum_{g=1}^{r-1} \mathbf{a}_g - 
i \cdot j \cdot (j-i)^{-1}
\cdot \sum_{h=r+1}^{s-1} \mathbf{a}_h - i^2 \cdot (j-i)^{-1}
\cdot \mathbf{a}_s, \label{pott1} \\
\mathbf{y}_{r,s} &=& \mathbf{a}_r + j \cdot (j-i)^{-1}
\cdot \sum_{h=r+1}^{s-1} \mathbf{a}_h + i \cdot (j-i)^{-1}
\cdot \mathbf{a}_s. \label{pott2}
\end{eqnarray}
Note that $\sum_{h=r+1}^{s-1} a_h = \mathbf{0}$ for $s = r+1$.
As $\langle \mathbf{a}_0; \mathbf{a}_1, \dots , \mathbf{a}_m \rangle $ is in
SNF, so are the affine lines $\langle \mathbf{x}_{r,s};\mathbf{y}_{r,s}\rangle$. Namely,
the first nonzero entry of $\mathbf{y}_{r,s}$ arises from the first nonzero
entry of the vector $\mathbf{a}_r$, hence is equal to $1$, 
and the corresponding coordinate of the vector  $\mathbf{x}_{r,s}$ 
is equal to $0$.

All affine lines in $S$ are colored the same. With (\ref{pott1}), and (\ref{pott2})
we infer
\begin{eqnarray*}
\mathbf{x}_{r,s} + i \cdot \mathbf{y}_{r,s} &=& \mathbf{a}_0
             + j \cdot \sum_{g=1}^{r-1} \mathbf{a}_g + i \cdot \mathbf{a}_r,\\
\mathbf{x}_{r,s} + j \cdot \mathbf{y}_{r,s} &=&
     \mathbf{a}_0 + j \cdot \sum_{g=1}^{s-1} \mathbf{a}_g + i \cdot \mathbf{a}_s,
\end{eqnarray*}
and  by (\ref{otto1a}) for  $1 \leq r < s \leq k$  we obtain
$$
\{\mathbf{a}_0 + j \cdot \sum_{g=1}^{r-1} \mathbf{a}_g + i \cdot \mathbf{a}_r,\
\mathbf{a}_0 + j \cdot \sum_{g=1}^{s-1} \mathbf{a}_g +
i \cdot \mathbf{a}_s \} \in E.
$$
Hence the points
$\mathbf{a}_0 + j \cdot \sum_{g=1}^{r-1} \mathbf{a}_g + i \cdot \mathbf{a}_r$,
$r = 1, \dots , k$, yield a complete subgraph
$K_k$ in $G$, which is a contradiction.
As all $1$-dimensional affine subspaces in $S$ are colored the same,
no affine line in $S$ contains an edge of $G$.
Since two distinct  points determine uniquely an affine line, it follows that
the set of points in $S$ is an independent set in $G$.
\end{proof}

\subsection{A Different Proof}
Using methods from  ergodic theory, the following
density version of Theorem \ref{theo1} for affine points was given by
F\"urstenberg and Katznelson \cite{FK:85}.
For another proof by purely 
combinatorial methods,
following the original approach of Szemer\'edi \cite{Szem:75}, 
which he used for proving
the density result for arithmetic progressions, compare 
Eggenwirth~\cite{Egg:87}.

\begin{theorem} \label{th20a}
For every prime power $q$,  $\varepsilon > 0$ and $\ell\in\mathbb{Z}^+$, there exists a
least positive integer $n_3 = n_3(q,\varepsilon, \ell)$ such that for every integer
$n \geq n_3$ every subset $X \subseteq \mathbb{F}_q^{n}$
with $|X| \geq \varepsilon \cdot q^{n}$ contains an $\ell$-dimensional affine subspace.
\end{theorem}

Theorem \ref{th20a} can be used to give another proof of Theorem \ref{theo2a},
a proof similar to one given in \cite{GLPR:03}, where the corresponding problem for arithmetic progressions in $\mathbb{Z}^+$ was investigated.

\begin{proof}
(second proof of Theorem~\ref{theo2a}) 
Let $S(k,m,q)$ denote the following statement: There exists 
$ n_0(k,m,q)$ such that for every integer $n \geq n_0(k,m,q)$,
every $K_k$-free graph with vertex-set being
the set of all $q^n$ affine points in an $n$-dimensional affine
vector space over $\mathbb{F}_q$
contains an $m$-dimensional affine subspace whose affine points
yield an independent set in $G$.

Fix $m$ and $q$; the proof of $S(k,m,q)$ is  by induction on $k$.
Certainly $S(2,m,q)$ holds, hence assume that for some $k\geq 3$, 
statement  $S(k-1,m,q)$ holds.
Let $n_0(k,m,q) = n_3(q, 2/q^{2m},  n_0(k-1,m,q))$ and let $n \geq
n_0(k,m,q)$. Let $G =(V,E)$ be a $K_k$-free graph with vertex-set being
the set of all points in an $n$-dimensional affine
vector space over  $\mathbb{F}_q$.

The number
of $m$-dimensional linear subspaces in $\mathbb{F}_q^{n}$ is  equal to
\begin{eqnarray*}
\binom{n}{m}_{q}=\frac{(q^{n} - 1)\cdot (q^{n-1} - 1)\cdots(q^{n-m+1}-1)}{
             (q^{m} - 1) \cdot (q^{m-1} - 1) \cdots (q - 1)},
\end{eqnarray*}
and the number of $m$-dimensional affine subspaces in $\mathbb{F}_q^{n}$ is
$q^{n-m} \cdot \binom{n}{m}_{q}$.
Moreover, each affine line can be extended in $\binom{n - 1}{m - 1}_{q}$ ways
to an $m$-dimensional affine subspace in $\mathbb{F}_q^n$.
Thus, if every $m$-dimensional affine subspace in $\mathbb{F}_q^{n}$
contains an edge, then $G$ contains at least
\[
\frac{q^{n-m} \cdot \binom{n}{m}_{q}}{\binom{n - 1}{m - 1}_{q}}
= q^{n-m} \cdot \frac{q^n  - 1}{q^m - 1} \geq q^{2n - 2m}
\]
edges. Hence there exists a vertex $v$ in $G$ such that the set $N(v)$
of its neighbors has cardinality at least $2 \cdot q^{n-2m}$.
The subgraph of $G$ induced on the vertex-set $N(v)$ is
by assumption $K_{k-1}$-free.
By Theorem \ref{th20a} with $\varepsilon = 2/q^{2m}$ and by choice of $n_0(k,m,q)$
the set $N(v)$ contains an $n_0(k-1,m,q)$-dimensional
affine subspace $S$. By the induction assumption this affine space
$S$ contains an $m$-dimensional affine subspace and the set of all
its  affine points is an independent set in $G$, completing the
induction step.
\end{proof}

{\em Remark:} It would be nice to have a proof of Theorem~\ref{theo2a} that
does not use these deep Theorems~\ref{theo1} or \ref{th20a}. 

\subsection{Higher Dimensional Version }
In Theorem~\ref{theo2a} vertices are points ($0$-dimensional
subspaces) and one might expect by using  methods as
in \cite{Voigt:84}, for example, that an
analogue to Theorem~\ref{theo2a}  might
also hold, where vertices  are higher dimensional affine
subspaces.
However, the following observation yields a counterexample,
and shows that Theorem~\ref{theo2a} is optimal in this sense.


\begin{proposition} \label{counter1}
Fix a prime power $q$ and let $ \ell, n $ be positive integers with $n
\geq \ell + 2$.  
There exists a triangle-free 
graph $G = (V, E)$ with vertex-set $V$ being the set of all
$\ell$-dimensional affine subspaces of ${\mathbb F}_q^n$, such that each 
$(\ell +1)$-dimensional affine subspace contains two $\ell$-dimensional 
affine subspaces $R$ and $S$ of ${\mathbb F}_q^n$, which are joined 
by an edge, i.e., $\{ R, S\} \in E$.
\end{proposition}

\begin{proof}
% First we define an ordering of the vectors in  ${\mathbb F}_q^n$
%in SNF.
%For two vectors ${\mathbf a}, {\mathbf b} \in {\mathbb F}_q^n$ in SNF, i.e.,\
%the first nonzero entry is a $1$, let ${\mathbf a} \leq  {\mathbf b}$
%if and  only if either (i) the first entry $1$ in ${\mathbf a}$
%occurs strictly before the first occurence of a $1$ in ${\mathbf b}$, or 
%(ii) if the first entries of $1$ in  ${\mathbf a}$ and ${\mathbf b}$
%occur at the same position, then according to some fixed total ordering of the 
%field ${\mathbb F}$, the vector  ${\mathbf a}$ is in the
%lexicographic ordering at most 
%vector ${\mathbf b}$.

Fix a  total ordering $<^*$ of the $\ell$-dimensional affine
subspaces of ${\mathbb F}_q^n$ with the following property:
for two $\ell$-dimensional affine spaces $R = \langle {\mathbf a}_0;
{\mathbf a}_1, 
\ldots , {\mathbf a}_{\ell} \rangle$ and 
$S = \langle {\mathbf b}_0; {\mathbf b}_1, 
\ldots , {\mathbf b}_{\ell} \rangle$ in SNF, if the position of the first
occurrence of $1$ in $ {\mathbf a}_1$ is less than  the position of the first
occurrence of $1$ in $ {\mathbf b}_1$, then 
$R <^* S$.

Next we define the edge-set $E$ of the graph $G =(V,E)$. 
For two $\ell$-dimensional 
affine subspaces $R = \langle {\mathbf a}_0; {\mathbf a}_1, 
\ldots , {\mathbf a}_{\ell} \rangle$ and
 $S = \langle {\mathbf b}_0; {\mathbf b}_1, 
\ldots , {\mathbf b}_{\ell} \rangle$ in SNF  of ${\mathbb F}_q^n$
with $R <^* S$,
let $\{ R, S \} \in E$ if and only if $ {\mathbf b}_0 = 
{\mathbf a}_0 +  {\mathbf a}_1$ and
$ {\mathbf b}_i =  {\mathbf a}_{i+1}$, $ i = 1, \ldots , \ell -1$.

We claim that  $G$ is 
triangle-free. Namely, assume that the vertices $R, S, U$ with
$R <^* S <^* U$ form a triangle, i.e.,\ 
$R = \langle {\mathbf a}_0; {\mathbf a}_1, 
\ldots , {\mathbf a}_{\ell} \rangle$, and $S = \langle {\mathbf a}_0
+ {\mathbf a}_1;
{\mathbf a}_2, 
\ldots , {\mathbf a}_{\ell}, {\mathbf a_{\ell +1}} \rangle$, and 
$U = \langle {\mathbf a}_0 + {\mathbf a}_1 + {\mathbf a}_2; {\mathbf a}_3, 
\ldots , {\mathbf a}_{\ell}, {\mathbf a}_{\ell + 1}, {\mathbf a}_{\ell +2}
\rangle$ in SNF, as $\{ R, S\}, \{S, U\} \in E$. The
assumption that $\{ R, U \} \in E$ implies
${\mathbf a}_0 + {\mathbf a}_1 =  {\mathbf a}_0 + {\mathbf a}_1 + 
{\mathbf a}_2$, i.e.,\ $ {\mathbf a}_2$ is the all-zeros vector, which is a 
contradiction. 


Now let $W = \langle {\mathbf c}_0; {\mathbf c}_1, 
\ldots , {\mathbf c}_{\ell +1} \rangle$ in SNF
be an $(\ell + 1)$-dimensional affine
subspace of ${\mathbb F}_q^n$. Then, by construction, for 
the two $\ell$-dimensional affine
subspaces  $R = \langle {\mathbf c}_0; {\mathbf c}_1, 
\ldots , {\mathbf c}_{\ell} \rangle$ and 
$S = \langle {\mathbf c}_0 + {\mathbf c}_1; {\mathbf c}_2, 
\ldots , {\mathbf c}_{\ell +1} \rangle$  in SNF we have $R<^* S$, and 
$R$ and $S$ are joined by an edge in $G$. 
\end{proof}



\section{Linear Lines}\label{se:linearlines}
In this section we consider the corresponding problem to Theorem \ref{theo2a} for
graphs with the vertex-set consisting of all linear lines of a linear vector space
over  $\mathbb{F}_q$.
We prove the following  analog of Theorem \ref{theo2a} for linear spaces.

\begin{theorem} \label{theo5}
Let $q$ be a prime power, and let $k,m$ be  positive integers with $k\geq 3$ 
and $m \geq 2$.
Then, there exists a positive
integer $n_4 = n_4(q,k,m)$ such that for every $n \geq n_4$,
every $K_k$-free graph $G$ with
vertex-set being  the set of all $1$-dimensional linear subspaces of  $\mathbb{F}_q^n$
contains an $m$-dimensional linear subspace $S$ such that the set of all
$1$-dimensional linear subspaces in $S$ is an independent set in the graph $G$.
\end{theorem}

In our arguments we use the following  version of Theorem~\ref{theo1} for linear
spaces due to  Graham, Leeb and Rothschild \cite{GLR:72}.

\begin{theorem} \label{theo3}
Let $q$ be a prime power and
let $\ell, m, r$ be positive integers with $\ell \leq m$ and $r \geq 1$.
Then, there exists a positive integer $n_5 = n_5(q,\ell,m,r)$ such that
for every integer $n \geq n_5$ and for every $r$-coloring of the
$\ell$-dimensional linear  subspaces of  $\mathbb{F}_q^n$,
there exists an $m$-dimensional linear subspace of $\mathbb{F}_q^n$ 
such that all its
$\ell$-dimensional linear subspaces are colored the same.
\end{theorem}

As in the affine case,  an $m$-dimensional
linear space $S=\langle \mathbf{a}_1, \dots , \mathbf{a}_m \rangle$ is given in SNF.
\begin{proof} (of Theorem~\ref{theo5}) Since we may replace 
$m$ by $\mbox{max} \{ m, k+1\}$, 
we may assume that  $m \geq k +1$. Fix $n_4 =
n_4(q,k,m)= n_5(q,2,m, 2^{q+1})$ according to Theorem~\ref{theo3}.
Let $n \geq n_4$ and let $G =(V,E)$ be a  $K_k$-free graph  with
vertex-set $V$, where  $V$ is  the  set of all
$1$-dimensional linear subspaces of $\mathbb{F}_q^n$.

Color each $2$-dimensional linear subspace $P$ of $\mathbb{F}_q^n$
according to the pattern of the edges occurring in $P$,
{\it i.e.},  color the  $2$-dimensional linear subspace
given by $\langle \mathbf{a}_1,\mathbf{a}_2 \rangle$ in SNF
by the set of all unordered pairs $\{ (i_1,i_2), (j_1, j_2)\}$
such that the two $1$-dimensional linear subspaces given by
$\langle i_1 \cdot \mathbf{a}_1 + i_2 \cdot \mathbf{a}_2\rangle$
and $\langle j_1 \cdot \mathbf{a}_1 +j_2 \cdot \mathbf{a}_2\rangle$
are in SNF and form an edge in the
graph $G$.  Note that all $1$-dimensional linear subspaces of
a $2$-dimensional  linear subspace $P=
\langle \mathbf{a}_1, \mathbf{a}_2 \rangle$
in SNF   are given  by
$\langle\mathbf{a}_1 + i \cdot \mathbf{a}_2\rangle$ for some $ i \in \mathbb{F}_q$
and by $\langle\mathbf{a}_2\rangle$, so
there are exactly $q+1$ such spaces. Therefore
the color of $P$ contains
only the unordered pairs of the form $\{ (1,i), (0,1) \}$,
and $\{ (1,i), (1,j) \}$ for some $i,j \in \mathbb{F}_q$, $i \neq j$. 
For this coloring 
at most $2^{q+1}$ colors are used.

By Theorem \ref{theo3}, there exists an $m$-dimensional linear
subspace $S$  such that all $2$-dimensional linear subspaces
of $S$ are colored the same, hence they all
have the same pattern with respect to the occurring edges. Let the
linear subspace $S$ be given by $\langle \mathbf{a}_1, \dots , \mathbf{a}_m
\rangle$ in SNF.

We claim that the set of all linear lines in $S$ is independent  in $G$.
Suppose, for a contradiction, that the color of some $2$-dimensional
linear subspace in $S$ is not the empty set, hence contains some unordered pair
$p= \{ (p_1, p_2), (p_3, p_4) \}$.
Then for the $2$-dimensional linear space given by $\langle\mathbf{a}_1, \mathbf{a}_2\rangle$ in
SNF,
\begin{eqnarray} \label{klm}
&& \{ p_1 \cdot \mathbf{a}_1 + p_2 \cdot 
\mathbf{a}_2, p_3 \cdot \mathbf{a}_1 + p_4 \cdot \mathbf{a}_2\} \in E.
\end{eqnarray}
All $2$-dimensional linear subspaces of $S$ are colored the same.
According to the type of this pair $p$ we distinguish two cases. \medskip

Case (i): $p= \{ (1, i), (0,1) \}$.

We claim that the $1$-dimensional linear subspaces 
$\langle\mathbf{a}_j + i \cdot \sum_{\ell=j+1}^m \mathbf{a}_{\ell}\rangle$
of $S$,
$j = 1,
\dots , k$, form a complete subgraph $K_k$ in $G$.
To see this, consider all $2$-dimensional linear subspaces in $S$
given by $\langle\mathbf{x}_{r,s}, \mathbf{y}_{r,s}\rangle$, $1 \leq r < s \leq k$, where
\begin{eqnarray}
\mathbf{x}_{r, s} &=& \mathbf{a}_r + i \cdot\sum_{\ell=r+1}^{s-1} 
\mathbf{a}_{\ell} +(i - i^2) \cdot
\sum_{\ell=s+1}^m \mathbf{a}_{\ell} \label{elk1}\\
\mathbf{y}_{r, s} &=& \mathbf{a}_s + i \cdot \sum_{\ell=s+1}^m 
\mathbf{a}_{\ell}, \label{elk2}
\end{eqnarray}
where $\sum_{\ell = r+1}^{s-1} \mathbf{a}_{\ell} = \mathbf{0}$ for $s = r+1$.

With $\langle\mathbf{a}_1, \dots , \mathbf{a}_m\rangle$ in SNF,
the $2$-dimensional subspaces $\langle\mathbf{x}_{r,s}, \mathbf{y}_{r,s}\rangle$,
$1 \leq r < s \leq k$, are also in SNF.
Namely, the first nonzero entry of $\mathbf{x}_{r,s}$ arises from the vector
$\mathbf{a}_r$ and is equal to $1$, and the first nonzero entry of $\mathbf{y}_{r,s}$ arises from
the vector $\mathbf{a}_s$ and is equal to $1$ and the corresponding coordinate of
the vector $\mathbf{x}_{r,s}$ is equal to $0$.  By (\ref{klm}) with (\ref{elk1}) and (\ref{elk2}),
\begin{eqnarray*}
\mathbf{x}_{r,s}+i\cdot\mathbf{y}_{r,s} &=& \mathbf{a}_r + 
i \cdot\sum_{\ell = r+1}^m \mathbf{a}_{\ell},\\
0 \cdot \mathbf{x}_{r,s}+1\cdot \mathbf{y}_{r,s}&=&\mathbf{a}_s+i\cdot 
\sum_{\ell=s+1}^m \mathbf{a}_{\ell},
\end{eqnarray*}
hence, for $ 1 \leq r < s \leq k$
\[ \left\{ \mathbf{a}_r + i\cdot\sum_{\ell = r+1}^m \mathbf{a}_{\ell}, \
\mathbf{a}_s + i \cdot \sum_{\ell=s+1}^m \mathbf{a}_{\ell} \right\}\in E,\]
and we have found a complete subgraph $K_k$ in $G$, which is a contradiction.
Thus every $2$-dimensional linear subspace of $S$ is colored by the empty
set. As any two $1$-dimensional linear subspaces of $S$ are contained in
a $2$-dimensional linear space,  the set of all $1$-dimensional
linear subspaces of $S$ is an independent set in $G$. \medskip

Case (ii): $p= \{ (1, i), (1,j) \}$, where $i \neq j$.

We claim that the $1$-dimensional linear subspaces
$\langle\mathbf{a}_1 + j \cdot \sum_{g=2}^{r} \mathbf{a}_g + 
i \cdot \mathbf{a}_{r+1}\rangle$ of $S$,
 $r=1,\dots , k-1$, and $\langle\mathbf{a}_1 + j \cdot \sum_{g=2}^{m}
\mathbf{a}_g  
\rangle$ form a complete subgraph $K_k$ in $G$. To see this,
consider first the $2$-dimensional linear subspaces of $S$ given by
$\langle\mathbf{x}_{r,s}, \mathbf{y}_{r,s}\rangle$, $1 \leq r < s \leq k-1$,
with
\begin{eqnarray}
\mathbf{x}_{r,s} &=& \mathbf{a}_1 + j \cdot \sum_{g=2}^{r} \mathbf{a}_g-
i \cdot j \cdot (j-i)^{-1}
       \cdot \sum_{h=r+2}^s\mathbf{a}_h-
i^2 \cdot (j-i)^{-1} \cdot\mathbf{a}_{s+1}, \label{elk3} \\
\mathbf{y}_{r,s} &=&\mathbf{a}_{r+1}+ j \cdot (j-i)^{-1}\cdot
\sum_{h=r+2}^s\mathbf{a}_h+ i \cdot (j-i)^{-1}
                                                     \cdot \mathbf{a}_{s+1}, \label{elk4}
\end{eqnarray}
where $\sum_{\ell = r+1}^{s-1} \mathbf{a}_{\ell} = \mathbf{0}$ for $s = r+1$.

As before, with $\langle \mathbf{a}_1, \dots , \mathbf{a}_m \rangle$  in SNF
 each $2$-dimensional linear subspace given by $\langle\mathbf{x}_{r,s},
\mathbf{y}_{r,s}\rangle$ is in SNF, too, $1 \leq r < s \leq k-1$.

By (\ref{klm}) with (\ref{elk3}) and (\ref{elk4}),
\begin{eqnarray*}
\mathbf{x}_{r,s}+  i \cdot \mathbf{y}_{r,s}&=& \mathbf{a}_1 +j
\cdot\sum_{g=2}^{r} \mathbf{a}_g + i\cdot\mathbf{a}_{r+1},\\
\mathbf{x}_{r,s}+  j\cdot \mathbf{y}_{r,s}&=& \mathbf{a}_1 +j\cdot
\sum_{g=2}^{s}\mathbf{a}_g + i\cdot\mathbf{a}_{s+1},
\end{eqnarray*}
hence for $1 \leq i < j \leq k-1$ we infer
\begin{eqnarray} \label{complete}
\left\{\mathbf{a}_1 + j\cdot\sum_{g=2}^{r} \mathbf{a}_g + i\cdot
\mathbf{a}_{r+1},\ \mathbf{a}_1 + j \cdot \sum_{g=2}^{s} \mathbf{a}_g
+ i \cdot\mathbf{a}_{s+1}\right\} \in E,
\end{eqnarray}
giving so far a copy of $K_{k-1}$ in $G$. This we will extend to a copy of $K_k$ in $G$.

Next  consider the $2$-dimensional linear subspaces of $S$ given by
$\langle\mathbf{x}_{r}, \mathbf{y}_{r}\rangle$, $r = 1, \ldots,  k-1$,
with
\begin{eqnarray}
\mathbf{x}_{r} &=& \mathbf{a}_1 + j \cdot \sum_{g=2}^{r} \mathbf{a}_g
-
i \cdot j \cdot (j-i)^{-1}
       \cdot \sum_{h=r+2}^m\mathbf{a}_h,
\label{elk3_new} \\
\mathbf{y}_{r} &=&\mathbf{a}_{r+1}+ j \cdot (j-i)^{-1}\cdot
\sum_{h=r+2}^m\mathbf{a}_h.
  \label{elk4_new}
\end{eqnarray}
Again, with $\langle \mathbf{a}_1, \dots , \mathbf{a}_m \rangle$  in SNF
 each linear subspace given by $\langle\mathbf{x}_{r},
\mathbf{y}_{r}\rangle$ is in SNF, too, $r = 1, \ldots , k-1$.

By (\ref{klm}) with (\ref{elk3_new}) and (\ref{elk4_new}),
\begin{eqnarray*}
\mathbf{x}_{r}+  i \cdot \mathbf{y}_{r}&=& \mathbf{a}_1 +j
\cdot\sum_{g=2}^{r} \mathbf{a}_g + i\cdot\mathbf{a}_{r+1},\\
\mathbf{x}_{r}+  j\cdot \mathbf{y}_{r}&=& \mathbf{a}_1 +j\cdot
\sum_{g=2}^{m}\mathbf{a}_g,
\end{eqnarray*}
hence for $r = 1, \ldots , k-1$ we infer
\[
\left\{\mathbf{a}_1 + j\cdot\sum_{g=2}^{r} \mathbf{a}_g + i\cdot
\mathbf{a}_{r+1},\ \mathbf{a}_1 + j \cdot \sum_{g=2}^{m} \mathbf{a}_g
\right\} \in E.
\]
With (\ref{complete}) we obtain a copy of $K_k$ in $G$,
which is a contradiction.
Thus each $2$-dimensional linear subspace of $S$ does not contain 
any edge of $G$.
As two $1$-dimensional linear spaces are contained in a $2$-dimensional linear space,
the set of all $1$-dimensional linear subspaces in $S$ is an independent set in $G$.
\end{proof}

With arguments similar to those  used in the proof
of Proposition~\ref{counter1}, the next result follows.

\begin{proposition} \label{counter2}
Fix a prime power $q$ and let $ \ell, n $ be positive integers with
$\ell \geq 2$ and $n
\geq \ell + 2$.  
There exists a triangle-free 
graph $G = (V, E)$ with vertex-set $V$ being the set of all
$\ell$-dimensional linear subspaces of ${\mathbb F}_q^n$, such that each 
$(\ell +1)$-dimensional linear subspace contains two $\ell$-dimensional 
linear subspaces $R$ and $S$ of ${\mathbb F}_q^n$, which are joined 
by an edge, i.e., $\{ R, S\} \in E$.
\end{proposition}

\begin{proof}
Fix an arbitrary total ordering $<^*$ of the $\ell$-dimensional linear
subspaces of ${\mathbb F}_q^n$ with the property that for two 
$\ell$-dimensional 
linear subspaces $R = \langle {\mathbf a}_1, 
\ldots , {\mathbf a}_{\ell} \rangle$ and
 $S = \langle {\mathbf b}_1, 
\ldots , {\mathbf b}_{\ell} \rangle$ in SNF  of ${\mathbb F}_q^n$:
if the position of the first occurrence of $1$ in  ${\mathbf a}_1$ is 
smaller than  the position of the first occurrence of $1$ in  ${\mathbf b}_1$,
then $R <^* S$.

Let the edge-set $E$ of the graph $G = (V, E)$ be defined as follows. 
For two $\ell$-dimensional 
linear subspaces $R = \langle  {\mathbf a}_1, 
\ldots , {\mathbf a}_{\ell} \rangle$ and
 $S = \langle  {\mathbf b}_1, 
\ldots , {\mathbf b}_{\ell} \rangle$ in SNF  of ${\mathbb F}_q^n$
with $R <^* S$,
let $\{ R, S \} \in E$ if and only if
$ {\mathbf b}_i =  {\mathbf a}_{i+1}$, $ i = 1, \ldots , \ell -1$.

It is easy to see that the graph $G$ is 
triangle-free. Namely, for contradiction assume that the vertices $R, S, U$ with
$R <^* S <^* U$ form a triangle. Then
we have $R = \langle  {\mathbf a}_1, 
\ldots , {\mathbf a}_{\ell} \rangle$, and $S = \langle 
{\mathbf a}_2, 
\ldots , {\mathbf a}_{\ell}, {\mathbf a}_{\ell + 1} \rangle$, and 
$U = \langle  {\mathbf a}_3, 
\ldots , {\mathbf a}_{\ell}, {\mathbf a}_{\ell+1},
{\mathbf a}_{\ell + 2} \rangle$ in SNF, as $\{ R, S\}, \{S, U\} \in E$. By
assumption, 
$\{ R, U \} \in E$, which  implies 
that the vectors $ {\mathbf a}_2$ and $ {\mathbf a}_3$ are identical,
hence with  $\ell \geq 2$ this contradicts the fact that the 
$\ell$-dimensional
linear space 
$S$ is in SNF.

Now let $W = \langle  {\mathbf c}_1, 
\ldots , {\mathbf c}_{\ell +1} \rangle$ be an $(\ell + 1)$-dimensional linear
subspace of ${\mathbb F}_q^n$ in SNF. Then, by construction, 
for the two $\ell$-dimensional linear
subspaces  $R = \langle  {\mathbf c}_1, 
\ldots , {\mathbf c}_{\ell} \rangle$ and 
$S = \langle  {\mathbf c}_2, 
\ldots , {\mathbf c}_{\ell +1} \rangle$ in SNF
we have $R <^* S$, and $R$ and $S$
are joined by an edge in $G$.
\end{proof}

\section{Partition Regular Systems of Equations}\label{se:pr}

In this section we give an application of Theorem~\ref{theo5} to
solutions of systems of linear equations.

For an integer-valued $k \times \ell$-matrix $M$, the system
$M\mathbf{x} = \mathbf{0}$ is called {\em partition regular} if and only if
for every coloring of $\mathbb{Z}^{+}$ with finitely many colors,
there exists a solution $\mathbf{x} = (x_1, \ldots , x_\ell)^T\in (\mathbb{Z}^{+})^\ell$
to $M\mathbf{x} = \mathbf{0}$ such that $\{x_1,\ldots,x_\ell\}$ is monochromatic.
Define $M$ to be partition regular  if and only if
 the system $M\mathbf{x} = \mathbf{0}$
is partition regular. For example, the matrix $[1, 1, -1]$ is partition regular,
which is just Schur's theorem  \cite{Schur:16}, i.e.,\  under any
finite coloring of $\mathbb{Z}^{+}$, there exists $x,y, z$ all with the same
color 
satisfying $x+y=z$.
(See, {\it e.g.}, \cite{GrRS:90} for more examples of partition regular
matrices.)

The above definition of ``partition regular'' has been extended. A $k\times \ell$ matrix
$M$ with integer entries is {\em partition regular over a set $X$} 
if and only if for any  finite
coloring of $X$, there exists a solution $\mathbf{x} = 
(x_1,\ldots,x_\ell)^T\in X^{\ell}$ to $M\mathbf{x}=\mathbf{0}$
so that $\{x_1,\ldots,x_\ell\}$ is monochromatic. So a partition regular
matrix  defined above is partition regular over $\mathbb{Z}^{+}$.  Rado \cite{Rado:33}
observed that partition regularity over $\mathbb{Z}^{+}$ is equivalent to
partition regularity over $\mathbb{Z}\setminus\{0\}$ or to partition
regularity over $\mathbb{Q}\setminus\{0\}$.

The similar definition can be made over a group:
Let ${\mathcal G}$ be an (additive) Abelian group.
An integer-valued $k \times \ell$-matrix $M$
is {\em partition regular} over $\mathcal{G}\setminus\{0\}$ 
if and only if for every coloring 
of  $\mathcal{G}\backslash \{0\}$ with a finite number of colors  there
exists a monochromatic solution $\mathbf{x} = (x_1, \ldots , x_\ell)^T \in
({\mathcal G}\setminus \{ 0\})^\ell$ to the system $M\mathbf{x} = \mathbf{0}$.

In 1933, a characterization of the set of all partition regular
systems  was given by Rado \cite{Rado:33}
in terms of a property of the columns of the matrix.
An integer-valued matrix $M$ has the {\em columns property} over $\mathbb{Z}$
if and only if there exists a
partition $I_0, I_1, \dots , I_m$  of the set of column indices of $M$
such that (i)
the sum of all columns with indices  from $I_0$ is the all zero-vector, and
(ii) for each $j=1, \ldots,m$, the sum of all column vectors  with indices
from $I_j$ 
is a (rational) linear combination 
of the columns  with indices from $I_0 \cup \dots \cup I_{j-1}$ 
(equivalently, there is
$c_j\in \mathbb{Z}$ so that $c_j$ times the sum of the columns 
with indices from 
$I_j$
is a linear combination with coefficients in $\mathbb{Z}$ of the columns
with indices from $I_0 \cup \dots \cup I_{j-1}$ ). Rado \cite{Rado:33}
proved that if $M$ is
a matrix with integer entries, then  $M\mathbf{x}=\mathbf{0}$ is partition
regular over $\mathbb{Z}\setminus\{0\}$ if and only if $M$ has the columns
property over $\mathbb{Z}$. Rado \cite[Thm VII]{Rado:39} generalized his theorem
for partition regularity and columns condition over any subring of complex
numbers. Bergelson, Deuber, and Hindman \cite{BDH:91}
showed that for any finite field $\mathbb{F}_q$ and any $k\times \ell$ matrix $M$ over
$\mathbb{F}_q$, $M$ has the columns property over $\mathbb{F}_q$ if and only
if
for every $r\in\mathbb{Z}^{+}$, there exists $n_0$ so that for every
$n\geq n_0$, if $\mathbb{F}_q^n\setminus\{\mathbf{0}\}$ is $r$-colored,
then there exists a solution $\mathbf{x}=(x_1,\ldots, x_{\ell})^T$
to $M\mathbf{x}=\mathbf{0}$ so that $\{x_1,\ldots, x_{\ell}\}$
is monochromatic.

Another characterization of partition regular systems over $\mathbb{Z}
\setminus
\{ 0 \}$
was given by Deuber \cite{Deub:73} in terms of
so-called $(m,p,c)$-sets; in the following definition, the notation
$[-p,p]=\{z\in\mathbb{Z}:-p\leq z\leq p\}$  is used.
\begin{definition}
Let $m,p,c$ be nonnegative integers.
A set $S \subset \mathbb{Z}^{+}$
is called an $(m,p,c)$-set if and only if there exist $m+1$ positive integers
$a_0, \dots , a_m$
such that
\begin{eqnarray*}
S=\{ca_0+\lambda_1a_1+\lambda_2a_2+\cdots+\lambda_m a_m: &&
                           \lambda_1,\lambda_2,\ldots,\lambda_m\in[-p,p]\}\\
\cup\{c a_1+\lambda_2 a_2+\cdots +\lambda_m  a_m: && \lambda_2,\ldots,\lambda_m\in[-p,p]\}\\
\vdots && \\
\cup \{c  a_{m-1} + \lambda_m  a_m: && \lambda_m\in [-p,p]\} \\
\cup \{c  a_m \}.&&
\end{eqnarray*}
\end{definition}
Today, $(m,p,c)$-sets are sometimes called {\em Deuber sets}.

The next result of Deuber  \cite{Deub:73} shows that solutions of partition
regular systems can be found in $(m,p,c)$-sets.

\begin{theorem} \label{theo13}
Let $M$ be an integer-valued
$k \times \ell$-matrix so that $M\mathbf{x}=\mathbf{0}$ is partition regular
over $\mathbb{Z}\setminus\{0\}$. Then
there exists a triple $(m,p,c)$ of  positive integers  such that every $(m,p,c)$-set in
$\mathbb{Z}^{+}$ contains a solution ${\bf x}=(x_1, \ldots , x_\ell)^T \in
(\mathbb{Z}^{+})^\ell$ to the system $M\mathbf{x}=\mathbf{0}$.
\end{theorem}

The following result is by Gunderson, Leader, Pr\"omel and 
R\"odl \cite{GLPR:03}:
\begin{theorem} \label{theo14}
Let $k,m,p,c$ be positive integers.
Then there exists a triple $(n,q,d)$ of positive integers such that
for every $(n,q,d)$-set $V$ and every $K_k$-free graph $G = (V, E)$,
there exists an $(m,p,c)$-set in $V$ which is an
independent set in $G$.
\end{theorem}
As a consequence of Theorem \ref{theo14}, if $G$ is a $K_k$-free
graph on the set of 
positive integers, any finite system $M\mathbf{x}=\mathbf{0}$
of partition regular equations
can be satisfied in an independent set, and hence Theorem \ref{theo14}
generalizes most Ramsey-type theorems for finite arithmetic structures. Deuber,
Gunderson, Hindman, and Strauss 
\cite{DGHS:97} gave an example of a $K_3$-free graph on $\mathbb{Z}^{+}$
that does not contain an independent Hindman set (an infinite sequence
of positive integers, together with all finite sums from the sequence), so
in general 
Theorem~\ref{theo14} cannot be extended to include infinite families
of partition regular equations. 
However, there are infinite systems of partition
regular equations, where a similar statement like in Theorem~\ref{theo14}
can be shown \cite{KL:08}.

If a system $M\mathbf{x}=\mathbf{0}$
is not partition regular over $\mathbb{Z}^+$, then for some positive
integer $r$ there is an $r$-coloring $\Delta$ of $\mathbb{Z}^{+}$ that prevents
monochromatic solutions. Let $S_1, \ldots , S_r$ be the color classes.
Then, consider the complete $r$-partite graph $G$ with vertex-set
  $\mathbb{Z}^{+}$ and classes  $S_1, \ldots , S_r$.  By choice of the coloring $\Delta$,
each solution to  $M\mathbf{x}=\mathbf{0}$ must intersect at least 
two classes, hence $G$ is $K_{r+1}$-free, but any solution $\mathbf{x}$
contains an edge of $G$.

A $q$-analog of $(m,p,c)$-sets, which are called $m$-sets in \cite{Deub:75},
is now defined in the straightforward way:
\begin{definition}
A subset $S$ of points in a vector space $V$ over  $\mathbb{F}_q$
is called an $[m,q,1]$-set if and only if there exist $(m+1)$ vectors
$\mathbf{a}_0, \ldots , \mathbf{a}_m\in V$,
which are linearly independent over $\mathbb{F}_q$,
such that
\begin{align*}
S=\{\mathbf{a}_0 + \lambda_1  \mathbf{a}_1 + \lambda_2 \mathbf{a}_2 + \cdots +
\lambda_m \mathbf{a}_m : &  \;
\lambda_1, \lambda_2,\ldots, \lambda_m \in \mathbb{F}_q\}\\
\cup\{ \mathbf{a}_1 +    \lambda_2  \mathbf{a}_2 + \cdots +
      \lambda_m  \mathbf{a}_m : & \;
      \lambda_2,\ldots, \lambda_m  \in \mathbb{F}_q\}\\
\vdots & \\
\cup\{ \mathbf{a}_{m-1} + \lambda_m\mathbf{a}_m : & \;
\lambda_m\in \mathbb{F}_q\}\\
\cup\{\mathbf{a}_m\}&.
\end{align*}
\end{definition}

Using Theorem \ref{theo5} we  obtain the following:
\begin{theorem} \label{theo7}
Let $\mathbb{F}_q$ be a finite field with $q$ elements.
For each  $k,m \in \mathbb{Z}^+$ there exists
$n\in \mathbb{Z}^+ $ such that every $K_k$-free graph
$G$ with vertex-set being the set of all points of an $[n,q,1]$-set
in a linear vector space over  $\mathbb{F}_q$
contains an $[m,q,1]$-set, which is an independent set in $G$.
\end{theorem}

\begin{proof}
Let  $N = n_4(q,k,m+1)$ and let $U = \langle \mathbf{y}_0,
\dots, \mathbf{y}_{N-1} \rangle$ be an $N$-dimensional linear vector space
over $\mathbb{F}_q$ in SNF. Let $G = (V, E)$ be a $K_k$-free graph with
vertex-set being the set of all $(q^N-1)/(q-1)$  points in $U$
of the form $\sum_{i=0}^{N-1} \mu_i \mathbf{y}_i$, $\mu_i \in \mathbb{F}_q$,
$i= 0, 1, \dots , N-1$, where the first nonzero entry in the sequence $(\mu_0,
\mu_1, \dots , \mu_{N-1})$ is equal to $1$. Hence $V$ is
an $[N-1, q, 1]$-set.

Construct a new
graph $G' = (V', E')$ with vertex-set being the set of all $1$-dimensional
linear subspaces of $U$; hence $|V'| = (q^N - 1)/(q-1)$,
where edges are defined as follows: for $1$-dimensional subspaces
$\langle \mathbf{x}\rangle$ and  $\langle \mathbf{y}\rangle$ of $U$ in SNF,
 let $\{\langle \mathbf{x}\rangle, \langle \mathbf{y} \rangle \} \in E'$
 if and only if $ \{ \mathbf{x} , \mathbf{y} \}\in E$.

We claim that $G'$ is $K_k$-free. Otherwise, there exist
pairwise distinct $1$-dimensional linear subspaces
$\langle \mathbf{x}_1\rangle, \dots, \langle \mathbf{x}_k \rangle$ in
SNF such that $\{\langle \mathbf{x}_i\rangle,\langle \mathbf{x}_j\rangle\} \in E'$,
$1 \leq i < j \leq k$. But then
$\{\mathbf{x}_i, \mathbf{x}_j\} \in E$,  $1 \leq i < j \leq k$,
which contradicts $G$ being $K_k$-free.

By Theorem \ref{theo5}, in $G'$ there exists an $(m+1)$-dimensional
linear subspace $\langle \mathbf{a}_0, \dots , \mathbf{a}_m \rangle$
in SNF, such that the set of all its $1$-dimensional linear
subspaces is an independent set in $G'$. Then the $[m,q,1]$-set
\begin{eqnarray*}
S= \bigcup_{j=0}^m \{\mathbf{a}_{j}+\sum_{i=j+1}^m \lambda_i\mathbf{a}_{i}
       : && \lambda_{j+1},\ldots , \lambda_m\in\mathbb{F}_q\} \\
\end{eqnarray*}
is an independent set in $G$.
\end{proof}

For a prime $p$, an integer-valued matrix $M$ has the {\em $p$-columns
property,}
if $M$ has the columns property over ${\mathbb Z}$ where all calculations are
done modulo $p$.

Let ${\mathcal G}$ be an (additive) Abelian group viewed as a module over
$\mathbb{Z}$. The {\em order} of an element $g \in {\mathcal G}$
is the least positive integer $n$ such that $n \cdot g =
g + \cdots + g = 0$. If no such integer
$n$ exists, then the order of the element $g$ is $\infty$.

Deuber \cite{Deub:75}
characterized all partition regular matrices with respect to
Abelian groups:
\begin {theorem} \label{theo11}
Let ${\mathcal G}$ be an (additive) Abelian group and let $M$ be an integer-valued matrix.
Then $M$ is partition regular if and only if at least one of the following
conditions hold:
\begin{itemize}
\item{(i)} There exists $x \in {\mathcal G}
\setminus \{ 0\}$ such that $M(x,x, \dots , x)^T =\mathbf{0}$.
\item{(ii)} $M$ has the columns property over ${\mathbb Z}$
and  ${\mathcal G}$  contains
elements of arbitrary large finite or infinite order.
\item{(iii)} For some prime $p$ the matrix $M$ has the $p$-columns
property and ${\mathcal G}$
contains the countably infinite direct sum $\mathbb{Z}_p^{<\omega}$
of  $\mathbb{Z}_p$ (so only finitely many entries are non-zero),
where  ${\mathbb Z}_p$ is the cyclic group of order $p$.
\end{itemize}
\end{theorem}


Similarly as in Theorem \ref{theo13}, $[m,p,1]$-sets are universal for the 
solutions of integer-valued 
matrices with the $p$-columns property, as the following result 
of  Deuber shows, see Lemma~15 in \cite{Deub:75}:
\begin{theorem} \label{theo13a}
Let $p$ be prime. Let $M$ be an integer-valued
$k \times \ell$-matrix, which has the $p$-columns property.
Then there
exists a positive integer $m$ such that every $[m,p,1]$-set $S \subset
\mathbb{Z}_p^{<\omega}$ contains
a solution $\mathbf{x}=(x_1, \ldots , x_\ell)^T \in
S^\ell$ to the system $M\mathbf{x}=\mathbf{0}$ (mod $p$).
\end{theorem}

We now have all tools together to prove the following consequence.

\begin{theorem} \label{theo12}
Let ${\mathcal G}$ be an  (additive) Abelian group and let $M$ 
be an integer-valued
$k \times \ell$-matrix, which is partition regular over 
${\mathcal G}\setminus\{0\}$.
Let $G=(V,E)$ be a $K_k$-free graph with vertex-set   ${\mathcal G}\setminus\{0\}$.
Then there exists a solution $\mathbf{x}=(x_1, \ldots , x_\ell)^T
\in ({\mathcal G}\setminus \{ 0\} )^\ell$ to
$M\mathbf{x}=\mathbf{0}$, such that $\{x_1, \ldots , x_\ell\}$
is an independent set in the graph $G$.
\end{theorem}

\begin{proof}
Since the matrix $M$ is partition regular over ${\mathcal G}\setminus\{0\}$,
at least one of the  conditions (i), (ii), or (iii) from Theorem \ref{theo11} hold.
\medskip

If (i) holds, there is nothing to show.\medskip

Assume that (ii) holds, i.e.,\  the matrix $M$ has the columns property over
${\mathbb Z}$. Moreover, the Abelian group ${\mathcal G}$
contains elements of arbitrary large finite or infinite order.
By Theorem \ref{theo13} there exist positive integers $m,p,c$ such
that every $(m,p,c)$-set in $\mathbb{Z}^{+}$ contains a solution
 $\mathbf{x}=(x_1, \ldots , x_\ell)^T$
 to the system $M\mathbf{x}=\mathbf{0}$.

By Theorem \ref{theo14} fix positive integers $n,q,d$ such that
for every $(n,q,d)$-set $V \subset \mathbb{Z}^{+}$ and every $K_k$-free
graph $G = (V, E)$ there exists an $(m,p,c)$-set $S \subseteq V$, which is an
independent set in $G$.
Fix any $(n,q,d)$-set $T$ in $\mathbb{Z}^{+}$. Let $M = \mbox{max}\ T$.
Let $g$ be an element in ${\mathcal G}$ with $\mbox{ord}(g) > M$.
Consider the subset $ T \cdot g = \{ t \cdot g \; \; | \; \; t \in T\}$
which is of size $|T|$, since $\mbox{ord}(g) > M$, of
the vertex-set ${\mathcal G}$.
By  Theorem~\ref{theo14} there exists an $(m,p,c)$-set $S \subseteq T $, such
that the set $ S \cdot g$  is an
independent set in the graph $G$.
Then there exist $x_1, \ldots , x_\ell \in S$, such that $\mathbf{x}
= (x_1 \cdot g, \ldots , x_\ell \cdot g)^T$ is a solution to the system 
$M\mathbf{x}=\mathbf{0}$, and $\{ x_1, \ldots , x_\ell \}$ 
is an independent set in ${\mathcal G}$.
\medskip

If  (iii) holds, then for some prime $p$ the matrix $M$ has the
$p$-columns property. Moreover, the Abelian group ${\mathcal G}$
contains ${\mathbb Z}_p^{< \omega}$. By Theorem \ref{theo13a} there
exists a positive integer $m$ such that every $[m,p,1]$-set $S \subset
{\mathbb Z}_p^{<\omega}$ contains
a solution $\mathbf{x}=(x_1, \ldots , x_\ell)^T \in
S^\ell$ to the system $M\mathbf{x}=\mathbf{0}$.


By Theorem \ref{theo7} there exists $n\in \mathbb{Z}^{+}$
such that every $K_k$-free graph $G$ with vertex-set being the set of all
points of an $[n,p,1]$-set in a vector space over $\mathbb{F}_p$
contains an $[m,p,1]$-set which is an independent set in $G$. Pick any
$[n,p,1]$-set $T \subset \mathbb{Z}_p^{< \omega}$ and pick such an 
$[m,p,1]$-set contained in $T$. This
$[m,p,1]$-set contains a solution to the system $M\mathbf{x}=\mathbf{0}$.
\end{proof}

\subsection*{Acknowledgement} The authors would like to thank the referee for 
carefully reading the paper.

\begin{thebibliography} {999}

\bibitem{BDH:91} V.~Bergelson, W.~A.~Deuber, and N.~Hindman.
\newblock Rado's theorem for finite fields.
\newblock {\em Colloquia Mathematica Societatis J\'anos Bolyai}
 60 ({\em Sets, Graphs, and Numbers}, Budapest, 1991),
D.~Mikl\'os, T.~Sz\H{o}nyi, eds.,
J\'anos Bolyai Mathematical Society, Budapest, 77--88, 1992.

\bibitem{Deub:73} W.~Deuber. \newblock Partitionen und lineare Gleichungssysteme.
\newblock {\em Math. Z.}, 133:109--123, 1973.

\bibitem{Deub:75} W.~Deuber. \newblock Partition theorems for Abelian groups. \newblock
{\em J. Combin. Th. Ser. A},  19:95--108, 1975.

\bibitem{DGHS:97}W.~Deuber,  D.~S.~Gunderson, N.~Hindman, and D.~Strauss.
\newblock Independent finite sums for $K_m$-free graphs. \newblock
{\em J. Combin. Th. Ser. A},  78:171--198, 1997.

\bibitem{Egg:87} W.~Eggenwirth.\newblock Ein Szemer\'edisatz f\"ur affine R\"aume.
\newblock {\em Dissertation}, M\"unster, 1987.

\bibitem{FK:85} H.~F\"urstenberg and Y.~Katznelson. \newblock An ergodic
Szemer\'edi theorem for $IP$-systems and combinatorial theory. \newblock
{\em J. d'Analyse Math.},  45:117--168, 1985.

\bibitem{GLR:72} R.~L.~Graham, K.~Leeb, and B.~L~ Rothschild.
\newblock Ramsey's theorem for a class of categories.
\newblock {\em Advances in Math.},  8:417--433, 1972.

\bibitem{GrRS:90} R~ L.~Graham, B.~L.~Rothschild, and J.~H.~Spencer.
\newblock {\em Ramsey theory}, 2nd ed.,
{\em Wiley-Interscience Ser. in Discrete Math.}, New York, 1990.

\bibitem{GLPR:01} D.~S.~Gunderson, I.~Leader, H.~J.~Pr\"omel, and V~ R\"odl.
\newblock Independent arithmetic progressions in clique-free graphs
on the natural numbers. \newblock {\em J. Combin. Th. Ser. A},  93:1--17, 2001.

\bibitem{GLPR:03} D.~S.~Gunderson, I.~Leader, H.~J~ Pr\"omel, and V.~R\"odl.
\newblock Independent Deuber sets in graphs on the natural numbers.
\newblock {\em J. Combin. Th. Ser. A}, 103:305--322, 2003.

\bibitem{KL:08} Y.~Kohayakawa and H.~Lefmann. \newblock $K_{\ell}$-free graphs and
systems of linear equations. \newblock {\em manuscript}, 2009. 

\bibitem{LRS:96} T.~{\L}uczak, V.~R\"odl, and T.~Schoen.
 \newblock Independent finite
sums in graphs defined on the natural numbers. \newblock {\em Discrete Math.},
181:289--294, 1998.

\bibitem{Rado:33} R.~Rado. \newblock Studien zur Kombinatorik. \newblock {\em
Math. Z.}, 36:424--480, 1933.

\bibitem{Rado:39} R.~Rado. \newblock Note on combinatorial analysis.
\newblock {\em Proc. London Math. Soc.}, 48:122-160, 1943.

\bibitem{Ram:30} F.~P.~Ramsey.
\newblock On a problem of formal logic.
\newblock {\em Proc. London Math. Soc.}, 30:264--286,  1930.

\bibitem{Schur:16} I.~Schur.
\newblock \"Uber die Kongruenz $x^m + y^m \equiv z^m \pmod{p}$.
\newblock {\em Jber. Deutsch. Math.-Verein}, 25:114--116, 1916.

\bibitem{Szem:75} E.~Szemer\'edi.
\newblock On sets of integers containing no $k$ elements in arithmetic progression.
\newblock {\em Acta Arithmetica}, 27:199--245, 1975.

\bibitem{Voigt:84} B.~Voigt. \newblock Canonization theorems for finite affine and linear
spaces. \newblock {\em Combinatorica}, 4(2):219--239, 1984.
\end{thebibliography}

\end{document}
