1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Finding a semi-sparse vertex in a grid

Discussion in 'Mathematics' started by user113298, Oct 8, 2018.

  1. user113298

    user113298 Guest

    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$?

    Login To add answer/comment

Share This Page