Finding a semi-sparse vertex in a grid

Question

Let $H$ be a $r \times r$ grid. Suppose that at most $r/10^5$ vertices of this grid are colored red. For every vertex $v \in V(H)$, let $B_i(v)$ be the ball of radius $i$ centered at $v$. (Or for simplicity you can consider the $2i+1 \times 2i+1$ sub-grid centered at $v$.). Let $C_i(v) = B_i(v) \setminus B_{i/2}(v)$, for $i \in I:=\{2^k\colon k\in\mathbb{Z}, 1\leq k\leq\frac{\log r}{\log 2} \}$; that is the annulus of radius $i$ around $v$. Is the following claim true: There exists a vertex $v \in V(H)$ such that for every $i \in I$, we have that the number of red vertices in $C_i(v)$ is at most $i$?

Answer 1

(This is not an answer to the OP's question¹, under any of its interpretations, only an extended comment which the comment box is too small to contain, a comment thought to be helpful to the OP. It is an illustrated summary of what the OP---who so far has not responded to even the more important requests for clarification in the comments--- seems to be asking for.)

Beginning of extended comment on OP.

One-sentence summary of what the OP seems to be asking for in essence. What is the lowest density such that one can still find a 'mass distribution' in a 2-dimensional grid such that around each grid-point there exists at least one 'balancedly-hollow shell'² of density $\Omega(\frac{1}{\text{radiusoftheshell}})$?

Detailed summary of what the OP is asking(with a little interpretation on my part, in particular assuming toroidal topology on the grid). The OP in essence seems to be asking for what is the smallest $\delta\in[0,1]$ such that it is still possible to choose the following data:

• a number $r\in\omega$,
• a function $\mathrm{c}\colon (\mathbb{Z}/r\mathbb{Z})^2\rightarrow\{0,1\}$,
• a function $\mathrm{k}\colon (\mathbb{Z}/r\mathbb{Z})^2\rightarrow\mathbb{Z}$,

such that the following axioms are satisfied:

1. $\frac{\lvert\mathrm{c}^{-1}(1)\rvert}{r^2}\leq \delta$,
2. for each $v\in (\mathbb{Z}/r\mathbb{Z})^2,\qquad$ $1\leq\mathrm{k}(v)\leq\frac{\log r}{\log 2}$,
3. for each $v=(x_0,y_0)\in (\mathbb{Z}/r\mathbb{Z})^2,\qquad$ ${\small\lvert\{ (x_1,y_1)\in (\mathbb{Z}/r\mathbb{Z})^2\colon\qquad { \small 2^{\mathrm{k}(v)-1}<\lvert x_1-x_0\rvert_{\mathrm{mod}\ r}\leq 2^{\mathrm{k}(v)},\ 2^{\mathrm{k}(v)-1}<\lvert y_1-y_0\rvert_{\mathrm{mod}\ r}\leq 2^{\mathrm{k}(v)},\ \mathrm{c}(x_1,y_1)=1\}\rvert>2^{\mathrm{k}(v)}}}$

Remarks.

• The $\mathrm{c}$-value $1$ is interpreted as the color 'red'.

• For each $r\in\omega(r)$ there is a smallest $\delta_{\text{user113298}}(r)\in[0,1]$ such that a 'mass-distribution'(i.e. function $\mathrm{c}$) like the above exists, since in the trivial case $\delta:=1$, upon choosing $\mathrm{c}(v)=1$ for all $v$ and $\mathrm{k}(v):=1$, one finds that 1. and 2. hold by definition, and that 3. is true in the form of $16>2$.

• The OP in particular seems to be asking for something similar to whether $\delta_{\text{user113298}}(r) > \frac{1}{10^5}\frac{1}{r}$ ($= \frac{r/10^5}{\lvert r\times r \rvert}$). (This seems the greatest distortion the present interpretation causes compared with the OP's original formulation; I have strengthened a formulation one obtains when applying the usual negation-rules to the OP's original question which has quantifier structure

$\exists v \forall i\quad \text{$C_i(v)$ sparse}$

whose negation of course is

$\forall v \exists i\quad \text{$C_i(v)$ not sparse}$. )

• Like 'domotorp' suggested, there are generalizations of the above to an arbitrary dimension $d\geq 1$, suggesting an analogously defined 'physical constant' $\delta_{\text{user113298}}(d,r)\in [0,1]$.

• There is the followig reason for the $\Omega(\frac{1}{\text{outerradius}})$ in the above one-sentence-rendition. Evidently, abbreviating $k:=\mathrm{k}(v)$, there are exactly $(2^{k+1}+1)(2^{k+1}+1)-(2^k+1)(2^k+1) = 2^{k+1}\cdot(3\cdot 2^{k-1}+1)$ grid-points in the set ${\{ (x_1,y_1)\in (\mathbb{Z}/r\mathbb{Z})^2\colon\qquad { \small 2^{\mathrm{k}(v)-1}<\lvert x_1-x_0\rvert_{\mathrm{mod}\ r}\leq 2^{\mathrm{k}(v)},\ 2^{\mathrm{k}(v)-1}<\lvert y_1-y_0\rvert_{\mathrm{mod}\ r}\leq 2^{\mathrm{k}(v)}\}}}$

and hence the red-dot-density ($=$'mass density') of the 'shell' picked by the 'witness function' $\mathrm{k}(v)$ is required to be $>\frac{1}{3\cdot 2^k + 2} \in \Theta_{i=2^k\rightarrow\infty}(\frac{1}{i})$.

An illustration relevant to the OP. In the following picture one sees a representation of an 100x100 grid, which I would suggest to be equipped not with the topology of the plane, but rather with the quotient topology w.r.t. identifying opposite points of its boundary (aka 'toroidal topology'). In particular, the 'overlapping' annulus is to be thought of as 'wrapping around the torus'.

Moreover, one sees a representation of one "annulus of radius $i$" in the OP, using the "$2i+1\times 2i+1$ subgrid"-interpretation permitted by the OP, for $i:=\mathrm{k}(v):=2^5$. (Note that the annulus has exactly $(2^6+1)(2^6+1)-(2^5+1)(2^5+1)=3136$ black grid-points.) Instead of the center-vertex $v$ I have displayed the 'outer radius' $2^5$ of the 'grid annulus' in the center of the annulus.

Moreover, I have displayed exactly $33>2^5$ randomly selected red vertices in said annulus, which, by itself make this annulus violate the property that the OP seems to be hoping for.

Here, axiom 3. holds in the instance of this particular annulus-center in the form of $33>2^5$.

Needless to say, this is not a counterexample to the OP's question, already because this is but one of the $100\times 100 = 10^4$ such annuli one would have to display if one were to give an explicit counterexample in such a way.

¹ _{Which appears (to me) to have some non-trivial substance and not to be answerable straight out of the literature.}

² _{Where 'balancedly-hollow shell' is the shortest sort-of-self-explanatory term I can think of for 'hollow shell of outer radius a power of two and inner radius equal to half of the outer radius. Moreover, arguably the essence of the OP's formulation is not that the inner radius be half the outer radius, rather the asymptotic statement that $\mathrm{innerradius}\sim_{r\to\infty}\mathrm{outerradius}$. Because of this, and for brevity, I replaced '$\Omega(\frac{1}{\mathrm{outerradiusofshell}})$ with $\Omega(\frac{1}{\mathrm{radiusofshell}})$ in the 'one-sentence summary above.}

End of extended comment on OP.