Kunal Dutta
email: duttkunal@gmail.com

Arijit Ghosh

On Subgraphs of Bounded Degeneracy in Hypergraphs

Keywords: degenerate graphs, independent sets, hypergraphs, and random permutations . We will call

A k-uniform hypergraph has degeneracy bounded by d if every induced subgraph has a vertex of degree at most d. Given a kuniform hypergraph H = (V (H), E(H)), we show there exists an induced subgraph of size at least

,

and dH (v) denotes the degree of vertex v in the hypergraph H. This extends and generalizes a result of Alon-Kahn-Seymour (Graphs and Combinatorics, 1987) for graphs, as well as a result of Dutta-Mubayi-Subramanian (SIAM Journal on Discrete Mathematics, 2012) for linear hypergraphs, to general k-uniform hypergraphs. We also generalize the results of Srinivasan and Shachnai (SIAM Journal on Discrete Mathematics, 2004) from independent sets (0-degenerate subgraphs) to d-degenerate subgraphs. We further give a simple nonprobabilistic proof of the Dutta-Mubayi-Subramanian bound for linear k-uniform hypergraphs, which extends the Alon-Kahn-Seymour (Graphs and Combinatorics, 1987) proof technique to hypergraphs. Our proof combines the random permutation technique of Bopanna-Caro-Wei (see e.g. The Probabilistic Method, N. Alon and J. H. Spencer; Dutta-Mubayi-Subramanian) and also Beame-Luby (SODA, 1990) together with a new local density argument which may be of independent interest. We also provide some applications in discrete geometry, and address some natural algorithmic questions.

Introduction

For k ≥ 2, a k-uniform hypergraph is a pair (V (H), E(H)) where E(H) ⊆

V (H) k

When there is no chance of confusion, we will use V and E to denote V (H) and E(H). For a vertex v ∈ V (H), degree d H (v) of V (H) will denote |{e : e ∈ E(H), v ∈ e}|. For readability, k -1 will be denoted by t.

For a subset I ⊆ V (H), the induced k-uniform hypergraph H(I) of I denotes the hypergraph (I, E(H) ∩ I k ). A hypergraph is linear if every pair of vertices are contained in at most a single hyperedge, i.e. any pair of hyperedges intersect in at most one vertex. A hypergraph H = (V, E) is d-degenerate if the induced hypergraph of all subsets of V has a vertex of degree at most d, i.e., for all I ⊆ V , there exists v ∈ I such that d H(I) (v) ≤ d. For a k-uniform hypergraph H = (V, E), we will denote by α k, d (H) the size of a maximum-sized subset of V whose induced hypergraph is d-degenerate, i.e.,

α k, d (H) = max {|I| : I ⊆ V, H(I) is d-degenerate} .
Observe that α(H) := α k, 0 (H) is the independence number of the hypergraph H.

Previous Results

Turán [START_REF] Turán | On an extremal problem in graph theory[END_REF] gave a lower bound on the independence number of graphs: α(G) ≥ n d+1 where d is the average degree of vertices in G. Caro [START_REF] Caro | New results on the independence number[END_REF] and Wei [START_REF] Wei | A lower bound on the stability number of a simple graph[END_REF] independently showed that for graphs

α(G) ≥ v∈V (G) 1 d G (v) + 1
, see [START_REF] Alon | The Probabilistic Method[END_REF]. This degree-sequence based bound improves on the original averagedegree based lower bound of Turán, and matches it in the case when all degrees are equal.

For hypergraphs, Spencer [START_REF] Spencer | Turán's theorem for k-graphs[END_REF] gave a bound on the independence number, based on the average degree d: α(H) ≥ c k n d 1/t , where c k is independent of n and d. Caro and Tuza [START_REF] Caro | Improved lower bounds on k -independence[END_REF] generalized the Caro-Wei result to the case of hypergraphs:

Theorem 1. For all k-uniform hypergraph H, we have α(H) ≥ v∈V 1 d H (v)+1/t d H (v)
.

The above theorem directly implies the following corollary, which gives Spencer's bound:

Corollary 1. For all k ≥ 2, There exists d k > 0 such that all k-uniform hypergraphs H satisfy

α(H) ≥ d k v∈V 1 (1 + d H (v)) 1/t .
Further, Thiele [START_REF] Thiele | A lower bound on the independence number of arbitrary hypergraphs[END_REF] obtained a lower bound on the independence number of arbitrary (non-uniform) hypergraphs, in terms of the degree rank, a generalization of the degree sequence.

On the algorithmic side, Srinivasan and Shachnai [START_REF] Shachnai | Finding large independent sets in graphs and hypergraphs[END_REF], used the random permutation method of Beame and Luby [START_REF] Beame | Parallel search for maximal independence given minimal dependence[END_REF] and also Bopanna-Caro-Wei (see e.g. [START_REF] Alon | The Probabilistic Method[END_REF], [START_REF] Dutta | New Lower Bounds for the Independence Number of Sparse Graphs and Hypergraphs[END_REF]), together with the FKG correlation inequality, to obtain a randomized parallel algorithm for independent sets, which matched the asymptotic form of the Caro-Tuza bound. Dutta, Mubayi and Subramanian [DMS12] also used the Bopanna-Caro-Wei method; using elementary techniques they obtained degree-sequence based lower bounds on the independence numbers of K r -free graphs and linear k-uniform hypergraphs, which generalized the earlier average-degree based bounds of Ajtai et al. [START_REF] Ajtai | A Note on Ramsey Numbers[END_REF], Shearer [START_REF] Shearer | A note on the independence number of triangle-free graphs[END_REF][START_REF] Shearer | On the Independence Number of Sparse Graphs[END_REF] and Duke, Lefmann and Rödl [START_REF] Duke | On Uncrowded Hypergraphs[END_REF], in terms of degree sequences.3 Average degree vs. degree-sequence In general, a bound using the degree sequence would be intuitively expected to be better than a bound using just the average degree, since it has more information about the graph. For the above bounds on the independence numbers, this essentially follows from the convexity of the function x -1/t . Dutta-Mubayi-Subramanian [START_REF] Dutta | New Lower Bounds for the Independence Number of Sparse Graphs and Hypergraphs[END_REF] gave constructions of hypergraphs which show that the bounds based on the degree-sequence can be stronger than those based on the average degree by a polylogarithmic (in the number of vertices) factor.

Large d-degenerate subgraphs Compared to independent sets, d-degenerate subgraphs have been less well-investigated. However, it includes as special cases zero-degenerate subgraphs i.e. independent sets, as well as 1-degenerate subgraphs, i.e. maximum induced forests, whose complements are the well-known hitting set and feedback vertex set problems respectively. The best known result on this question is that of Alon, Kahn and Seymour [START_REF] Alon | Large induced degenerate subgraphs[END_REF], who proved the following lower bound for α 2, d (G):4 Theorem 2 ([AKS87]). For all graphs G = (V, E) we have

α 2, d (G) ≥ v∈V min 1, d + 1 d G (v) + 1 .
This bound is sharp for every G which is a disjoint union of cliques. Moreover, they gave a polynomial time algorithm that finds in G an induced d-degenerate subgraph of at least this size.

On the algorithmic side, Pilipczuk and Pilipczuk [START_REF] Pilipczuk | Proceedings, chapter Finding a Maximum Induced Degenerate Subgraph Faster Than 2 n[END_REF] addressed the question of finding a maximum d-degenerate subgraph of a graph, giving the first algorithm with running time o(2 n ). Zaker [START_REF] Zaker | Generalized degeneracy, dynamic monopolies and maximum degenerate subgraphs[END_REF] studied a more general version of degeneracy and gave upper and lower bounds for finding the largest subgraph of a 2-uniform graph having a given generalized degeneracy.

The proof of Dutta-Mubayi-Subramanian [START_REF] Dutta | New Lower Bounds for the Independence Number of Sparse Graphs and Hypergraphs[END_REF] implies the following lower bound on α k, d for linear hypergraphs (though not explicitly stated in their paper):

Theorem 3 ([DMS12]). Let G = (V, E) be a linear k-uniform hypergraph, and for all v ∈ V , d G (v) denote the degree of v in G. Then α k, d (G) ≥ w(G) := v∈V w G (v), (1)
where

w(v) =    1 if d G (v) ≤ d 1 1+(t(d+1)) -1 ( d G (v) d+1 ) ( d G (v)+1/t d G (v)-d-1 ) if d G (v) > d.
(2)

Our Results

We first give a completely different and an extremely simple proof of Theorem 3 using a weight function. Our proof follows along the lines of the proof of Theorem 2 due to Alon, Kahn and Seymour [START_REF] Alon | Large induced degenerate subgraphs[END_REF].

Next, we extend Theorem 3 to the case of general hypergraphs:

Theorem 4. Let G = (V, E) be a k-uniform hypergraph, and for all v ∈ V , d G (v) denote the degree of v in G. Then α k, d (G) ≥ v∈V min 1, c k d + 1 d(v) + 1 1/t , (3)
where t = k -1 and c k = 2 -1-1/(k-1) . There exists a randomized algorithm that can extract a d-degenerate set of above size in expectation.

Our proof uses the random permutation method [AS08] of Bopanna-Caro-Wei, together with a new local density argument, avoiding advanced correlation inequalities. As a consequence, we obtain a simpler proof as well as a generalization of the result of Srinivasan-Shachnai [START_REF] Shachnai | Finding large independent sets in graphs and hypergraphs[END_REF].

As an application of Theorem 4 we will prove the following result in incidence geometry, which generalizes a result of Payne and Wood [START_REF] Payne | On the General Position Subset Selection Problem[END_REF] on the maximum size of a subset, out of n points in the plane, such that no three points in the subset are collinear.

Lemma 1. 1. Let P be a set of n points in the plane such that for any line l in the plane |l ∩ P | ≤ . For d ≤ O(n log + 2 ) there exists a subset S ⊆ P with at most d|S| collinear triples in S and

|S| = Ω d n 2 n log + 2 . And if ≤ O( √ n), then |S| = Ω d n log .
2. Let P be a set of n points in the plane such that for any line l in the plane

|l ∩ P | ≤ . Let k ≥ 4 be a constant and d ≤ O( k-3 n + k-1
). Then there exists a subset S ⊆ P of size

Ω n d k-3 n + k-1 1/(k-1) such that S has at most d|S| collinear k-tuples in S. And if ≤ O( √ n), then |S| = Ω n k-2 d k-3 1/(k-1)
.

The proof of Lemma 1 uses the following lemma by Payne and Wood [PW13], proved using Szemerédi-Trotter theorem [START_REF] Szemerédi | Extremal problems in discrete geometry[END_REF] on incidence geometry.

Lemma 2 ([PW13]).

1. Let P be a set of n points in the plane such that for any line l in the plane |l∩P | ≤ . Then the number of collinear 3-tuples in P is at most O(n 2 log + n 2 ). 2. Let P be a set of n points in the plane such that for any line l in the plane |l ∩ P | ≤ . Then, for k ≥ 4, the number of collinear k-tuples in P is at most

O( k-3 n 2 + k-1 n).
Proof (Lemma 1). Let H be a k-uniform hypergraph with V (H) = P , and {p 1 , . . . , p k } ∈ E(H) if there exists a line a line l in the plane with {p 1 , . . . , p k } ∈ l. Lemma 2 bounds the size of E(H). The result now follows directly from Theorem 4.

The rest of the paper is organised as follows: Section 2 has the simpler proof of Theorem 3, and Section 3 has the proof of Theorem 4. Finally in the Conclusions section there are some remarks and open questions.

In this section we will give an alternative proof of the Theorem 3. The proof will follow exactly along the lines of the proof by Alon, Kahn and Seymour [START_REF] Alon | Large induced degenerate subgraphs[END_REF] of Theorem 2.

First observe that

d G (v) r d G (v)+1/t d G (v)-r = 1 1 + 1 t(r+1) . . . 1 + 1 td G (v) This implies that w(v) is decreasing in d G (v) for all values of d G (v) ≥ r. Also, observe that d G (v)-1 r d G (v)-1+1/t d G (v)-1-r = 1 + 1 t d G (v) d G (v) r d G (v)+1/t d G (v)-r (4)
The alternative proof will be by induction on the number n of vertices of the k-uniform hypergraph G. The base case of n = 1 follows trivially. Assuming the result holds for n -1, we will now show that the result also holds for n.

Case 1

