Rado Partition Theorem for Random Subsets of Integers

From MaRDI portal





The paper is a contribution to Ramsey theory. It introduces a new partition theorem for random subsets of integers. Let \(A=(a_{ij})\) be an \(l\times k\) matrix of integers. The symbol \({\mathcal L}(A)\) denotes the system of homogeneous linear equations \[ \sum_{j=1}^{k} a_{ij} x_j=0,\qquad\text{for}\qquad 1\leq i\leq l. \] The authors assume (without loss of generality) that the system \({\mathcal L}(A)\) is irredundant, i.e. that for each \(i\not= j\) there exists a solution \((x_1,\ldots, x_k)\) such that \(x_i\not= x_j\). The matrix \(A\) is said to be partition regular if for any finite colouring of the integers there is always a solution to \({\mathcal L}(A)\) with all \(x_j\) having the same colour. The matrix \(A\) is said to be density regular if every set of integers \(F\), such that \[ \limsup_{n\rightarrow\infty}\frac{|F\cap[n]|}{n} > 0, \] contains a distinct-valued solution of \({\mathcal L}(A)\) (\([n]\) denotes the set of integers \(\{1,\ldots, n\}\)). In the theorem presented below the authors use the ``arrow notation of Erdős and Rado. Let \(A\) be a partition regular matrix, \(r\) be an integer and \(F\) be a set of integers. The symbol \(F\rightarrow (A)_r\) denotes that for any partition \(F=F_1\cup\cdots\cup F_r\) there exists \(i\in\{1,\ldots, r\}\) and a solution \((x_1,\ldots, x_k)\) of \({\mathcal L}(A)\) such that \(x_s\in F_i\) for all \(s=1,\ldots, k\). The theorem presents a threshold specifying for which \(N\) (\(1\leq N\leq n\)) almost all randomly selected \(N\)-element subsets \(F\subset[n]\) have the property \(F\rightarrow (A)_r\). Theorem. For every \(l\times k\) irredundant, density regular matrix \(A\) of rank \(h(A)=l\) and for every integer \(r\geq 2\), there exist constants \(c\) and \(C\) such that \[ \lim_{n\rightarrow\infty} P([n]_N\rightarrow (A)_r)=\begin{cases} 0 &\text{ if } N < cn^{(1 -\frac{1}{m_A})},\\ 1 &\text{ if } n>Cn^{(1-\frac{1}{m_A})},\end{cases} \] where \[ m_a=\max_{2\leq q\leq k}\max_{Q\subseteq[k],|Q|=q}\frac{q-1}{q-1+h(A^Q)-l}. \] In the last expression \(A^Q\) denotes the matrix which is derived from \(A\) by deletion of the columns with indices from \(Q\).




Cited in
(31)








This page was built for publication: Rado Partition Theorem for Random Subsets of Integers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4344037)