On the arrangement of point sets in the unit interval (Q1942247): Difference between revisions

Let \(X=(\mathbf{x}_n)_{n=1}^M\) and \(Y=(\mathbf{y}_n)_{n=1}^N\) be two point sets in \([0,1)^s\) with \(1\leq M\leq N\). The following quantity is defined \[ \|X\rightarrow Y\|:=\min_{\substack{ f:X\to Y\\ f\,\text{injective}}}\sum_{n=1}^M\|f(x_n)-x_n\|_2, \] where \(\|\cdot\|\) denotes the usual euclidean norm. \textit{S. Steinerberger} [J. Comb. Optim. 24, No. 3, 280--298 (2012; Zbl 1282.90156)] showed \[ \|X\rightarrow Y\|\leq \sqrt{s}\left(D_N(Y)+\frac{M}{N}\right)^{1/s}M, \] where \(D_N(Y)\) is the extreme discrepancy of \(Y\). The authors improve on the result of Steinerberger in dimension one. First they give the following result on arrangement of a finite point set. For \(Y=(y_n)_{n=1}^N\subset [0,1)\) with the star discrepancy \(D^*_N(Y)\) there exists a permutation \(\pi\) of the set \(\{1,\dots, N\}\) such that \[ D^*_M(y_{\pi(1)},\dots,y_{\pi(M)})\leq \frac{\log M}{M\log 2}+\frac{1}{M}-\frac{1}{2N}+D^*_N(Y) \] for \(1\leq M\leq N\). Finally, the authors obtain the following result in dimension one \[ \|X\rightarrow Y\|\leq 2\frac{M}{N}+\frac{M^2}{N}D_M(X)+MD_N(Y). \] Moreover, they show that if \(|x_n-x_k|>1/N\) for \(n, k\in\{1,\dots, M\}, n\neq k\), then \[ \|X\rightarrow Y\|\leq 3\frac{M}{N}+MD_N(Y). \]