The tag has no wiki summary.

learn more… | top users | synonyms

5
votes
1answer
194 views

$L^2$ discrepancy bound for sequences in $[0,1)$

Given a sequence $x_1,x_2,\dots$, let $D_n$ be the $L^2$-norm of the function $f_n$ whose value at $t \in [0,1)$ is $nt$ minus the number of $1 \leq i \leq n$ with $x_i \leq t$. What can be said ...
1
vote
1answer
38 views

How to compute hereditary discrepancy

I want to compute exactly the hereditary discrepancy of a small (on up to 20 points) set system - is there an efficient way to do it? Brute force search over the discrepancies of all subsystems seems ...
1
vote
1answer
61 views

Beck-Fiala for other discrepancies

Is there an analogue of the Beck-Fiala theorem for linear or hereditary discrepancies of hypergraphs?
6
votes
1answer
283 views

Maximal disarrangement of $n \times n$ numbers

This question is inspired by Martin Erickson's question, "Labeling a Square Array." I'll start by quoting Martin: the $n^2$ cells of an $n \times n$ array are labeled with the integers $1, ...
8
votes
1answer
446 views

Do Shift-chain have Property B?

For $A\subset [n]$ denote by $a_i$ the $i^{th}$ smallest element of $A$. For two $k$-element sets, $A,B\subset [n]$, we say that $A\le B$ if $a_i\le b_i$ for every $i$. A $k$-uniform hypergraph ...
7
votes
3answers
636 views

Distribution of fractional parts of n^{3/2}

What can be said about the limiting distribution of the sequence of fractional parts of $\{n^{a},n>0\}$ for $a\in(1,2)$. I ran a computer experiment for $n\sqrt{n}$ and it looks like uniformly ...
6
votes
1answer
128 views

If every point is contained in at most 3 sets and all sets are big, then is the discrepancy zero?

Suppose we have a finite, 100-uniform system of sets such that any point is contained in at most 3 sets. Is it true that we can color the points such that every set contains 50 red and 50 blue points? ...
38
votes
8answers
4k views

1 rectangle <= 4 squares

Almost 25 years ago a professor at Indiana U showed me the following problem: given a map $\mathbb{Z}^2\rightarrow\mathbb{R}$ such that the sum inside every square (parallel to the axes) is $\leq1$ ...