If we have a vertex v ∈ V (G) with d G (v) ≤ d, then consider the hypergraph H = G(V ) where V = V \ {v}. Observe that α k, d (G) = α k, d (H) + 1. Since ∀u ∈ V , we have from Equation (4), w G (u) ≤ w H (u). This implies w(H) = u∈V w H (u) ≥ u∈V w G (u) = w(G) -1.
The last inequality follows from the fact that w G (v) = 1 since d G (v) ≤ d. Using the induction hypothesis α k, d (G) ≥ w(G) and the fact that

α k, d (G) = α k, d (H) + 1, we get α k, d (G) = α k, d (H) + 1 ≥ w(H) + 1 ≥ w(G).
Case 2 Now we will consider the case where

d G (v) > d, ∀v ∈ V (G). Let ∆ = max u∈V (G) d G (u),
and let v ∈ V (G) be a vertex with d G (v) = ∆. Let u 1 , . . . , u l , where l = t∆, be the neighbors of v in G. Note that l = t∆ follows from the fact that G is a linear hypergraph. We will now show that w(H) ≥ w(G), where H = G(V ) and V = V \ {v}. We will now show w(H) ≥ w(G).

w(H) = u∈V w H (u) = w(G) -w G (v) - l i=1 w G (u i ) + l i=1 w H (u i ) = w(G) -w G (v) + l i=1 w G (u i ) t d G (u i ) ≥ w(G)
The second last inequality follows from the facts that d H (u i ) = d G (u i ) -1 (as G is a linear hypergraph) and Equation (4). The last inequality follows from the facts that d G (u) ≤ ∆ for all u ∈ V and w G (u i ) ≥ w G (v) (direct consequence of Equation ( 4)). From induction hypothesis we have

α k, d (H) ≥ w(H) ≥ w(G).
This completes the proof of Theorem 3 since α k, d (G) ≥ α k, d (H).

General k-uniform Hypergraphs

In this section we shall prove a lower bound on α k,d (H) for general k-uniform hypergraph H in terms of its degree sequence. We will give a very simple randomized algorithm to obtain an d-degenerate subgraph of a k-uniform hypergraph, whose analysis in expectation will yield the desired bound in Theorem 4.

Details of the Algorithm

Before we can give the details of the algorithm, we will need some definitions. Definition 1. Let σ be an ordering of the vertices of H.

-Fix a vertex v ∈ V (H). Call a hyperedge e ∈ E(H) with v ∈ e a backward edge with respect to σ, if ∀u ∈ e \ {v}, σ(u) < σ(v). -We will denote by b σ (v) the number of backward edges of the vertex v with respect to the ordering σ.

Algorithm 1 RandPermute

Input:

