Ramsey Theory and Sequences of Random Variables
The authors study families of random events \((E_A)_{A\in {[n]\choose k}}\) indexed by the \(k\)-element subsets of \(\{1,\ldots,n\}\) (no assumption is made on the distribution or dependence of these events). They study the minimum of the probability that \(E_A\) is true and \(E_B\) is false, this minimum taken over all shift pairs \((A,B)\), i.e. pairs of \(k\)-element subsets such that \(A\) minus its minimum element is the same as \(B\) minus its maximum element. Let \(\lambda(n,k)\) denote the maximum of this minimum probability, the maximum taken over all such families of random events (so any such family contains a shift pair \((A,B)\) such that the probability that \(E_A\) is true and \(E_B\) false is at most \(\lambda(n,k)\)). For fixed \(k\) the sequence \(\lambda(n,k)\) is decreasing, so there is a limit \(\lambda_k = \lim_{n\to\infty} \lambda(n,k)\). The authors show that \(\lambda_k\) is strictly increasing in \(k\), \[ \lambda_1 = {1\over 4},\quad \lambda_2={1\over 3},\quad \text{and}\quad {1\over 2} - {1\over 2k+2}\leq \lambda_k \leq {1\over 2} - {1\over 4k+2}. \] The authors then apply these results to show that the supremum of the fractional dimension of interval orders is 4, answering a question of Brightwell and Schechtman. They also consider a variant of this structure with sequences of random variables (\(k=1\)) with values in an \(m\)-element set, which leads to theorems on the existence of subsequences near an i. i. d. mix.
This page was built for publication: Ramsey Theory and Sequences of Random Variables
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4212883)
