<p>Here is an easy estimate.  Here we call a set <i>S</i>⊆<i>X</i> an <em><i>ε</i>-net</em> of a metric space <i>X</i> when for every point <i>x</i>∈<i>X</i>, there exists a point <i>s</i>∈<i>S</i> such that the distance between <i>x</i> and <i>s</i> is <strong>at most</strong> <i>ε</i>.  If you want a strict inequality in the definition of <i>ε</i>-net, you can tweak the value of <i>ε</i> slightly.</p>

<p>It holds that ||<i>A</i>||<sub>∞</sub> ≤ ||<i>A</i>||<sub>C</sub> ≤ <i>n</i><sup>2</sup>||<i>A</i>||<sub>∞</sub>, where ||<i>A</i>||<sub>∞</sub> denotes the entrywise max-norm of an <i>n</i>×<i>n</i> matrix <i>A</i>.</p>

<p>It is easy to construct an <i>ε</i>-net of the metric space ([0,1]<sup><i>N</i></sup>, <i>d</i><sub>∞</sub>) with size ⌈1/(2<i>ε</i>)⌉<sup><i>N</i></sup>, and it is not hard to show that this size is the minimum.  (To show the minimality, consider the ⌈1/(2<i>ε</i>)⌉<sup><i>N</i></sup> points whose coordinates are multiples of 1/⌈1/(2<i>ε</i>)−1⌉ and show that the distance between any two of these points is greater than 2<i>ε</i>.)  By setting <i>N</i>=<i>n</i><sup>2</sup> and combining this with the aforementioned comparison between the cut norm and the max-norm, the minimum cardinality of an <i>ε</i>-net with respect to the cut norm is at least ⌈1/(2<i>ε</i>)⌉<sup><i>n</i><sup>2</sup></sup> and at most ⌈<i>n</i><sup>2</sup>/(2<i>ε</i>)⌉<sup><i>n</i><sup>2</sup></sup>.</p>

<hr>

<p><em>Update</em>: If my calculation is correct, a better lower bound Ω(<i>n</i>/<i>ε</i>)<sup><i>n</i><sup>2</sup></sup> can be obtained by the volume argument.  To do this, we need an upper bound on the volume of an <i>ε</i>-ball with respect to the cut norm.</p>

<p>First we consider the “cut norm” of a single vector, which is the maximum between the sum of positive elements and the negated sum of negative elements.  It is not hard to show that the volume of an <i>ε</i>-ball in ℝ<sup><i>n</i></sup> with respect to this “cut norm” is equal to</p>

<p>$$ \varepsilon^n \sum_{I \subseteq \{1,\dotsc,n\}} \frac{1}{|I|!} \cdot \frac{1}{(n-|I|)!}
= \varepsilon^n \sum_{r=0}^n \binom{n}{r} \frac{1}{r!(n-r)!} $$</p>

<p>$$ = \frac{\varepsilon^n}{n!} \sum_{r=0}^n \binom{n}{r}^2
= \frac{\varepsilon^n}{n!} \binom{2n}{n}
= \frac{(2n)!\varepsilon^n}{(n!)^3}. $$</p>

<p>Next, since the cut norm of an <i>n</i>×<i>n</i> matrix <i>A</i> is greater than or equal to the cut norm of each row, the volume of an <i>ε</i>-ball in ℝ<sup><i>n</i>×<i>n</i></sup> is at most the <i>n</i>th power of the volume of an <i>ε</i>-ball in ℝ<sup><i>n</i></sup>.  Therefore the size of an <i>ε</i>-net of [0,1]<sup><i>n</i>×<i>n</i></sup> must be at least</p>

<p>$$ \frac{(n!)^{3n}}{(2n)!^n \varepsilon^{n^2}} = \left(\Omega\left(\frac{n}{\varepsilon}\right)\right)^{n^2}, $$</p>

<p>where the last equality is a boring calculation in which we use <a href="http://en.wikipedia.org/wiki/Stirling%27s_approximation" rel="noreferrer">Stirling’s formula</a>: ln <i>n</i>! = <i>n</i> ln <i>n</i> − <i>n</i> + O(log <i>n</i>).</p>

CC BY-SA 2.5
2011-01-30T13:59:48.783Z
In response to the edit (revision 4) of the question, the lower bound stated in this answer is also applicable to “non-proper” ε-nets.
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-31T04:15:00.690Z
Looks correct, nicely done!
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-01-31T05:15:43.220Z
@Hsien-Chih: Thanks.  The part I like the most is the use of binomial coefficients in the calculation of the volume of an ε-ball in ℝ^n.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-21T21:22:53.843Z
I suspect that the lower bound on the size of the net (equivalently, the upper bound on the volume) can be improved.  I asked a [related question](http://mathoverflow.net/questions/56218/the-volume-of-the-unit-ball-in-mathbbrm-times-n-with-respect-to-the-cut) on MathOverflow.
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-29T22:51:02.423Z
2011-01-30T22:52:00.483Z
2011-01-30T22:52:00.483Z
Tsuyoshi Ito
<p>The cut norm $||A||_C$ of a real matrix $A = (a_{i,j}) \in \mathcal{R}^{n\times n}$ is the maximum over all $I \subseteq [n], J \subseteq [n]$ of the quantity $\left|\sum_{i \in I, j \in J}a_{i,j}\right|$. </p>

<p>Define the distance between two matrices $A$ and $B$ to be $d_C(A,B) = ||A-B||_C$</p>

<blockquote>
  <p>What is the cardinality of the smallest $\epsilon$-net of the metric space $([0,1]^{n\times n}, d_C)$?</p>
</blockquote>

<p>i.e. the size of the smallest subset $S \subset [0,1]^{n\times n}$ such that for all $A \in [0,1]^{n\times n}$, there exists an $A' \in S$ such that $d_C(A, A') \leq \epsilon$.  </p>