H := (V,

Analysis of the Algorithm

Theorem 4 directly follows from the following result.

Claim.

E [|I|] ≥ v∈V min 1, c k d + 1 d H (v) + 1 1/t , where c k = c k = 2 -(1+ 1 k-1 ) 1 -1 k = 2 -(1+o k (1)
) . Proof. For all vertices v ∈ V , we will denote by N (v) the neighbors of v in H.

Given an arbitrary vertex v ∈ V , and a random ordering of the vertices σ, we need to bound Pr [v ∈ I] from below. Since the event of v being selected depends on the relative ordering of the vertices in N (v), therefore, the probability v being selected in I in a random ordering is the number of orderings for which v is selected, divided by (|N (v)| + 1)!. Let σ be an ordering of the vertices of V , such that v is selected in I in the ordering σ. Given a vertex v ∈ V , consider now

L v := (V (L v ), E(L v ))
, the (k -1)-uniform link hypergraph on the neighbourhood of v, defined as follows:

V (L v ) := N (v), and

E(L v ) := {S ⊂ V (L v ) : S ∪ {v} ∈ E},
i.e., the vertices are the neighbours of v, and the edges are those edges of the original hypergraph

H which contained v, but with v removed. Clearly |E(L v )| = d H (v). Let F ⊂ V (L v ) be F := {u ∈ N (v) : σ(u) < σ(v)} ,
i.e., the vertices in the neighbourhood of v which occur before v in the ordering σ. We want L v (F ) to have at most d hyperedges. The vertices occurring before v can be ordered arbitrarily amongst themselves, and similarly for the vertices occuring after v. So we get that the probability that v is selected in I is given by:

Pr [v ∈ I] = J⊂V (Lv) : |E(Lv(J))|≤d (|J|)! (|V (L v )| -|J|)! (|V (L v )| + 1)! = 1 |V (L v )| + 1 J⊂V (Lv) : |E(Lv(J))|≤d 1 |V (Lv)| |J|
For k = 2, the link hypergraph is a 1-graph i.e. a set of vertices, each vertex being a 1-edge. Hence the summation in the RHS evaluates to d + 1 (counting 1 for each case when there are exactly 0, 1, . . . , d vertices before v, in the random ordering). Therefore

E [|I|] = v∈V Pr [v ∈ I] = v∈V min 1, d + 1 d(v) + 1 ,
and we get the theorem of Alon-Kahn-Seymour (Theorem 2). For general k-uniform hypergraphs, observe that if d H (v) ≤ d, then Pr [v ∈ I] = 1. However, if d H (v) > d, then we need to look at the link hypergraph which can be an arbitrary k -1-uniform hypergraph. In this case, we shall prove the following general lemma, (which may be of independent interest). where

c k = 2 -(1+1/k) .
Indeed, we get that the probability that v is selected in I is given by:

Pr [v ∈ I] = 1 |V (L v )| + 1 J⊂V (Lv) : |E(Lv(J))|≤d 1 |V (Lv)| |J| ≥ c k-1 |V (L v )| |V (L v )| + 1 × (d + 1) 1/(k-1) |E(L v )| 1/(k-1) (from Lemma 3) ≥ c k-1 |V (L v )| |V (L v )| + 1 × (d + 1) 1/(k-1) d H (v) 1/(k-1) (as |E(L v )| = d H (v)) ≥ c k d + 1 d H (v) + 1 1/(k-1) , (5)
where

c k = 2 -(1+ 1 k-1 ) 1 - 1 k = 2 -(1+o k (1)) .
Note that Inequality (5) follows from the fact that since d H (v) > d ≥ 0, we must have at least k -1 vertices in the hypergraph L v , i.e., |V (L v )| ≥ k -1.

It only remains to prove Lemma 3, which we will prove using a local density argument.

Proof (of Lemma 3). For all 1 ≤ s ≤ n, we define

ρ s := E |S|=s [|E(H(S))|] = S⊆V, |S|=s E(H(S)) n s .
Note that the expectation is taken over all subsets of V of size s, and E(H(S)) = {e ∈ E(H) : e ⊆ S}.

Counting the number of pairs (e, S), where e ∈ E(H), and S ⊂ V : |S| = s, e ∈ S, in two ways, we get the average local density of sets of size s is

ρ s = m n-k s-k n s = m(s) k (n) k ≤ ms k n k .
(Here a b := 0 if b < 0). This is as follows: let

z := # (e, S) : e ∈ E, S ∈ V s , e ⊂ S .
Then each of the n s sets of size s contributes, on average, ρ s -many entries to z. On the other hand, each edge e ∈ E(H) belongs to n-k s-k -many sets of size s. Equating the two summations gives the claimed average local density. Now, we use the above observation to prove the lemma. Partition the summands on the LHS into n parts, depending on the size of the set J (i.e. the number of neighbouring vertices which precede v in the random ordering):

n i=1   J⊆V : |J|=i, |E(H(J))|<a 1 n i   .
When i < k, it is easy to see that the inner summation is 1. The main idea of the proof is the following: first, observe that for any i ∈ [n], the inner summation is just the probability that a randomly picked set of exactly i vertices has fewer than a+1 edges. Then for small enough i, the expected number of edges is upper bounded by ρ i , and is much smaller than (a + 1)/2. So the probability that a random i-set contains more than twice the expected number, is at most half. Therefore for all such i, the contribution to the outer sum is at least 1/2. The number of such terms in the outer sum, then gives the claimed lower bound.

Formally, let X i be a random variable giving the number of edges contained in a randomly chosen set on i vertices. By Markov's inequality:

Pr [X i ≥ 2.E [X i ]] ≤ 1 2 .
We have that E [X i ] = ρ i . Therefore, the LHS becomes:

n i=1 Pr [X i < a + 1] = 1 - n i=1 Pr [X i ≥ a + 1]
With foresight, we split the above sum into two parts, when i ≤ t * := n(a+1) 1/k (2m) 1/k , and when i > t * . Observe that when i ≤ t * , we have that mi k n k ≤ a+1 2 . We get

n i=1 Pr [X i < a + 1] = t * i=1 Pr [X i < a + 1] + i>t * Pr [X i < a + 1] ≥ t * i=1 1 - E [X i ] a + 1 = t * i=1 1 - m(i) k (a + 1)(n) k ≥ t * i=1 1 - mi k (a + 1)n k ≥ t * i=1 1 - 1 2 ≥ n(a + 1) 1/k 2(2m) 1/k
where in the second step we used Markov's inequality on the first summation, and in the penultimate step we used the observation on t * noted above.

Remark 1 (Regarding the constant "c k ").

1. Observe that

c k = 2 -(1+ 1 k-1 ) 1 - 1 k ≥ 1 8 ,
for all k ≥ 2, and c k → 1 2 as k → ∞. 2. For simplicity of exposition we did not try to optimize c k .

Conclusion

Our randomized algorithm for finding d-degenerate subgraphs of k-uniform hypergraphs inherits the analysis of Srinivasan-Shachnai [START_REF] Shachnai | Finding large independent sets in graphs and hypergraphs[END_REF] for independent sets: (i) The RandPermute algorithm runs in RNC, as long as d is polylogarithmic in the number of vertices and edges. (ii) Our proof technique generalizes to non-uniform hypergraphs. (iii) All our results generalize to the vertex-weighted scenario, where we want an induced d-degenerate subgraph of maximum weight.

It is interesting to ask if the RandPermute algorithm can be used to obtain lower bounds for the generalized degeneracy of Zaker, or to solve the conjecture of Beame and Luby [START_REF] Beame | Parallel search for maximal independence given minimal dependence[END_REF], which asks whether iterating the RandPermute algorithm always yields a maximal independent set.

Lemma 3 .

 3 For each k-uniform hypergraph H = (V, E), such that |V | = n, |E| = m, we have J⊂V (H) : |E(J)|≤a

Their proof also yields an elementary proof of the main bound of Srinivasan and Shachnai[START_REF] Shachnai | Finding large independent sets in graphs and hypergraphs[END_REF] without using correlation inequalities, though they do not state this explicitly.

Alon, Kahn and Seymour [AKS87] actually defined a d-degenerate graph as one where every subgraph has a vertex of degree less than d, whereas we use the more usual definition in which every subgraph has a vertex of degree at most d.

Acknowledgement Kunal Dutta and Arijit Ghosh are supported by European Research Council under Advanced Grant 339025 GUDHI (Algorithmic Foundations of Geometric Understanding in Higher Dimensions) and Ramanujan Fellowship (No. SB/S2/RJN-064/2015) respectively.

Part of this work was done when Kunal Dutta and Arijit Ghosh were Researchers at Max-Planck-Institute for Informatics, Germany, supported by the Indo-German Max Planck Center for Computer Science (IMPECS).

Kunal Dutta is supported by the European Research Council Advanced Grant 339025 GUDHI (Geometric Understanding in Higher Dimensions). is supported by Ramanujan Fellowship, 2016.


Kunal Dutta
email: kdutta@mpi-inf.mpg.de

Esther Ezra
email: eezra3@math.gatech.edu

Arijit Ghosh

Two proofs for Shallow Packings

Introduction

Let V be a set system defined over an n-point set X. We follow the notation in [START_REF] Haussler | Sphere Packing Numbers for Subsets of the Boolean N-cube with Bounded Vapnik-Chervonenkis Dimension[END_REF], and view V as a set of indicator vectors in R n , that is, V ⊆ {0, 1} n . Given a subsequence of indices (coordinates) I = (i 1 , . . . , i k ), 1 ≤ i j ≤ n, k ≤ n, the projection V | I of V onto I (also referred to as the restriction of V to I) is defined as

V | I = {(v i 1 , . . . , v i k ) | v = (v 1 , . . . , v n ) ∈ V} .
With a slight abuse of notation we write I ⊆ [n] to state the fact that I is a subsequence of indices as above. We now recall the definition of the primal shatter function of V:

The notions of primal shatter dimension and VC-dimension are interrelated. By the Sauer-Shelah Lemma (see [START_REF] Sauer | On the density of families of sets[END_REF][START_REF] Shelah | A combinatorial problem, stability and order for models and theories in infinitary languages[END_REF] and the discussion below) the VC-dimension of a set system V always bounds its primal shatter dimension, that is, d ≤ d 0 . On the other hand, when the primal shatter dimension is bounded by d, the VC-dimension d 0 does not exceed O(d log d) (which is straightforward by definition, see, e.g., [START_REF] Har-Peled | Geometric Approximation Algorithms[END_REF]).

A typical family of set systems that arise in geometry with bounded primal shatter (resp., VC-) dimension consists of set systems defined over points in some low-dimensional space R d , where V represents a collection of certain simply-shaped regions, e.g., halfspaces, balls, or simplices in R d . In such cases, the primal shatter (and VC-) dimension is a function of d; see, e.g., [START_REF] Har-Peled | Geometric Approximation Algorithms[END_REF] for more details. When we flip the roles of points and regions, we obtain the so-called dual set systems (where we refer to the former as primal set systems). In this case, the ground set is a collection S of algebraic surfaces in R d , and V corresponds to faces of all dimensions in the arrangement A(S) of S, that is, this is the decomposition of R d into connected open cells of dimensions 0, 1, . . . , d induced by S. Each cell is a maximal connected region that is contained in the intersection of a fixed number of the surfaces and avoids all other surfaces; in particular, the 0-dimensional cells of A(S) are called "vertices", and d-dimensional cells are simply referred to as "cells"; see [START_REF] Sharir | Davenport-Schinzel Sequences and Their Geometric Applications[END_REF] for more details. The distinction between primal and dual set systems in geometry is essential, and set systems of both kinds appear in numerous geometric applications, see, once again [START_REF] Har-Peled | Geometric Approximation Algorithms[END_REF] and the references therein.

δ-packing

The length v of a vector v ∈ V under the L 1 norm is defined as n i=1 |v i |, where v i is the ith coordinate of v, i = 1, . . . , n. The distance ρ(u, v) between a pair of vectors u, v ∈ V is defined as the L 1 norm of the difference uv, that is, ρ(u, v) = n i=1 |u i -v i |. In other words, it is the symmetric difference distance between the corresponding sets represented by u, v. 1 Let δ > 0 be an integer parameter. We say that a subset of vectors W ⊆ {0, 1} n is δ-separated if for each pair u, v ∈ W, ρ(u, v) > δ. The δ-packing number for V, denote it by M(δ, V), is then defined as the cardinality of a largest δ-separated subset W ⊆ V. A key property, originally shown by Haussler [START_REF] Haussler | Sphere Packing Numbers for Subsets of the Boolean N-cube with Bounded Vapnik-Chervonenkis Dimension[END_REF] (see also [START_REF] Chazelle | A note on Haussler's packing lemma[END_REF][START_REF] Chazelle | Quasi-optimal Range Searching in Spaces of Finite VCdimension[END_REF][START_REF] Dudley | Central limit theorems for empirical measures[END_REF][START_REF] Matousek | Geometric Discrepancy: An Ilustrated Guide (Algorithms and Combinatorics)[END_REF][START_REF] Welzl | On Spanning Trees with Low Crossing Numbers[END_REF]), is that set systems of bounded primal shatter dimension admit small δ-packing numbers. That is:

Theorem 3 (Packing Lemma [START_REF] Haussler | Sphere Packing Numbers for Subsets of the Boolean N-cube with Bounded Vapnik-Chervonenkis Dimension[END_REF][START_REF] Matousek | Geometric Discrepancy: An Ilustrated Guide (Algorithms and Combinatorics)[END_REF]) Let V ⊆ {0, 1} n be a set of indicator vectors of primal shatter dimension d, and let 1 ≤ δ ≤ n be an integer parameter. Then M(δ, V) = O((n/δ) d ), where the constant of proportionality depends on d.

We note that in the original formulation in [START_REF] Haussler | Sphere Packing Numbers for Subsets of the Boolean N-cube with Bounded Vapnik-Chervonenkis Dimension[END_REF] the assumption is that the set system has a finite VC-dimension. However, its formulation in [START_REF] Matousek | Geometric Discrepancy: An Ilustrated Guide (Algorithms and Combinatorics)[END_REF], which is based on a simplification of the analysis of Haussler by Chazelle [START_REF] Chazelle | A note on Haussler's packing lemma[END_REF], relies on the assumption that the primal shatter dimension is d, which is the actual bound that we state in Theorem 3 (we comment though that one component of the analysis uses the fact that the VC-dimension d 0 is finite, but this follows from the bound O(d log d) on d 0 ). We also comment that a closer inspection of the analysis in [START_REF] Haussler | Sphere Packing Numbers for Subsets of the Boolean N-cube with Bounded Vapnik-Chervonenkis Dimension[END_REF] shows that this assumption can be replaced with that of having bounded primal shatter dimension (independent of the analysis in [START_REF] Chazelle | A note on Haussler's packing lemma[END_REF]). We describe these considerations in Section 2.1.

Previous work

In his seminal work, Dudley [START_REF] Dudley | Central limit theorems for empirical measures[END_REF] presented the first application of chaining, a proof technique due to Kolmogorov, to empirical process theory, where he showed the bound O((n/δ) d 0 log d 0 (n/δ)) on M(δ, V), with a constant of proportionality depending on the VC-dimension d 0 (see also previous work by Haussler [START_REF] Haussler | Decision Theoretic Generalizations of the PAC Model for Neural Net and Other Learning Applications[END_REF] and Pollard [START_REF] Pollard | Convergence of Stochastic Processes[END_REF] for an alternative proof and a specification of the constant of proportionality). This bound was later improved by Haussler [START_REF] Haussler | Sphere Packing Numbers for Subsets of the Boolean N-cube with Bounded Vapnik-Chervonenkis Dimension[END_REF], who showed M(δ, V) ≤ e(d 0 + 1) 2en δ d 0 , where e is the base of the natural logarithm (see also Theorem 3), and presented a matching lower bound, which leaves only a constant factor gap, which depends exponentially in d 0 . In fact, the aforementioned bounds are more general, and can also be applied to classes of real-valued functions of finite "pseudo-dimension" (the special case of set systems corresponds to Boolean functions), see, e.g., [START_REF] Haussler | Decision Theoretic Generalizations of the PAC Model for Neural Net and Other Learning Applications[END_REF], however, we do not discuss this generalization in this paper and focus merely on set systems V of finite primal shatter (resp., VC-) dimension.

The bound of Haussler [START_REF] Haussler | Sphere Packing Numbers for Subsets of the Boolean N-cube with Bounded Vapnik-Chervonenkis Dimension[END_REF] (Theorem 3) is in fact a generalization of the so-called Sauer-Shelah Lemma [START_REF] Sauer | On the density of families of sets[END_REF][START_REF] Shelah | A combinatorial problem, stability and order for models and theories in infinitary languages[END_REF], asserting that |V| ≤ (en/d 0 ) d 0 , and thus this bound is O(n d 0 ). Indeed, when δ = 1, the corresponding δ-separated set should include all vectors in V, and then the bound of Haussler [START_REF] Haussler | Sphere Packing Numbers for Subsets of the Boolean N-cube with Bounded Vapnik-Chervonenkis Dimension[END_REF] becomes O(n d 0 ), matching the Sauer-Shelah bound up to a constant factor that depends on d 0 .

There have been several studies extending Haussler's bound or improving it in some special scenarios. We name only a few of them. Gottlieb et al. [START_REF] Gottlieb | VC Bounds on the Cardinality of Nearly Orthogonal Function Classes[END_REF] presented a sharpening of this bound when δ is relatively large, i.e., δ is close to n/2, in which case the vectors are "nearly orthogonal". They also presented a tighter lower bound, which considerably simplifies the analysis of Bshouty et al. [START_REF] Bshouty | Using the Doubling Dimension to Analyze the Generalization of Learning Algorithms[END_REF], who achieved the same bound.

A major application of packing is in obtaining improved bounds on the sample complexity in machine learning. This was studied by Li et al. [START_REF] Li | Improved Bounds on the Sample Complexity of Learning[END_REF] (see also [START_REF] Haussler | Decision Theoretic Generalizations of the PAC Model for Neural Net and Other Learning Applications[END_REF]), who presented an asymptotically tight bound on the sample complexity, in order to guarantee a small "relative error." This problem has been revisited by Har-Peled and Sharir [START_REF] Har-Peled | Relative (ε, ρ)-Approximations in Geometry[END_REF] in the context of geometric set sys- tems, where they referred to a sample of the above kind as a "relative approximation", and showed how to integrate it into an approximate range counting machinery, which is a central application in computational geometry. The packing number has also been used by Welzl [Wel92] in order to construct spanning trees of low crossing number (see also [START_REF] Matousek | Geometric Discrepancy: An Ilustrated Guide (Algorithms and Combinatorics)[END_REF]) and by Matoušek [START_REF] Matousek | Tight Upper Bounds for the Discrepancy of Half-Spaces[END_REF][START_REF] Matousek | Geometric Discrepancy: An Ilustrated Guide (Algorithms and Combinatorics)[END_REF] in order to obtain asymptotically tight bounds in geometric discrepancy.

Our Result

Shallow packing lemma. In the sequel, we refine the bound in the Packing Lemma (Theorem 3) so that it becomes sensitive to the length of the vectors v ∈ V, based on an appropriate refinement of the underlying primal shatter function. This refinement has several geometric applications. Our ultimate goal is to show that when the set system is "shallow" (that is, the underlying vectors are short), the packing number becomes much smaller than the bound in Theorem 3.

Nevertheless, we cannot always enforce such an improvement, as in some settings the worst-case asymptotic bound on the packing number is Ω((n/δ) d ) even when the set system is shallow. See Figure 1 and the paragraph at the end of this section where we give a more detailed description of this construction to the non-expert reader.

Therefore, in order to obtain an improvement on the packing number of shallow set systems, we may need further assumptions on the primal shatter function. Such assumptions stem from the random sampling technique of Clarkson and Shor [START_REF] Clarkson | Applications of random sampling in computational geometry[END_REF], which we define as follows. Let V be our set system. We assume that for any sequence I of m ≤ n indices, and for any parameter 1 ≤ k ≤ m, the number of vectors in

V | I of length at most k is only O(m d 1 k d-d 1 )
, where d is the primal shatter dimension and 1 ≤ d 1 ≤ d is a real parameter.2 When k = m we obtain O(m d ) vectors in total, in accordance with the assumption that the primal shatter dimension is d, but the above bound is also sensitive to the length of the vectors as long as d 1 < d. From now on, we say that a primal shatter function of this kind has the (d, d 1 ) Clarkson-Shor property.

Let us now denote by M(δ, k, V) the δ-packing number of V, where the vector length of each element in V is at most k, for some integer parameter 1 ≤ k ≤ n. With this notation we can assume, without loss of generality, that k ≥ δ/2, as otherwise the distance between any two elements in V must be strictly less than δ, in which case the packing contains at most one element. In Sections 2-3 we present two proofs for our main result, stated below: Theorem 4 (Shallow Packing Lemma) Let V ⊆ {0, 1} n be a set of indicator vectors, whose primal shatter function has a (d, d 1 ) Clarkson-Shor property (where d is the primal shatter dimension and 1 ≤ d 1 ≤ d is a real parameter). Let δ ≥ 1 be an integer parameter, and k an integer parameter between 1 and n, and suppose that k ≥ δ/2. Then:

M(δ, k, V) = O n d 1 k d-d 1 δ d ,
where the constant of proportionality depends on d.

The actual dependence of the constant of proportionality on d is analyzed at end of Section 2 for the first proof, and end of Section 3 for the second proof. This problem has initially been addressed by the second author in [START_REF] Ezra | A Size-sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension[END_REF] as a major tool to obtain size-sensitive discrepancy bounds in set systems of this kind, where it has been shown

M(δ, k, V) = O n d 1 k d-d 1 log d (n/δ) δ d
. The analysis in [START_REF] Ezra | A Size-sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension[END_REF] is a refinement over the technique of Dudley [START_REF] Dudley | Central limit theorems for empirical measures[END_REF] combined with the existence of small-size relative approximations (see [START_REF] Ezra | A Size-sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension[END_REF] for more details). In the current analysis we completely remove the extra log d (n/δ) factor appearing in the previous bound. In particular, when d 1 = d (where we just have the original assumption on the primal shatter function) or k = n (in which case each vector in V has an arbitrary length), our bound matches the tight bound of Haussler, and thus appears as a generalization of the Packing Lemma (when replacing VC-dimension by primal shatter dimension). We present two proofs for Theorem 4, the first is an extension of Haussler's approach (Section 2), and the second is an extension of Chazelle's proof [START_REF] Chazelle | A note on Haussler's packing lemma[END_REF] to the Packing Lemma (Section 3).

We note that after the submission of this paper we found a third proof by Mustafa [START_REF] Mustafa | A simple proof of the shallow packing lemma[END_REF], based on the simplification of Chazelle's proof [START_REF] Chazelle | A note on Haussler's packing lemma[END_REF] and combining Markov's inequality. While we find this proof simpler than ours, we emphasize the fact that the problem of shallow packings has initially been posed by the second author in [START_REF] Ezra | A Size-sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension[END_REF], and the preliminary version of this paper [START_REF] Dutta | Two proofs for shallow packings[END_REF] is the first to resolve it (in the sense of Theorem 4). We thus believe the results in [START_REF] Mustafa | A simple proof of the shallow packing lemma[END_REF] were somewhat inspired by the preliminary version in [START_REF] Dutta | Two proofs for shallow packings[END_REF] .

Applications. Theorem 4 implies smaller packing numbers for several natural geometric set systems under the shallowness assumption. These set systems are described in detail in Section 4.1. In Section 4.2 we show an application in geometric discrepancy, where the goal is to obtain discrepancy bounds that are sensitive to the length of the vectors in V. Due to the bound in Theorem 4 we obtain an improvement over the one presented in [START_REF] Ezra | A Size-sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension[END_REF].

An example of a shallow set system with large packing numbers Consider a ground set that is a collection of axis-parallel rectangles, and the vectors V represent subsets of rectangles that cover a point in the plane. For simplicity of exposition, we define these vectors to represent all two-dimensional cells in the arrangement of the given rectangles. In this case, the (d, d 1 ) Clarkson-Shor property holds only for d = d 1 = 2. Indeed, even when the arrangement is very shallow (say, each point in the plane is covered by at most two rectangles), one can still have quadratically many cells by just taking a grid of long and skinny rectangles, and thus in general we cannot obtain size-sensitive bounds on |V|.

It is well known that the primal shatter function of V is quadratic (see, e.g., [START_REF] Har-Peled | Geometric Approximation Algorithms[END_REF]), and therefore, by Theorem 3, the packing number is O((n/δ) 2 ). Nevertheless, we claim that even when the arrangement is shallow, the asymptotic bound on the packing number is not any better than (n/δ) 2 . Indeed, fix a positive even parameter δ > 0, and suppose, without loss of generality, that n/δ is an integer number. Consider now an n δ × n δ grid of long and skinny rectangles, where each rectangle in the grid is duplicated δ/2 times (with a possibly infinitesimal perturbation), as illustrated in Figure 1. Clearly, each (two-dimensional) cell in the arrangement is covered by at most δ rectangles, and thus the set system is δ-shallow. Consider now only the cells at "depth" δ (that is, they are covered by precisely δ rectangles), and let F ⊂ V be the set of their representative vectors. It is easy to verify that, for each pair v, v ∈ F, the distance ρ(v, v ) is at least δ (see once again Figure 1), and thus F is both δ-separated and δ-shallow. However, by construction, we have |F| = Ω((n/δ) 2 ), and thus the δ-shallowness assumption does not yield an improvement over the general case.

2 First Proof: Refining Haussler's Approach

Preliminaries

Relative approximations and ε-nets. We mentioned in the introduction the notion of relative (ε, η)-approximations. We now define them formally: Following the definition from [START_REF] Har-Peled | Relative (ε, ρ)-Approximations in Geometry[END_REF], given a set system V ⊆ {0, 1} n and two parameters, 0 < ε < 1 and 0 < η < 1, we say that a subsequence I of indices is a relative (ε, η)-approximation if it satisfies, for each vector v ∈ V,

v | I |I| - v n ≤ η v n , if v n ≥ ε, and
v | I |I| - v n ≤ ηε, otherwise,
where

v | I is the projection of v ∈ V onto I.
As observed by Har-Peled and Sharir [START_REF] Har-Peled | Relative (ε, ρ)-Approximations in Geometry[END_REF], the analysis of Li et al. [START_REF] Li | Improved Bounds on the Sample Complexity of Learning[END_REF] implies that if V has primal shatter dimension d, then a random sample of cd log (1/ε) εη 2 indices (each of which is drawn independently) is a relative (ε, η)-approximation for V with constant probability, where c > 0 is an absolute constant. More specifically, success with probability at least 1 -q is guaranteed if one samples c(d log (1/ε)+log (1/q)) εη 2

indices. 3

It was also observed in [START_REF] Har-Peled | Relative (ε, ρ)-Approximations in Geometry[END_REF] that ε-nets arise as a special case of relative (ε, η)-approximations. Specifically, an ε-net is a subsequence of indices I with the property that any vector v ∈ V with v ≥ nε satisfies v | I ≥ 1. In other words, N is a hitting set for all the "long" vectors. In this case, if we set η to be some constant fraction, say, 1/4, then a relative (ε, 1/4)-approximation becomes an ε-net. Moreover, a random sample of O d log (1/ε)+log (1/q) ε indices (with an appropriate choice of the constant of proportionality) is an ε-net for V, with probability at least 1 -q; see [START_REF] Har-Peled | Relative (ε, ρ)-Approximations in Geometry[END_REF] for further details.

Overview of Haussler's approach. For the sake of completeness, we repeat some of the details in the analysis of Haussler [Hau95] and use similar notation for ease of presentation.

Let V ⊆ {0, 1} n be a collection of indicator vectors of bounded primal shatter dimension d, and denote its VC-dimension by d 0 . By the discussion above, d 0 = O(d log d). From now on we assume that V is δ-separated, and thus a bound on |V| is also a bound on the packing number of V. The analysis in [START_REF] Haussler | Sphere Packing Numbers for Subsets of the Boolean N-cube with Bounded Vapnik-Chervonenkis Dimension[END_REF] exploits the method of "conditional variance" in order to conclude

|V| ≤ (d 0 + 1) Exp I |V | I | = O d log d Exp I |V | I | , (1)
where

Exp I |V | I | is the expected size of V when projected onto a subset I = {i 1 , . . . , i m-1 } of m -1 indices chosen uniformly at random without replacements from [n],
and

m := (2d 0 + 2)(n + 1) δ + 2d 0 + 2 = O d 0 n δ = O nd log d δ . (2)
We justify this choice in Appendix A, as well as the facts that m ≤ n and I consists of precisely m -1 indices.

Moreover, we refine Haussler's analysis to include two natural extensions (see Appendix A for details):

|V | I | = O((m -1) d ) = O(m d ),
with a constant of proportionality that depends on d, and thus the packing number is O((n/δ) d ), as asserted in Theorem 3.4 However, in our analysis we would like to have a more subtle bound on the actual expected value of |V | I |. In fact, the scenario imposed by our assumptions on the set system eventually yields a much smaller bound on the expectation of |V | I |, and thus on |V| due to Inequality (1). We review this in more detail below. (ii) Relaxing the bound on m. We show that Inequality (1) is still applicable when the sample I is slightly larger than the bound in (2), as a stand alone relation, this may result in a suboptimal bound on |V|, however, this property will assist us to obtain local improvements over the bound on |V|, eventually yielding the bound in Theorem 4. Specifically, in our analysis we proceed in iterations, where at the first iteration we obtain a preliminary bound on |V| (Corollary 6), and then, at each subsequent iteration j > 1, we draw a sample I j of m j -1 indices where

m j := m log (j) (n/δ) = O d 0 n log (j) (n/δ) δ , (3)
m is our choice in (2), and log (j) (•) is the jth iterated logarithm function. Then, by a straightforward generalization of Haussler's analysis (described in Appendix A), we obtain, for each j = 2, . . . , log * (n/δ):

|V| ≤ (d 0 + 1) Exp I j |V | I j | . (4)
We note that since the bounds (1)-(4) involve a dependency on the VC-dimension d 0 , we will sometimes need to explicitly refer to this parameter in addition to the primal shatter dimension d. Nevertheless, throughout the analysis we exploit the relation

d ≤ d 0 = O(d log d), mentioned in Section 1.

Overview of our Approach

We next present the proof of Theorem 4. In what follows, we assume that V is δ-separated, and denote by d its primal shatter dimension and by d 0 its VC-dimension. We first recall the assumption that the primal shatter function of V has a (d, d 1 ) Clarkson-Shor property, and that the length of each vector v ∈ V under the L 1 norm is at most k. This implies that V consists of at most

O(n d 1 k d-d 1 ) vectors.
Since the Clarkson-Shor property is hereditary, then this also applies to any projection of V onto a subset of indices, implying that the bound on

|V | I | is at most O(m d 1 k d-d 1 )
, where I is a subset of m -1 indices as above. However, due to our sampling scheme we expect that the length of each vector in V | I should be much smaller than k, (e.g., in expectation this value should not exceed k(m -1)/n), from which we may conclude that the actual bound on

|V | I | is smaller than the trivial bound of O(m d 1 k d-d 1 )
. Ideally, we would like to show that this bound is

O(m d 1 (km/n) d-d 1 ) = O(n d 1 k d-d 1 /δ d )
, which matches our asymptotic bound in Theorem 4 (recall that m = O(n/δ)). However, this is likely to happen only in case where the length of each vector in V | I does not exceed its expected value, or that there are only a few vectors whose length deviates from its expected value by far, whereas, in the worst case there might be many leftover "long" vectors in V | I . Nevertheless, our goal is to show that, with some care one can proceed in iterations, where initially I is a slightly larger sample, and then at each iteration we reduce its size, until eventually it becomes O(m) and we remain with only a few long vectors. At each such iteration V | I is a random structure that depends on the choice of I and may thus contain long vectors, however, in expectation they will be scarce! Specifically, we proceed over at most log * (n/δ) iterations, where we perform local improvements over the bound on |V|, as follows. Let |V| (j) be the bound on |V| after the jth iteration is completed, 1 ≤ j ≤ log * (n/δ). We first show in Corollary 6 that for the first iteration,

|V| ≤ |V| (1) = O n d 1 k d-d 1 log d (n/δ) δ d
, with a constant of proportionality that depends on d. Then, at each further iteration j ≥ 2, we select a set I j of m j -1 = O(n log (j) (n/δ)/δ) indices uniformly at random without replacements from [n] (see (3) for the bound on m j ). Our goal is to bound Exp I j |V | I j | using the bound |V| (j-1) , obtained at the previous iteration, which, we assume by induction to be

O n d 1 k d-d 1 (log (j-1) (n/δ)) d δ d
(see Lemma 8 for the recursive relation that we derive, as well as our observation that the coefficient of the recursive term is at most 1), where the base case j = 2 is shown in Corollary 6.

A key property in the analysis is to show that the probability that the length of a vector v ∈ V | I j (after the projection of V onto I j ) deviates from its expectation decays exponentially (Lemma 7). Note that in our case this expectation is at most k(m j -1)/n. This, in particular, enables us to claim that in expectation the overall majority of the vectors in V | I j have length at most O(k(m j -1)/n), whereas the remaining longer vectors are scarce. This is the key idea to derive a recursive inequality for |V| (j) using the bound on Exp I j |V | I j | (Lemma 8). Roughly speaking, since the Clarkson-Shor property is hereditary, we apply it to V | I j and conclude that the number of its vectors of length

at most O(k(m j -1)/n) is only O n d 1 k d-d 1 (log (j) (n/δ)) d δ d
, with a constant of proportionality that depends on d. On the other hand, due to Lemma 7 and our inductive hypothesis, the number of longer vectors does not exceed

O n d 1 k d-d 1 δ d
, which is dominated by the first bound. We thus

conclude Exp I j |V | I j | = O n d 1 k d-d 1 (log (j) (n/δ)) d δ d
. Then we apply Inequality (4) in order to complete the inductive step, whence we obtain the bound on |V| (j) , and thus on |V|. Note that the full analysis is somewhat more subtle, as we need to show that the actual coefficient of the recursive term |V| (j) is at most 1 (Lemma 8). We emphasize the fact that the sample I j is always chosen from the original ground set [n], and thus, at each iteration we construct a new sample from scratch, and then exploit our observation in Inequality (4).

In what follows, we also assume that δ < n/2 (d 0 +1) (where d 0 is the VC-dim), as otherwise the bound on the packing number is a constant that depends on d and d 0 by the Packing Lemma (Theorem 3). This assumption is crucial for the recursive analysis presented in this section-see below.

The First Iteration

In order to show our bound on |V (1) |, we form a subset

I 1 = (i 1 , . . . , i m 1 ) of m 1 = |I 1 | = O dn log (n/δ) δ
indices5 with the following two properties: (i) each vector in V is mapped to a distinct vector in V | I 1 , and (ii) the length of each vector in

V | I 1 does not exceed O(k • m 1 /n).
A set I 1 as above exists by the considerations in [START_REF] Ezra | A Size-sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension[END_REF]. Specifically: Lemma 5 A sample I 1 as above satisfies properties (i)-(ii), with probability at least 1/2. Proof : We rely on the notions of "relative approximations" and "ε-nets", defined in Section 2.1. In order to show (i), we first form the set system corresponding to all symmetric difference pairs induced by V. That is, we form the vector set D, where

D = {(|u 1 -v 1 |, . . . , |u n -v n |) | u, v ∈ V}.
Since we assume that V is δ-separated, we have w ≥ δ, for each w ∈ D. As observed in [START_REF] Dudley | Central limit theorems for empirical measures[END_REF] (see also [START_REF] Har-Peled | Geometric Approximation Algorithms[END_REF]), D has a finite VC-dimension.

We now construct an ε-net for D, with ε = δ/n. By our discussion above a sample I 1 of O(d(n/δ) log (n/δ)) indices has this property with probability greater than, say, 3/4 (for a sufficiently large constant of proportionality). Thus, by definition, any vector w ∈ D (recall that its length is at least δ) must satisfy |w | I 1 | ≥ 1, where w | I 1 denotes the projection of w onto I 1 . But this implies that we must have u | I 1 = v | I 1 , for each pair u, v ∈ V, and thus u, v must be mapped to distinct vectors in the projection of V onto I 1 , from which property (i) follows.

In order to have property (ii) we observe that the same sample I 1 is a relative (δ/n, 1/4)approximation for V with probability at least 3/4 (for an appropriate choice of the constant of proportionality). Given this property of I 1 , this implies that any vector v ∈ V satisfies

v | I 1 m 1 - v n ≤ 1 4 • v n , if v /n ≥ δ/n, and v | I 1 m 1 - v n ≤ 1 4 • δ n ,
otherwise. Since v ≤ k, and k ≥ δ/2 by assumption, it is easy to verify that we always have

v | I 1 ≤ 3/2 • km 1 /n. In other words, v | I 1 = O(k • m 1 /n), as asserted.
Combining the two roles of I 1 (each with probability 3/4), it follows that it is both a (δ/n)-net for D and a relative (δ/n, 1/4)-approximation for V, with probability at least 1/2, and thus it satisfies properties (i)-(ii) with this probability. This completes the proof of the lemma.

We next apply Lemma 5 in order to bound |V | I 1 |. We first recall that the (d, d 1 ) Clarkson-Shor property of the primal shatter function of V is hereditary. Incorporating the bound on m 1 and property (ii), we conclude that

|V | I 1 | = O m d 1 1 km 1 n d-d 1 = O n d 1 k d-d 1 log d (n/δ) δ d ,
with a constant of proportionality that depends on d. Now, due to property (i), |V| ≤ |V | I 1 |, we thus conclude:

Corollary 6 After the first iteration we have:

|V| ≤ |V| (1) = O n d 1 k d-d 1 log d (n/δ) δ d
, with a constant of proportionality that depends on d.

Remark: We note that the preliminary bound given in Corollary 6 is crucial for the analysis, as it constitutes the base for the iterative process described in Section 2.4. In fact, this step of the analysis alone bypasses our refinement to Haussler's approach, and instead exploits the approach of Dudley [START_REF] Dudley | Central limit theorems for empirical measures[END_REF].

The Subsequent Iterations: Applying the Inductive Step

Let us now fix an iteration j ≥ 2. As noted above, we assume by induction on j that the bound |V| (j-1) on |V| after the (j -1)th iteration is

O n d 1 k d-d 1 (log (j-1) (n/δ)) d δ d
. Let I j be a subset of m j -1 indices, chosen uniformly at random without replacements from [n], with m j given by (3). Let v ∈ V, and denote by v | I j its projection onto

I j . The expected length Exp[ v | I j ] of v | I j is at most k(m j -1)/n = O(d 0 k log (j) (n/δ)/δ).
We next show:

Lemma 7 (Exponential Decay Lemma) Prob v | I j ≥ t • k(m j -1) n < 2 -tk(m j -1)/n ,
where t ≥ 2e is a real parameter and e is the base of the natural logarithm.

Proof : We first observe that the length of v | I j is a random variable with a hypergeometric distribution. Indeed, this is precisely the question of uniformly choosing m j -1 elements at random (into our set I j ) from a given set of n elements without replacements, and then, for a given velement subset of the full set (recall that the length of v corresponds to the cardinality of an appropriate subset in the set system), we consider how many of its elements have been chosen into I j . Specifically, we have:

Prob v | I j = s = v s n-v m j -1-s n m j -1 , for each non-negative integer s ≤ min{ v , m j -1}.
Our goal is to show a Chernoff-type bound over the probability that v | I j deviates from its expectation. However, we face the difficulty that the corresponding indicator variables are not independent, and thus we cannot apply a Chernoff bound directly (see, e.g. [START_REF] Alon | The Probabilistic Method[END_REF]). Nevertheless, in our scenario a Chernoff bound is still applicable, this can be viewed by various approaches, see, e.g., [START_REF] Auger | Theory of Randomized Search Heuristics:Foundations and Recent Developments[END_REF][START_REF] Mulzer | Chernoff Bounds, Personal note[END_REF][START_REF] Panconesi | Randomized distributed edge coloring via an extension of the Chernoff-Hoeffding bounds[END_REF]. For the sake of completeness we describe the proof in detail, and rely on the analysis of Panconesi and Srinivasan [START_REF] Panconesi | Randomized distributed edge coloring via an extension of the Chernoff-Hoeffding bounds[END_REF], which implies that when the underlying indicator variables are "negatively correlated", one can still apply a Chernoff bound (see also [START_REF] Auger | Theory of Randomized Search Heuristics:Foundations and Recent Developments[END_REF]).

We enumerate all non-zero coordinates of v in an arbitrary order, let L = {l 1 , . . . l v } be this set of indices (in this notation we ignore all the zero-coordinates), and attach an indicator variable X i to each index l i ∈ L, which is defined to be one if and only if l i ∈ I j (in other words, the corresponding element in the underlying set induced by v has been chosen to be included into the sample of the m j -1 elements). According to this notation, v | I j is represented by the sum

X = v i=1 X i .
It is now easy to verify that Prob[X i = 1] = (m j -1)/n, and by linearity of expectation Exp[ v

| I j ] = v • (m j -1)/n.
However, the variables X i are not independent due to our probabilistic model (that is, I j is chosen without replacements), nevertheless, they are negatively correlated. This implies that for each subset

K ⊆ {1, . . . , v } Prob[ i∈K X i = 0] ≤ i∈K Prob[X i = 0], and Prob[ i∈K X i = 1] ≤ i∈K Prob[X i = 1].
Indeed, following the considerations in [START_REF] Auger | Theory of Randomized Search Heuristics:Foundations and Recent Developments[END_REF], let us show first the latter inequality. Put

L K = i∈K {l i }. Then Prob[ i∈K X i = 1] = Prob[L K ⊆ I j ],
and since I j is uniformly chosen, in order to bound the latter we need to take the proportion between the number of subsets of size m j -1 that contain L K and the entire number of subsets of size m j -1 that can be chosen from an n-element set. Hence

Prob[L K ⊆ I j ] = n-|K| m j -1-|K| n m j -1 = (m j -1)(m j -2) • • • (m j -|K|) n(n -1) • • • (n -|K| + 1) ,
and the latter is smaller than

m j -1 n |K|
, as is easily verified. Using similar arguments for the first correlation inequality, we obtain

Prob[ i∈K X i = 0] = n-|K| m j -1 n m j -1 < 1 - m j -1 n |K| .
We are now ready to apply [PS97, Theorem 3.4] stating that if the indicator variables X i are negatively correlated then (recall that

X = v i=1 X i ) 6 : Prob[X > ρ Exp[X]] < e ρ-1 ρ ρ Exp[X]
,

for any ρ > 1. In particular, when ρ ≥ 2e (where e is the base of the natural logarithm), the latter term is bounded by 2 -ρ Exp [X] . Recall that we assumed v ≤ k, and thus Exp

[X] = Exp[ v | I j
] ≤ k • (m j -1)/n. Thus, for any t ≥ 2e, we obtain:

Prob v | I j > tk(m j -1)/n = Prob v | I j > tk(m j -1)/n Exp[ v | I j ] • Exp[ v | I j ] ,
observe that in this case ρ :=

tk(m j -1)/n Exp[ v | I j
] ≥ 2e, due to our assumption on t and the fact that

k(m j -1)/n Exp[ v | I j
] ≥ 1, and thus the latter term is bounded by: 2

- tk(m j -1)/n Exp[ v | I j ] Exp[ v | I j ]
= 2 -tk(m j -1)/n , as asserted.

We now proceed as follows. Recall that we assume k ≥ δ/2, and by (3) we have m j = O d 0 n log (j) (n/δ) δ . Thus it follows from Lemma 7 that

Prob v | I j ≥ C • k(m j -1) n < 1 (log (j-1) (n/δ)) D , (5)
where C ≥ 2e is a sufficiently large constant, and D > d 0 is another constant whose choice depends on C and d 0 , and can be made arbitrarily large. Since d 0 ≥ d we obviously have D > d. We next show:

Lemma 8 Under the assumption that k ≥ δ/2, we have, at any iteration j ≥ 2:

|V| (j) ≤ A(d 0 + 1) • n d 1 k d-d 1 (log (j) (n/δ)) d δ d + (d 0 + 1) • |V| (j-1) (log (j-1) (n/δ)) D , (6)
where |V| (l) is the bound on |V| after the lth iteration, and A > 0 is a constant that depends on d (and d 0 ) and the constant of proportionality determined by the Clarkson-Shor property of V.

6 We note that in the original formulation in [START_REF] Panconesi | Randomized distributed edge coloring via an extension of the Chernoff-Hoeffding bounds[END_REF], one needs to have a set of independent random variables Xi, i ∈ {1, . . . , v } with X = v i=1 Xi, such that Exp[X] ≤ Exp[ X]. In the scenario of our problem Xi is taken to be a Bernoulli indicator random variable, which takes value one with probability (mj -1)/n, in which case

Exp[X] = Exp[ X] = v • (mj -1)/n.
Proof : We in fact show:

Exp I j |V | I j | ≤ A • n d 1 k d-d 1 (log (j) (n/δ)) d δ d + |V| (j-1)
(log (where C ≥ 2e is a sufficiently large constant as above) in the projection of V onto a subset I j of m j -1 indices (in this part of the analysis I j can be arbitrary). Since the primal shatter function of V has a (d, d 1 ) Clarkson-Shor property, which is hereditary, we obtain at most

O(m j d 1 (k(m j -1)/n) d-d 1 ) = O n d 1 k d-d 1 (log (j) (n/δ)) d δ d vectors in V | I j of length smaller than C • k(m j -1) n = O( k log (j) (n/δ) δ
). It is easy to verify that the constant of proportionality A in the bound just obtained depends on d, d 0 , and the constant of proportionality determined by the (d, d 1 ) Clarkson-Shor property of V (observe that the latter one is at most (2(d 0 + 1)) d , since m j depends linearly in d 0 ).

Next, in order to obtain the second term, we consider the vectors v ∈ V that are mapped to vectors

v | I j ∈ V | I j with v | I j > C • k(m j -1) n
. By Inequality (5):

Exp v ∈ V | v | I j > C • k(m j -1) n < |V| (log (j-1) (n/δ)) D ,
and recall that |V| (j-1) is the bound on |V| after the previous iteration j -1. This completes the proof of the lemma.

Remark:

We note that the bound on Exp I j |V | I j | consists of the worst-case bound on the number of short vectors of length at most C • k(m j -1)/n, obtained by the (d, d 1 ) Clarkson-Shor property, plus the expected number of long vectors.

Wrapping up. We now complete the analysis and solve Inequality (6). Our initial assumption that δ < n/2 (d 0 +1) , and the fact that D > d is sufficiently large, imply that the coefficient of the recursive term is smaller than 1, for any 2 ≤ j ≤ log * (n/δ) -log * (d 0 + 1).7 Then, using induction on j, one can verify that the solution is

|V| (j) ≤ 2A(d 0 + 1) n d 1 k d-d 1 (log (j) (n/δ)) d δ d , (7)
for any 2 ≤ j ≤ log * (n/δ) -log * (d 0 + 1).

We thus conclude

|V| (j) = O n d 1 k d-d 1 (log (j) (n/δ)) d δ d
. In particular, at the termination of the last iteration j * = log * (n/δ) -log * (d 0 + 1), we obtain:

|V| ≤ |V| (j * ) = O n d 1 k d-d 1 δ d ,
with a constant of proportionality that depends exponentially on d (and d 0 ). Specifically, it is easy to verify that due to our choice of j * and the fact that A is at most (2(d 0 + 1)) d , the resulting constant of proportionality in the bound on |V| is at most (d 0 + 1) O(d) . This at last completes the proof of Theorem 4.

3 Second Proof: Refining Chazelle's Approach

In this section, we shall prove a size-sensitive version of Haussler's upper bound for δ-separated set of vectors, having bounded primal shatter dimension, building on Chazelle's presentation of Haussler's proof as explained in [START_REF] Matousek | Geometric Discrepancy: An Ilustrated Guide (Algorithms and Combinatorics)[END_REF]. By Haussler's result [START_REF] Haussler | Sphere Packing Numbers for Subsets of the Boolean N-cube with Bounded Vapnik-Chervonenkis Dimension[END_REF], we know that

M(δ, k, V) = g d • n δ d 1 k δ d-d 1 , where g := g(n, k, δ) is such that g d = O n k d-d 1 .
We shall show that the optimal (up to constants) upper bound for g, is in fact c * , where c * is independent of n, k and δ.

Overview of the second approach

Consider a preliminary attempt to extend Chazelle's proof to shallow packings. Like Chazelle, one chooses a random subsequence of indices I of size roughly n/δ, and estimates the number of projections on I caused by δ-separated vectors of size bounded by k. Suppose that the projection of every vector in the δ-separated system V onto I, were nearly equal to its expected value k/δ. By the definition of the (d, d 1 ) Clarkson-Shor property, the number of projections on the subsequence

I would then be bounded by c n δ d 1 k δ d-d 1 = c n d 1 k d-d 1 δ d
, for some constant c, and Chazelle's proof would go through in a straightforward manner. However, for a given vector, its projection on I can be much larger than expected. To handle this, we shall choose I in a way that the number of such "bad" vectors, is at most a constant times their expected number. Also, we treat the unknown "extra" factor g (at most the Haussler packing bound, divided by

n d 1 k d-d 1 δ d
) as a function of n, k, δ, whose value we show to be bounded by a constant independent of n, k, and δ (see Inequality (12) and succeeding paragraph). This allows us to get the final bound in a single iteration.

Details of the Proof

Before we give the details of the second proof, we will need the definition of the unit distance graph of a family of vectors which will play a central role in the proof of the theorem.

Definition 9 (Unit Distance Graph) For a family V ⊆ {0, 1} n of indicator vectors, the unit distance graph UD(V) = (V, E) is a graph with vertex set V and {v 1 , v 2 } is an edge, i.e.

{v 1 , v 2 } ∈ E, if ρ(v 1 , v 2 ) = 1.
Proof : Consider a random subsequence of indices I = (i 1 , . . . , i s ) obtained by selecting each i ∈ [n] with probability p = 11d 0 K δ , and then taking a random permutation of the selected indices. Here K = K(n, k, δ) ≥ 4 is a parameter to be fixed later. Define V 1 := V | I . Consider the unit distance graph UD(V 1 ). For each vector v 1 ∈ V 1 , define the weight of v 1 as:

w(v 1 ) := v ∈ V : v | I = v 1 .
Observe that

v 1 ∈V 1 w(v 1 ) = M(δ, k, V).

Now define the weight of an edge {v

1 , v 1 } ∈ E as w ({v 1 , v 1 }) := min{w(v 1 ), w(v 1 )}. Let W := {v1,v 1 }∈E w ({v 1 , v 1 }).
We now need the following lemma, whose proof we include from Matoušek's book [START_REF] Matousek | Geometric Discrepancy: An Ilustrated Guide (Algorithms and Combinatorics)[END_REF], in order to make the exposition self-contained. Since the VC-dimension of V 1 is bounded by d 0 from the hereditary property of VC-dimension, the lemma implies that there exists a vertex v 1 ∈ V 1 , whose degree is at most 2d 0 . Removing v 1 , the total vertex weight will be reduce by w(v 1 ), and the total edge weight will be reduce by at most 2d 0 w(v 1 ). By continuing the process and the argument until all vertices are removed, we get the lemma.

Lemma 10 W ≤ 2d 0 v 1 ∈V 1 w(v 1 ) = 2d 0 M(δ, k, V).
Next, we shall prove a lower bound on the expectation Exp[W ]. Set I := (i 1 , i 2 , . . . , i s-1 ), and let V 2 := V | I . Let E 1 ⊆ E be those edges {v 1 , v 1 } of E where vectors v 1 and v 1 differ in the coordinate i s , and let

W 1 := {v1,v 1 }∈E1 w v 1 , v 1 .
We need to lower bound

Exp[W 1 ]. Given I , let Y = Y (I ) := v ∈ V : v | I > ekp ,
i.e., the number of vectors in V, each of whose length after projecting onto I is more than ekp, (where e is the base of the natural logarithm function).

respectively. Also, let N ice denote the event N Y ∩ N S . Conditioning W on N ice, we get:

Exp[W ] = Prob [N ice] Exp[W |N ice] + Prob N ice Exp[W |N ice] ≥ Prob [N ice] Exp[W |N ice].

By Markov's Inequality, we have

Prob N Y = Prob [Y ≥ 8 Exp[Y ]] ≤ 1/8,
and using Chernoff Bounds, (see [AS08, App. A]), with the fact that n/δ ≥ 1, we get

Prob N S = Prob |s -np| > np 2 ≤ 2 exp -11d 0 Kn 3 • 2 2 δ ≤ 2 exp (-11K/12) 1/8, since d 0 ≥ 1 and K ≥ 4. This implies that Prob [N ice] = Prob [N Y ∩ N S ] = Prob N Y ∪ N S = 1 -Prob N Y ∪ N S ≥ 1 -Prob N S -Prob N Y ≥ 1 - 1 8 - 1 8 = 3 4 ,
where the last inequality follows from the bounds on Prob [N S ] and Prob [N Y ]. Hence,

Exp[W ] ≥ 3 4 Exp[W |N ice] = 3 4 s • Exp[W 1 |N ice] ≥ 3np 8 Exp[W 1 |N ice], (8)
where the equality follows by symmetry of the choice of i s from the indices in I, and the last inequality comes from the lower bound on s under the condition N ice.

So to lower bound Exp

[W ], it suffices to lower bound Exp[W 1 |N ice]. Let W 2 denote W 1 |N ice. We shall lower bound Exp[W 2 |I ],
that is, the expected weight contributed by i s , under the event N ice, for a fixed choice of I .

By definition, W

1 = {v1,v 1 }∈E1 w ({v 1 , v 1 }). Partition V into equivalence classes V 1 , . . . , V r
according to their projection onto I :

V = V 1 . . . V r , where r ≤ c(3np/2) d = O((n/δ) d ).
Here, c is the constant independent of n, δ, occuring in the definition of primal shatter dimension. Define B ⊂ [r] as follows:

B := {j ∈ [r] : v ∈ V j ⇔ v | I > ekp}.
Further, let G be [r] \ B. Since N ice holds, we have:

j∈B |V j | ≤ 8 Exp[Y ]. (9)
We will estimate the contribution of the classes in G to the expected weight Exp[W 2 |I ], that is, the contribution of the edges of UD(V 1 ) which have both of their endpoints in G. Consider a class V i such that i ∈ G. Let V 1 ⊂ V i be those vectors in V i with 1 in the i s -th coordinate, and let

V 2 = V i \ V 1 . Let b = |V i |, b 1 = |V 1 | and b 2 = |V 2 |.
Then the edge {v, v } ∈ E 1 formed by the projection of V i onto I, has weight

w v, v = min(b 1 , b 2 ) ≥ b 1 b 2 b . (10)
Observe that in Inequality (10), b depends only on the subset I . Also, since I is fixed, the product b 1 2 depends on the choice of i s . The product b 1 b 2 is the number of ordered pairs of vectors (v, v ), with v and v in V i , such that v and v differs only in the i s -th coordinate. Observe that under the event N ice, for a fixed I , the probability that any given element i ∈ [n] is the chosen element i s , is

1 n-|I | = 1 n-s+1 ≥ 1 n 8 . Since for a given ordered pair (v, v ) of distinct vectors v, v ∈ V i , v and v differ in ρ(v, v ) > δ coordinates, the probability that (v, v ) differ in the chosen i s -th coordinate is Prob |v is -v is | = 1 = ρ(v, v ) n -s + 1 ≥ δ n .
Therefore, the expected contribution of (v, v ) to b 1 b 2 is at least δ n and this implies

Exp[w v, v |N ice] ≥ Exp (b 1 b 2 /b)|N ice ≥ b(b -1)δ bn = δ(b -1) n = δ(|V i | -1) n ,
where the inequality in the second line comes from Inequality (10).

Hence, the expected contribution of G to the weight W 2 is:

Exp[W 2 |I ] ≥ {v,v }∈G Exp[w v, v |N ice] ≥ i∈G (|V i | -1) δ n . (11)
Observe that by the (d, d 1 ) Clarkson-Shor property and the fact that |I | < 3np 2 , we have

|G| ≤ C|I | d 1 (ekp) d-d 1 < C (3np/2) d 1 (ekp) d-d 1 ,
where C is a constant. Substituting the bound of |G| in Inequality (11) and the fact that j∈B |V j | ≤

8 Exp[Y ] (see Inequality (9)) we get:

Exp[W 2 |I ] ≥ i∈G |V i | -|G| δ n ≥ i∈G |V i | -C(3np/2) d 1 (ekp) d-d 1 δ n = |V| - i∈B |V i | -C(3np/2) d 1 (ekp) d-d 1 δ n ≥ |V| -8 Exp[Y ] -C(11d 0 K) d .(3/2) d 1 e d-d 1 n δ d 1 k δ d-d 1 δ n ≥ M(δ, k, V) -8 Exp[Y ] -C 1 K d n δ d 1 k δ d-d 1 δ n ,
where

C 1 = C • (11d ) d (3/2) d 1 e d-d 1 .
Since the above holds for each I which satisfies N ice, we get that

Exp[W 2 ] ≥ M(δ, k, V) -8 Exp[Y ] -C 1 K d n δ d 1 k δ d-d 1 δ n ,
Using Inequality (8), and comparing with the upper bound on W ,

(3np/8) Exp[W 2 ] ≤ Exp[W ] ≤ 2d 0 M(δ, k, V),
and substituting the lower bound on Exp[W 2 ] and solving for M(δ, k, V), we get

M(δ, k, V) ≤ 33K 8 Exp[Y ] + C 1 K d n δ d 1 k δ d-d 1 33K -16 .
Next, the following lemma connects the parameters K and g:

Lemma 12 For K = max 4, 2d log g 11d 0 , Exp[Y ] ≤ n d 1 k d-d 1 δ d .
Substituting the choice of K and the value of Exp[Y ] from Lemma 12, we get that

g d n δ d 1 k δ d-d 1 = M(δ, k, V) ≤ C 1 K d n δ d 1 • k δ d-d 1 + 8 n δ d 1 • k δ d-d 1 1 -16/33K ≤ C 2 K d n δ d 1 • k δ d-d 1 ≤ C 2 max 4, 2d log g 11d 0 d • n δ d 1 • k δ d-d 1 ,
(where in the second step we used that 1 -16/33K ≥ 1/2, and hence C 2 is a positive constant.)

The last inequality above implies that

g d ≤ C 2 max{4, 2d log g 11d 0 } d , or with C 3 = C 1/d 2 : g ≤ C 3 max 4, 2d log g 11d 0 . ( 12
)
We claim that the above implies that g, and hence K, must be bounded from above by a constant independent of n, k, δ. If g is not increasing with n, k, and δ, then g is bounded, and we are done.

Otherwise, for any g = g(n, k, δ) growing with n, k, or δ, we have g C 4 log g (where C 4 = 2dC 3 11d 0 ) for sufficiently large n, k or δ. This inequality can only be satisfied when g is bounded by a constant function of n, k and δ, i.e., g(n, k, δ) ≤ c * , where c * is independent of n, k and δ. Thus in either case, g = g(n, k, δ) is a function bounded by an absolute constant. Therefore, it suffices to take K ≥ 2d log c * 11d 0 , where c * is the greatest positive value satisfying Inequality (12).

Exp[Y ] ≤ M(δ, k, V) exp - 11d 0 Kk δ ≤ M(δ, k, V) exp (-11d 0 K/2) ,
since k ≥ δ/2. Substituting the value of M(δ, k, V) in terms of g, we have

Exp[Y ] ≤ g d n δ d 1 • k δ d-d 1 • exp(-11d 0 K/2) ≤ n δ d 1 • k δ d-d 1 • exp d log g - 11d 0 K 2 ≤ n δ d 1 • k δ d-d 1 , for K ≥ 2d log g 11d 0 .
4 Applications

Realization to Geometric Set Systems

We now incorporate the random sampling technique of Clarkson and Shor [START_REF] Clarkson | Applications of random sampling in computational geometry[END_REF] with Theorem 4 in order to conclude that small shallow packings exist in several useful scenarios. This includes the case where V represents: (i) A collection of halfspaces defined over an n-point set in d-space (that is, each set in the set system is the subset of points contained in a halfspace). In this case, for any integer parameter 0 ≤ k ≤ n, the number of halfspaces that contain at most k points is O(n d/2 k d/2 ), and thus the primal shatter function has a (d, d/2 ) Clarkson-Shor property.

(ii) A collection of balls defined over an n-point set in d-space. Here, the number of balls that contain at most k points is O(n (d+1)/2 k (d+1)/2 ), and therefore the primal shatter function has a (d + 1, (d + 1)/2 ) Clarkson-Shor property. (iii) A collection of parallel slabs (that is, each of these regions is enclosed between two parallel hyperplanes and has an arbitrary width), defined over an n-point set in d-space. The number of slabs, which contains at most k points is O(n d k).

(iv) A dual set system of points in d-space and a collection F of n (d -1)-variate (not necessarily continuous or totally defined) functions of constant description complexity. Specifically, the graph of each function is a semi-algebraic set in R d defined by a constant number of polynomial equalities and inequalities of constant maximum degree (see [SA95, Chapter 7] for a detailed description of these properties, which we omit here).9 In this case, V is represented by the cells (of all dimensions) in the arrangement of the graphs of the functions in F (see Section 1 for the definition) that lie below at most k function graphs. This portion of the arrangement is also referred to as the at most k-level, and its combinatorial complexity is O(n d-1+ε k 1-ε ), for any ε > 0, where the constant of proportionality depends on d and ε. Thus the primal shatter function has a (d, d -1 + ε) Clarkson-Shor property.

All bounds presented in (i)-(iv) are well known in the field of computational geometry; we refer the reader to [CS89, Mat02, SA95] for further details. We thus conclude:

Corollary 13 Let V ⊆ {0, 1} n be a set of indicator vectors representing a set system of halfspaces defined over an n-point set in d-space, and let δ, k be two integer parameters as in Theorem 4. Then:

M(δ, k, V) = O n d/2 k d/2 δ d ,
where the constant of proportionality depends on d.

Corollary 14 Let V ⊆ {0, 1} n be a set of indicator vectors representing a set system of balls defined over an n-point set in d-space, and let δ, k be two integer parameters as in Theorem 4. Then:

M(δ, k, V) = O n (d+1)/2 k (d+1)/2 δ d+1 ,
Concluding Remarks. The analogy between shallow packings for dual set systems and shallow cuttings [START_REF] Matoušek | Reporting Points in Halfspaces[END_REF] may cause one to interpret shallow packings as the "primal version" of shallow cuttings. For an example of getting shallow packing, though now explicitly stated as such, for dual set systems with small union complexity via shallow cuttings refer to Mustafa and Ray's paper on Mnets [START_REF] Mustafa | Near-Optimal Generalisations of a Theorem of Macbeath[END_REF]. In this paper we presented discrepancy applications for shallow packings. We hope to find additional applications in geometry and beyond.

coordinates of the random variable V, the variance in the choice of the remaining coordinate is relatively small. That is:

Lemma 18 ( [START_REF] Haussler | Sphere Packing Numbers for Subsets of the Boolean N-cube with Bounded Vapnik-Chervonenkis Dimension[END_REF]) For any distribution P on V,

n i=1 Var(V i |V 1 , . . . , V i-1 , V i+1 , . . . , V n ) ≤ d 0 .
As observed in [START_REF] Haussler | Sphere Packing Numbers for Subsets of the Boolean N-cube with Bounded Vapnik-Chervonenkis Dimension[END_REF], Lemma 18 continues to hold on any restriction of V to a sequence I = {i i , . . . , i m } of m ≤ n indices. Indeed, when projecting V onto I the VC-dimension in the resulting set system remains d 0 . Furthermore, the conditional variance is now defined w.r.t. the induced probability distribution on V | I in the obvious way, where the probability to obtain a sequence of m values corresponds to an appropriate marginal distribution, that is,

Prob | I (u 1 , . . . , u m ) = Prob(v ∈ V | v i j = u j , 1 ≤ j ≤ m).
With this observation, we can rewrite the inequality stated in Lemma 18 as

m i=1 Var(V i j |V i 1 , . . . , V i j-1 , V i j+1 , . . . , V im ) ≤ d 0 .
If I is a sequence chosen uniformly at random (over all such m-tuples), then when averaging over all choices of I we clearly obtain:

Exp m i=1 Var(V i j |V i 1 , . . . , V i j-1 , V i j+1 , . . . , V im ) ≤ d 0 , or m i=1 Exp Var(V i j |V i 1 , . . . , V i j-1 , V i j+1 , . . . , V im ) ≤ d 0 ,
by linearity of expectation. In fact, by symmetry of the random variables V i j (recall that I is a random m-tuple) each of the summands in the above inequality has an equal contribution, and thus, in particular (recall once again that the expectation is taken over all choices of I = {i i , . . . , i m }):

Exp I Var(V im |V i 1 , . . . , V i m-1 ) ≤ d 0 m , (13)
where we write Exp I [•] to emphasize the fact that the expectation is taken over all choices of I . The above bound is now integrated with the next key property:

Lemma 19 ( [ Hau95
]) Let V be δ-separated subset of {0, 1} n , for some 1 ≤ δ ≤ n integer, and form a uniform distribution P on V. Let I = (i 1 , . . . , i m-1 ) be a sequence of m -1 distinct indices between 1 and n, where m is any integer between 1 and n. Suppose now that another index i m is drawn uniformly at random from the remaining n -m + 1 indices. Then

Exp Var V im |V i 1 . . . , V i m-1 ≥ δ 2(n -m + 1) 1 - |V | I | |V| ,
where the conditional variance is taken w.r.t. the distribution P , and the expectation is taken w.r.t. the random choice of i m .

We now observe that when the entire sequence I = (i 1 , . . . , i m ) is chosen uniformly at random, then the bound in Lemma 19 continues to hold when averaging on the entire sequence I (rather than just on i m ), that is, we have:

Exp I Var V im |V i 1 . . . , V i m-1 ≥ Exp I δ 2(n -m + 1) 1 - |V | I | |V| (14) = δ 2(n -m + 1) 1 - Exp I [|V | I |] |V| .
Note that under this formulation, |V | I | (the number of sets in the projection of V onto I) is a random variable that depends on the choice of I = (i 1 , . . . , i m-1 ), in particular, since it does not depend on the choice of i m , we have

Exp I [|V | I |] = Exp I [|V | I |].
The analysis of Haussler [START_REF] Haussler | Sphere Packing Numbers for Subsets of the Boolean N-cube with Bounded Vapnik-Chervonenkis Dimension[END_REF] then proceeds as follows. We assume that V is δ-separated as in Lemma 19 (then a bound on |V| is the actual bound on the packing number), and then choose m := (2d 0 + 2)(n + 1) δ + 2d 0 + 2 , indices i 1 , . . . , i m uniformly at random without replacements from [n] (without loss of generality, we can assume that δ ≥ 3 as, otherwise, we set the bound on the packing to be O(n d 1 k d-d 1 ), as asserted by the (d, d 1 ) Clarkson-Shor property of V. Moreover, we can assume, without loss of generality, n ≥ d 0 , δ, and thus we have m ≤ n). Put I = {i 1 , . . . , i m }, I = I \ {i m }. Then the analysis in [START_REF] Haussler | Sphere Packing Numbers for Subsets of the Boolean N-cube with Bounded Vapnik-Chervonenkis Dimension[END_REF] combines the two bounds in Inequalities ( 13) and ( 14) in order to derive an upper bound on |V|, from which the bound in the Packing Lemma (Theorem 3) is obtained. Specifically, using simple algebraic manipulations, we obtain:

|V| ≤ Exp I |V | I | 1 -2d 0 (n-m+1) mδ (15)
It has been shown in [START_REF] Haussler | Sphere Packing Numbers for Subsets of the Boolean N-cube with Bounded Vapnik-Chervonenkis Dimension[END_REF] that due to our choice of m, we have:

2d 0 (n -m + 1) mδ ≤ d 0 d 0 + 1 , (16)
from which we obtain Inequality (1), as asserted. This completes the description of our first extension of Haussler's analysis, as described in Section 2.1.

In order to apply our second extension, we observe that one only needs to assume m ≤ n when obtaining Inequalities (13) and ( 14). In addition, the choice of m in Inequality (15) can be made slightly larger (but still smaller than n), since the term 2d 0 (n-m+1) mδ in Inequality ( 16) is a decreasing function of m, as can easily be verified. Recall that in our analysis we replace m by m j := m log (j) (n/δ), where 2 ≤ j ≤ log * (n/δ), in which case we still obtain |V| ≤ (d 0 + 1) Exp I j |V | I j | , where I j is a set of m j -1 indices chosen uniformly at random without replacements from [n].

B Proof of Theorem 17.

We use the framework of Ezra [START_REF] Ezra | A Size-sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension[END_REF], together with the Shallow Packing Lemma (Theorem 4), to show Theorem 17. To this end, we use the machinery and notation in [START_REF] Ezra | A Size-sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension[END_REF] and only revise the proof of [Ezr16, Theorem 3.5], where we now plug into the analysis the new bound in (Theorem 4). In particular, we use the same notation and definitions for F i j (representing an appropriate collection of "canonical sets") and ∆ i j (representing a desired discrepancy bound on the canonical sets), and then bound an appropriate entropy function in order to apply the mechanism of Lovett and Meka [START_REF] Lovett | Constructive Discrepancy Minimization by Walking on the Edges[END_REF]. We do not repeat these details here, and instead refer the reader for the notation and machinery presented in [START_REF] Ezra | A Size-sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension[END_REF]. In the sequel we only show the derivation of the bound for ∆ i j , then the derivation of the discrepancy bound for the original sets S ∈ Σ is straightforward by the analysis in [START_REF] Ezra | A Size-sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension[END_REF], in which S is represented by the disjoint union of the symmetric difference of pairs of canonical sets.

Assume without loss of generality that log n is an integer, and let k := log n. By Theorem 4 and the analysis in [START_REF] Ezra | A Size-sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension[END_REF], we have that for each i = 1, . . . , k and j = i -1, . . . , k,

|F i j | ≤ C • 2 jd 2 (i-1)(d-d 1 ) ,
where C > 0 is an appropriate constant as stated in Theorem 4. By the construction in [START_REF] Ezra | A Size-sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension[END_REF], each set F i j ∈ F i j satisfies |F i j | = O(n/2 i-1 ), for a fixed index i, and any j = i -1, . . . , k. Our discrepancy parameter ∆ i j is chosen as follows:

∆ i j := A • 1 (1 + |j -j 0 |) 2
n 1/2-1/(2d) 2 (i-1)•(1/2-d 1 /(2d)) log 1/2d n, for an appropriate constant B > 5 + log C, and for a sufficiently large constant of proportionality A > 0, whose choice depends on B, and will be determined shortly (note that all the three constants A, B, and C depend on d).

In order to apply the constructive discrepancy minimization technique of Lovett and Meka [LM12], we need to show: Lemma 20 Put s j := n/2 j-1 . The choice in (17), for A > 0 sufficiently large (whose choice depends on C and thus on d), satisfies

k i=1 k j=i-1 C • 2 jd 2 (d-d 1 )(i-1) exp - (∆ i j ) 2 16s j ≤ n 16 . ( 18
)
We next proceed almost verbatim as in [START_REF] Ezra | A Size-sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension[END_REF].

We first note that at j = j 0 the above exponent becomes a constant, whereas the bound C • We now fix an index i, split the summation into the two parts j ≥ j 0 and i -1 ≤ j < j 0 , and then bound each part in turn. In the first part, the exponent will "take over" the summation in the sense that it decreases superexponentially, making the other factors (with j > j 0 ) insignificant, and in the second part, the packing size will decrease geometrically. Thus the "peak" of this summation is obtained at j = j 0 , and is decreasing as we go beyond or below j.

For the first part, put j := j 0 + l, for an integer l ≥ 0, and then

k i=1 k j=j 0 C • 2 jd 2 (d-d 1 )(i-1) exp - (∆ i j ) 2 16s j ≤ k i=1 k-j 0 l=0 C • n2 ld 2 dB log n exp - A 2 16 • 2 l-(B+1) (1 + l) 4 ≤ C • n2 -dB k-j 0 l=0 2 ld exp - A 2 16 • 2 l-(B+1) (1 + l) 4 ,
where the logarithmic factor is now eliminated due to the summation over i. The exponents in the above sum decrease superexponentially. Choosing A sufficiently large (say, A > 2 6+(B+1)+log d ) and having B > 5 + log C as above, we can guarantee that the latter sum is strictly smaller than n/32.

When j < j 0 , put j := j 0 -l, l > 0 as above. We now obtain, by just bounding the exponent from above by 1, and using similar considerations as above:

k i=1 j0-1 j=i-1 C • 2 jd 2 (d-d1)(i-1) exp - ∆ i j 2 16s j ≤ k i=1 j0-1 j=i-1 C • n log n2 d(l+B) ≤ j0-(i-1) l=1 C • n 2 d(l+B) .
Once again, our choice for B guarantees that the above (geometrically decreasing) sum is strictly smaller than n/32. Thus the entire summation is bounded by n/16, as asserted. This completes the proof of Theorem 17.

Figure 1 :

 1 Figure 1: A grid of n δ × n δ axis-parallel rectangles, each of which with multiplicity δ/2. The multiplicity in the figure is depicted only for the leftmost vertical and the top horizontal rectangles. The small shaded rectangle in the figure is a δ-shallow cell of the arrangement.

  (i) Obtain a refined bound on Exp I |V | I | : In the analysis of Haussler Exp I |V | I | is replaced by its upper bound O(m d ), resulting from the fact that the primal shatter dimension of V (and thus of V | I ) is d, from which we obtain that for any choice of I,

  (j-1) (n/δ)) D , and then exploit the relation |V| ≤ (d 0 + 1) Exp I j |V | I j | (Inequality (4)), in order to prove Inequality (6). In order to obtain the first term in the bound on Exp I j |V | I j | , we consider all vectors of length at most C • k(m j -1) n

