A Note on the Size-Sensitive Packing Lemma
Nabil H. Mustafa\footnote{Universit\'e Paris-Est
Laboratoire d'Informatique Gaspard-Monge
Equipe A3SI
ESIEE Paris. E-email: mustafan@esiee.fr. The work of Nabil H. Mustafa in this paper has been supported by the grant ANR SAGA (JCJC-14-CE25-0016-01).
We show that the size-sensitive packing lemma follows from a simple modification of the standard proof, due to Haussler and simplified by Chazelle, of the packing lemma.
mac.tex
%MACROS
%
%MATH MACROS
%
\newcommand{\dd}{ ,\, \ldots,\, }
\newcommand{\cd}{\,  \cdots \,  }
\newcommand{\vd}{\,  \vdots \,  }
\newcommand{\ib}{\subseteq }
\newcommand{\nmem}{\not\member}
\newcommand{\as}{\mbox{\,:=\,}}
\newcommand{\st}{\::\:}
\newcommand{\es}{\emptyset}
\newcommand{\mt}{\rightarrow}
\newcommand{\imp}{\Rightarrow}
%\newcommand{\dfrac}[2]{\displaystyle{\frac{#1}{#2}}}
\newcommand{\arro}[1]{\mathop{#1}\limits^{\rightarrow}}
\newcommand{\larro}[1]{{\mathop{#1}\limits^{\longrightarrow}}}
\newcommand{\barro}[1]{{\mathop{#1}\limits^{\longleftarrow}}}
\newcommand{\dhat}[1]{{\skew4\hat\hat #1}}
\def\floor#1{\left\lfloor #1 \right\rfloor}
\newcommand{\bfloor}[1]{\lfloor #1 \rfloor}
\def\ceil#1{\left \lceil #1 \right\rceil}
\newcommand{\bceil}[1]{\lceil #1 \rceil}
%
%\newcommand{\reals}{{\rm I\!\hspace{-0.025em} R}}
%\newcommand{\naturals}{\mbox{\rm I$\!$N}}
%\newcommand{\complex}{\mbox{\rm $~\vrule height6.5pt width0.5pt depth0.3pt\!\!$C}}
%\newcommand{\rational}{\mbox{\rm $~\vrule height6.5pt width0.5pt
%depth0.3pt\!\!$Q}}
%%\newcommand{\integers}{\mbox{\rm \lower0.3pt\hbox{$\angle\!\!\!$}Z}}
%\newcommand{\sphere}{{\cal S}}
%\newcommand{\integers}{{\sf Z}\!\hspace{-.25em}{\sf Z}}
%\newcommand{\eu}{{\cal E}}
\newcommand{\euclidean}{\ensuremath{\mathbb{E}}}
\newcommand{\reals}{\ensuremath{\mathbb{R}}}
\newcommand{\sphere}{\ensuremath{\mathbb{S}}}
\newcommand{\integers}{\ensuremath{\mathbb{Z}}}
\newcommand{\naturals}{\ensuremath{\mathbb{N}}}
\newcommand{\nat}{\ensuremath{\mathbb{N}}}
\newcommand{\complex}{\ensuremath{\mathbb{C}}}
\newcommand{\rationals}{\ensuremath{\mathbb{Q}}}
\newcommand{\seg}[1]{\overline{#1}}
\newcommand{\li}{\item}
\newcommand{\rbox}{\begin{flushright}
	\vspace{-4mm}
	$\Box$
	\vspace{-1mm}
	\end{flushright}}
\newcommand{\dstyle}{\displaystyle}
\newcommand{\sstyle}{\scriptstyle}
\def\etal{\emph{et al.}}
%
%
%
%
%
%
%
%
%
%
\newcounter{listcounter}
\newcommand{\chlist}[1]
{\renewcommand{\thelistcounter}{#1{listcounter}}}
\renewcommand{\thelistcounter}{\roman{listcounter}}
%
\newcommand{\descr}{\begin{list}{(\thelistcounter)}
{\usecounter{listcounter}
\setlength{\rightmargin}{0mm}}}
%
%
% New theorem environments.
%
%
 

\newtheorem{lemma}{Lemma}[section]
\newtheorem{theorem}{Theorem}
\newtheorem{cor}[lemma]{Corollary}
\newtheorem{prop}[lemma]{Proposition}
\newtheorem{exer}[lemma]{Exercise}
\newtheorem{rmk}[lemma]{Remark}
\newtheorem{claim}[lemma]{Claim}
\newtheorem{fact}[lemma]{Fact}
\newtheorem{Def}[lemma]{Definition}
%
%New environments.
%
%\newenvironment{pf}{{\bf Proof:}}{{\rbox}}
%\newenvironment{Pf}{\par\noindent{\bf Proof:}}{\mbox{}\hfill$\Box$}
%%\newenvironment{pf}{{\bf Proof:}}{{\bf
%%Q.E.D.} \vspace{3mm}\\ \noindent}
\newif\ifpfsymb
\newenvironment{pf}{\par\addvspace{6pt}\addtocounter{proof}{1}
       \noindent{\bf Proof:}}{{\ifnum\value{proof}>0
		\hfill\hbox{\mbox{}\hfill$\Box$}\addtocounter{proof}{-1}
                \par\addvspace{10pt} \else\par\fi}}
%
\newenvironment{Pf}{\par\addvspace{6pt}\addtocounter{proof}{1}
       \noindent{\bf Proof:}}{{\ifnum\value{proof}>0
                \hfill\hbox{\mbox{}\hfill$\Box$}
		\addtocounter{proof}{-1}\par\addvspace{10pt}\else\par\fi
        }}
%
\newenvironment{Pfsketch}{\par\addvspace{6pt}\addtocounter{proof}{1}
        \noindent{\bf Proof (Sketch):}}{{\ifnum\value{proof}>0
               \hfill\hbox{\mbox{}\hfill$\Box$}
		\addtocounter{proof}{-1}\par\addvspace{10pt}\else\par\fi
        }}
%
\newenvironment{sketch}[2]{\par\addvspace{6pt}\addtocounter{proof}{1}
        \noindent{\bf Proof of #1~\ref{#2}.}}{{\ifnum\value{proof}>0
                \hfill\hbox{\mbox{}\hfill$\Box$}
		\addtocounter{proof}{-1}\par\addvspace{10pt}\else\par\fi
        }}
%
\def\endpfsymb{\hfill\hbox{\mbox{}\hfill$\Box$}
                \addtocounter{proof}{-1} \par\addvspace{10pt}
        }


\newenvironment{remark}{\par\addvspace{10pt}\noindent{\bf Remark 
		\addtocounter{lemma}{1} \hspace{-1mm}\thelemma
		\hspace{2mm}}}{\par\addvspace{10pt}}
\newenvironment{remarks}{\par\addvspace{10pt}\noindent{\bf Remarks 
		\addtocounter{lemma}{1} \hspace{-1mm}\thelemma
		\hspace{2mm}}}{\par\addvspace{10pt}}
\newenvironment{defn}{\par\addvspace{13pt}\noindent{\bf Definition
		\addtocounter{lemma}{1} \hspace{-1mm}\thelemma
		\hspace{2mm}}}{\par\addvspace{10pt}}
\newenvironment{defin}{\par\addvspace{13pt}\noindent{\bf Definition
		\addtocounter{lemma}{1} \hspace{-1mm}\thelemma
		\hspace{2mm}}}{\par\addvspace{10pt}}
\newenvironment{Defn}[1]{\par\noindent{\bf Definition 
		\addtocounter{lemma}{1}\hspace{-1mm}\thelemma\ [#1]:
		\hspace{2mm}}}{}
\newenvironment{hint}{{\bf Hint:\hspacve{2mm}}}{}

\makeatletter
\newcounter{algo}
\def\thealgo{\@arabic\c@algo}
\def\fps@algo{tbp}
\def\ftype@algo{1}
\def\ext@algo{loa}
\def\fnum@algo{Algorithm \thealgo}
\def\algo{\@float{algo}}
\def\endalgo{\end@float}
\makeatother

\newcounter{mycounter}
%
%GENERAL MACROS
%
%\newcommand{\remarks}{{\bf Remarks: \hspace{3mm}}}
\newcommand{\Example}{{\bf Example:}}
%
%
%
%
% Macros for cross referencing.
\newcommand{\alglab}[1]{\label{alg:#1}}
\newcommand{\lemlab}[1]{\label{lemma:#1}}
\newcommand{\factlab}[1]{\label{fact:#1}}
\newcommand{\prolab}[1]{\label{prop:#1}}
\newcommand{\proplab}[1]{\label{prop:#1}}
\newcommand{\exelab}[1]{\label{exer:#1}}
\newcommand{\theolab}[1]{\label{theo:#1}}
\newcommand{\chaplab}[1]{\label{chap:#1}}
\newcommand{\eqnlab}[1]{\label{eqn:#1}}
\newcommand{\corlab}[1]{\label{cor:#1}}
\newcommand{\figlab}[1]{\label{fig:#1}}
\newcommand{\tablab}[1]{\label{tab:#1}}
\newcommand{\seclab}[1]{\label{sec:#1}}
\newcommand{\subseclab}[1]{\label{subsec:#1}}
\makeatletter
\def\remlab#1{\@bsphack\if@filesw {\let\thepage\relax
   \def\protect{\noexpand\noexpand\noexpand}%
\xdef\@gtempa{\write\@auxout{\string
	   \newlabel{rem:#1}{{\thelemma}{\thepage}}}}}\@gtempa
            \if@nobreak \ifvmode\nobreak\fi\fi\fi\@esphack}
%\def\remlab#1{\write\@auxout{\string
	%\newlabel{rem:#1}{{\thelemma}{\thepage}}}}
\def\deflab#1{\write\@auxout{\string
	\newlabel{def:#1}{{\thelemma}{\thepage}}}}
\makeatother

\def\lemref#1{Lemma~\ref{lemma:#1}}
\def\algref#1{Algorithm~\ref{alg:#1}}
\def\factref#1{Fact~\ref{fact:#1}}
\def\proref#1{Proposition~\ref{prop:#1}}
\def\propref#1{Proposition~\ref{prop:#1}}
\def\exeref#1{Exercise~\ref{exer:#1}}
\def\theoref#1{Theorem~\ref{theo:#1}}
\def\corref#1{Corollary~\ref{cor:#1}}
\def\figref#1{Figure~\ref{fig:#1}}
\def\tabref#1{Table~\ref{tab:#1}}
\def\Figref#1{Figure~\ref{fig:#1}}
\def\chapref#1{Chapter~\ref{chap:#1}}
\def\secref#1{Section~\ref{sec:#1}}
\def\subsecref#1{Section~\ref{subsec:#1}}
\def\remref#1{Remark~\ref{rem:#1}}
\def\defref#1{Definition~\ref{def:#1}}
\def\mchapref#1{\ref{chap:#1}}
\def\msecref#1{\ref{sec:#1}}
\def\msubsecref#1{\ref{subsec:#1}}
\def\mtheoref#1{\ref{theo:#1}}
\def\mfigref#1{\ref{fig:#1}}
\def\eqnref#1{(\ref{eqn:#1})}
%
%
%
% Macros for generating table of contents
\newcommand{\secadd}[2]{\addcontentsline{toc}{section}{
		\protect\numberline{\msecref{#1}}{#2}}}
\newcommand{\subsecadd}[2]{\addcontentsline{toc}{subsection}{
		\protect\numberline{\msubsecref{#1}}{#2}}}
\newcommand{\chapadd}[2]{\addcontentsline{toc}{chapter}{
		\protect\numberline{\mchapref{#1}}{#2}}}
\newcommand{\figadd}[2]{\addcontentsline{lof}{figure}{
		\protect\numberline{\mfigref{#1}}{#2}}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Producing table of contents entries without
%numbers.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\nsecadd}[1]{\addcontentsline{toc}{section}{#1}}
\newcommand{\nsubsecadd}[1]{\addcontentsline{toc}{subsection}{#1}}
\newcommand{\nchapadd}[1]{\addcontentsline{toc}{chapter}{#1}}
%
%
% Macros for page style.
{\catcode`\@=11
\gdef\setft#1#2#3{%
\def\@oddfoot{%
{\setbox0=\hbox{#1}%
\setbox1=\hbox{#3}%
\ifdim\wd0>\wd1%
\dimen0=\wd0%
\box0\hfil#2\hfil\hbox to\dimen0{\hfil\hfil\box1}%
\else \dimen0=\wd1%
\hbox to\dimen0{\box0\hfil}\hfil#2\hfil\box1\fi%
}}}}

{\catcode`\@=11
\gdef\sethd#1#2#3{%
\def\@oddhead{\vbox{\hbox to\hsize{{#1}\hfil{#2}\hfil{#3}}%
\vspace{0.06in}%
\hbox to \hsize{\hrulefill}\vspace*{-0.09in}}}
\def\@evenhead{\@oddhead}
	}
}

%Macro for sections.
\def\mysec#1{\setcounter{equation}{0}
\section{#1}\mark{#1}}

\def\mysecn#1{\setcounter{equation}{0}
\section*{#1}\mark{#1}}

\def\myplsec#1{\setcounter{equation}{0}
       		\section*{#1}\mark{#1}}


\def\thebibliography#1{\mysecn{References}
\addcontentsline{toc}{section}{References}\list
{[\arabic{enumi}]}{\settowidth\labelwidth{[#1]}\leftmargin\labelwidth
 \advance\leftmargin\labelsep
 \usecounter{enumi}}
 \def\newblock{\hskip .11em plus .33em minus .07em}
 \sloppy\clubpenalty4000\widowpenalty4000
 \sfcode`\.=1000\relax
 \small}
\let\endthebibliography=\endlist
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  %%  Some code to insert marginal comments and number them in a paper.	%%
  %%  By default marginal comments are ignored.  If the command		%%
  %%  \withcomplaints is called, complaints are numbered, the number	%%
  %%  between dashes appears on the tex raised in a 0 width box so it	%%
  %%  does not affect the layout.					%%
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\complaint#1{}
\def\withcomplaints{
%\addtolength{\oddsidemargin}{-1.4cm}
%\addtolength{\evensidemargin}{-1.4cm}
\newcounter{mycomplaints}
\def\complaint##1{\refstepcounter{mycomplaints}%
\ifhmode%
\unskip%
{\dimen1=\baselineskip \divide\dimen1 by 2 %
\raise\dimen1\llap{\tiny -\themycomplaints-}}\fi%
\marginpar{\tiny [\themycomplaints]: ##1}}%
}
%

\newcounter{printertype}
\setcounter{printertype}{0}
\def\figprint#1{
        \ifcase \theprintertype

		\begin{center}
                 \input{#1}
		\end{center}
              \or
                 \centerline{\psfig{figure=#1.ps}}
              \else
                 \vspace*{1in}
        \fi}


\makeatletter
\long\def\@myfootnotetext#1{\insert\footins{\footnotesize
    \interlinepenalty\interfootnotelinepenalty 
    \splittopskip\footnotesep
    \splitmaxdepth \dp\strutbox \floatingpenalty \@MM
    \hsize\columnwidth \@parboxrestore
   \edef\@currentlabel{\csname p@footnote\endcsname\@thefnmark}\@makemyfntext
    {\rule{\z@}{\footnotesep}\ignorespaces
      #1\strut}}}

\def\myfootnotetext{\@ifnextchar
[{\@xfootnotenext}{\xdef\@thefnmark{\thempfn}\@myfootnotetext}}

\long\def\@makemyfntext#1{\parindent 5mm #1}

%Equation environment to take care of the end-of-proof symbol

\newcounter{proof}
\def\@@meqncr{\let\@tempa\relax
    \ifcase\@eqcnt \def\@tempa{& & &}\or \def\@tempa{& &}
      \else \def\@tempa{&}\fi
     \@tempa $\Box$\addtocounter{proof}{-1}
     \global\@eqnswtrue\global\@eqcnt\z@\cr}
\@namedef{meqnarray*}{\def\@eqncr{\nonumber\@seqncr}\eqnarray}
\@namedef{endmeqnarray*}{\global\@eqcnt\tw@\@@meqncr\egroup
      \global\advance\c@equation\m@ne$$\global\@ignoretrue}

\@namedef{meqnarray}{\eqnarray}
\@namedef{endmeqnarray}{\@@meqncr\egroup
        \global\advance\c@equation\m@ne$$\global\@ignoretrue}
\def\mequation{$$\global\@ignoretrue}
\def\endmequation{\eqno \Box$$\addtocounter{proof}{-1}}
\@namedef{Pf*}{\Pf}
\@namedef{endPf*}{\par\addvspace{10pt}}

\makeatother



shallowpackinglemma.tex
\documentclass[11pt]{article}

\usepackage{times}
\usepackage{url, color, epsfig, subfigure, amsmath, amsthm, amssymb}

\setlength{\textwidth}{6.5in}
\setlength{\evensidemargin}{0.0in}
\setlength{\oddsidemargin}{0.0in}
\setlength{\textheight}{8.8in}
\setlength{\topmargin}{-0.5in}



%\setlength{\oddsidemargin}{0.25in}
%\setlength{\evensidemargin}{0.25in}
%\setlength{\textwidth}{6in}
%\setlength{\textheight}{8in}


\usepackage{times}
\usepackage{url,amsmath, amssymb,epsfig,subfigure}

\usepackage{algorithm}
\usepackage[noend]{algorithmic}

\input mac
\setlength{\parindent}{0mm}
\setlength{\parskip}{2mm}

%\def\Ex{\ensuremath{\textbf{E}}}
\def\Ex{\mathop{\rm \textbf{E}}}

\def\F{\ensuremath{\mathcal{F}}}
\def\S{\ensuremath{\mathcal{S}}}
\def\P{\ensuremath{\mathcal{P}}}
\def\H{\ensuremath{\mathcal{H}}}
\def\R{\ensuremath{\mathcal{R}}}
\def\D{\ensuremath{\mathcal{D}}}
\def\OO{\ensuremath{\mathcal{O}}}
\def\C{\ensuremath{\mathcal{C}}}
\def\eps{\ensuremath{\epsilon}}
\newcommand{\bigcupdot}{\mathop{\dot{\bigcup}}}
\newcommand{\cupdot}{\mathbin{\mathaccent\cdot\cup}}
\newcommand{\myproof}{\textit{Proof. }}

\newtheorem{thmx}{Theorem}
\renewcommand{\thethmx}{\Alph{thmx}} % "letter-numbered" theorems



\newcommand{\remove}[1]{}

\def\polylog{{\mathop{\mathrm{polylog}}\nolimits}}

\newtheorem{corollary}{Corollary}[section]

%\renewcommand{\Re}{{\rm I\!\hspace{-0.025em} R}}
\renewcommand{\Re}{\mathbb{R}}
\newcommand{\inprod}[2]{\left\langle #1 , #2 \right\rangle}


% proof
\newsavebox{\smallProofsym}                            % smallproofsymbol
\savebox{\smallProofsym}                               %
{%                                                     %
\begin{picture}(6,6)                                   %
\put(0,0){\framebox(6,6){}}                            %
\put(0,2){\framebox(4,4){}}                            %
\end{picture}                                          %
}   

\begin{document}
        
\title{A Note on the Size-Sensitive Packing Lemma}
\date{}
 

\author{Nabil H. Mustafa\footnote{Universit\'e Paris-Est, Laboratoire d'Informatique Gaspard-Monge, Equipe A3SI, ESIEE Paris. E-email: mustafan@esiee.fr. The work of Nabil H. Mustafa
in this paper has been supported by the grant ANR SAGA (JCJC-14-CE25-0016-01).}}

\maketitle
 
\begin{abstract}
We show that the size-sensitive packing lemma
follows from a simple modification of the standard proof, due to Haussler and simplified by Chazelle, of the packing lemma.
\end{abstract}
 
\section{Introduction}
\label{sec:intro}

In 1995 Haussler~\cite{H95} proved the following interesting theorem\footnote{In what follows below, we refer the reader to Matousek's textbook~\cite[Section 5.3]{M99} for notations and proofs.}.

\begin{theorem}[Packing lemma {\cite[Lemma 5.14, p. 156]{M99}}]
Let $(X, \P)$ be a set-system on $n$ elements, and with VC-dimension at most $d$.
Let $\delta$ be an integer, $1 \leq \delta \leq n$, 
such that  $|\Delta(R, S)|\geq \delta$  for every $R, S \in \P$,
where $\Delta(R, S) = (R \setminus S) \cup (S \setminus R)$.
Then $|\P| = O( (n/\delta)^d )$.
\label{thm:1}
\end{theorem}

Haussler's proof is a beautiful application of the probabilistic method,
and was simplified by Chazelle~\cite{C92}.
We refer to the discussion in~\cite{M99} for motivations and applications.
Recently much effort has been devoted to finding 
size-sensitive generalizations of this result.
After a series of partial
bounds~\cite{E14, MR14}, the following
statement has been recently established in~\cite{DEG15},
via \emph{two} different proofs (one building on Haussler's original proof
while the other extends Chazelle's proof):

\begin{theorem}[Size sensitive packing lemma]
Let $(X, \P)$ be a set-system on $n$ elements, 
and let $d, d_1, k, \delta > 0$ be  integers.
Assume the system has VC-dimension at most $d$.
Further, assume that for any set $Y \subseteq X$ the
number of sets in $\P_{|Y}$ of size at most $r$ is  at most
$f( |Y|, r ) = O( |Y|^{d_1} r^{d-d_1} )$.
If $|\Delta(R, S)|\geq \delta$  for every $R, S \in \P$
and $|S| \leq k$ for all $S \in \P$, then 
$|\P| = O( n^{d_1} k^{d-d_1} /\delta^d )$. 
\label{thm:2}
\end{theorem}
 
The objective of this present note is to point out
that Theorem~\ref{thm:2}, with a simple trick, is an immediate
consequence of the textbook proof~\cite{M99} of Theorem~\ref{thm:1}.

\paragraph{Haussler and Chazelle's Proof.} We rewrite the main step in their proof in a slightly more general form:

\begin{lemma}[{\cite[Proof of Packing Lemma 5.14, pp. 157--159]{M99}}]
Let $(X, \P)$ be a set-system on $n$ elements. 
Let $d, \delta$ be two integers such that
the VC-dimension of $\P$ is at most $d$,
and $|\Delta(S, T)| \geq \delta$ for all $S, T \in \P$.
Then
$$ |\P| \leq 2 \cdot \Ex[|\P_{|A'}|], \text{where $A'$ is a random
sample of size $\frac{4dn}{\delta}-1$}.$$
\label{lemma:1}
\end{lemma}
\myproof
Let $W, W_1, A, s = \frac{4dn}{\delta}$ 
%as well as $A \subseteq X$ (random subset of size $s$)
%and $A' \subseteq X$ (random subset of size $s-1$) 
be precisely as defined in the 
proof in the textbook~\cite[Proof of Packing Lemma 5.14, pp. 157--159]{M99},
where the following relations are proven:
$i)$ $2d|\P| \geq \Ex[W] = s \cdot \Ex[W_1]$, where the expectation
is over the choice of $A$, and 
$ii)$ $\Ex[W_1 | A' = Y] \geq \frac{\delta}{n} \big( |\P| - |\P_{|Y}| \big)$,
where  $A'$ is set to a fixed $Y$, and the expectation is over
the choice of a random element in $X \setminus Y$. Together they imply the lemma:
%
%\begin{eqnarray}
%2d|\P| &\geq& \Ex[W] = s \cdot \Ex[W_1]  \label{eq:1}\\
%\Ex[W_1 | A'] &\geq& \frac{\delta}{n} \big( |\P| - |\P_{|A'}| \big) \label{eq:2}
%\end{eqnarray}
%where the expectation is over a random subset  $A \subseteq X$ of size $s$,
%and where $A' \subseteq X$ is a fixed set of size $s-1$. Then
%from Equations~(\ref{eq:1}) and (\ref{eq:2}), we get:
$$2d|\P| \geq \Ex[W] = s \cdot \Ex[W_1] \geq s \cdot \Big( \sum_{\substack{Y \subseteq X \\ |Y| = s-1}} \frac{\delta}{n} \big( |\P| - |\P_{|Y}| \big) \cdot \Pr[A'=Y] \Big) = 4d |\P| - 4d\Ex[|\P_{|A'}].$$ 
\qed

The proof in~\cite[Proof of Packing Lemma 5.14, pp. 157--159]{M99}
uses the primal shatter lemma to conclude the proof
of Theorem~\ref{thm:1}: $|\P_{|A'}| = O( (4dn/\delta)^d)$ for any $A'$ of size $s-1$.
Now we show that the proof of Theorem~\ref{thm:2} is also a similar step away,
by using instead the size-sensitive bound given in the assumption.


\paragraph{Proof of Theorem~\ref{thm:2}.} 

%%We now show that Our main result is to show that Theorem~\ref{thm:2} follows immediately and obviously from Equation~(\ref{eq:1}).
Let $A' \subseteq X$ be a random sample of size $\frac{4dn}{\delta}-1$.
Let $\P_1 = \{ S \in \P \text{ s.t. } |S \cap A'| \geq 3 \cdot 4dk/\delta \}$.
Note that $\Ex[|S \cap A'|] \leq 4dk/\delta$ as $|S| \leq k$ for all $S \in \P$.
By Markov's inequality, for any $S \in \P$, $\Pr[ S \in \P_1] = \Pr[ |S \cap A'| > 3 \cdot 4dk/\delta ] \leq 1/3$.
Thus
$$ \Ex[|\P_{|A'}|] \leq \Ex[|\P_1|] + \Ex[|(\P \setminus \P_1)_{|A'}|] \leq
\sum_{S \in \P} \Pr[ S \in \P_1 ] +   f(|A'|, 12dk/\delta) \leq \frac{|\P|}{3} + 
O\big( (\frac{4dn}{\delta})^{d_1} (\frac{12dk}{\delta})^{d-d_1} \big)$$
where the projection size of $\P \setminus \P_1$ to $A'$
is bounded by  $f(\cdot,\cdot)$. Applying
Lemma~\ref{lemma:1} finishes the proof.
\qed

\paragraph{Discussion.}

Besides a dramatically shorter proof,
%(the proof in~\cite{DEG15} is more than 15 pages),
%and using only Markov's inequality (unlike earlier work which
%used Chernoff bounds for hypergeometric series, among other tools)
% 
our proof also improves
the constants in the bounds. Furthermore, we have shown that it follows
without any modification or addition to the Chazelle-Haussler proof. 
%The first proof in~\cite{DEG15} uses a complicated iterative process, while
%the second proof of~\cite{DEG15} uses a function `$g$' which is then related
%to `$\ln g$' via the `fixed point' of the $\log$ function, some `nice' events
%and Chernoff bounds.  
The
somewhat subtle  key idea
that was missed by   earlier work~\cite{DEG15, E14} is that it is fine if
$\Ex[|\P_{|A'}|]$ is bounded in terms of $c|\P|$ for a small-enough constant
$c$, as in any case
it would be absorbed by the LHS of the equation in Lemma~\ref{lemma:1}.
This allows us to replace the complicated technical machinery developed
in earlier work (iterative processes, Chernoff bounds for hypergeometric series, complicated probabilistic computations) for over 20 pages-long proofs
by a mere Markov's inequality.
%and that Theorem~\ref{thm:2}, with a simple trick, is an immediate
%consequence of the textbook proof of Haussler and Chazelle.
%shows that all this is unnecessary.

% This allows to replace most of the heavy machinery (recursions, ) of the 15 pages-long proofs of [2] by a mere Chernoff bound.


\remove{
instead of using the shatter function bound 
to get Theorem~\ref{thm:1}, use
the assumed shatter function bound $f(\cdot, \cdot)$ to Theorem~\ref{thm:2}.



 

 (which presents Haussler's proof as simplified by Chazelle~\cite{C92}). 
The key statement that they proved is the following~(\cite{M99}, page 159):
\begin{equation}
\label{eq:1}
\end{equation}
From Equation~(\ref{eq:1}), the required bound follows trivially: by the
assumption (or the primal shatter lemma), $|\R_{|A}| = O( (4dn/\delta)^d)$
for any such $A$, and we're done.


\section{Conclusions}

In this note, 
}

\vspace{-0.2in}

\bibliographystyle{plain}
\bibliography{shallowpackinglemma}{}


\end{document}




shallowpackinglemma.bbl
\begin{thebibliography}{1}

\bibitem{C92}
Bernard Chazelle.
\newblock A note on {H}aussler's packing lemma.
\newblock 1992.

\bibitem{DEG15}
Kunal Dutta, Esther Ezra, and Arijit Ghosh.
\newblock Two proofs for shallow packings.
\newblock In {\em 31st International Symposium on Computational Geometry
  {SoCG}}, pages 96--110, 2015.

\bibitem{E14}
Esther Ezra.
\newblock A size-sensitive discrepancy bound for set systems of bounded primal
  shatter dimension.
\newblock In {\em Proc. of the Twenty-Fifth Annual {ACM-SIAM} Symposium on
  Discrete Algorithms}, pages 1378--1388, 2014.

\bibitem{H95}
David Haussler.
\newblock Sphere packing numbers for subsets of the boolean n-cube with bounded
  {V}apnik-{C}hervonenkis dimension.
\newblock 69(2):217 -- 232, 1995.

\bibitem{M99}
Jiri Matousek.
\newblock {\em Geometric discrepancy : an illustrated guide}.
\newblock Algorithms and combinatorics. Springer, Berlin, New York, 1999.

\bibitem{MR14}
Nabil~H. Mustafa and Saurabh Ray.
\newblock Near-optimal generalisations of a theorem of macbeath.
\newblock In {\em 31st International Symposium on Theoretical Aspects of
  Computer Science {STACS}}, pages 578--589, 2014.

\end{thebibliography}