<p>(EDIT: I forgot to mention, but I am also interested in "non-proper" $\epsilon$-nets, with $S \subset \mathcal{R}_+^{n\times n}$ -- i.e. if the elements of the $\epsilon$-net have entries outside of [0,1], that is also interesting.)</p>

<p>I am interested in both upper bounds and lower bounds. </p>

<p>Note that cut sparsifier techniques imply $\epsilon$-nets for cut metrics, but give something stronger than I need -- they give an $\epsilon$-net for which you can efficiently find an $\epsilon$-close point to any matrix simply by sampling from that matrix. One might imagine that there exist much smaller $\epsilon$-nets for which you cannot simply sample do find an $\epsilon$-close point to an arbitrary matrix.</p>

<p>I initially asked this question <a href="https://mathoverflow.net/questions/53542/epsilon-nets-with-respect-to-the-cut-norm">here</a> on mathoverflow. </p>

CC BY-SA 2.5
2011-01-29T21:20:35.797Z
Because the cut norm of A is greater than or equal to the absolute value of each entry of A, it is clear that an ε-net must have size at least (1/(2ε))^(n^2).  What is the upper bound derived from the cut sparsifier technique?  (This is probably a dumb question, but I do not know that technique.)
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-30T00:51:09.230Z
Just to make sure, I turned the first half of my previous comment into an answer (and added an upper bound to it).  I am still interested in the upper bound derived from the cut sparsifier technique.
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-30T13:46:48.823Z
The above technique yields matrices with entries in $\{0, m||A||_1\}$ rather than in $[0,1]$. I forgot to mention it in the post, but I am also interested in these kinds of $\epsilon$-covers.
Aaron Roth
CC BY-SA 2.5
2011-01-30T14:15:08.767Z
The $\epsilon$-net you get from cut sparsification does not actually lie in $[0,1]^{n×n}$. Interpret the matrix as a probability distribution over the edges of a directed graph, and sample $m=\tilde{O}(n/\epsilon^2)$ edges from the distribution. Weight each edge by $||A||_1/m$. By VC-dimension arguments (or just a union bound over cuts), the max additive error on any cut will w.h.p. be $O(\epsilon n^2)$. So this implies that that the set of (appropriately weighted) graphs on $n^5/\epsilon^2$ edges form an $\epsilon$-net, which is non-trivial for $\epsilon>n^{3/2}$.
Aaron Roth
<graph-theory><co.combinatorics><metrics><max-cut><epsilon-nets>
$\epsilon$-nets with respect to the cut norm
Aaron Roth
# $\epsilon$-nets with respect to the cut norm

(Asked by: username_0 on 2011-01-28)

The cut norm $||A||\_C$ of a real matrix $A = (a\_{i,j}) \in \mathcal{R}^{n\times n}$ is the maximum over all $I \subseteq [n], J \subseteq [n]$ of the quantity $\left|\sum\_{i \in I, j \in J}a\_{i,j}\right|$.

Define the distance between two matrices $A$ and $B$ to be $d\_C(A,B) = ||A-B||\_C$

> What is the cardinality of the smallest $\epsilon$-net of the metric space $([0,1]^{n\times n}, d\_C)$?

i.e. the size of the smallest subset $S \subset [0,1]^{n\times n}$ such that for all $A \in [0,1]^{n\times n}$, there exists an $A' \in S$ such that $d\_C(A, A') \leq \epsilon$.

(EDIT: I forgot to mention, but I am also interested in "non-proper" $\epsilon$-nets, with $S \subset \mathcal{R}\_+^{n\times n}$ -- i.e. if the elements of the $\epsilon$-net have entries outside of [0,1], that is also interesting.)

I am interested in both upper bounds and lower bounds.

Note that cut sparsifier techniques imply $\epsilon$-nets for cut metrics, but give something stronger than I need -- they give an $\epsilon$-net for which you can efficiently find an $\epsilon$-close point to any matrix simply by sampling from that matrix. One might imagine that there exist much smaller $\epsilon$-nets for which you cannot simply sample do find an $\epsilon$-close point to an arbitrary matrix.