Proof:

  The proof is based on the following lemma, proved by Haussler [Hau95] for set systems with bounded VC-dimension. The following version appears in [Mat99]: Lemma 11 ([Hau95]) Let V ⊆ {0, 1} n be a set of indicator vectors with VC-dimension d 0 . Then the unit-distance graph UD(V) has at most d 0 |V| edges.

  The constants C 1 , C 2 are of the order of d d 0 . Therefore C 3 is O(d 0 ), and C 4 is O(d). Hence, c * = O(d log d), and therefore g d = O((d log d) d ). Thus the constant of proportionality in the bound, in the proof based on Chazelle's approach, can be upper bounded by O((d log d) d ) = O(2 d log d ).It only remains to prove Claim 12:Proof of Lemma 12: The proof follows easily from Chernoff Bounds. Fix v ∈ V, and letZ = v | I and Z = v | I . Observe that Z ≥ Z. Since v ≤ k, we have Exp[Z ] ≤ kp.The probability that Z ≥ ekp is upper bounded using Chernoff bounds, see [AS08, Theorem A.1.12], as follows:Prob [Z > ekp] ≤ Prob Z -Exp[Z ] > β -1 Exp[Z ] , where β = ekp Exp[Z ] , ≤ exp -Exp[Z ](β log β -β + 1) ≤ exp -ekp(log β -1 + 1 β ) ≤ exp(-kp) ≤ exp -11d 0 Kk δ , since β = ekp Exp[Z ]≥ e, and as can be verified by elementary calculus, for any β ≥ e, log β -1+1/β ≥ 1/e. Hence the expected number Exp[Y ] of vectors whose projections on I have norm at least (11ed 0 Kk/δ), is at most:

