- graph-theory co.combinatorics metrics max-cut epsilon-nets
- Updated Wed, 22 Jun 2022 08:47:50 GMT

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 on mathoverflow.

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)^{n2} and at most *n*^{2}/(2)^{n2}.

*Update*: If my calculation is correct, a better lower bound (*n*/)^{n2} 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 ^{nn} is at most the *n*th power of the volume of an -ball in ^{n}. Therefore the size of an -net of [0,1]^{nn} 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 Stirlings formula: ln *n*! = *n* ln *n* *n* + O(log *n*).

- +0 – In response to the edit (revision 4) of the question, the lower bound stated in this answer is also applicable to non-proper -nets. — Jan 30, 2011 at 13:59
- +0 – Looks correct, nicely done! — Jan 31, 2011 at 04:15
- +0 – @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. — Jan 31, 2011 at 05:15
- +0 – 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 on MathOverflow. — Feb 21, 2011 at 21:22

External links referenced by this document: