Rado Partition Theorem for Random Subsets of Integers
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\).
- Independent Deuber sets in graphs on the natural numbers
- Random strategies are nearly optimal for generalized van der Waerden games
- Threshold functions and Poisson convergence for systems of equations in random sets
- Counting sum-free sets in abelian groups
- Random sum-free subsets of abelian groups
- Random Van der Waerden theorem
- An asymmetric random Rado theorem: 1-statement
- A note on sparse supersaturation and extremal results for linear homogeneous systems
- Upper tails for counting objects in randomly induced subhypergraphs and rooted random graphs
- The typical structure of sparse \(K_{r+1}\)-free graphs
- A sharp threshold for van der Waerden's theorem in random subsets
- Ramsey properties of random discrete structures
- Online containers for hypergraphs, with applications to linear equations
- Transference for the Erdős-Ko-Rado theorem
- Extremal results for random discrete structures
- Combinatorial theorems in sparse random sets
- Regular pairs in sparse random graphs I
- Independent sets in hypergraphs and Ramsey properties of graphs and the integers
- The Maker-Breaker Rado game on a random set of integers
- The Sharp Threshold for Maximum-Size Sum-Free Subsets in Even-Order Abelian Groups
- Counting configuration-free sets in groups
- Contributions to the problem of Zrankiewicz
- Deviation probabilities for arithmetic progressions and other regular discrete structures
- An asymmetric random Rado theorem for single equations: The 0‐statement
- Schur properties of randomly perturbed sets
- On uncommon systems of equations
- Sharp thresholds for Ramsey properties
- The list-Ramsey threshold for families of graphs
- On the stability of the Erdős-Ko-Rado theorem
- A probabilistic threshold for monochromatic arithmetic progressions
- A Rademacher type formula for partitions and overpartitions
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)