where j 0

 0 := (1/d) log n + (1 -d 1 /d)(i -1) -(1/d) log log n -B,

  2 jd 2 (d-d 1 )(i-1) (representing an appropriate packing number) becomes roughly n/ log n (for a fixed index i). Indeed, applying our choice in (17), we haveexp -A 2 • 2 j-1 log 1/d n 16(1 + |j -j 0 |) 4 n 1/d 2 (1-d 1 /d)•(i-1) , which is exp -A 2 16•2 B+1 at j = j 0 = (1/d) log n + (1 -d 1 /d)(i -1) -(1/d) log log n -B. Concerning the bound C • 2 jd2 (d-d 1 )(i-1) , at j = j 0 we obtain:C • n2 (d-d 1 )(i-1) 2 (d-d 1 )(i-1) 2 dB log n = C • n 2 dB log n ,as asserted.

We ignore the cases where d1 < 1, as it does not seem to appear in natural set systems-see below.

We note that although in the original analysis for this bound d is the VC-dimension, this assumption can be replaced by having just a primal shatter dimension d; see, e.g.,[START_REF] Har-Peled | Geometric Approximation Algorithms[END_REF] for the details of the analysis.

We note, however, that the original analysis of Haussler[START_REF] Haussler | Sphere Packing Numbers for Subsets of the Boolean N-cube with Bounded Vapnik-Chervonenkis Dimension[END_REF] does not rely on the primal shatter dimension, and the bound on Exp I |V | I | is just O(m d 0 ) due to the Sauer-Shelah Lemma.