I initially asked this question [here](https://mathoverflow.net/questions/53542/epsilon-nets-with-respect-to-the-cut-norm) on mathoverflow.

**Tags:** graph-theory, co.combinatorics, metrics, max-cut, epsilon-nets
> **Comments:**
> **username_1**: Because the cut norm of A is greater than or equal to the absolute value of each entry of A, it is clear that an ε-net must have size at least (1/(2ε))^(n^2).  What is the upper bound derived from the cut sparsifier technique?  (This is probably a dumb question, but I do not know that technique.)  
> **username_1**: Just to make sure, I turned the first half of my previous comment into an answer (and added an upper bound to it).  I am still interested in the upper bound derived from the cut sparsifier technique.  
> **username_0**: The above technique yields matrices with entries in $\{0, m||A||_1\}$ rather than in $[0,1]$. I forgot to mention it in the post, but I am also interested in these kinds of $\epsilon$-covers.  
> **username_0**: The $\epsilon$-net you get from cut sparsification does not actually lie in $[0,1]^{n×n}$. Interpret the matrix as a probability distribution over the edges of a directed graph, and sample $m=\tilde{O}(n/\epsilon^2)$ edges from the distribution. Weight each edge by $||A||_1/m$. By VC-dimension arguments (or just a union bound over cuts), the max additive error on any cut will w.h.p. be $O(\epsilon n^2)$. So this implies that that the set of (appropriately weighted) graphs on $n^5/\epsilon^2$ edges form an $\epsilon$-net, which is non-trivial for $\epsilon>n^{3/2}$.  

---

## 1 answers

### Answer by username_1 on 2011-01-29. Score: 9 | Accepted answer

Here is an easy estimate. Here we call a set *S*⊆*X* an **ε*-net* of a metric space *X* when for every point *x*∈*X*, there exists a point *s*∈*S* such that the distance between *x* and *s* is **at most** *ε*. If you want a strict inequality in the definition of *ε*-net, you can tweak the value of *ε* slightly.

It holds that ||*A*||∞ ≤ ||*A*||C ≤ *n*2||*A*||∞, where ||*A*||∞ denotes the entrywise max-norm of an *n*×*n* matrix *A*.

It is easy to construct an *ε*-net of the metric space ([0,1]*N*, *d*∞) with size ⌈1/(2*ε*)⌉*N*, and it is not hard to show that this size is the minimum. (To show the minimality, consider the ⌈1/(2*ε*)⌉*N* points whose coordinates are multiples of 1/⌈1/(2*ε*)−1⌉ and show that the distance between any two of these points is greater than 2*ε*.) By setting *N*=*n*2 and combining this with the aforementioned comparison between the cut norm and the max-norm, the minimum cardinality of an *ε*-net with respect to the cut norm is at least ⌈1/(2*ε*)⌉*n*2 and at most ⌈*n*2/(2*ε*)⌉*n*2.

---

*Update*: If my calculation is correct, a better lower bound Ω(*n*/*ε*)*n*2 can be obtained by the volume argument. To do this, we need an upper bound on the volume of an *ε*-ball with respect to the cut norm.

First we consider the “cut norm” of a single vector, which is the maximum between the sum of positive elements and the negated sum of negative elements. It is not hard to show that the volume of an *ε*-ball in ℝ*n* with respect to this “cut norm” is equal to

$$ \varepsilon^n \sum\_{I \subseteq \{1,\dotsc,n\}} \frac{1}{|I|!} \cdot \frac{1}{(n-|I|)!}
= \varepsilon^n \sum\_{r=0}^n \binom{n}{r} \frac{1}{r!(n-r)!} $$

$$ = \frac{\varepsilon^n}{n!} \sum\_{r=0}^n \binom{n}{r}^2
= \frac{\varepsilon^n}{n!} \binom{2n}{n}
= \frac{(2n)!\varepsilon^n}{(n!)^3}. $$

Next, since the cut norm of an *n*×*n* matrix *A* is greater than or equal to the cut norm of each row, the volume of an *ε*-ball in ℝ*n*×*n* is at most the *n*th power of the volume of an *ε*-ball in ℝ*n*. Therefore the size of an *ε*-net of [0,1]*n*×*n* must be at least

$$ \frac{(n!)^{3n}}{(2n)!^n \varepsilon^{n^2}} = \left(\Omega\left(\frac{n}{\varepsilon}\right)\right)^{n^2}, $$

where the last equality is a boring calculation in which we use [Stirling’s formula](http://en.wikipedia.org/wiki/Stirling%27s_approximation): ln *n*! = *n* ln *n* − *n* + O(log *n*).

> **Comments:**
> **username_1**: In response to the edit (revision 4) of the question, the lower bound stated in this answer is also applicable to “non-proper” ε-nets.  
> **username_2**: Looks correct, nicely done!  
> **username_1**: @Hsien-Chih: Thanks.  The part I like the most is the use of binomial coefficients in the calculation of the volume of an ε-ball in ℝ^n.  
> **username_1**: I suspect that the lower bound on the size of the net (equivalently, the upper bound on the volume) can be improved.  I asked a [related question](http://mathoverflow.net/questions/56218/the-volume-of-the-unit-ball-in-mathbbrm-times-n-with-respect-to-the-cut) on MathOverflow.  

---

