%\widehat{}
% EJC papers *must* begin with the following two lines. 
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P1.70}{25(1)}{2018}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed; 
% i.e. there must be no text protruding into the margins


% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%











%documentclass[12pt]{amsart}


\usepackage{amsmath,amssymb,amsthm,color,graphicx,cite,hyperref,tikz}
\renewcommand{\epsilon}{\varepsilon}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% defs
\newcommand{\F}{\mathcal{F}}
\newcommand{\I}{\mathcal{I}}
\newcommand{\J}{\mathcal{J}}
\newcommand{\M}{\mathcal{M}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\T}{\mathcal{T}}

\newcommand{\e}{\varepsilon}
\newcommand{\sset}[1]{\left\{#1\right\}}
\newcommand{\ceil}[1]{\lceil#1\rceil}
\newcommand{\floor}[1]{\lfloor#1\rfloor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\begin{document}


\title{\bf Piercing axis-parallel boxes}

\author{Maria Chudnovsky\thanks{Supported by NSF grant DMS-1550991 and US Army Research Office Grant W911NF-16-1-0404.}\\
\small Department of Mathematics\\[-0.8ex]
\small Princeton University\\[-0.8ex] 
\small Princeton, NJ, U.S.A.\\
\small\tt mchudnov@math.princeton.edu\\
\and
Sophie Spirkl \\
\small Department of Mathematics\\[-0.8ex]
\small Princeton University\\[-0.8ex] 
\small Princeton, NJ, U.S.A.\\
\small\tt sspirkl@math.princeton.edu\\
\and  Shira Zerbib\\
\small Department of Mathematics\\[-0.8ex]
\small University of Michigan\\[-0.8ex]
\small Ann Arbor, MI, U.S.A\\
\small\tt zerbib@umich.edu
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{May 20, 2017}{Mar 5, 2018}{Mar 29, 2018}\\
\small Mathematics Subject Classifications: 05B40, 52C17, 52C15}

\begin{document}

\maketitle


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{abstract}
Let $\F$ be a finite family of axis-parallel boxes in $\R^d$ such that $\F$ contains no $k+1$ pairwise disjoint boxes.
We prove that if $\F$ contains a subfamily $\M$ of $k$ pairwise disjoint boxes with the property that for every $F\in \F$ and $M\in \M$ with $F \cap M \neq \emptyset$, either 
$F$ contains a corner of $M$ or 
$M$ contains $2^{d-1}$ corners of $F$, then $\F$ can be pierced by $O(k)$ points. One consequence of this result is that if $d=2$ and the ratio between any of the side lengths of any box is bounded by a constant, then $\F$ can be pierced by $O(k)$ points.        
We further show that if  
for each two intersecting boxes in $\F$ a corner of one is contained in the other, then $\F$ can be pierced by at most $O(k\log\log(k))$ points, and in the special case where $\F$ contains only cubes this bound improves to $O(k)$.  
\end{abstract}

%\maketitle

\section{Introduction}
A \emph{matching} in a hypergraph $H=(V,E)$ on  vertex set $V$ and edge set $E$ is a subset of disjoint edges in $E$, and a \emph{cover} of $H$ is a subset of $V$ that intersects all edges in $E$. The \emph{matching number} $\nu(H)$ of $H$ is the maximal size of a matching in $H$, and the \emph{covering number} $\tau(H)$ of $H$ is the minimal size of a cover. The fractional relaxations of these numbers are denoted as usual by $\nu^*(H)$ and $\tau^*(H)$. By LP duality we have that $\nu^*(H)=\tau^*(H)$.  


Let $\F$ be a finite family of axis-parallel boxes in $\R^d$. We identify $\F$ with the hypergraph with vertex set $\R^d$ and 
 edge set $\F$. Thus a matching in $\F$ is a subfamily of pairwise disjoint boxes (also called an {\em independent set} in the literature) and a cover in $\F$ is a set of points in $\R^d$ intersecting every box in $\F$ (also called a {\em hitting set}).  
 
An old result due to Gallai is the following (see e.g. \cite{hajnalsuranyi}): 
\begin{theorem}[Gallai]\label{thm:gallai} 
If $\F$ is a family of intervals in $\R$ (i.e., a family of boxes in $\R$) then $\tau(\F) = \nu(\F)$.
\end{theorem} 

For a family $\F$ of axis-parallel boxes in $\R^d$ with $\nu(\F) = 1$, Helly's theorem \cite{helly} implies that $\tau(\F) = 1$. 
\begin{observation}[Helly \cite{helly}] \label{obs:pairwise} Let $\F$ be a family of axis-parallel boxes in $\R^d$ with $\nu(\F) = 1$. Then $\tau(\F) = 1$. 
\end{observation}

A \emph{rectangle} is an axis-parallel box in $\R^2$. In 1965, Wegner \cite{wegner} conjectured that in a hypergraph of axis-parallel rectangles in $\R^2$, the ratio $\tau/\nu$ is bounded by 2. G\'{y}arf\'{a}s and Lehel conjectured in \cite{gyarfaslehel} that the same ratio is bounded by a constant. The best known lower bound, $\tau = \lfloor 5 \nu/3 \rfloor$, is attained by a construction due to Fon-Der-Flaass and Kostochka in \cite{fonderflaass}. K{\'a}rolyi \cite{karolyi} proved that in families of axis-parallel boxes in $\R^d$ we have $\tau(\F) \leq \nu(\F) \left(1 + \log\left(\nu(\F)\right)\right)^{d-1}$, where $\log=\log_2$. Here is a short proof of K{\'a}rolyi's bound.

\begin{theorem}[K\'arolyi \cite{karolyi}] \label{karolyi} If $\F$ is a finite family of axis-parallel boxes in $\R^d$, then $\tau(\F) \leq \nu(\F) \left(1 + \log\left(\nu(\F)\right)\right)^{d-1}$. 
\end{theorem}
\begin{proof}
We proceed by induction on $d$ and $\nu(\F)$. Note that if $\nu(\F) \in \{0, 1\}$ then the result holds for all $d$ by Helly's theorem \cite{helly}. Now let $d, n \in \mathbb{N}$. Let $F_{d'}:\R \to \R$ be a function for which $\tau(\T) \le F_{d'}(\nu(\T))$ for every family $\T$ of axis-parallel boxes in $\R^{d'}$ with $d' < d$, or with $d=d'$ and $\nu(\T) < n$.

Let $\F$ be a family of axis-parallel boxes in $\R^d$ with $\nu(\F) = n$. For $a \in \R$, let $H_a$ be the hyperplane $\sset{x = (x_1, \dots, x_d) : x_1=a}$. Write $L_a = \sset{x = (x_1, \dots, x_d) : x_1 \leq a}$, and let $\F_a = \sset{F \in \F: F \subseteq L_a}$. Define $a^* = \min \sset{a : \nu(F_a) \geq \ceil{\nu/2}}$. The hyperplane $H_{a^*}$ gives rise to a partition $\F=\bigcup_{i=1}^3\F_i$, where $\F_1 = \sset{F \in \F : F \subseteq L_{a^*} \setminus H_{a^*}}$, $\F_2 = \sset{F \in \F: F \cap H_{a^*} \neq \emptyset}$, and $\F_3 = \F \setminus (\F_1 \cup F_2)$. It follows from the choice of $a^*$ that $\nu(\F_1) \leq \ceil{\nu(\F)/2}-1$, $\nu(\F_2) \leq \nu(\F)$, and $\nu(\F_3) \leq \floor{\nu(\F)/2}$. 

Therefore, 
\begin{align*}
F_d\left(\nu\left(\F\right)\right) &\le \tau\left(\F_1\right) + \tau\left(\F_3\right) + \tau\left(\sset{F\cap H_{a^*} : F\in \F_2}\right)\\
&\le F_d\left(\nu\left(\F_1\right)\right) + F_d\left(\nu\left(\F_3\right)\right) + F_{d-1}\left(\nu\left(\F_2\right)\right)\\
&\le F_d\left(\Big\lceil\frac{\nu\left(\F\right)}{2}\Big\rceil-1\right) + F_d\left(\Big\lfloor\frac{\nu\left(\F\right)}{2}\Big\rfloor\right) + F_{d-1}\left(\nu\left(\F\right)\right) \\
&\le 2~\frac{\nu\left(\F\right)}{2}  \left(1 + \log\left(\frac{\nu\left(\F\right)}{2}\right)\right)^{d-1} + \nu\left(\F\right)  \left(1 + \log\left(\nu\left(\F\right)\right)\right)^{d-2} \\
&\le \nu\left(\F\right) \left(1 + \log\left(\nu\left(\F\right)\right)\right)^{d-1}, 
\end{align*}
implying the result. 
\end{proof} 

Note that for $\nu(\F) = 2$, we have that $\F_1 = \emptyset$, $\nu(\F_2) = 1$ and so $\tau(\F) \leq F_{d-1}(2) + 1$. Therefore, we have the following, which was also proved in~\cite{fonderflaass}. 
\begin{observation}[Fon-der-Flaass and Kostochka \cite{fonderflaass}] \label{obs:nutwo}
Let $\F$ be a family of axis-parallel boxes in $\R^d$ with $\nu(\F) = 2$. Then $\tau(\F) \leq d+1$. 
\end{observation}

The bound from Theorem~\ref{karolyi} was improved by Akopyan~\cite{akopyan} to $\tau(\F) \leq (1.5 \log_3 2 + o(1)) \nu(\F) \left(\log_2\left(\nu(\F)\right)\right)^{d-1}$. 


A \emph{corner} of a box $F$ in $\R^d$ is a zero-dimensional face of $F$. 
We say that two boxes in $\R^d$ {\em intersect at a corner} if one of them contains a corner of the other.

A family $\F$ of connected subsets of $\R^2$ is a family of \emph{pseudo-disks}, if for every pair of distinct subsets in $\F$, their boundaries intersect in at most two points. In \cite{chanhar}, Chan and Har-Peled proved that families of pseudo-disks in $\R^2$ satisfy $\tau =O(\nu)$.   It is easy to check that if $\F$ is a family of axis-parallel rectangles in $\R^2$ in which every two intersecting rectangles intersect at a corner, then $\F$ is a family of pseudo-disks. Thus we have:

\begin{theorem}[Chan and Har-Peled \cite{chanhar}]\label{chenhar}
There exists a constant $c$ such that for every family $\F$ of axis-parallel rectangles in $\R^2$ in which every two intersecting rectangles intersect at a corner, we have that $\tau(\F)\le c\nu(\F)$. 
\end{theorem}

Here we prove a few different generalizations of this theorem. In Theorem~\ref{dloglog} we prove the bound  $\tau(\F) \leq  c\nu(\F)\log\log(\nu(\F))$ for families $\F$ of axis-parallel boxes in $\R^d$ in which every two intersecting boxes intersect at a corner, and in Theorem \ref{dloglogsquares} we prove $\tau(\F) \leq c \nu(\F)$ for families $\F$ of  axis-parallel cubes in $\R^d$, where in both cases $c$ is a constant depending only on the dimension $d$. We further prove in Theorem~\ref{mainthm1} that in families $\F$ of axis-parallel boxes in $\R^d$ satisfying certain assumptions on their pairwise intersections, the bound on the covering number improves to $\tau(\F) \leq c \nu(\F)$. For $d=2$, these assumptions are equivalent to the assumption that there is a maximum matching $\M$ in $\F$ such that every intersection between a box in $\M$ and a box in $\F \setminus \M$ occurs at a corner. We use this result to prove our Theorem~\ref{mainthm2}, asserting that for every $r$, if $\F$ is a family of axis-parallel rectangles in $\R^2$ with the property that the ratio between the side lengths of every rectangle in $\F$ is bounded by $r$, then $\tau(\F) \leq c \nu(\F)$ for some constant $c$ depending only on $r$. 

Let us now describe our results in more detail. First, for general dimension $d$ we have the following. 

\begin{theorem}\label{dloglog}
There exists a constant $c$ depending only on $d$, such that for every family $\F$ of axis-parallel boxes in $\R^d$ in which every two intersecting boxes intersect at a corner we have $\tau(\F) \leq  c\nu(\F)\log\log(\nu(\F))$. 
\end{theorem} 

For the proof, we first prove the bound  $\tau^*(\F) \leq  2^d\nu(\F)$ on the fractional covering number of $\F$, and then use Theorem~\ref{nets} below for the bound $\tau(\F) = O(\tau^*(\F)\log\log(\tau^*(\F)))$. 

An axis-parallel box is a \emph{cube} if all its side lengths are equal. Note that if $\F$ consists of axis-parallel cubes in $\R^d$, then every intersection in $\F$ occurs at a corner. Moreover, for axis-parallel cubes we have $\tau(\F) = O(\tau^*(\F))$ by Theorem~\ref{nets}, and thus we conclude the following.

\begin{theorem}\label{dloglogsquares}
If $\F$ is a family of axis-parallel cubes in $\R^d$, then $\tau(\F) \leq  c\nu(\F)$ for some constant $c$ depending only on $d$. 
\end{theorem}

To get a constant bound on the ratio $\tau/\nu$ in families of axis-parallel boxes in $\R^d$ which are not necessarily cubes, we make a more restrictive assumption on the intersections in $\F$. 

\begin{theorem}\label{mainthm1}
Let $\F$ be a family of axis-parallel boxes in $\R^d$. Suppose that there exists a maximum matching $\M$ in $\F$ such that for every $F\in \F$ and $M\in \M$, at least one of the following holds: 
\begin{enumerate}
\item $F$ contains a corner of $M$; 
\item $F \cap M = \emptyset$;  or
\item $M$ contains $2^{d-1}$ corners of $F$. 
\end{enumerate}
Then $\tau(\F) \leq (2^d+(4+d)d) \nu(\F)$. 
\end{theorem}

For $d=2$, this theorem implies the following corollary.  
\begin{corollary}\label{cor1}
Let $\F$ be a family of axis-parallel rectangles in $\R^2$. Suppose that there exists a maximum matching $\M$ in $\F$ such that for every $F\in \F$ and $M\in \M$, if $F$ and $M$ intersect then they intersect at a corner. 
Then $\tau(\F) \leq 16\nu(\F)$.
\end{corollary}

Note that Corollary \ref{cor1} is slightly stronger than Theorem \ref{chenhar}. Here we only need that the intersections with rectangles in some fixed maximum matching $\M$ occur at corners, but we do not restrict the intersections of two rectangles $F,F' \notin \M$.  

Given a constant $r>0$, we say that a family $\F$ of axis-parallel boxes in $\R^d$ has an \emph{$r$-bounded aspect ratio} if every box $F\in \F$ has $l_i(F)/l_j(F) \le r$ for all $i, j \in \sset{1,\dots, d}$, where $l_i(F)$ is the length of the orthogonal projection of $F$ onto the $i$th coordinate. 
 
For families of rectangles with bounded aspect ratio we prove the following. 

\begin{theorem}\label{mainthm2}
Let $\F$ be a family of axis-parallel rectangles in $\R^2$ that has an $r$-bounded aspect ratio. Then $\tau(\F) \leq (14+2r^2)\nu(\F)$.
\end{theorem}

A result similar to Theorem \ref{mainthm2} was announced in \cite{ahlkar}, but to the best of our knowledge the proof was not published. 

An application of Theorem \ref{mainthm2} is 
the existence of weak $\e$-nets of size $O \left(\frac{1}{\e} \right)$ for axis-parallel rectangles in $\R^2$ with bounded aspect ratio. More precisely, let $P$ be a set of $n$ points in $\R^d$ and let $\F$ be a family of sets in $\R^d$, each containing at least $\e n$ points of $P$.  
A \emph{weak $\e$-net} for $\F$ is a cover of $\F$, and a \emph{strong $\e$-net} for $\F$ is a cover of $\F$ with points of $P$. The existence of weak $\e$-nets of size $O \left(\frac{1}{\e} \right)$ for pseudo-disks in $\R^2$ was proved by Pyrga and Ray in \cite{pygra}. Aronov, Ezra and Sharir in \cite{aronovezrasharir} showed the existence of strong $\e$-nets of size $O \left( \frac{1}{\e} \log \log \frac{1}{\e} \right)$ for axis-parallel boxes in $\R^2$ and $\R^3$, and the existence of weak $\e$-nets of size $O \left( \frac{1}{\e} \log \log \frac{1}{\e} \right)$ for all $d$ was then proved by Ezra in \cite{ezra}. Ezra also showed that for axis-parallel cubes in $\R^d$ there exists an $\e$-net of size $O \left(\frac{1}{\e} \right)$. These results imply the following.

\begin{theorem}[Aronov, Ezra and Sharir \cite{aronovezrasharir}; Ezra \cite{ezra}]\label{nets}
If $\F$ is a family of axis-parallel boxes in $\R^d$ then $\tau(\F) \leq  c\tau^*(\F)\log\log(\tau^*(\F))$ for some constant $c$ depending only on $d$. If $\F$ consists of cubes, then this bound improves to $\tau(\F) \leq  c\tau^*(\F)$. 
\end{theorem}

An example where the smallest strong $\e$-net for axis-parallel rectangles in $\R^2$ is of size $\Omega \left(\frac{1}{\e} \log \log \frac{1}{\e} \right)$ was constructed by Pach and Tardos in \cite{pachtardos}. The question of whether weak $\e$-nets of size $O( \frac{1}{\e})$ for axis-parallel rectangles in $\R^2$ exist was raised both in \cite{aronovezrasharir} and in  \cite{pachtardos}. 

Theorem \ref{mainthm2} implies a positive answer for the family of axis-parallel rectangles in $\R^2$ satisfying the $r$-bounded aspect ratio property: 

\begin{corollary}\label{cor:aspect}
For every fixed constant $r$, there exists a weak $\e$-net of size $O(\frac{1}{\e})$ for the family $\F$ of axis-parallel rectangles in $\R^2$ with aspect ratio bounded by $r$. 
\end{corollary}
\begin{proof}
Given a set $P$ of $n$ points, there cannot be $\frac{1}{\e} + 1$ pairwise disjoint rectangles in $\F$, each containing at least $\e n$ points of $P$. Therefore $\nu(\F) \le \frac{1}{\e}$. Theorem~\ref{mainthm2} implies that there is a cover of $\F$ of size $O(\frac{1}{\e})$. 
\end{proof}

This paper is organized as follows. In Section 2 we prove Theorem \ref{dloglog}. Section 3 contains definitions and tools. Theorem \ref{mainthm1} is then proved in Section 4 and Theorem \ref{mainthm2} is proved in Section 5.

\section{Proofs of Theorems~\ref{dloglog} and \ref{dloglogsquares}}

Let $\F$ be a finite family of axis-parallel boxes in $\R^d$, such that every intersection in $\F$ occurs at a corner. By performing small perturbations on the boxes, we may assume that no two corners of boxes of $\F$ coincide.

\begin{proposition}
We have $\tau^*(\F) \le 2^d\nu(\F)$.  
\end{proposition}
\begin{proof}
We let $\nu(\F) = k$. Since an optimal fractional matching is an optimum solution to a linear program with integer coefficients, and by \cite[Theorem 10.1]{schrijver}, there exists an optimum fractional matching $g:\F \to \mathbb{Q}^+$ for $\F$. By choosing a common denominator $r$, we may assume that $g(F)=\frac{k_F}{r}$ for some $k_F \in \mathbb{N}$ for all $F \in \F$. We now let $\F'$ be the family of boxes that contains $k_F$ copies of each box $F \in \F$. Let $n$ be the number of boxes in $\F'$. It follows that $\tau^*(\F) = \nu^*(\F) = \frac{n}{r}$, and thus our aim is to show that $\frac{n}{r} \le 2^dk$. 

For $x \in \R^d$, we let $\F_x$ be the set of $F \in \F$ containing $x$. Since $g$ is a fractional matching, it follows that $\sum_{F \in \F_x} g(F) \leq 1$. Thus, the number of boxes in $\F'$ that intersect $x$ is at most $\sum_{F \in \F_x} k_F \leq r$. 

Since a matching of $\F'$ cannot contain two copies of the same box in $\F$, it follows that $\nu(\F') \leq \nu(\F)$. Since $\nu(\F')\leq k$, it follows from Tur\'{a}n's theorem that there are at least $n(n - k)/(2k)$ unordered intersecting pairs of boxes $\F'$. Each such unordered pair contributes at least two pairs of the form $(x,F)$, where $x$ is
a corner of a box $F'\in \F'$, $F$ is box in $\F'$ different from $F'$, and $x$ pierces $F$. Therefore, since there are altogether $2^dn$ corners of boxes in $\F'$, there must exist a corner $x$   
of a box $F\in \F'$ that pierces at least $(n - k)/2^dk$ boxes in $\F'$, all different from $F$. Together with $F$, $x$ intersects at least $n/2^dk$ boxes of $\F'$, implying that $n/2^dk \le r$. Thus $\frac{n}{r} \le 2^dk$, as desired.  
\end{proof}

Combining this bound with Theorem \ref{nets}, we obtain the proofs of Theorems \ref{dloglog} and \ref{dloglogsquares}.

\section{Definitions and tools}
Let $R$ be an axis-parallel box in $\R^d$ with $R = [x_1, y_1] \times \dots \times [x_d, y_d]$. For $i \in \sset{1, \dots, d}$, let $p_i(R) = [x_i, y_i]$ denote the  orthogonal projection of $R$ onto the $i$-th coordinate. Two intervals $[a,b], [c,d] \subseteq \R$, are \emph{incomparable} if $[a,b] \not\subseteq [c,d]$ and $[c,d] \not\subseteq [a,b]$. We say that $[a, b] \prec [c, d]$ if $b < c$. For two axis-parallel boxes $Q$ and $R$ we say that $Q \prec_i R$ if $p_i(Q) \prec p_i(R)$. 

\begin{observation} \label{obs:disjoint} Let $Q, R$ be disjoint axis-parallel boxes in $\R^d$. Then there exists $i \in \sset{1, \dots, d}$ such that $Q \prec_i R$ or $R \prec_i Q$. 
\end{observation}

\begin{lemma} \label{lem:contains} Let $Q, R$ be axis-parallel boxes in $\R^d$ such that $Q$ contains a corner of $R$ but $R$ does not contain a corner of $Q$. Then, for all $i \in \sset{1, \dots, d}$, either $p_i(R)$ and $p_i(Q)$ are incomparable, or $p_i(R) \subseteq p_i(Q)$, and there exists  $i \in \sset{1, \dots, d}$ such that $p_i(R) \subsetneq p_i(Q)$. 

Moreover, if $R \not\subseteq Q$, then there exists  $j \in \sset{1, \dots, d} \setminus \sset{i}$ such that $p_i(R)$ and $p_i(Q)$ are incomparable. 
\end{lemma}
\begin{proof}
Let $x = (x_1, \dots, x_d)$ be a corner of $R$ contained in $Q$. By symmetry, we may assume that $x_i = \max(p_i(R))$ for all $i \in \sset{1, \dots, d}$. Since $x_i \in p_i(Q)$ for all $i \in \sset{1, \dots, d}$, it follows that $\max(p_i(Q)) \geq \max(p_i(R))$ for all $i \in \sset{1, \dots, d}$. If $\min(p_i(Q)) \leq \min(p_i(R))$, then $p_i(R) \subseteq p_i(Q)$; otherwise, $p_i(Q)$ and $p_i(R)$ are incomparable. If $p_i(Q)$ and $p_i(R)$ are incomparable for all $i \in \sset{1, \dots, d}$, then $y = (y_1, \dots, y_d)$ with $y_i = \min(p_i(Q))$ is a corner of $Q$ and since $\min(p_i(Q)) > \min(p_i(R))$, it follows that $y \in R$, a contradiction. It follows that there exists an $i \in \sset{1, \dots, d}$ such that $p_i(R) \subsetneq p_i(Q)$. 

If $p_i(R) \subsetneq p_i(Q)$ for all $i \in \sset{1, \dots, d}$, then $R \subseteq Q$; this implies the result.
\end{proof}

\begin{observation} \label{lem:contains2} Let $\F$ be a family of axis-parallel boxes in $\R^d$. Let $\F'$ arise from $\F$ by removing every box in $\F$ that contains another box in $\F$. Then $\nu(\F) = \nu(\F')$ and $\tau(\F) = \tau(\F')$. 
\end{observation}
\begin{proof}
Since $\F' \subseteq \F$, it follows that $\nu(\F') \leq \nu(\F)$ and $\tau(\F') \leq \tau(\F)$. Let $\M$ be a matching in $\F$ of size $\nu(\F)$. Let $\M'$ arise from $\M$ by replacing each box $R$ in $\M \setminus \F'$ with a box in $\F'$ contained in $R$. Then $\M'$ is a matching in $\F'$, and so $\nu(\F') = \nu(\F)$. Moreover, let $P$  be a cover of $\F'$. Since every box in $\F$ contains a box in $F'$ (possibly itself) which, in turn, contains a point in $P$, we deduce that $P$ is a cover of $\F$. It follows that $\tau(\F') = \tau(\F)$. 
\end{proof}

A family $\F$ of axis-parallel boxes is \emph{clean} if no box in $\F$ contains another box in $\F$. By Observation~\ref{lem:contains2}, we may restrict ourselves to clean families of boxes. 

\section{Proof of Theorem \ref{mainthm1}}

Throughout this section, let $\F$ be a clean family of axis-parallel boxes in $\R^d$, and let $\M$ be a matching of maximum size in $\F$. We let $\F(\M)$ denote the subfamily of $\F$ consisting of those boxes $R$ in $\F$ for which for every $M \in \M$, either $M$ is disjoint from $R$ or $M$ contains at least $2^{d-1}$ corners of $R$. Our goal is to bound $\tau(\F(\M))$.

\begin{lemma} \label{lem:intersect} Let $R \in \F(\M)$. Then $R$ intersects at least one and at most two boxes in $\M$. If $R$ intersects two boxes $M_1, M_2 \in \M$, then there exists $j \in \sset{1,\dots, d}$ such that $M_1 \prec_j M_2$ or $M_2 \prec_j M_1$, and for all $i \in \sset{1, \dots, d} \setminus \sset{j}$, we have that $p_i(R) \subseteq p_i(M_1)$ and $p_i(R) \subseteq p_i(M_2)$.
\end{lemma}
\begin{proof}
If $R$ is disjoint from every box in $\M$, then $\M \cup \sset{R}$ is a larger matching, a contradiction. So $R$ intersects at least one box in $\M$. Let $M_1$ be in $\M$ such that $R \cap M_1 \neq \emptyset$. We claim that there exists $j \in \sset{1, \dots, d}$ such that $M_1$ contains precisely the set of corners of $R$ with the same $j$th coordinate. 

By Lemma~\ref{lem:contains}, there exists $j \in \sset{1,\dots,d}$ such that $p_j(R) = [a,b]$ and $p_j(M_1)$ are incomparable. By symmetry, we may assume that $a \in p_j(M_1)$, $b \not\in p_j(M_1)$. This proves that $M_1$ contains all $2^{d-1}$ corners of $R$ with $a$ as their $j$th coordinate, and our claim follows.

Consequently, $p_i(R) \subseteq p_i(M_1)$ for all $i \in \sset{1, \dots, d} \setminus \sset{j}$. Since $R$ has exactly $2^d$ corners, and members of $\M$ are disjoint, it follows that there exist at most two boxes in $\M$ that intersect $R$. If $M_1$ is the only one such box, then the result follows. Let $M_2 \in \M \setminus \sset{M_1}$ such that $R \cap M_1 \neq \emptyset$. By our claim, it follows that $M_2$ contains $2^{d-1}$ corners of $R$; and since $M_1$ is disjoint from $M_2$, it follows that $M_2$ contains precisely those corners of $R$ with $j$th coordinate equal to $b$. Therefore, $p_i(R) \subseteq p_i(M_2)$ for all $i \in \sset{1, \dots, d} \setminus \sset{j}$.  We conclude that $p_i(M_2)$ is not disjoint from $p_i(M_1)$ for all $i \in \sset{1, \dots, d} \setminus \sset{j}$, and  since $M_1, M_2$ are disjoint, it follows from Observation~\ref{obs:disjoint} that either $M_1 \prec_j M_2$ or $M_2 \prec_j M_1$. 
\end{proof}

For $i \in \sset{1, \dots, d}$, we define a directed graph $G_i$ as follows. We let $V(G_i) = \M$, and for $M_1, M_2 \in \M$ we let $M_1M_2 \in E(G_i)$ if and only if $M_1 \prec_i M_2$ and there exists $R \in \F(\M)$ such that $R \cap M_1 \neq \emptyset$ and $R \cap M_2 \neq \emptyset$. In this case, we say that $R$ \emph{witnesses} the edge $M_1M_2$. For $i = \sset{1, \dots, d}$, we say that $R$ is \emph{$i$-pendant} at $M_1 \in \M$ if $M_1$ is the only box of $\M$ intersecting $R$ and $p_i(R)$ and $p_i(M_1)$ are incomparable. Note that by Lemma~\ref{lem:intersect}, every box $R$ in $\F(\M)$ satisfies exactly one of the following:  
$R$ witnesses an edge in exactly one of the graphs $G_i$, $i \in \sset{1,\dots,d}$; or
 $R$ is $i$-pendant for exactly one $i \in \sset{1,\dots, d}$.


\begin{lemma} \label{lem:edges} Let $i \in \sset{1,\dots,d}$. Let $Q, R \in \F(\M)$ be such that $Q$ witnesses an edge $M_1M_2$ in $G_i$, and $R$ witnesses an edge $M_3M_4$ in $G_i$. If $Q$ and $R$ intersect, then either $M_1 = M_4$, or $M_2 = M_3$, or $M_1M_2 = M_3M_4$. 
\end{lemma}
\begin{proof} By symmetry, we may assume that $i=1$. Let $p_1(M_1) = [x_1,y_1]$ and $p_1(M_2) = [x_2,y_2]$. It follows that $p_1(Q) \subseteq [x_1,y_2]$. Let $a = (a_1, a_2, \dots, a_d) \in Q \cap R$. It follows that $a_j \in p_j(Q) \subseteq p_j(M_1) \cap p_j(M_2)$ and $a_j \in p_j(R) \subseteq p_j(M_3) \cap p_j(M_4)$ for all $j \in \sset{2, \dots, d}$. 


\begin{figure}[!t]
  \centering{
    \resizebox{\linewidth}{!}{
      \begin{tikzpicture}
        \draw [draw=black, ->, very thick] (-1,-2) -- (-1,8);
        \draw [draw=black, ->, very thick] (-2,-1) -- (8,-1);
        \draw [draw=black, very thick] (0,-1.25) --  node[below=10] {$x_1$}  (0,-0.75);
        \draw [draw=black, very thick] (2,-1.25) -- node[below=10] {$y_1$} (2,-0.75);
        \draw [draw=black, very thick] (5,-1.25) -- node[below=10] {$x_2$} (5,-0.75);
        \draw [draw=black, very thick] (7,-1.25) -- node[below=10] {$y_2$} (7,-0.75);
        \node [draw=none, fill=none] at (1,1){$M_1$};
        \node [draw=none, fill=none] at (3.5,3){$Q$};
        \node [draw=none, fill=none] at (6,5){$M_2$};
        \node [circle, inner sep=2, draw=none, fill=red, label=above:$a$] at (4.5,2.5){};
        \draw [draw=red, very thick] (4.5,2.5) -- (2,2.5);
        \node [circle, inner sep=2, draw=none, fill=red, label=below:$a$] at (5.5,3.5){};
        \draw [draw=red, very thick] (5.5,3.5) -- (2,3.5);
       	\draw [draw=black] (0,0) rectangle (2,5);
      	\draw [draw=black] (5,1) rectangle (7,6);
      	\draw [draw=black] (1,2) rectangle (6,4);
      \end{tikzpicture}
    }
    \caption{Proof of Lemma~\ref{lem:edges} for $d = 2$; two possible locations for $a$ are shown.} 
    %Since $a \in Q \cap R$, and $M_1 \not\in \sset{M_3,M_4}$, it follows that $M_3$ intersects the red line. Since $M_3 \neq M_1$ and $M_3$ intersects $Q$, it follows that $M_3 = M_2$.}
    \label{fig:edges}\label{figure11}%
  }
\end{figure}

If $M_1 \in \sset{M_3, M_4}$ and $M_2 \in \sset{M_3, M_4}$, then $M_1M_2 = M_3M_4$, and the result follows. Therefore, we may assume that this does not happen. By symmetry, we may assume that $M_1$ is distinct from $M_3$ and $M_4$. (If $M_2$ is distinct from $M_3$ and $M_4$, and $M_1$ is not, then we reflect the family of boxes along the origin; this switches the roles of $M_1$ and $M_2$, and of $M_3$ and $M_4$.)

It follows that $a \not\in M_1$, for otherwise $R$ intersects three distinct members of $\M$, contrary to Lemma~\ref{lem:intersect}. Since $R$ is disjoint from $M_1$, it follows that either $M_1 \prec_1 R$ or $R \prec_1 M_1$. But $p_1(Q) \subseteq [x_1,y_2]$, and since $Q \cap R \neq \emptyset$, it follows that $M_1 \prec_1 R$ (see Figure~\ref{figure11}).

Since $M_3 \neq M_1$ and $p_j(M_3) \cap p_j(M_1) \ni a_j$ for all $j \in \sset{2, \dots, d}$, it follows that either $M_1 \prec_1 M_3$ or $M_1 \prec_1 M_3$. Since $M_1 \prec_1 R$ and $R \cap M_3 \neq \emptyset$, it follows that $M_1 \prec_1 M_3$. 

Suppose that $a \in M_3$. Then $Q \cap M_3 \neq \emptyset$, and since $M_1 \prec_1 M_3$, we have that $M_3 = M_2$ as desired. 

Therefore, we may assume that $a \not\in M_3$, and thus $p_1(M_1) \prec p_1(M_3) \prec [a_1,a_1]$. Since $[y_1, a_1] \subseteq p_1(Q)$, it follows that $p_1(M_3) \cap p_1(Q) \neq \emptyset$. But $p_j(M_3) \cap p_j(Q) \ni a_j$ for all $j \in \sset{2, \dots, d}$, and hence $Q \cap M_3 \neq \emptyset$. But then $M_3 \in \sset{M_1, M_2}$, and thus $M_3 = M_2$. This concludes the proof. 
\end{proof}

The following is a well-known fact about directed graphs; we include a proof for completeness. 
\begin{lemma} \label{lem:digraph} Let $G$ be a directed graph. Then there exists an edge set $E \subseteq E(G)$ with $|E| \geq |E(G)|/4$ such that for every vertex $v \in V(G)$, either $E$ contains no incoming edge at $v$, or $E$ contains no outgoing edge at $v$. 
\end{lemma}
\begin{proof}
For $A, B \subseteq V(G)$, let $E(A, B)$ denote the set of edges of $G$ with head in $A$ and tail in $B$. 

Let $X_0 = Y_0 = \emptyset$, $V(G) = \sset{v_1, \dots, v_n}$. For $i=1, \dots, n$ we will construct $X_i, Y_i$ such that $X_i \cup Y_i = \sset{v_1, \dots, v_i}$, $X_i \cap Y_i = \emptyset$ and $|E(X_i, Y_i)| + |E(Y_i, X_i)| \geq |E(G|(X_i \cup Y_i))|/2$, where $G|(X_i \cup Y_i)$ denotes the induced subgraph of $G$ on vertex set $X_i \cup Y_i$. This holds for $X_0, Y_0$. Suppose that we have constructed $X_{i-1}, Y_{i-1}$ for some $i \in \sset{1, \dots, n}$. If $|E(X_{i-1}, \sset{v_i})| + |E(\sset{v_i}, X_{i-1})| \geq |E(Y_{i-1}, \sset{v_i})| + |E(\sset{v_i}, Y_{i-1})|$, we let $X_i = X_{i-1}, Y_i = Y_{i-1} \cup \sset{v_i}$; otherwise, let $X_i = X_{i-1} \cup \sset{v_i}, Y_i = Y_{i-1}$. It follows that $X_i, Y_i$ still have the desired properties. Thus, $|E(X_n, Y_n)| + |E(Y_n, X_n)| \geq |E(G)|/2$. By symmetry, we may assume that $|E(X_n, Y_n)| \geq |E(G)|/4$. But then $E(X_n, Y_n)$ is the desired set $E$; it contains only incoming edges at vertices in $X_n$, and only outgoing edges at vertices in $Y_n$. This concludes the proof. 
\end{proof}

\begin{theorem}\label{thm:edges} For $i \in \sset{1,\dots, d}$, $|E(G_i)| \leq 4 \nu(\F)$. 
\end{theorem}
\begin{proof}
Let $E \subseteq E(G_i)$ as in Lemma~\ref{lem:digraph}. For each edge in $E$, we pick one box witnessing this edge; let $\F'$ denote the family of these boxes. We claim that $\F'$ is a matching. Indeed, suppose not, and let $Q, R \in \F'$ be distinct and intersecting. Let $Q$ witness $M_1M_2$ and $R$ witness $M_3M_4$. By Lemma~\ref{lem:edges}, it follows that either $M_1M_2 = M_3M_4$ (impossible since we picked exactly one witness per edge) or $M_1 = M_4$ (impossible because $E$ does not contain both an incoming and an outgoing edge at $M_1 = M_4$) or  $M_2 = M_3$ (impossible because $E$ does not contain both an incoming and an outgoing edge at $M_2 = M_3$). This is a contradiction, and our claim follows. Now we have $\nu(\F) \geq |\F'| = |E| \geq |E(G_i)|/4$, which implies the result. 
\end{proof}

A matching $\M$ of a clean family $\F$ of boxes is \emph{extremal} if for every $M \in \M$ and $R \in \F \setminus \M$, either $(\M \setminus \sset{M}) \cup \sset{R}$ is not a matching or there exists an $i \in \sset{1, \dots, d}$ such that $\max(p_i(R)) \geq \max (p_i(M))$. Every family $\F$ of axis parallel boxes has an extremal maximum matching. For example, the maximum matching $\M$ minimizing $\sum_{M \in \M} \sum_{i=1}^d \max(p_i(M))$ is extremal. 

\begin{theorem} \label{thm:cover} For $i \in \sset{1,\dots, d}$, let $\F_i$ denote the set of boxes in $\F(\M)$ that either are $i$-pendant or witness an edge in $G_i$. Then $\tau(\F_i) \leq (4+d)\nu(\F)$. If $\M$ is extremal, then  $\tau(\F_i) \leq (3+d)\nu(\F)$.
\end{theorem}
\begin{proof}
By symmetry, it is enough to prove the theorem for $i=1$. For $M \in \M$, let $\F_M$ denote the set of boxes in $\F_1$ that either are 1-pendant at $M$, or witness an edge $MM'$ of $G_1$. It follows that $\bigcup_{M \in \M} \F_M = \F_1$. For $M \in \M$, let $d^+(M)$ denote the out-degree of $M$ in $G_1$. We will prove that $\tau(\F_M) \leq d^+(M) + d$ for all $M \in \M$. 

We fix a box $M \in \M$. Let $\mathcal{A}$ denote the set of boxes that are $1$-pendant at $M$. Suppose that $\mathcal{A}$ contains two disjoint boxes $M_1, M_2$. Then $(\M \setminus \sset{M}) \cup \sset{M_1, M_2}$ is a larger matching than $\M$, a contradiction. So every two boxes in $\mathcal{A}$ pairwise intersect. By Observation~\ref{obs:pairwise}, it follows that $\tau(\mathcal{A}) = 1$. 

Let $\mathcal{B} = \F_M \setminus \mathcal{A}$, i.e.\ $\mathcal{B}$ is the set of boxes in $\F_1$ that witness an outgoing edge $MM'$ at $M$. For every edge $MM' \in E(G_1)$, we let $\mathcal{B}(M')$ denote the set of boxes in $\F_1$ that witness the edge $MM'$. 

Suppose that there is an edge $MM' \in E(G_1)$ such that the set $\mathcal{B}(M')$ satisfies $\nu(\mathcal{B}(M')) \geq 3$. Then $\M$ is not a maximum matching, since removing $M$ and $M'$ from $\M$ and adding $\nu(\mathcal{B}(M'))$ disjoint rectangles in $\mathcal{B}(M')$ yields a larger matching.  Moreover, for distinct $M', M'' \in \M$, every box in $\mathcal{B}(M')$ is disjoint from every box in $\mathcal{B}(M'')$ by Lemma~\ref{lem:edges}. Thus, if there exist $M', M''$ such that $\nu(\mathcal{B}(M')) = \nu(\mathcal{B}(M'')) = 2$ and $M' \neq M''$, then removing $M, M'$ and $M''$ and adding two disjoint rectangles from each of $\mathcal{B}(M')$ and $\mathcal{B}(M'')$ yields a bigger matching, a contradiction. 

\begin{figure}[!t]
  \centering{
    \resizebox{\linewidth}{!}{
      \begin{tikzpicture}
        \draw [draw=black, ->, very thick] (-1,-2) -- (-1,8);
        \draw [draw=black, ->, very thick] (-2,-1) -- (8,-1);
        \draw [draw=black, very thick] (1,-1.25) --  node[below=10] {$a$}  (1,-0.75);
        \draw [draw=black, very thick] (3,-1.25) -- node[below=10] {$b$} (3,-0.75);
        \node [draw=none, fill=none] at (2,0.5){$M$};
        \node [draw=none, fill=none] at (7,5){$M'_1$};
        \node [draw=none, fill=none] at (5.625,5){$M'_2$};
        \node [draw=none, fill=none] at (6,1){$M'_3$};
       	\draw [draw=black, very thick] (1,0) rectangle (3,7.5);
      	\draw [draw=black, very thick] (6.5,7.5) rectangle (7.5,2.5);
      	\draw [draw=black, very thick] (5,6) rectangle (6,4);
      	\draw [draw=black, very thick] (5,0) rectangle (7,2);
        
      	\draw [dash pattern={on 8pt off 2pt}, draw=red, thick] (0,7) rectangle (2,3);
      	\draw [dash pattern={on 8pt off 2pt}, draw=red, thick] (-0.5,4) rectangle (2.5,1);
      	\draw [dash pattern={on 8pt off 2pt}, draw=red, thick] (3.25,6) rectangle (1.5,1.75);
      	\draw [dash pattern={on 8pt off 2pt}, draw=blue, thick] (2.5,7.25) rectangle (7,6.25);
      	\draw [dash pattern={on 8pt off 2pt}, draw=blue, thick] (2.25,2.75) rectangle (7,3.75);
      	\draw [dash pattern={on 8pt off 2pt}, draw=green, thick] (2.5,5.5) rectangle (5.25,4.5);
      	\draw [dash pattern={on 8pt off 2pt}, draw=gray, thick] (2.75,0.5) rectangle (6.5,1.5);
        
        \node [draw=none, fill=none] at (2,2.25){$\mathcal{A}$};
        \node [draw=none, fill=none] at (0.5,6){$\mathcal{A}$};
        \node [draw=none, fill=none] at (0.25,1.5){$\mathcal{A}$};
        \node [draw=none, fill=none] at (5,3.25){$\mathcal{B}(M_1')$};
        \node [draw=none, fill=none] at (5,6.75){$\mathcal{B}(M_1')$};
        \node [draw=none, fill=none] at (4,5){$\mathcal{B}(M_2')$};
        \node [draw=none, fill=none] at (4.,1){$\mathcal{B}(M_3')$};
        
        
        \node [circle, inner sep=2, draw=none, fill=black] at (1.75,3.5){};
        \node [circle, inner sep=2, draw=none, fill=black] at (3,6.75){};
        \node [circle, inner sep=2, draw=none, fill=black] at (3,3.25){};
        \node [circle, inner sep=2, draw=none, fill=black] at (2.75,5){};
        \node [circle, inner sep=2, draw=none, fill=black] at (5.25,1){};
        
      \end{tikzpicture}
    }
    \caption{Proof that $\tau(\mathcal{F}_M) \leq d^+(M) = d$ for $d = 2$; here $d^+(M) = 3$. The red boxes in $\mathcal{A}$ satisfy $\tau(\mathcal{A})=\nu(\mathcal{A})=1$, since $M$ is the only box in $\mathcal{M}$ they intersect. There is only one $M'$, namely $M' = M_1'$, such that $\nu(\mathcal{B}(M')) > 1$; since all those boxes intersect the line $x=b$, $\tau(\mathcal{B}(M')) \leq d = 2$. For all of the $d^+(M) -1$ boxes $M'$ such that $M' \neq M_1'$, $\tau(\mathcal{B}(M')) = \nu(\mathcal{B}(M')) = 1$. So $\tau(\mathcal{F}_M) \leq 5$, as shown.}\label{figure22}
    \label{fig:cover}%
  }
\end{figure}

Let $p_1(M) = [a,b]$. Two boxes in $\mathcal{B}(M')$ intersect if and only if their intersections with the hyperplane $H = \sset{(x_1, \dots, x_d) : x_1 = b}$ intersect. If $\nu(\mathcal{B}(M')) = 1$, then $\tau(\mathcal{B}(M')) = 1$ by Observation~\ref{obs:pairwise}. If $\nu(\mathcal{B}(M')) = 2$, then $\nu(\sset{F \cap H : F \in \mathcal{B}(M')}) = 2$ and so $$\tau(\mathcal{B}(M')) = \tau(\sset{F \cap H : F \in \mathcal{B}(M')}) \leq d$$ by Observation~\ref{obs:nutwo}. 

Therefore, $$\tau(\mathcal{B}) \leq \sum_{M': MM' \in E(G_1)} \tau(\mathcal{B}(M')) \leq d^+(M) - 1 + d,$$ and since $\tau(\mathcal{A}) \leq 1$, it follows that $\tau(\F_M) \leq d^+(M) + d$ as claimed (see Figure \ref{figure22}).  

Summing over all rectangles in $\M$, we obtain
\begin{align*}
\tau(\F_i) &\leq \sum_{M \in \M} \tau(\F_M) \leq \sum_{M \in \M} (d^+(M) + d) \\
&= d|V(G_1)| + |E(G_1)|\leq d|\M| + 4|\M| = (4+d)\nu(\F),
\end{align*}
where we used Theorem \ref{thm:edges} for the inequality $|E(G_1)| \leq 4 |\M|$. 

If $\M$ is extremal, then every $1$-pendant box at $M$ also intersects $H$. Let $M'$ be such that $\nu(\mathcal{B}(M'))$ is maximum. It follows that $\nu(\mathcal{A} \cup \mathcal{B}(M')) \leq 2$ and thus $\tau(\mathcal{A} \cup \mathcal{B}(M')) \leq d$, implying  $\tau(\F_M) \leq d^+(M) + d -1$. 
This concludes the proof of the second part of the theorem.
\end{proof}

\begin{theorem} \label{maintechnical}  Let $\F' \subseteq \F$ be the set of boxes $R \in \F$ such that for each $M \in \M$, either $M \cap R = \emptyset$, or $M$ contains $2^{d-1}$ corners of $R$, or $R$ contains a corner of $M$. Then $\tau(\F') \leq  (2^d+(4+d)d)   \nu(\F)$. If $\M$ is extremal, then  $\tau(\F') \leq  (2^d+(3+d)d)   \nu(\F)$.
\end{theorem}
\begin{proof}
We proved in Theorem~\ref{thm:cover} that $\tau(\F_i) \leq (4+d)\nu(\F)$ for $i=1,\dots,d$. Let $\mathcal{F}'' = \F' \setminus \F(\M)$. Then $\F''$ consists of boxes $R$ such that $R$ contains a corner of some box $M \in \M$. Let $P$ be the set of all corners of boxes in $\M$. It follows that $P$ covers $\F''$, and so $\tau(\F'') \leq 2^d\nu(\F)$. Since $\F' = \F'' \cup \F_1 \cup \dots \cup \F_d$, it follows that $\tau(\F') \leq (2^d+(4+d)d)  \nu(\F)$. If $\M$ is extremal, the same argument yields that $\tau(\F') \leq (2^d+(3+d)d)  \nu(\F)$, since $\tau(\F_i) \leq (3+d)\nu(\F)$ for $i = 1\dots, d$ by Theorem~\ref{thm:cover}. 
\end{proof}

We are now ready to prove our main theorems. 
\begin{proof}[Proof of Theorem~\ref{mainthm1}] Let $\F$ be a family of axis-parallel boxes in $\R^d$, and let $\M$ be a maximum matching in $\F$ such that for every $F \in \F$ and $M \in \M$, either $F \cap M = \emptyset$, or $F$ contains a corner of $M$, or $M$ contains $2^{d-1}$ corners of $F$. It follows that $\F = \F'$ in Theorem~\ref{maintechnical}, and therefore, $\tau(\F) \leq (2^d+(4+d)d) \nu(\F)$. 
\end{proof}

\section{Proof of Theorem \ref{mainthm2}}

Let $\M$ be a maximum matching in $\F$, and let $\M$ be extremal. Observe that each rectangle $R \in \F$ satisfies one of the following:
\begin{itemize}
\item $R$ contains a corner of some $M \in \M$; 
\item some $M \in \M$ contains two corners of $R$; or
\item there exists $M \in \M$ such that $M \cap R \neq \emptyset$, and $p_i(R) \supseteq p_i(M)$ for some $i \in \sset{1,2}$.
\end{itemize}
By Theorem~\ref{maintechnical}, $14 \nu(\F)$ points suffice to cover every rectangle satisfying at least one of the first two conditions. Now, due to the $r$-bounded aspect ratio, for each $M \in 
\M$ and for each $i\in \{1,2\}$, at most $r^2$ disjoint rectangles $R\in \F$ can satisfy the third condition for $M$ and $i$. Thus the family of projections of the rectangles satisfying the third condition for $M$ and $i$ onto the $(3-i)$th coordinate have a matching number at most $r^2$. Since all these rectangles intersect the boundary of $M$ twice,  by Theorem~\ref{thm:gallai}, we need at most $r^2$ additional points to cover them for each $i \in \{1,2\}$. We conclude that $\tau(\F) \leq (14+2r^2) \nu(\F)$. 
\qed

\section*{Acknowledgments}
We are thankful to Paul Seymour for many helpful discussions. 
%%%%%%%%%%%%%%%%% the text file
%\bibliography{piercingd}{}
%\bibliographystyle{plain}

\begin{thebibliography}{10}

\bibitem{ahlkar}
Rudolf Ahlswede and Iskander Karapetyan.
\newblock Intersection graphs of rectangles and segments.
\newblock {\em Proceedings GTIT-C, LNCS}, 4123:1064--1065, 2006.

\bibitem{akopyan}
Arseny Akopyan.
\newblock On point coverings of boxes in $\mathbb{R}^d$.
\newblock \arxiv{0706.3405}, 2007.

\bibitem{aronovezrasharir}
Boris Aronov, Esther Ezra, and Micha Sharir.
\newblock Small-size $\epsilon$-nets for axis-parallel rectangles and boxes.
\newblock {\em SIAM Journal on Computing}, 39(7):3248--3282, 2010.

\bibitem{chanhar}
Timothy~M. Chan and Sariel Har-Peled.
\newblock Approximation algorithms for maximum independent set of pseudo-disks.
\newblock \emph{Discrete \& Computational Geometry}, 48(2):373--392, 2012.

\bibitem{ezra}
Esther Ezra.
\newblock A note about weak $\varepsilon$-nets for axis-parallel boxes in
  d-space.
\newblock {\em Information Processing Letters}, 110(18):835--840, 2010.

\bibitem{fonderflaass}
Dima Fon-Der-Flaass and Alexandr Kostochka.
\newblock Covering boxes by points.
\newblock {\em Discrete Mathematics}, 120(1-3):269--275, 1993.

\bibitem{gyarfaslehel}
Andr{\'a}s Gy{\'a}rf{\'a}s and Jen{\"o} Lehel.
\newblock Covering and coloring problems for relatives of intervals.
\newblock {\em Discrete Mathematics}, 55(2):167--180, 1985.

\bibitem{hajnalsuranyi}
Andr{\'a}s Hajnal and J{\'a}nos Sur{\'a}nyi.
\newblock {\"U}ber die {Aufl{\"o}sung} von {Graphen} in vollst{\"a}ndige
  {Teilgraphen}.
\newblock {\em Ann. Univ. Sci. Budapest, E{\"o}tv{\"o}s Sect. Math},
  1:113--121, 1958.

\bibitem{helly}
Eduard Helly.
\newblock {\"U}ber {M}engen konvexer {K}\"orper mit gemeinschaftlichen
  {P}unkten.
\newblock {\em Jahresbericht der Deutschen Mathematiker-Vereinigung},
  32:175--176, 1923.

\bibitem{karolyi}
Gyula K{\'a}rolyi.
\newblock On point covers of parallel rectangles.
\newblock {\em Periodica Mathematica Hungarica}, 23(2):105--107, 1991.

\bibitem{pachtardos}
J{\'a}nos Pach and G{\'a}bor Tardos.
\newblock Tight lower bounds for the size of epsilon-nets.
\newblock {\em Journal of the American Mathematical Society}, 26(3):645--658,
  2013.

\bibitem{pygra}
Evangelia Pyrga and Saurabh Ray.
\newblock New existence proofs {$\epsilon$}-nets.
\newblock In {\em Proceedings of the Twenty-Fourth Annual Symposium on
  Computational Geometry}, pages 199--207. ACM, 2008.

\bibitem{schrijver}
Alexander Schrijver.
\newblock {\em Theory of linear and integer programming}.
\newblock John Wiley \& Sons, 1998.

\bibitem{wegner}
G.~Wegner.
\newblock {\"U}ber eine kombinatorisch-geometrische {Frage} von {Hadwiger} und
  {Debrunner}.
\newblock {\em Israel Journal of Mathematics}, 3(4):187--198, 1965.

\end{thebibliography}


\end{document}




\end{document}