In this particular step we use a different machinery than that of Haussler[START_REF] Haussler | Sphere Packing Numbers for Subsets of the Boolean N-cube with Bounded Vapnik-Chervonenkis Dimension[END_REF]; see the proof of Lemma 5 and our remark after Corollary

Therefore, |I1| = m1, rather than m1 -1. Furthermore, the constant of proportionality in the bound on m1 depends just on the primal shatter dimension d instead of the VC-dimension d0 as in (3).

We observe that 2 ≤ log * (n/δ) -log * (d0 + 1) ≤ log * (n/δ), due to our assumption that δ < n/2 (d 0 +1) , and the fact that d0 ≥ 1.

For any p ∈ (0, 1), the binomial distribution with parameter p on a finite set X, under the conditions that only one element is selected and that it does not belong to a fixed subset I ⊂ X, is just the uniform distribution on X \ I .

In[START_REF] Sharir | Davenport-Schinzel Sequences and Their Geometric Applications[END_REF] it is also required that the projection of each function onto the plane x d = 0 has a constant description complexity.

Acknowledgments. We authors would like to thank two anonymous referees for their useful comments. The second author wishes to thank Boris Aronov, Sariel Har-Peled, Aryeh Kontorovich, and Wolfgang Mulzer for useful discussions and suggestions. Last but not least, the second author thanks Ramon Van Handel, for various discussions and for spotting an error in an earlier version of this paper.

