diff options
| author | Chris Wells <chris@mathematicaster.org> | 2026-09-29 09:40:15 -0400 |
|---|---|---|
| committer | Chris Wells <chris@mathematicaster.org> | 2026-09-29 09:40:15 -0400 |
| commit | db06300320d1bebd9a231a3908ca8bb0682761f2 (patch) | |
| tree | adabbf4dfaad8ded426e67092a5671dde66c92ba /data | |
| parent | 2ee4c2b31e409c5cf99bcf867df5446452650026 (diff) | |
| download | main-db06300320d1bebd9a231a3908ca8bb0682761f2.tar main-db06300320d1bebd9a231a3908ca8bb0682761f2.tar.gz main-db06300320d1bebd9a231a3908ca8bb0682761f2.tar.bz2 main-db06300320d1bebd9a231a3908ca8bb0682761f2.tar.lz main-db06300320d1bebd9a231a3908ca8bb0682761f2.tar.xz main-db06300320d1bebd9a231a3908ca8bb0682761f2.tar.zst main-db06300320d1bebd9a231a3908ca8bb0682761f2.zip | |
Diffstat (limited to 'data')
| -rw-r--r-- | data/papers.bib | 2 |
1 files changed, 1 insertions, 1 deletions
diff --git a/data/papers.bib b/data/papers.bib index fb9ae90..f9bde4b 100644 --- a/data/papers.bib +++ b/data/papers.bib @@ -19,7 +19,7 @@ eprintclass = {math.CO}, archivePrefix = {arXiv}, archiveClass = {math.CO}, - abstract = {We study a finite form of the classical interval discrepancy problem. Starting from the unit interval, one repeatedly splits an existing interval into two until $n$ intervals have been produced. The discrepancy of such a process is the maximum, over all intermediate stages, of the ratio between the longest interval and the shortest interval. A theorem of de Bruijn and Erdős from 1949 shows that this ratio must approach $2$ as $n\to\infty$, and they give a sharp construction achieving this bound. For fixed $n$, their construction gives the upper bound $\operatorname{disc}(n)\leq 2-\frac{3}{2n}+O(1/n^2)$. In this paper, we improve the first-order term of this bound. Specifically, we construct a strategy, called <em>lex-merge</em>, with $\operatorname{disc}(n)\leq 2-\frac{4\ln 2}{n}+O(1/n^2)$. We prove also the lower bound $\operatorname{disc}(n)\geq 2-\frac{6\ln 2}{n}-O(1/n^2)$, showing that the first-order term in this improvement over the de Bruijn–Erdős construction has the correct order of magnitude. We conjecture that the lex-merge strategy is optimal for every $n$.}, + abstract = {We study a finite form of the classical interval discrepancy problem. Starting from the unit interval, one repeatedly splits an existing interval into two until $n$ intervals have been produced. The discrepancy of such a process is the maximum, over all intermediate stages, of the ratio between the longest interval and the shortest interval. A theorem of de Bruijn and Erdős from 1949 shows that this ratio must approach $2$ as $n\to\infty$, and they give a sharp construction achieving this bound. For fixed $n$, their construction gives the upper bound $\operatorname{disc}(n)\leq 2-\frac{3}{2n}+O\bigl({1\over n^2}\bigr)$. In this paper, we prove that $\operatorname{disc}(n)=2^{1-1/\lceil n/2\rceil}=2-{4\ln 2\over n}+O\bigl({1\over n^2}\bigr)$ for every $n$.} } @article{briggs_gromov, |