* Work on this paper by Kunal Dutta and Arijit Ghosh has been supported by the Indo-German Max-Planck Center for Computer Science (IMPECS). Work on this paper by Esther Ezra has been supported by NSF Grants CCF-11-17336, CCF-12-16689, and NSF CAREER CCF-15-53354. A preliminary version of this paper appeared in

where the constant of proportionality depends on d.

Corollary 15 Let V ⊆ {0, 1} n be a set of indicator vectors representing a set system of parallel slabs defined over an n-point set in d-space, and let δ, k be two integer parameters as in Theorem 4. Then:

where the constant of proportionality depends on d.

Corollary 16 Let V ⊆ {0, 1} n be a set of indicator vectors representing a dual set system of n (d -1)-variate (not necessarily continuous or totally defined) functions of constant description complexity and points in d-space. Let δ, k be two integer parameters as in Theorem 4. Then:

where the constant of proportionality depends on d and on ε.

Size-Sensitive Discrepancy Bounds

Suppose we are given a set system Σ defined over an n-point set X (for simplicity of exposition, we refer to Σ as a collection of subsets of X rather than a collection of vectors defined over the unit cube). We now wish to color the points of X by two colors, such that in each set of Σ the deviation from an even split is as small as possible.

Formally, a two-coloring of X is a mapping χ : X → {-1, +1}. For a set S ∈ Σ we define χ(S) := x∈S χ(x). The discrepancy of Σ is then defined as disc(Σ) := min χ max S∈Σ |χ(S)|.

In a previous work [START_REF] Ezra | A Size-sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension[END_REF], the second author presented size-sensitive discrepancy bounds for set systems of halfspaces defined over n points in d-space. These bounds were achieved by combining the entropy method [START_REF] Lovett | Constructive Discrepancy Minimization by Walking on the Edges[END_REF] with δ-packings, and, as observed in [START_REF] Ezra | A Size-sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension[END_REF], they are optimal up to a poly-logarithmic factor. Incorporating our bound in Theorem 4 into the analysis in [START_REF] Ezra | A Size-sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension[END_REF], the bounds on χ(S) improve by a logarithmic factor. Specifically, we obtain (see Appendix B for the proof):

Theorem 17 Let Σ be a set system, defined over an n-point set, whose primal shatter function has a (d, d 1 ) Clarkson-Shor property. Then, there is a two-coloring χ, such that for each S ∈ Σ:

Such a two-coloring χ can be computed in expected polynomial time.

A Overview of Haussler's Approach

Let V ⊆ {0, 1} n be a collection of indicator vectors of primal shatter dimension d. We denote its VC-dimension by d 0 ; as discussed in Section 1

We first form a probability distribution P over V, implying that V can be viewed 10 as an n-dimensional random variable taking values in {0, 1} n . Thus its components V i , i = 1, . . . , n, represent n correlated indicator random variables (Bernoulli random variables), and each of their values is determined by randomly selecting a vector v ∈ V, and letting V i be the ith component of v. The variance of a Bernoulli random variable B is known to be Prob[B = 1] Prob[B = 0], and then, for a sequence B 1 , . . . , B m of Bernoulli random variables, the conditional variance of B m given B 1 , . . . , B m-1 is defined as

A key property in the analysis of Haussler [START_REF] Haussler | Sphere Packing Numbers for Subsets of the Boolean N-cube with Bounded Vapnik-Chervonenkis Dimension[END_REF] lies in the density of a unit distance graph G = (V, E), defined over V, whose edges correspond to all pairs u, v ∈ V, whose symmetric difference distance is (precisely) 1. In other words, u, v appear as neighbors on the unit cube {0, 1} n . It has been shown by Haussler et al. [HLW94] that the density of G is bounded by the VC-dimension of V, that is, |E|/|V| ≤ d 0 ; see also [START_REF] Haussler | Sphere Packing Numbers for Subsets of the Boolean N-cube with Bounded Vapnik-Chervonenkis Dimension[END_REF] for an alternative proof using the technique of "shifting". 11 Then, this low density property is exploited in order to show that once we have chosen (n -1) 10 For the time being, P is an arbitrary distribution, but later on (Lemma 19) it is taken to be the uniform distribution in the obvious way, where each vector in V is equally likely to be chosen. This distribution, however, may not remain uniform after the projection of V onto a proper subsequence I = (i1, . . . , im) of m < n indices, as several vectors in V may be projected onto the same vector in V | I .

11 We cannot guarantee such a relation when the VC-dimension d0 is replaced by the primal shatter dimension d, and therefore we proceed with the analysis using this ratio.