# MogFace: Towards a Deeper Appreciation on Face Detection

Yang Liu 1 Fei Wang 1 Jiankang Deng 2 Zhipeng Zhou 1 Baigui Sun 1 Hao Li * 1
1Alibaba Group 2Imperial College London

###### Abstract

Benefiting from the pioneering design of generic object detectors, significant
achievements have been made in the field of face detection. Typically, the
architectures of the backbone, feature pyramid layer, and detection head
module within the face detector all assimilate the excellent experience from
general object detectors. However, several effective methods, including label
assignment and scale-level data augmentation strategy, fail to maintain
consistent superiority when applying on the face detector directly.
Concretely, the former strategy involves a vast body of hyper-parameters and
the latter one suffers from the challenge of scale distribution bias between
different detection tasks, which both limit their generalization abilities.
Furthermore, in order to provide accurate face bounding boxes for facial down-
stream tasks, the face detector imperatively requires the elimination of false
alarms. As a result, practical solutions on label assignment, scale-level data
augmentation, and reducing false alarms are necessary for advancing face
detectors. In this paper, we focus on resolving three aforementioned
challenges that exiting methods are difficult to finish off and present a
novel face detector, termed MogFace. In our Mogface, three key components,
Adaptive Online Incremental Anchor Mining Strategy, Selective Scale
Enhancement Strategy and Hierarchical Context-Aware Module, are separately
proposed to boost the performance of face detectors. Finally, to the best of
our knowledge, our MogFace is the best face detector on the Wider Face leader-
board, achieving all champions across different testing scenarios. The code is
available at https://github.com/damo-cv/MogFace.

††* Corresponding Author.
Email<EMAIL_ADDRESS>

##  1 Introduction

Face detector, predicting location coordinates of face boxes, serves as the
fundamental step for many facial downstream tasks, including face alignment
[1], face recognition [5] [28] and face attribute analysis [24]. In the past
few years, we have witnessed the quick development on the general object
detectors, deriving from the Fast-RCNN [8] and SSD [18] to Retinanet [16] and
DERT [3]. Motivated by this, state-of-the-art face detectors adopt the great
architecture designs from general object detectors, such as Feature Pyramid
Network [15] and One-stage Single-Shot framework [16].

However, label assignment and scale-level data augmentation strategy
111enriches the scale distribution of the training data to resolve scale
variance challenge., achieving great superiority on the task of generic object
detection, bring rare gains on face detectors . On the one hand , the
designation of former strategy involves a vast body of hyper-parameters (e.g.
$K$ in ATSS [34], $\alpha$ in OTA [7] ) , which limits its generalization
ability. On the other hand, as shown in Fig. 1, compared with generic object
detector, face detector confronts more severe scale variance challenge.
Uniform sampling based scale-level data augmentation strategies (e.g. multi-
scale training and random square crop [18]), serving as the main scale
enhancement methods on generic object detectors [23, 16, 34], fail to provide
effective scale information for face detector (more analysis can be seen in
the supplementary material). Furthermore, the face detector is a real-world
application that emphasizes reducing the number of false alarms urgently.
Therefore, how to distinguish false alarms away from true positive faces is an
another distinctive challenge on the task of face detection.

Based on the above analysis, we discover that label assignment strategy,
scale-level data augmentation strategy and eliminating false alarms have a
huge potential for constructing a high-performance face detector. Then we
perform a systematically quantitative and qualitative analysis on 3
aforementioned perspectives to provide some intrinsic insights.

Figure 1: Motivation illustration. (a) Online and offline information both can
be adopted as criterion to determine the boundary between positive and
negative anchors. But how to effectively and adaptively combine them remains a
huge challenge. (b) Cumulative density curve of face or object scale relative
to the fixed scale (640). In the Wider face and COCO dataset, almost 55% and
18% ground-truth scale is less than 20, demonstrating that compared to generic
object detector, a more severe scale variance challenge is occurred on the
task of face detection. (c) For the same detector, we discover the top-left
calendar is a false alarm in the left image, while the top-left calendar in
the other two images are not.

Label Assignment. Label assignment strategies adopt predefined rules to match
ground-truth (gt) or background for each anchor. As shown in the Fig. 1, the
designation of predefined rules highly depends on offline and online
information. Offline information contains Intersection-over-Union (IoU) and
Center Point Distance (CPD) between gt and anchor, which can be computed
during the process of data preparation. Online information consists of the
predicted classification scores (PCS) and the predicted location coordinates
(PLC), which can be extracted at the end of forward propagation. Traditional
label assignment strategies adopt offline information as threshold criterion
for $pos/neg$ anchors division, e.g. IoU in retinanet [16], faster-rcnn [23],
IoU and CPD in ATSS [34]. Recently, Hambox [21] further points out the
effectiveness of online information and put forwards an online high-quality
anchor mining strategy to utilize the PLC. OTA [7] formulates the assigning
procedure as an optimal transport problem, where the cost function is designed
by the weighed combination of CPD, PCS and PLC.

However, there exist two drawbacks lying behind current label assignment
strategies: 1) Online information cannot provide high-confidence matching
information as well as offline one. Thus, it will result in the emergence of
sub-optimal label assignment strategy when encouraging online rules to serve
as main metric on distinguishing positive and negative anchors like OTA and
Hambox. 2) The selection of hyper-parameter in the recent label assignment
strategies frequently goes through constant trials and errors, making it
difficult for transferring different detection tasks, e.g. from general object
detection to face detection. In this paper, we address the aforementioned
issues by proposing an adaptive online incremental anchor mining strategy
(Ali-AMS), which is based on the standard anchor matching strategy adopted in
retinanet [16] and further compensates outlier ground-truths with incremental
anchors at the end of forward propagation. In our Ali-AMS, two key components,
quality assessment based anchor mining strategy and pyramid-level consistency
principle, are proposed to mine and assign the high-quality anchor adaptively.
Concretely, the former strategy regards the PCS as the quality assessment
criterion to re-sort the anchor mined with the CPD and IoU information; then,
the latter principle guarantees that ground-truths located at the same pyramid
layer can match the same number of anchors. The motivation and more details of
our Ali-AMS can be seen in section 3.1.

Scale-level Data Augmentation.  Generic object detector frequently introduces
scale-level data augmentation strategy to resolve extreme scale variance on
the COCO dataset. However, the most authoritative face detection dataset Wider
Face [31] contains more severe scale variance than COCO [17]. As shown in Fig.
1, we display the scale distribution of ground-truths on the COCO and Wider
Face benchmark, respectively. Comparing with COCO dataset which is famous with
extreme scale variance, Wider Face has more rigorous scale distribution, where
contains almost 55% small scale faces 222the scale of ground-truth is less
than 20.

To resolve extreme scale variance challenge, there exist 3 widely-adopted data
augmentation strategies, including Multi-scale-training (MST), Random Square
Crop (RSP) and Data-anchor-sampling (DAS). Multi-scale-training strategy,
resizing each image into a random scale selected from fixed scale range,
frequently serves as the optimal solution on handling with scale variance
problem, which has demonstrated its significance in many technology reports on
the COCO detection challenge. Random Square Crop strategy, cropping the square
area from a given image randomly, is a main-stream scale-level data
augmentation strategy on the task of face detection [6], [35]. Data-anchor-
sampling strategy [26] aims to introduce more small scale faces by resizing
each image into a smaller scale.

MST and RSP are both designed from uniform sampling perspective while DAS
focuses on generating many small faces. Meanwhile, in the Wider Face training
set, almost 55% face scale is less than 20, making uniform sampling based
augmentation strategies generate a large number of small faces. As a result,
MST and RSP both have great detection ability on small faces. This raises a
worth solving problem: How to increase the detection ability on the middle and
large scale faces since the training set only contains a small proportion
large faces (10%) ? In this paper, we investigate this question by analyzing
the relationship between the performance of each pyramid layer and the number
of ground-truths it matches. Based on comprehensive quantitative and
qualitative analysis in supplementary material, we unexpected discover that it
is not the more ground-truths that is matched in a single pyramid layer, the
greater performance of this pyramid layer. As a result, this phenomenon
releases an amazing conclusion that in order to improve the representation of
certain pyramid layer, the number of ground-truths matched in this layer
should be appropriate instead of ’the more, the better’. Under the guidance of
this meaningful conclusion, we propose a simplex selective scale enhancement
strategy for detecting large scale face accurately on the basis of prior
statistical result, which controls the ground-truths distribution to improve
the deep pyramid layer representation, achieving the best detection
performance on large and middle scale faces. To the best of our knowledge, our
selective scale enhancement strategy is the first novel work to consider the
relationship between the performance of each pyramid layer and the number of
ground-truths it matches, which provides a solid knowledge on how to mine the
learning capacity of certain pyramid layer.

Eliminating False Alarms. Reducing the number of false alarms is vitally
important for the real-world face detector. The common solution is to
introduce additional training data with false alarms, which helps the detector
acquire more knowledge on the property of false alarms. However, collecting
extra training data is labor-intensive such that the solution without extra
data is deserved exploring. In this paper, we present a Hierarchical Context-
Aware Module (HCAM) to help false alarms away from ground-truths, which
explicitly encodes neighbour context information into high-confidence anchors
333high-confidence anchors contains correct predicted positive anchors and
false predicted negative anchors. The effectiveness of neighbour context
information can be seen in Fig. 1, we send the left image into the Hambox [21]
face detector and find a top-left false alarm. However, when we crop this
false alarm with expanding context area (middle image) and less expanding
context area (right image), we unexpectedly discover that the same detector
believes there is no false positives in these two images. Moreover, we utilize
Hambox face detector to find all false alarms in the Wider Face validation
dataset, almost 95% false alarms are disappeared when adopting similar
operations like above. This phenomenon demonstrates that the appropriate
neighbour context information is conducive to eliminating false alarms.

In summary, our contribution can be summarized as:

  * •

Presenting 3 worthy of in-depth research topics on the task of face detection,
including Label Assignment, Scale-level Data Augmentation and Eliminating
False Alarms.

  * •

Proposing Adaptive Online Incremental Anchor Mining Strategy, Selective Scale
Enhancement Strategy, Hierarchical Context-Aware module respectively to
construct a promising face detector, termed as MogFace.

  * •

Achieving state-of-the-art results in all popular face detection benchmarks,
including Wider Face, AFW, FDDB and Pascal Face.

##  2 Related Work

Recently, a large number of face detectors [20, 19, 9, 26, 6, 13] has been
proposed to advance face detection community. In this section, we mainly
review the related work from two following perspectives, label assignment and
scale-level data augmentation strategies.

Label Assignment. In the field of face detection, zhang et.al. [35] propose a
scale compensation anchor matching strategy to increase the matched anchors of
outer faces by reducing the IoU threshold. Liu et al. [21] discover that some
negative anchors have stronger localization ability than positive ones and
further propose an “online high-quality anchor mining strategy” by
compensating outer faces with high-quality negative anchors. In the field of
object detection, ATSS [34] automatically selects positive and negative
samples according to statistical characteristics of object. OTA [7] formulates
the label assigning procedure as an optimal transport problem, which converts
the best assignment solution into solving the optimal transport plan at
minimal transportation costs.

Scale-level Data Augmentation.  SNIP [25] introduces a Scale Normalization for
Image Pyramids (SNIP) strategy which selectively back-propagates the gradients
of object instances of different sizes as a function of the image scale. Li
et.al [14] proposes a novel Trident Network to generate scale-specific feature
maps with a uniform representational power. Data-anchor-sampling [26] augments
the training samples to increase the diversity of training data for smaller
faces. Zhang et.al [35] proposes a scale-equitable face detection framework to
handle different scales of faces. ASFD [32] introduces an automatic feature
enhance module to allow multi-scale feature fusion efficiently.

##  3 Method

In this section, we consecutively introduce three components of our MogFace,
including Adaptive Online Incremental Anchor Mining Strategy, Selective Scale
Enhancement Strategy and Hierarchical Context-Aware Module.

###  3.1 Adaptive Online Incremental Anchor Mining Strategy

Algorithm 1 describes how our Ali-AMS compensates high-quality anchors for
outer ground-truths, when given an input image. Concretely, our Ali-AMS
consists of pyramid-level consistency principle and quality assessment based
anchor mining strategy, which identifies the number of anchors matched with
each ground-truth among all pyramid layers and mines the high-quality anchors
for outer ground-truth, respectively. The first principle (line 2-3) is
described as follows: on each pyramid level, we first find the set of ground-
truths ($\mathcal{G}$) matched in this pyramid layer based on the standard
anchor matching strategy [16] and compute the maximum number ($\mathcal{T}$)
of anchors that matched in $\mathcal{G}$. For each gt ($g$) in $\mathcal{G}$,
if the number of anchors matched with $g$ is less than $\mathcal{T}$, the
number of anchors that the $g$ matches will be compensated to $T$ with
following metric. The description of second strategy is from line 8 to 12: For
each ground-truth that needs to be matched with incremental anchors, the
select process of compensated anchors contains three following steps: 1)
select $\mathcal{T}$ anchors from the view of CPD and IoU separately. 2) Sort
all 2 * $\mathcal{T}$ anchors by the predicted classification score 3)
Compensate top-$\mathcal{N}_{g}$ anchors for the outer ground-truth. Note that
the number of top-$\mathcal{N}_{g}$ is computed in the first principle
adaptively. The motivation behind our Ali-AMS is explained as follows.

Algorithm 1 Adaptive Online Incremental Anchor Mining Strategy (Ali-AMS)

0: $\mathcal{A}$ is a dict, key is ground-truth, value is the number of
anchors matched with this ground-truth with standard anchor matching strategy.

1: for pyramid layer $pi$ in $[p2,p3,p4,p5,p6,p7]$ do

2: $\mathcal{G}\leftarrow{}$ ground-truths that matched in the $pi$

3: $\mathcal{T}\leftarrow{}$ maximum number of anchors that matched in
$\mathcal{G}$ with standard anchor matching strategy.

4: for each ground-truth $g\in\mathcal{G}$ do

5: if $\mathcal{A}[g]==\mathcal{T}$ then

6: continue

7: end if

8: compute the number of compensated anchors for $g$:
$\mathcal{N}_{g}=\mathcal{T}-\mathcal{A}[g]$;

9: $cpd\leftarrow{}$ select $\mathcal{T}$ anchors whose centers are closest to
the center of ground-truth $g$ based on L2 distance;

10: $iou\leftarrow{}$ select $\mathcal{T}$ anchors whose have the highest iou
with ground-truth;

11: $conf\\_candidate\leftarrow{}$ sort the anchor in $iou$ and $cpd$
according to predicted classification scores;

12: select top-$\mathcal{N}_{g}$ confident anchors from $conf\\_condidate$ to
serve as positive anchors for $g$;

13: end for

14: end for

Adopting predicted classification score as quality assessment on the
candidates mined with CPD and IoU information. We explain this from the view
on the necessity and the role of online information separately. 1) The success
of anchor-based detector demonstrates that only utilizing offline information
(CPD or IoU) as metric to determine the boundary between $pos/neg$ anchors can
provide a great optimization direction for the detector. However, with the
number of iterations increasing, offline information can not provide the
progressive matching rules, resulting in the sub-optimal optimization
direction. Analogously, Hambox [21] points out the same conclusion that even
though adopting offline information as metric to distinguish $pos/neg$
anchros, many negative anchors have amazing regression ability. Such
inconsistent phenomenon between the learnt knowledge on detector and the
formulated knowledge on offline information (IoU) suggests that offline
information based label assignment strategy fails to satisfy the requirements
of optimization process. Therefore, combing offline and online information can
provide more accurate optimization direction, due to online information can
reflect the learnt knowledge on the detector. 2) Relying too much on the
online rule to identify $pos/neg$ anchors has an obvious drawback that it is
easily over fitting on the bias assignment strategy, especially on the early
stage of optimization process. Thus, rather than serving the online
information as dominant criterion, we regard online rule as quality assessment
tool (auxiliary role) to measure the candidates which already have mined with
CPD and IoU rules.

Figure 2: Hierarchical Context-Aware Module.

###  3.2 Selective Scale Enhancement Strategy

As discussed above, previous scale-level data augmentation strategies fail to
resolve the challenging problem: How to increase the detection ability on the
medium and large scale faces since the training set only contains a small
proportion large faces (10%) ? To resolve this, we first analyze the
relationship between the performance of each pyramid layer and the number of
ground-truths it matches in the supplementary material. To our surprise, we
discover an amazing conclusion: it is not accurate that the more ground-truths
matched in one pyramid layer, the greater performance of this pyramid layer.
Based on this instructive finding, we propose a selective scale enhancement
strategy (SSE) to maximize the learning capacity of deeper pyramid layer by
controlling the distribution of ground-truths among pyramid layers from $p2$
to $p7$ based on the prior statistical result.

To begin with, we introduce three prerequisites for our SSE strategy. (1) We
firstly define the conception of the main pyramid layer and the auxiliary
pyramid layer, which embraces the top-2 greatest detection abilities on the
large-scale faces among all pyramid layers according to the empirical results
reported in the supplementary material. As a result, p5/p6 are the
main/auxiliary pyramid layer for the SSE strategy. (2) Then we determine the
ratio of the ground-truths matched in the main and auxiliary pyramid layer.
Let $r\\_pi$ (i=2,3,4,5,6,7) represents the maximum performance ratio matched
in the pyramid layer $pi$. The maximum performance ratio refers to that this
ratio together with our proposed scale control strategy 444Details shown in
the supplementary materials achieves the best performance among all candidate
ratios, that is shown on the table 1 with bold annotation. Thus, $r\\_p5$
equals to 20% and $r\\_p6$ equals to 20%. For the main pyramid layer, we
define the ratio of the total ground-truths matched in the main pyramid layer
as $tr\\_mpl$ that equals to $r\\_p5$. Moreover, we define the ratio of the
total ground-truths matched in the auxiliary pyramid layer as $tr\\_apl$ that
equals to (1 - $tr\\_mpl$) $*$ $r\\_p6$. This assignment strategy on the scale
information of ground-truths can guarantee the learning capacity of the main
and auxiliary pyramid layer successively. (3) Finally, in the table 2, we
compute the scale range ($sr\\_pi$, i=2,3,4,5,6,7) of the faces that matched
in different pyramid layers. Note that the overlap scale range between
neighbour pyramid layers is divided uniformly for convenience.

| 20% | 40% | 60% | 80%
---|---|---|---|---
p4 (easy) | 67.0 | 75.3 | 81.3 | 84.3
p4 (med) | 75.3 | 82.6 | 84.5 | 83.6
p5 (easy) | 81.8 | 82.2 | 77.9 | 73.2
p5 (med) | 85.4 | 85.2 | 85.0 | 83.7
p6 (easy) | 86.2 | 83.1 | 84.8 | 83.3
p6 (med) | 85.2 | 80.5 | 82.2 | 81.2
Table 1: The results of scale control strategy on the Wider Face validation subsets.  |  start scale |  end scale
---|---|---
$sr\\_p2$ |  8.4 |  20.7
$sr\\_p3$ |  20.7 |  48.2
$sr\\_p4$ |  48.2 |  106.2
$sr\\_p5$ |  106.2 |  212.4
$sr\\_p6$ |  212.4 |  420.8
$sr\\_p7$ |  420.8 |  640
Table 2: The scale range of the ground-truths that matched in different
pyramid layers.

Based on 3 above prerequisites, algorithm 2 shows the pipeline of our SSE
strategy on each training image. 1) Resize image by reshaping the short side
of image into a scale selected from scale range [640, 1280]. 2) Randomly
sample a face from the resized image and compute its scale $fs$. 3) Identify
the target pyramid layer ($tpl$) . Randomly sample a floating-point number
($rn$) from 0 to 1. If the value of the $rn$ is less than $tr\\_p5$, we define
the target pyramid layer as $p5$. If $rn$ is over $r\\_p5$ and less than
$r\\_p5$ \+ $r\\_p6$, the target pyramid layer ($tpl$) equals to p6. If $rn$
is over $r\\_p5$ \+ $r\\_p6$, the target pyramid layer equals to the random
one of the pyramid layers except for $p5$ and $p6$. 4) Random select a scale
from $sr\\_tpl$ and compute the target resize ratio ($trr$) by $fs$ / this
scale. 5) Resize image with $trr$. 6) Define the resolution of the input image
as N $\times$ N. If the resolution of the resized image is over N $\times$ N,
we crop N $\times$ N area randomly as the input image and pad zero pixel if it
is less than N $\times$ N. The motivation behind our SSE strategy is as
follows.

Algorithm 2 Selective Scale Enhancement Strategy (SSE)

0: $\mathcal{I}$ is a set of all training data $tr\\_p5$ is a hyperparameter
that represents the ratio of the total ground-truths matched in the main
pyramid layer (p5). $tr\\_p6$ is a hyperparameter that represents the ratio of
the total ground-truths matched in the auxiliary pyramid layer (p6).
$sr\\_tpl$ is the scale range of the ground-truths that matched in the $tpl$.
$\mathcal{N}$ is the side of the resolution for the input image.

0: $\mathcal{S}$ is a set of training data augmented by our SSE strategy

1: for each image $i\in\mathcal{I}$ do

2: $\mathcal{R}_{i}\leftarrow{}$ Resize image by reshaping the short side of
image into a scale selected from scale range [640, 1280] randomly.

3: $\mathcal{F}_{s}\leftarrow{}$Compute the face scale that is selected from
$\mathcal{R}_{i}$ randomly.

4: $Random\\_float=Random.random(0,1)$

5: if $Random\\_float<tr\\_p5$ then

6: $tpl=p5$

7: else if $Random\\_float<=(tr\\_p5+tr\\_p6)$ then

8: $tpl=p6$

9: else

10: $tpl=random([p2,p3,p4,p7])$

11: end if

12: compute target resize ratio: $trr=random(sr\\_tpl)/\mathcal{F}_{s}$;

13: $\mathcal{R}^{trr}_{i}\leftarrow{}$ Resize $\mathcal{R}_{i}$ with the
shrink ratio $trr$;

14: if $resolution(\mathcal{R}^{trr}_{i})>(\mathcal{N},\mathcal{N})$ then

15: $\mathcal{R}^{trr}_{i}\leftarrow{}$ crop $\mathcal{N}\times\mathcal{N}$
area randomly from $\mathcal{R}^{trr}_{i}$;

16: else

17: $\mathcal{R}^{trr}_{i}\leftarrow{}$ expand $\mathcal{R}^{trr}_{i}$ into
($\mathcal{N},\mathcal{N}$) by padding zero pixel;

18: end if

19: if $\mathcal{S}$ is None then

20: $\mathcal{S}\leftarrow{}\varnothing$

21: end if

22: $\mathcal{S}=\mathcal{S}\cup\mathcal{R}^{trr}_{i}$;

23: end for

24: return $\mathcal{S}$;

Depending on the main and auxiliary pyramid layer to control the scale
distribution of ground-truths. The previous designation on controlling the
scale distribution of the ground-truths can be divided into following two
types. MST and RCS emphasize on the uniform sampling while DAS points out an
alternative view that the more small-scale data can boost the detection
ability on small faces. However, such heuristic designation can not utilize
the scale information effectively. On the one hand, in the supplementary
material, we find RSC and DAS achieve almost consistent performance on the
Wider Face hard subset although DAS brings more small faces. On the other
hand, as described in the table 1, we find it is not accurate that the more
ground-truths that is matched in one pyramid layer, the greater performance of
this pyramid layer. These two findings demonstrate that heuristically
controlling the scale distribution of ground-truths fail to satisfy the
ground-truths requirements on the related pyramid layer. Therefore, our SSE,
consecutively satisfying the requirement of main and auxiliary pyramid layer
on the ground-truths, is a better strategy than other heuristic designation.

(a) AFW

(b) PASCAL Face

(c) FDDB

Figure 3: Evaluation on common face detection benchmarks.

###  3.3 Hierarchical Context-Aware Module

As analyzed above, we find the appropriate neighbour context information is
conducive to eliminating false alarms. Motivated by this finding, we propose a
Hierarchical Context-Aware Module (HCAM) to distinguish false alarms away from
the face by encoding the neighbour context information into related high-
confidence anchors in Fig. 2. Under the rescue of neighbour context
information, false predicted negative anchors and correct predicted positive
anchors within the high-confidence anchors can be separated explicitly. The
training pipeline is as follows:

1) We firstly send a batch of images into the detector and get the
classification score of each anchor on the main classifier. Then we mask the
position of all high-confidence anchors to generate two attention feature
maps. For each attention feature map, we assign the position of high-
confidence anchors and their related neighbour information 555neighbour
information takes the target anchor point as the center and contains the
surrounding N$\times$N area, N is an integer greater than 0 as 1, otherwise is
0. The N are set 3 and 5 for generating different neighbour information.

2) We compute the two neighbour context information by dot-multiplying the
context-enhanced backbone feature maps and two attention feature maps,
respectively. This step aims to explicitly generate more abundant context
information related to the high-confidence anchors. Note that more ablative
experiments and architectures on context-enhanced modules are discussed in the
supplementary material.

3) We further encode two neighbour context information into pyramid feature
map by element-wise summation operator.

4) Finally, this combined feature map feeds into progressive classifier to
further distinguish false predicted negative anchors (false alarms) away from
correct predicted positive anchors according to Equ. 1.

$L=f_{fl}^{m}(f_{c},y)+\gamma*f_{fl}^{p}(f_{c}^{com},y_{hc})$ (1)

where $f_{fl}^{m}$ and $f_{fl}^{p}$ represent the sigmoid focal loss [16] over
two classes, that are applied on the main and progressive classifier,
respectively. $y$ is the the label of anchor which is assigned by anchor
matching strategy [23]. The weight $\gamma$ aims to balance the loss between
main and progressive classifiers (we find $\gamma$=1 has a best performance).
$fc$ and $f_{c}^{com}$ represent the output of main classifier and progressive
classifier, separately. $y_{hc}$ is dynamic discrepancy supervision label,
that is defined by following two steps: 1) In each iteration of the training
stage, we firstly mask the position of correctly predicted positive anchors
666refer to the positive anchors which have high confidence classification
score and false predicted negative anchors 777refer to the negative anchors
which have high confidence classification score according to the predicted
classification score on the main classifier at the end of forward propagation.
2) Assigning the position of correct predicted positive anchors as positive
samples, the position of false predicted negative anchors as negative samples,
the position of remaining anchors as ignore samples.

(a) Val: Easy (b) Val: Medium (c) Val: Hard (d) Test: Easy

(e) Test: Medium (f) Test: Hard

Figure 4: Precision-Recall (PR) curves on Wider Face validation and testing
subsets.

##  4 Experiment

In this section, we first elaborate the implementation details of our
baseline. Then, we conduct ablative experiments on the most authoritative face
detection benchmark, Wider Face. Finally, we test our method on all popular
face datasets, including AFW, PASCAL Face, FDDB and Wider Face.

###  4.1 Baseline Setup

Training Detail. We adopt SFD [35] architecture with Resnet50 [10] backbone as
our baseline. For anchor settings, we set 6 anchors whose scales are from the
set {16, 32, 64, 128, 256, 512}, and all anchors’ aspect ratios are set to
1:1. The losses applied on our baseline are focal loss and smooth L1 loss with
the weight ratio 1:2. For optimization details, each training iteration
contains 7 images per GPU on 4 NVIDIA Tesla V100s. Models are optimized by
synchronized SGD. The momentum and weight decay are set to 0.9 and
5$\times$10-5, respectively. For learning rate schedule, the initial learning
rate is set to 4e-3 and decreases to 4e-4 in 50000 iterations. The total
iteration is 70000.

Inference Detail. In the phase of inference, we adopt single scale test
strategy to evaluate the experiment result. Firstly, we feed the image with
original scale into the detector and then get top-5000 highest confidence
bounding boxes. Then, the Non-maximum Suppression is applied with the IoU
threshold 0.6 to get top 750 confident detection scores and related bounding
boxes.

###  4.2 Ablation Study

The Effectiveness of Ali-AMS. In the table 3, we compare our Ali-AMS with
recent proposed label assignment strategies, including HAMBox [21], OTA [7]
and ATSS [34]. Our Ali-AMS achieves the best performance among all recent
label assignment strategies on the Wider Face hard subset with outperforming
baseline, HAMBox, ATSS, OTA by 0.8%, 0.4%, 1.0%, 2.6% AP score, respectively.

Method | Easy | Medium | Hard
---|---|---|---
Baseline | 94.6 | 93.4 | 86.5
Baseline + HAMBox | 94.5 | 93.8 | 86.9
Baseline + ATSS | 94.5 | 93.2 | 86.3
Baseline + OTA | 93.3 | 91.7 | 84.7
Baseline + Ali-AMS | 94.6 | 93.6 | 87.3
Table 3: Results of Ali-AMS on the Wider Face validation subsets.

The Effectiveness of SSE. In the table 4, we compare our SSE with other scale-
level data augmentation strategies, including data-anchor-sampling, random
square crop and multi scale training strategy. Our SSE outperforms others by
1.0%, 0.7% AP on the Wider Face validation easy, medium subset respectively.
Such tremendous enhancement on detecting large-scale faces help our MogFace-E
achieve 4 champions on the Wider Face official leader-board.

Method | Easy | Medium | Hard
---|---|---|---
Baseline (w/o DAS) | 92.2 | 90.5 | 81.4
Baseline + MST | 93.3 | 91.5 | 83.6
Baseline + DAS | 94.6 | 93.4 | 86.5
Baseline + SSE | 95.6 | 94.1 | -
Table 4: Results of SSE on the Wider Face validation subsets.

The Effectiveness of HCAM. Table 5 presents the performance and the number of
false alarms (NFA) on our Hierarchical Context-Aware false alarms Module with
different N (defined in the footnote 5). The Hierarchical Context-Aware Module
achieves the best performance (87.4 % AP on the Wider Face Validation hard
subset) and contains the minimal false alarms, when N=3 and 5. Note that the
context-aware module can also only contain one neighbour context information,
e.g. N=3 or N=5.

Method | N | Easy | Medium | Hard | NFA
---|---|---|---|---|---
Baseline | - | 94.6 | 93.4 | 86.5 | 948
HCAM | 3 | 94.9 | 94.0 | 86.8 | 532
HCAM | 5 | 94.8 | 94.1 | 87.0 | 476
HCAM | 3 and 5 | 95.1 | 94.2 | 87.4 | 192
Table 5: Results of our Hierarchical Context-Aware Module on the Wider Face
validation subsets.

###  4.3 Evaluation on Common Benchmarks

In this subsection, we compare our MogFace with state-of-the-arts methods on
the common face detection benchmarks, including AFW [38], Pascal Face [30],
FDDB [12] and Wider Face [31]. We train the MogFace-E (Ali-AMS, HCAM, SSE) and
MogFace (Ali-AMS, HCAM) with some excellent modules introduced by Hambox [21]
detector on the Wider Face training dataset, including SSH head [22], Pyramid
Anchor [26] and deep head [16].

AFW Dataset. This dataset contains 205 images with 473 annotated faces. As
shown in Fig. 3(a), our Mogface significantly outperforms other methods by
1.0% AP at least.

PASCAL Face Dataset. This dataset contains 851 images with 1335 annotated
faces. Fig. 3(b) shows that our method achieves the state-of-the-art results
by outperforming the second one with $0.8\%$ AP.

FDDB Dataset. This dataset has 2,845 images with 5,171 annotated faces. Most
of them have low image resolutions and complicated scenes . Fig. 3(c) shows
that our MogFace achieves the highest (99.2%) performance.

Wider Face Dataset. We test our MogFace and MogFace-E with Multi-scale results
ensemble strategy on the Wider Face validation and test set. As shown in Fig.
4, we plot a precision-recall curve according to the official tool on the
Wider Face validation set. As for Wider Face test set, we submit the detection
bounding boxes and corresponding scores to the official server to get the
precision-recall curves that is shown in Fig. 4. Our method achieves 97.7%
(Easy), 96.9% (Medium), 93.8% (Hard) AP performance on the Wider Face
validation set and 97.0 % (Easy), 96.2% (Medium), 92.6% (Hard) AP performance
on the Wider Face test set. Comparing with other sota approaches [11, 29, 13,
27, 4, 33, 36, 2, 37, 32], our method outperforms them by 0.5% (Validation
Easy), 0.5 % (Validation Medium), 0.4 % (Validation Hard), 0.3 % (Test Easy),
0.2 % (Test Hard). Such tremendous enhancement in all scenarios demonstrates
the superiority of our MogFace.

##  5 Conclusion

In this paper, we first point out that the success experience from generic
object detection fails to provide effective solutions on label assignment,
scale-level data augmentation, and eliminating face alarms in the field of
face detection. Thereby, in order to advance the development of face
detectors, we resolve three aforementioned challenges by proposing Adaptive
Online Incremental Anchor Mining Strategy, Selective Scale Enhancement
Strategy, Hierarchical Context-Aware Module, respectively. Finally, benefiting
from prominent solutions of our MogFace, we achieve six champions on the Wider
Face dataset, which continues to this day.

## References

  * [1] Adrian Bulat and Georgios Tzimiropoulos.  How far are we from solving the 2d & 3d face alignment problem?(and a dataset of 230,000 3d facial landmarks).  In Proceedings of the IEEE International Conference on Computer Vision, pages 1021–1030, 2017.
  * [2] Zhaowei Cai, Quanfu Fan, Rogerio S Feris, and Nuno Vasconcelos.  A unified multi-scale deep convolutional neural network for fast object detection.  In European conference on computer vision, pages 354–370. Springer, 2016.
  * [3] Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko.  End-to-end object detection with transformers.  In European Conference on Computer Vision, pages 213–229. Springer, 2020.
  * [4] Cheng Chi, Shifeng Zhang, Junliang Xing, Zhen Lei, Stan Z Li, and Xudong Zou.  Selective refinement network for high performance face detection.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 8231–8238, 2019.
  * [5] J Deng, J Guo, and S Zafeiriou.  Arcface: additive angular margin loss for deep face recognition. corr abs/1801.07698 (2018), 1801.
  * [6] Jiankang Deng, Jia Guo, Yuxiang Zhou, Jinke Yu, Irene Kotsia, and Stefanos Zafeiriou.  Retinaface: Single-stage dense face localisation in the wild.  arXiv preprint arXiv:1905.00641, 2019.
  * [7] Zheng Ge, Songtao Liu, Zeming Li, Osamu Yoshie, and Jian Sun.  Ota: Optimal transport assignment for object detection.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 303–312, 2021.
  * [8] Ross Girshick.  Fast r-cnn.  In Proceedings of the IEEE international conference on computer vision, pages 1440–1448, 2015.
  * [9] Jia Guo, Jiankang Deng, Alexandros Lattas, and Stefanos Zafeiriou.  Sample and computation redistribution for efficient face detection.  arXiv preprint arXiv:2105.04714, 2021.
  * [10] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.
  * [11] Peiyun Hu and Deva Ramanan.  Finding tiny faces.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 951–959, 2017.
  * [12] Vidit Jain and Erik Learned-Miller.  Fddb: A benchmark for face detection in unconstrained settings.  2010\.
  * [13] Jian Li, Yabiao Wang, Changan Wang, Ying Tai, Jianjun Qian, Jian Yang, Chengjie Wang, Jilin Li, and Feiyue Huang.  Dsfd: dual shot face detector.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5060–5069, 2019.
  * [14] Yanghao Li, Yuntao Chen, Naiyan Wang, and Zhaoxiang Zhang.  Scale-aware trident networks for object detection.  In Proceedings of the IEEE international conference on computer vision, pages 6054–6063, 2019.
  * [15] Tsung-Yi Lin, Piotr Dollár, Ross Girshick, Kaiming He, Bharath Hariharan, and Serge Belongie.  Feature pyramid networks for object detection.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2117–2125, 2017.
  * [16] Tsung-Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár.  Focal loss for dense object detection.  In Proceedings of the IEEE international conference on computer vision, pages 2980–2988, 2017.
  * [17] Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick.  Microsoft coco: Common objects in context.  In European conference on computer vision, pages 740–755. Springer, 2014.
  * [18] Wei Liu, Dragomir Anguelov, Dumitru Erhan, Christian Szegedy, Scott Reed, Cheng-Yang Fu, and Alexander C Berg.  Ssd: Single shot multibox detector.  In European conference on computer vision, pages 21–37. Springer, 2016.
  * [19] Yang Liu and Xu Tang.  Bfbox: Searching face-appropriate backbone and feature pyramid network for face detector.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 13568–13577, 2020.
  * [20] Yang Liu, Xu Tang, Junyu Han, Jingtuo Liu, Dinger Rui, and Xiang Wu.  Hambox: Delving into mining high-quality anchors on face detection.  In 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 13043–13051. IEEE, 2020.
  * [21] Yang Liu, Xu Tang, Xiang Wu, Junyu Han, Jingtuo Liu, and Errui Ding.  Hambox: Delving into online high-quality anchors mining for detecting outer faces.  arXiv preprint arXiv:1912.09231, 2019.
  * [22] Mahyar Najibi, Pouya Samangouei, Rama Chellappa, and Larry S Davis.  Ssh: Single stage headless face detector.  In Proceedings of the IEEE International Conference on Computer Vision, pages 4875–4884, 2017.
  * [23] Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun.  Faster r-cnn: Towards real-time object detection with region proposal networks.  In Advances in neural information processing systems, pages 91–99, 2015.
  * [24] Ying Shu, Yan Yan, Si Chen, Jing-Hao Xue, Chunhua Shen, and Hanzi Wang.  Learning spatial-semantic relationship for facial attribute recognition with limited labeled data.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 11916–11925, 2021.
  * [25] Bharat Singh and Larry S Davis.  An analysis of scale invariance in object detection snip.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3578–3587, 2018.
  * [26] Xu Tang, Daniel K Du, Zeqiang He, and Jingtuo Liu.  Pyramidbox: A context-assisted single shot face detector.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 797–813, 2018.
  * [27] Jianfeng Wang, Ye Yuan, and Gang Yu.  Face attention network: An effective face detector for the occluded faces.  arXiv preprint arXiv:1711.07246, 2017.
  * [28] Kai Wang, Shuo Wang, Zhipeng Zhou, Xiaobo Wang, Xiaojiang Peng, Baigui Sun, Hao Li, and Yang You.  An efficient training approach for very large scale face recognition.  arXiv preprint arXiv:2105.10375, 2021.
  * [29] Yitong Wang, Xing Ji, Zheng Zhou, Hao Wang, and Zhifeng Li.  Detecting faces using region-based fully convolutional networks.  arXiv preprint arXiv:1709.05256, 2017.
  * [30] Junjie Yan, Xuzong Zhang, Zhen Lei, and Stan Z Li.  Face detection by structural models.  Image and Vision Computing, 32(10):790–799, 2014.
  * [31] Shuo Yang, Ping Luo, Chen-Change Loy, and Xiaoou Tang.  Wider face: A face detection benchmark.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 5525–5533, 2016.
  * [32] Bin Zhang, Jian Li, Yabiao Wang, Ying Tai, Chengjie Wang, Jilin Li, Feiyue Huang, Yili Xia, Wenjiang Pei, and Rongrong Ji.  Asfd: Automatic and scalable face detector.  arXiv preprint arXiv:2003.11228, 2020.
  * [33] Changzheng Zhang, Xiang Xu, and Dandan Tu.  Face detection using improved faster rcnn.  arXiv preprint arXiv:1802.02142, 2018.
  * [34] Shifeng Zhang, Cheng Chi, Yongqiang Yao, Zhen Lei, and Stan Z Li.  Bridging the gap between anchor-based and anchor-free detection via adaptive training sample selection.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9759–9768, 2020.
  * [35] Shifeng Zhang, Xiangyu Zhu, Zhen Lei, Hailin Shi, Xiaobo Wang, and Stan Z Li.  S3fd: Single shot scale-invariant face detector.  In Proceedings of the IEEE International Conference on Computer Vision, pages 192–201, 2017.
  * [36] Chenchen Zhu, Ran Tao, Khoa Luu, and Marios Savvides.  Seeing small faces from robust anchor’s perspective.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5127–5136, 2018.
  * [37] Chenchen Zhu, Yutong Zheng, Khoa Luu, and Marios Savvides.  Cms-rcnn: contextual multi-scale region-based cnn for unconstrained face detection.  In Deep learning for biometrics, pages 57–79. Springer, 2017.
  * [38] Xiangxin Zhu and Deva Ramanan.  Face detection, pose estimation, and landmark localization in the wild.  In 2012 IEEE conference on computer vision and pattern recognition, pages 2879–2886. IEEE, 2012.


# Lower bounds for piercing and coloring boxes

István Tomon Umeå University, _e-mail_<EMAIL_ADDRESS>
###### Abstract

Given a family $\mathcal{B}$ of axis-parallel boxes in $\mathbb{R}^{d}$, let
$\tau$ denote its _piercing number_ , and $\nu$ its _independence number_. It
is an old question whether $\tau/\nu$ can be arbitrarily large for given
$d\geq 2$. Here, for every $\nu$, we construct a family of axis-parallel boxes
achieving

$\tau\geq\Omega_{d}(\nu)\cdot\left(\frac{\log\nu}{\log\log\nu}\right)^{d-2}.$

This not only answers the previous question for every $d\geq 3$ positively,
but also matches the best known upper bound up to double-logarithmic factors.

Our main construction has further implications about the Ramsey and coloring
properties of configurations of boxes as well. We show the existence of a
family of $n$ boxes in $\mathbb{R}^{d}$, whose intersection graph has clique
and independence number $O_{d}(n^{1/2})\cdot\left(\frac{\log n}{\log\log
n}\right)^{-(d-2)/2}.$ This is the first improvement over the trivial upper
bound $O_{d}(n^{1/2})$, and matches the best known lower bound up to double-
logarithmic factors. Finally, for every $\omega$ satisfying $\frac{\log
n}{\log\log n}\ll\omega\ll n^{1-\varepsilon}$, we construct an intersection
graph of $n$ boxes with clique number at most $\omega$, and chromatic number
$\Omega_{d,\varepsilon}(\omega)\cdot\left(\frac{\log n}{\log\log
n}\right)^{d-2}.$ This matches the best known upper bound up to a factor of
$O_{d}((\log w)(\log\log n)^{d-2})$.

##  1 Introduction

Configurations of axis-parallel boxes in $\mathbb{R}^{d}$ are extensively
studied in combinatorial and computational geometry. There is group of old
problems addressing the relationship between the piercing number, clique
number, independence number, and chromatic number of families of boxes (here
and later, boxes are always axis-parallel, and closed, unless stated
otherwise), where the best known lower and upper bounds match up to
polylogarithmic factors. However, it remained an elusive problem to deal with
these logarithms, mainly because there were no known constructions beating the
trivial ones by more than an absolute constant factor. In this paper, for
every $d\geq 3$, we provide such constructions, also reducing the gaps between
the lower and upper bounds up to a factor of $(\log\log.)^{O(1)}$. Here and
later, the $O(.),\Omega(.),\Theta(.)$ notations hide a constant which might
depend on the dimension $d$, but no other parameter.

###  1.1 Piercing number

Given a family of sets $\mathcal{F}$, a _piercing set_ (or _hitting set_) of
$\mathcal{F}$ is a subset of $\bigcup_{F\in\mathcal{F}}F$ having a nonempty
intersection with every element of $\mathcal{F}$. The _piercing number_ of
$\mathcal{F}$, denoted by $\tau(\mathcal{F})$, is the minimal size of a
piercing set. The _independence number_ (also known as _matching number_ or
_packing number_) of $\mathcal{F}$, denoted by $\nu(F)$, is the maximum number
of pairwise disjoint elements of $\mathcal{F}$. Clearly,
$\tau(\mathcal{F})\geq\nu(\mathcal{F})$, and it is a well known result of
Gallai (see e.g. [13]) that equality holds if $\mathcal{F}$ is a family of
intervals. The situation becomes more complicated if we move to higher
dimensions. In 1965, Wegner [22] conjectured that if $\mathcal{R}$ is a family
of rectangles, then $\tau(\mathcal{R})\leq 2\nu(\mathcal{R})-1$, while Gyárfás
and Lehel [12] proposed the weaker conjecture that $\tau(\mathcal{R})\leq
O(\nu(\mathcal{R}))$. To begin with, it is not even clear that
$\tau(\mathcal{R})$ can be bounded by a function of $\nu(\mathcal{R})$ alone,
but this follows from a result of Károlyi [14], who proved that
$\tau(\mathcal{R})\leq O(\nu(\mathcal{R})\log\nu(\mathcal{R}))$. This was
improved by Correa, Feuilloley, Pérez-Lantero, and Soto [9] to the currently
best known upper bound $\tau(\mathcal{R})\leq
O(\nu(\mathcal{R}))\cdot(\log\log\nu(\mathcal{R}))^{2}$. In the special case
when the elements of $\mathcal{R}$ are $r$-bounded (i.e. the ratio of the two
sides of every rectangle in $\mathcal{R}$ is bounded by $r$), this upper bound
can be improved to linear, see [4, 6, 8]. From below, Jelínek (see [9]) showed
that $\tau(\mathcal{R})=2\nu(\mathcal{R})-4$ can be achieved for every
$\nu\geq 4$, while $\nu(\mathcal{R})=4$ and $\tau(\mathcal{R})=7$ is also
realizable [7].

Now consider $d\geq 3$. Let $\mathcal{B}$ be a family of boxes in
$\mathbb{R}^{d}$, and write $\tau=\tau(\mathcal{B})$ and
$\nu=\nu(\mathcal{B})$. It is a simple result that $\nu=1$ implies $\tau=1$,
which is equivalent to the statement that a family of pairwise intersecting
boxes has a nonempty intersection. In the next case $\nu=2$, Fon-der-Flaass
and Kostochka [11] showed that $\tau\leq d+1$, and that there exists a
construction achieving $\tau=\Omega(d^{1/2}/\log d)$. For general $\nu$,
Gyárfás and Lehel [12] observed that $\tau\leq\nu^{d}$ is easy to prove. This
was subsequently improved by Károlyi [14] to $\tau\leq
O(\nu)\cdot(\log\nu)^{d-1}$, which was then reproved a number of times [1, 8,
17]. Károlyi’s proof relies on a divide-and-conquer argument, and any
improvement for the $d=2$ case translates into an improvement for higher
dimensions as well. Therefore, the aforementioned result of [9] implies that
$\tau\leq O(\nu)\cdot(\log\nu)^{d-2}(\log\log\nu)^{2}$ also holds. For
completeness, we present a proof of this in Section 4, see Theorem 4.1. For
certain special families of boxes, this upper bound can be improved [8]: if
$\mathcal{B}$ consists of _cubes_ , then $\tau=O(\nu)$; also, in case for
every two intersecting boxes, one contains a corner of the other, then
$\tau=O(\nu\log\log\nu)$. On the other hand, it was a long-standing open
problem whether $\tau/\nu$ can be arbitrarily large for any fixed $d$, see
e.g. the survey of Eckhoff [10] (p. 359). Here, we show that the answer is yes
for $d\geq 3$, and even more, our construction matches the best known upper
bound up to a factor of $O((\log\log\nu)^{d})$.

######  Theorem 1.1.

Let $d\geq 3$, then there exists $c>0$ such that the following holds. For
every positive integer $k$, there exists a family of boxes in $\mathbb{R}^{d}$
containing at most $k$ pairwise disjoint sets and having piercing number at
least

$ck\left(\frac{\log k}{\log\log k}\right)^{d-2}.$

###  1.2 Ramsey number

The _intersection graph_ of a family of sets $\mathcal{F}$ is the graph, whose
vertices are the elements of $\mathcal{F}$, and two vertices are joined by an
edge if they have a nonempty intersection. Ramsey properties of intersection
graphs of geometric objects are extensively studied, see e.g. [21] as a
general reference. Larman, Matoušek, Pach, and Törőcsik [16] proved that if
$G$ is the intersection graph of $n$ boxes in $\mathbb{R}^{d}$, then $G$
contains either a clique or an independent set of size
$\Omega(n^{1/2})\cdot(\log n)^{-(d-1)/2}$. Note that this bound can be
improved to $\Omega(n^{1/2})\cdot(\log n)^{-(d-2)/2}(\log\log n)^{-1}$ using
the above mentioned result about piercing numbers. Indeed, let $\mathcal{B}$
be a family of boxes realizing $G$. Setting $k=n^{1/2}(\log
n)^{-(d-2)/2}(\log\log n)^{-1}$, either $\nu(\mathcal{B})\geq k$, which is
equivalent to $\alpha(G)\geq k$, or $\tau(G)\leq O(k)\cdot(\log
k)^{d-2}(\log\log k)^{2}$. But then there is a point piercing at least
$n/\tau(G)=\Omega(k)$ elements of $\mathcal{B}$, corresponding to a clique of
size $\Omega(k)$.

From above, it is easy to construct a family of $n$ boxes, whose intersection
graph contains no clique or independent set of size larger than $\sqrt{n}$.
Indeed, the disjoint union of $\sqrt{n}$ cliques of size $\sqrt{n}$ can be
realized as the intersection graph of boxes in any dimension. However, there
were no known constructions improving this simple bound by more than a
constant factor. Our next main result provides such a construction, and
matches the previously described lower bound up to a factor of $O((\log\log
n)^{d/2})$.

######  Theorem 1.2.

Let $d\geq 3$, then there exists $c>0$ such that the following holds. For
every positive integer $n$, there exists a family of $n$ boxes in
$\mathbb{R}^{d}$, whose intersection graph $G$ contains no clique or
independent set of size larger than

$cn^{1/2}\left(\frac{\log n}{\log\log n}\right)^{-(d-2)/2}.$

###  1.3 Coloring number

As usual, $\omega(G),\chi(G),\alpha(G)$ denote the _clique number_ ,
_chromatic number_ , and _independence number_ of a graph $G$, respectively. A
classical result of Asplund and Grünbaum [2] states that if $G$ is the
intersection graph of rectangles, then $\chi(G)\leq O(\omega(G)^{2})$. After
sixty years, this was only recently improved by Chalermsook and Walczak [5] to
$\chi(G)\leq O(\omega(G)\log\omega(G))$. On the other hand, there is no known
construction beating the trivial bound $\chi(G)\geq\Omega(\omega(G))$.

For $d\geq 3$, a celebrated construction of Burling [3] shows that the
chromatic number of intersection graphs of boxes in $\mathbb{R}^{d}$ cannot be
bounded by the clique number alone. The so called _Burling graphs_ provide an
infinite family of graphs $G$ that are triangle-free, and if $G$ has $n$
vertices, then $\chi(G)=\Theta(\log\log n)$. See [19] for an alternative
construction of a family of $K_{5}$-free intersection graphs of boxes in
$\mathbb{R}^{3}$, whose chromatic number achieves a similar growth. Let $G$ be
an intersection graph of $n$ boxes in $\mathbb{R}^{d}$ and let
$\omega=\omega(G)$. Just as before, the best known upper bound on the
chromatic number of $G$ is supplied by a divide-and-conquer argument
(folklore). Using the aforementioned result of [5] as base case, we get
$\chi(G)\leq O(\omega)\cdot(\log\omega)(\log n)^{d-2}$. For completeness, we
present the proof of this in Section 4, see Theorem 4.2. Here, we provide the
first construction which matches this bound up to a factor of $O((\log
w)(\log\log n)^{d-2})$ for a wide range of values of $\omega$.

######  Theorem 1.3.

Let $d\geq 3$ and $\varepsilon>0$, then there exists $c,c^{\prime}\geq 0$ such
that the following holds. For every positive integer $n$ and $\omega$
satisfying $c\frac{\log n}{\log\log n}\leq\omega\leq n^{1-\varepsilon}$, there
exists a family of $n$ boxes in $\mathbb{R}^{d}$ such that its intersection
graph $G$ satisfies $\omega(G)\leq\omega$ and

$\chi(G)\geq c^{\prime}\cdot\omega\left(\frac{\log n}{\log\log
n}\right)^{d-2}.$

Unfortunately, Theorem 1.3 does not provide lower bounds in case $\omega(G)$
is a constant, the most interesting of which is when $\omega(G)=2$. It remains
open whether there exists triangle-free intersection graphs of $n$ boxes in
$\mathbb{R}^{d}$ of chromatic number growing much faster than $\log\log n$.

##  2 The main theorem

In this section, we state our main technical result, and show how to deduce
Theorems 1.1, 1.2, and 1.3 from it. We omit the use of floors and ceilings
whenever they are not crucial.

######  Theorem 2.1.

Let $d\geq 3$, then there exists $c_{1},c_{2}\geq 0$ such that the following
holds. For every positive integer $n$, there exists a family of $n$ boxes in
$\mathbb{R}^{d}$ such that its intersection graph has clique number at most
$c_{1}\frac{\log n}{\log\log n}$ and independence number at most
$c_{2}n(\frac{\log n}{\log\log n})^{-(d-1)}$

###### Proof of Theorem 1.1.

We may assume that $k$ is sufficiently large with respect to $d$. Let
$c_{1},c_{2}$ be the constants provided by Theorem 2.1, and let $n$ be the
largest positive integer such that $k\geq c_{2}n(\frac{\log n}{\log\log
n})^{-(d-1)}$. Then $n=\Theta(k(\frac{\log k}{\log\log k})^{d-1})$. Let
$\mathcal{B}$ be a family of $n$ boxes in $\mathbb{R}^{d}$ whose intersection
graph $G$ satisfies $\omega(G)\leq c_{1}\frac{\log n}{\log\log n}$ and
$\alpha(G)\leq c_{2}n(\frac{\log n}{\log\log n})^{-(d-1)}\leq k$. Note that a
family of boxes that can be pierced by a single point is a clique in $G$, so
the piercing number of $\mathcal{B}$ is at least

$\frac{n}{\omega(G)}\geq\frac{n\log\log n}{c_{1}\log
n}\geq\Omega\left(k\left(\frac{\log k}{\log\log k}\right)^{d-2}\right).$

Hence, $\mathcal{B}$ satisfies the required conditions. ∎

###### Proof of Theorem 1.2.

We may assume that $n$ is sufficiently large with respect to $d$, and let
$c_{1},c_{2}$ be the constants provided by Theorem 2.1. Let
$n_{0}=n^{1/2}(\frac{\log n}{\log\log n})^{d/2}$ and
$s=\frac{n}{n_{0}}=n^{1/2}(\frac{\log n}{\log\log n})^{-d/2}$. Let
$\mathcal{B}_{0}$ be a family of $n_{0}$ boxes in $\mathbb{R}^{d}$, whose
intersection graph $G_{0}$ satisfies $\omega(G_{0})\leq c_{1}\frac{\log
n_{0}}{\log\log n_{0}}$ and $\alpha(G_{0})\leq c_{2}n_{0}(\frac{\log
n_{0}}{\log\log n_{0}})^{-(d-1)}$. Let $\mathcal{B}$ be the family of
$n=sn_{0}$ boxes we get after taking each element of $\mathcal{B}$ with
multiplicity $s$, and let $G$ be the intersection graph of $\mathcal{B}$. Then
$v(G)=n$,

$\omega(G)=s\cdot\omega(G_{0})=O\left(n^{1/2}\left(\frac{\log n}{\log\log
n}\right)^{-(d-2)/2}\right)$

and

$\alpha(G)=\alpha(G_{0})=O\left(n^{1/2}\left(\frac{\log n}{\log\log
n}\right)^{-(d-2)/2}\right),$

finishing the proof. ∎

###### Proof of Theorem 1.3.

We may assume that $n$ is sufficiently large with respect to $d$ and
$\varepsilon$, and let $c_{1},c_{2}$ be the constants provided by Theorem 2.1.
Let $c=c_{1}$, $s=\frac{\omega\log\log n}{c_{1}\log n}$ (so then $s\geq 1$),
and $n_{0}=\frac{n}{s}\geq n^{\varepsilon-o(1)}$. Let $\mathcal{B}_{0}$ be a
family of $n_{0}$ boxes in $\mathbb{R}^{d}$, whose intersection graph $G_{0}$
satisfies $\omega(G_{0})\leq c_{1}\frac{\log n_{0}}{\log\log n_{0}}$ and

$\alpha(G_{0})\leq c_{2}n_{0}\left(\frac{\log n_{0}}{\log\log
n_{0}}\right)^{-(d-1)}\leq c_{3}\frac{n}{s}\cdot\left(\frac{\log n}{\log\log
n}\right)^{-(d-1)},$

where $c_{3}>0$ only depends on $c_{2}$ and $\varepsilon$. Let $\mathcal{B}$
be the family of $n=sn_{0}$ boxes we get after taking each element of
$\mathcal{B}$ with multiplicity $s$, and let $G$ be the intersection graph of
$\mathcal{B}$. Then $\omega(G)=s\cdot\omega(G_{0})\leq\omega$ and
$\alpha(G)=\alpha(G_{0})$. On the other hand, we have

$\chi(G)\geq\frac{n}{\alpha(G)}\geq\frac{s}{c_{3}}\left(\frac{\log n}{\log\log
n}\right)^{d-1}=\frac{w}{c_{1}c_{3}}\cdot\left(\frac{\log n}{\log\log
n}\right)^{d-2},$

so $c^{\prime}=\frac{1}{c_{1}c_{3}}$ suffices. ∎

##  3 The construction

This section is devoted to the proof of Theorem 2.1. We fix the following
parameters, some of which will be specified later with respect to $n$: let $s$
and $k$ be positive integers, and let $m:=s^{k}$ and $M:=m^{d-1}$. We assume
that $s$ and $k$ are sufficiently large with respect to $d$. Given
$\textbf{t}\in\mathbb{N}^{d}$ and $\textbf{p}\in\mathbb{Z}^{d}$, let
$B_{\textbf{t}}(\textbf{p})$ denote the $s^{\textbf{t}(1)}\times\dots\times
s^{\textbf{t}(d)}$ sized (not closed) box

$\prod_{i=1}^{d}\left[s^{\textbf{t}(i)}\cdot\mathbf{p}(i),s^{\textbf{t}(i)}\cdot(\mathbf{p}(i)+1)\right).$

Call $B_{\textbf{t}}(\textbf{p})$ a _t -block_, or simply a _block_. Clearly,
the _t -blocks_ partition $\mathbb{R}^{d}$ for every
$\textbf{t}\in\mathbb{N}^{d}$. Furthermore, an important observation is that
for any $i\in[d]$, the projections of any two blocks onto the $i$-th axis are
either disjoint, or one contains the other. In the special case $s=2$ and
$d=2$, the blocks we defined are sometimes referred to as _dyadic_ or
_canonical rectangles_ , and they play a key role in the celebrated result of
Pach and Tardos [18] about epsilon-nets, for example. For us, it will be
crucial that $s$ can grow slowly with $n$.

Let

$T=\left\\{\textbf{t}\in\mathbb{N}^{d}:\sum_{i=1}^{d}\mathbf{t}(i)=k\right\\},$

and let $\mathcal{B}$ be the family of all blocks of volume $m=s^{k}$
contained in $[0,m]^{d}$. In other words, $\mathcal{B}$ is the family of all
blocks $B_{\textbf{t}}(\textbf{p})$, where $\textbf{t}\in T$ and
$\textbf{p}(i)\in\\{0,\dots,s^{k-\mathbf{t}(i)}-1\\}$ for every $i\in[d]$.
Note that $|T|=\binom{k+d-1}{d-1}$ and $|\mathcal{B}|=|T|\cdot
m^{d-1}=|T|\cdot M$.

Let $G$ be the intersection graph of $\mathcal{B}$. While blocks are not
closed boxes, we can slightly shrink them and take their closures without
changing the intersection pattern, so $G$ is also an intersection graph of
closed boxes. Clearly, we have $\omega(G)=|T|$, as each point of $[0,m]^{d}$
is contained in a unique $\mathbf{t}$-block for every $\mathbf{t}\in T$. Also,
$\alpha(G)=M$, as the $\mathbf{t}$-blocks form an independent set of size $M$
for every $\mathbf{t}\in T$, and any family of $M+1$ blocks in $\mathcal{B}$
have total volume more than $m^{d}$.

Our aim is to show that a random sample of the vertices of $G$ with some
appropriate probability $p$ induces a subgraph $H$ satisfying the requirements
of Theorem 2.1 with high probability. The clique number of a random sample is
easy to analyze, as a clique is a set of blocks containing a given point. On
the other hand, independent sets are harder to control, and we will use the
celebrated _graph container method_ to do so. This method was first introduced
by Kleitman and Winston [15], and later formalized by Sapozhenko [20]. In
order to make our paper self contained, we do not assume familiarity with
these publications, and the container method in general. Roughly, we show that
there is a small collection $\mathcal{C}$ of subsets of $V(G)$, each of size
close to $\alpha(G)$, such that every independent set of $G$ is covered by an
element of $\mathcal{C}$. The members of the collection $\mathcal{C}$ are
called _containers_. Such a collection exists if $G$ admits a
_supersaturation_ result, i.e. every subset of the vertices slightly larger
than $\alpha(G)$ induces a subgraph of large maximum degree. We prove this
supersaturation result in the next lemma.

######  Lemma 3.1.

Let $\varepsilon>0$, and let $S\subset\mathcal{B}$ be of size at least
$(1+\varepsilon)M$. Then the maximum degree of $G[S]$ is at least
$\frac{\varepsilon s}{|T|^{2}}$.

###### Proof.

Let $\Delta$ be the maximum degree of $G[S]$. For a block $C$ and
$\mathbf{t}\in T$, let $S_{\mathbf{t}}[C]$ denote the set of
$\mathbf{t}$-blocks among the elements of $S$ that are contained in $C$.

Fix a pair of distinct $\textbf{t},\textbf{u}\in T$, and define
$\mathbf{w}\in\mathbb{N}^{d}$ such that
$\mathbf{w}(i)=\max\\{\mathbf{t}(i),\mathbf{u}(i)\\}$. Observe that if $B$ is
a $\mathbf{t}$-block and $B^{\prime}$ a is $\mathbf{u}$-block, then $B$ and
$B^{\prime}$ have a nonempty intersection if and only if $B$ and $B^{\prime}$
are contained in the same $\mathbf{w}$-block. Indeed, for $i\in[d]$ let
$B_{i}$ and $B_{i}^{\prime}$ be the projections of $B$ and $B^{\prime}$ onto
the $i$-th axis, respectively. Then $B$ and $B^{\prime}$ intersect if and only
if $B_{i}\subset B_{i}^{\prime}$ or $B_{i}^{\prime}\subset B_{i}$ for every
$i\in[d]$ (indeed, recall that if $B_{i}\cap B_{i}^{\prime}\neq\emptyset$,
then one must contain the other). Thus, if $B\cap B^{\prime}\neq\emptyset$,
then $(B_{1}\cup B_{1}^{\prime})\times\dots\times(B_{d}\cup B_{d}^{\prime})$
is a $\mathbf{w}$-block containing $B$ and $B^{\prime}$. On the other hand, if
$C$ is a $\mathbf{w}$-block containing $B$ and $B^{\prime}$, and $C_{i}$ is
the projection of $C$ onto the $i$-th axis, then either $C_{i}=B_{i}$ or
$C_{i}=B_{i}^{\prime}$, showing that $B_{i}\subset B^{\prime}_{i}$ or
$B^{\prime}_{i}\subset B_{i}$.

Define the family $\mathcal{M}(\textbf{t},\textbf{u})\subset S$ as follows. By
the previous, for every $\mathbf{w}$-block $C$, every element of
$S_{\mathbf{t}}[C]$ intersects every element of $S_{\mathbf{u}}[C]$.
Therefore, we have either $|S_{\mathbf{t}}[C]|\leq\Delta$ or
$|S_{\mathbf{u}}[C]|\leq\Delta$. In the first case, we add every element of
$S_{\mathbf{t}}[C]$ to $\mathcal{M}(\textbf{t},\textbf{u})$, in the second
case we add every element of $S_{\mathbf{u}}[C]$ to
$\mathcal{M}(\textbf{t},\textbf{u})$ (if both cases hold, we only add the
elements of $S_{\mathbf{t}}[C]$, say). The total number of $\mathbf{w}$-blocks
in $[0,m]^{d}$ is

$\frac{m^{d}}{s^{\mathbf{w}(1)+\dots+\mathbf{w}(d)}}\leq\frac{m^{d}}{s^{k+1}}=\frac{M}{s},$

where the first inequality holds by noting that
$\mathbf{w}(1)+\dots+\mathbf{w}(d)>\mathbf{t}(1)+\dots+\mathbf{t}(d)=k$.
Hence, $|\mathcal{M}(\textbf{t},\textbf{u})|\leq\Delta\cdot\frac{M}{s}$.
Moreover, $S\setminus\mathcal{M}(\textbf{t},\textbf{u})$ contains no t-block
intersecting a u-block, because if a $\mathbf{t}$-block intersects a
$\mathbf{u}$-block, then they are contained in the same $\mathbf{w}$-block.

Let $S^{\prime}=S\setminus\bigcup_{\mathbf{t},\mathbf{u}\in
T,\mathbf{t}\neq\mathbf{u}}\mathcal{M}(\mathbf{t},\mathbf{u})$. Then
$|S^{\prime}|\geq|S|-|T|^{2}\Delta\frac{M}{s}$. Crucially, any two blocks in
$S^{\prime}$ are disjoint, so $|S^{\prime}|\leq M$. Therefore, comparing the
lower and upper bound on $|S^{\prime}|$, we arrive to the inequality

$M\geq|S^{\prime}|\geq|S|-|T|^{2}\Delta\frac{M}{s}\geq(1+\varepsilon)M-|T|^{2}\Delta\frac{M}{s}.$

Comparing the left and right sides, we get the desired inequality
$\Delta\geq\frac{\varepsilon s}{|T|^{2}}$. ∎

With a slightly more involved calculation, the lower bound on the maximum
degree can be improved to $\Omega(\frac{\epsilon s}{|T|})$. However, this
improvement has no effect on the bound in Theorem 2.1. Moreover, it is worth
noting that in case $d=2$, one has the much stronger saturation result that
any set of size $M+1$ induces a subgraph of maximum degree $\Omega(s)$. This
no longer holds for $d\geq 3$, there exists a set of $M+1$ boxes that induces
a subgraph of maximum degree 1. We leave these claims as exercises, and they
will not be used later.

Now we are ready to state our container lemma, whose proof should be mostly
standard for anyone familiar with the container method.

######  Lemma 3.2.

Let $s\geq|T|^{3}$. Then there exists a collection $\mathcal{C}$ of subsets of
$\mathcal{B}$ such that

  1. (1)

every $C\in\mathcal{C}$ satisfies $|C|\leq 3M$,

  2. (2)

$|\mathcal{C}|\leq e^{(\log s)M|T|^{3}/s}$,

  3. (3)

every independent set of $G$ is contained in some element of $\mathcal{C}$.

###### Proof.

Let $<$ be an arbitrary total ordering of the elements of $\mathcal{B}$. For a
graph $H$ and vertex $v\in V(H)$, $N_{H}(v)=\\{w\in V(H):vw\in E(H)\\}$
denotes the _neighborhood_ of $v$ in $H$.

Fix an independent set $I$ of $G$. We construct a _fingerprint_ $S$ and a set
$f(S)$ (depending only on $S$) for $I$ with the help of the following
algorithm.

Let $S_{0}=\emptyset$ and $G_{0}=G$. If $S_{i}$ and $G_{i}$ are already
defined, we define $S_{i+1}$ and $G_{i+1}$ in the following manner. Let $v$ be
the first vertex (with respect to $<$) of maximum degree in $G_{i}$.

  * •

If $|V(G_{i})|\leq 2M$, then stop, and set $S=S_{i}$ and $f(S)=V(G_{i})$.

  * •

Otherwise, if $v\not\in I$, then set $S_{i+1}=S_{i}$, remove $v$ from $G_{i}$,
and let the resulting graph be $G_{i+1}$.

  * •

If $v\in I$, then set $S_{i+1}=S_{i}\cup\\{v\\}$, and remove $\\{v\\}\cup
N_{G_{i}}(v)$ from $G_{i}$, let $G_{i+1}$ be the resulting graph.

Let us analyze this algorithm. At each step, the size of $G_{i}$ decreases, so
the algorithm stops after a finite number of steps.

Firstly, let us argue that $f(S)$ indeed only depends on $S$. In particular,
we show that if $I_{1},I_{2}$ are independent sets, for which the algorithm
produces the same fingerprint $S$, then the algorithm produces the same sets
$S_{i}$ and graphs $G_{i}$ at every step for $I_{1}$ and $I_{2}$. Otherwise,
let $i$ be the last step, where $G_{j}$ and $S_{j}$ agree for $I_{1}$ and
$I_{2}$ for every $j\leq i$. Then the first vertex $v$ of maximum degree in
$G_{i}$ is contained in exactly one of $I_{1}$ and $I_{2}$, say $v\in
I_{1}\setminus I_{2}$. But then the algorithm for $I_{1}$ sets
$S_{i+1}=S_{i}\cup\\{v\\}$, so $v\in S$. On the other hand, the algorithm for
$I_{2}$ sets $S_{i+1}=S_{i}$, removes $v$ from $G_{i}$, and never processes
this vertex again, so $v\not\in S$, contradiction.

Secondly, observe that as $I$ is an independent set, we have $I\subset
S_{i}\cup V(G_{i})$ for every $i$, so in particular $I\subset S\cup f(S)$.

Finally, we have $|S|\leq\frac{M|T|^{3}}{s}$. Indeed, in case we added a
vertex $v$ to $S_{i}$ to get $S_{i+1}$, we removed at least $1+|N_{G_{i}}(v)|$
vertices from $G_{i}$ to get $G_{i+1}$. But $v$ is a vertex of maximum degree
in $G_{i}$, and $G_{i}$ has at least $2M$ vertices, so applying Lemma 3.1 with
$\varepsilon=1$, we get $1+|N_{G_{i}}(v)|>\frac{s}{|T|^{2}}$. Therefore, as we
started with $|\mathcal{B}|$ vertices, there are at most
$|\mathcal{B}|\frac{|T|^{2}}{s}=\frac{M|T|^{3}}{s}$ indices $i$ for which
$|S_{i+1}|=|S_{i}|+1$. In particular, we have $|S\cup
f(S)|\leq\frac{M|T|^{3}}{s}+2M\leq 3M$

Let $\mathcal{C}$ be the collection of all the set $S\cup f(S)$, where $S$ is
the fingerprint of some independent set $I$. Then (1) and (3) are clearly
satisfied. Also, as each fingerprint has size at most $\frac{M|T|^{3}}{s}$, we
have

$|\mathcal{C}|\leq\binom{|\mathcal{B}|}{M|T|^{3}/s}\leq\left(\frac{es}{|T|^{2}}\right)^{M|T|^{3}/s}\leq
e^{(\log s)M|T|^{3}/s}.$

Here, the second inequality holds by the general inequality
$\binom{a}{b}\leq(\frac{ea}{b})^{b}$ and substituting $|\mathcal{B}|=|T|M$.
This finishes proof. ∎

Let $p\in(0,1)$ be a parameter specified later, and sample the elements of
$\mathcal{B}$ independently with probability $p$. Let the resulting sample be
$X$, and let $H=G[X]$. In the following claims, we collect the important
properties of $H$. During our arguments, we use standard concentration
arguments.

######  Lemma 3.3 (Multiplicative Chernoff bound).

Let $X$ be the sum of independent indicator random variables. If $\lambda\geq
2\mathbb{E}(X)$, then $\mathbb{P}(X\geq\lambda)\leq e^{-\lambda/6}$. Also,
$\mathbb{P}(X\leq\mathbb{E}(X)/2)\leq e^{-\mathbb{E}(X)/8}.$

First, we bound the size of $X$.

######  Claim 3.4.

If $p\geq\frac{1}{s}$, then $|X|\geq\frac{p|\mathcal{B}|}{2}$ with probability
at least $3/4$.

###### Proof.

Follows simply from the multiplicative Chernoff bound:

$\mathbb{P}\left(|X|<\frac{p|\mathcal{B}|}{2}\right)\leq
e^{-p|\mathcal{B}|/8}<\frac{1}{4},$

where in the last inequality we used that $p|\mathcal{B}|>s^{kd-1}$ is
sufficiently large. ∎

Next, we bound the independence number of $H$. We argue that as the number of
containers covering the independent sets of $G$ is small, each of them must
shrink to approximately $p$ proportion after sampling. As the containers have
size $O(\alpha(G))$, this ensures that $\alpha(H)=O(p\alpha(G))$.

######  Claim 3.5.

If $s\geq|T|^{3}$ and $p>\frac{2(\log s)|T|^{3}}{s}$, then $\alpha(H)\leq 6pM$
with probability at least $3/4$.

###### Proof.

Let $\mathcal{C}$ be a collection of subsets of $\mathcal{B}$ satisfying the
conditions of Lemma 3.2. Let $C\in\mathcal{C}$, then $|C|\leq 3M$. Hence,
$\mathbb{E}(|C\cap X|)\leq 3pM$. By the multiplicative Chernoff bound (Lemma
3.3), we have

$\mathbb{P}(|C\cap X|\geq 6pM)\leq e^{-pM}.$

Note that

$|\mathcal{C}|\cdot e^{-pM}\leq e^{(\log s)M|T|^{3}/s-pM}<\frac{1}{4}.$

Hence, by the union bound, with probability at least $3/4$, we have $|C\cap
X|\leq 6pM$ for every $C\in\mathcal{C}$. But every independent set of $H$ is
contained in $C\cap X$ for some $C\in\mathcal{C}$, so we also have
$\alpha(H)\leq 6pM$. ∎

Finally, let us bound the clique number of $H$.

######  Claim 3.6.

If $p\leq\frac{1}{e|T|}$, then $\omega(H)<\frac{2dk\log s}{\log k}$ with
probability at least $3/4$.

###### Proof.

Let $r=\lceil\frac{2d(\log m)}{\log\log m}\rceil$ and let
$\mathbf{o}\in\mathbb{N}^{d}$ be the all zero vector. Note that if
$\mathcal{C}\subset\mathcal{B}$ is a clique, then the intersection of the
elements of $\mathcal{C}$ contains an $\mathbf{o}$-block. Let $B$ be an
$\mathbf{o}$-block of $[0,m]^{d}$, and let $\mathcal{C}_{0}\subset\mathcal{B}$
be the elements containing $B$. Then $|\mathcal{C}_{0}|=|T|$, as for every
$\mathbf{t}\in T$, there is a unique $\mathbf{t}$-block containing $B$.
Therefore, we have

$\mathbb{P}(|\mathcal{C}_{0}\cap X|\geq
r)\leq\binom{|T|}{r}p^{r}\leq\left(\frac{ep|T|}{r}\right)^{r}\leq e^{-r\log
r}\leq e^{-2d\log m}\leq\frac{1}{4m^{d}}.$

The number of o-blocks in $[0,m]^{d}$ is $m^{d}$, so the union bound shows
that with probability at least $3/4$, no o-block is contained in $r$ elements
of $X$. Thus, recalling that $m=s^{k}$, we have

$\omega(H)<\frac{2d\log m}{\log\log m}<\frac{2dk\log s}{\log k}$

with probability at least $3/4$. ∎

Now everything is set to prove our main theorem.

###### Proof of Theorem 2.1.

Given $n$, we will choose the parameters $k,s,p$ such that the graph $H$
defined above has (almost) $n$ vertices, and the conditions of Claims 3.4, 3.5
and 3.6 are satisfied. We may assume that $n$ is sufficiently large with
respect to $d$, which will ensure that $k$ and $s$ are also sufficiently large
with respect to $d$.

Let $k$ be the solution of the equation $n=\frac{1}{8}\cdot k^{4d(d-1)k}$, and
let $s=k^{4d}$. Then $n=\frac{1}{8}\cdot s^{k(d-1)}=\frac{M}{8}$,
$k=\Theta(\frac{\log n}{\log\log n})$ and

$k^{d-1}\geq|T|=\Theta\left(\left(\frac{\log n}{\log\log
n}\right)^{d-1}\right).$

Set $p=\frac{1}{4|T|}$, then $p$ clearly satisfies the condition of Claim 3.6.
Also, we have $s>k^{3d}>|T|^{3}$ and

$\frac{2(\log s)|T|^{4}}{s}\leq\frac{4d(\log
k)k^{4(d-1)}}{k^{4d}}<\frac{1}{4},$

which implies that $p$ satisfies the condition of Claim 3.5, and thus the
condition of Claim 3.4 as well. Therefore, with probability at least $1/4$,
the following are simultaneously satisfied

  * •

$|X|\geq\frac{p|\mathcal{B}|}{2}=\frac{M}{8}=n$,

  * •

$\alpha(H)\leq 6pM=\frac{12n}{|T|}=O(n(\frac{\log n}{\log\log n})^{-(d-1)})$,

  * •

$\omega(H)<\frac{2dk\log s}{\log k}=O(k)=O(\frac{\log n}{\log\log n})$.

After possibly removing some further vertices of $H$, we get an intersection
graph of $n$ boxes in $\mathbb{R}^{d}$, satisfying the required conditions. ∎

We remark that in case $d=2$, the graph $G$ defined above is a comparability
graph. Indeed, if $B$ is a $\mathbf{t}$-block and $B^{\prime}$ is
$\mathbf{t}^{\prime}$-block, then writing $B\prec B^{\prime}$ if $B\cap
B^{\prime}\neq\emptyset$ and $\mathbf{t}(1)<\mathbf{t}^{\prime}(1)$, $\prec$
is a partial ordering, whose comparability graph is $G$. But then
$\omega(H)=\chi(H)$ for every induced subgraph $H$ of $G$, showing that
unfortunately one cannot get interesting constructions by considering
subgraphs of $G$.

##  4 Upper bounds

As promised in the introduction, we present the upper bounds on the piercing
number and chromatic number of boxes. Without loss of generality, we may
assume that any family of boxes under consideration is in _general position_ ,
that is, the corners of the boxes have different coordinates.

In addition, we will use the following notation. Given a family of boxes
$\mathcal{B}$ in $\mathbb{R}^{d}$ and $t\in\mathbb{R}$, let
$\mathcal{B}^{-}(t)$ denote the set of elements of $\mathcal{B}$ that are
contained entirely in the open half-space
$\\{\mathbf{x}\in\mathbb{R}^{d}:\mathbf{x}(d)<t\\}$. Similarly, let
$\mathcal{B}^{+}(t)$ denote the set of elements of $\mathcal{B}$ that are
contained entirely in the open half-space
$\\{\mathbf{x}\in\mathbb{R}^{d}:\mathbf{x}(d)>t\\}$, and set
$\mathcal{B}^{0}(t)=\mathcal{B}\setminus(\mathcal{B}^{-}(t)\cup\mathcal{B}^{+}(t))$.
Finally, let $\mathcal{B}(t)=\\{B\cap H:B\in\mathcal{B}\\}$, where
$H=\\{\mathbf{x}\in\mathbb{R}^{d}:\mathbf{x}(d)=t\\}$. Then $\mathcal{B}(t)$
is equivalent to a family of boxes in $\mathbb{R}^{d-1}$, and the intersection
graph of $\mathcal{B}(t)$ is isomorphic to the intersection graph of
$\mathcal{B}^{0}(t)$.

Furthermore, we use the following well known inequalities on recursively
bounded functions. Let $f,g:\mathbb{Z}^{+}\rightarrow{R}^{+}$ be monotone
increasing functions. If $f(n)\leq f(\lceil n/2\rceil)+g(n)$ holds for every
$n\geq 2$, then $f(n)\leq cg(n)\log n$ for some $c>0$ depending only on
$f(1)$. Also, if $g$ is convex and $f(n)\leq f(\lfloor n/2\rfloor)+f(\lceil
n/2\rceil)+g(n)$ holds for every $n\geq 2$, then $f(n)\leq cg(n)\log n$ for
some $c>0$ depending only on $f(1)$.

######  Theorem 4.1.

For every $d\geq 2$ there exists a constant $c_{d}$ such that if $\mathcal{B}$
is a family of boxes in $\mathbb{R}^{d}$ satisfying $\nu(\mathcal{B})\leq k$,
then $\tau(\mathcal{B})\leq c_{d}k(\log k)^{d-2}(\log\log k)^{2}$.

###### Proof.

Let $f_{d}(k)$ denote the maximum possible piercing number of a family of
boxes in $\mathbb{R}^{d}$ with independence number $k$, and let $\mathcal{B}$
be a family of boxes realizing it. It is easy to show that $f_{d}$ is a convex
function by considering the disjoint union of two families of boxes. We
proceed by induction on $d$ and $k$ to show that $f_{d}(k)\leq c_{d}k(\log
k)^{d-2}(\log\log k)^{2}$ with some suitable constant $c_{d}$. This holds for
$d=2$ and every $k\in\mathbb{Z}^{+}$ by [9]. Also, we have $f_{d}(1)=1$ for
every $d\in\mathbb{Z}^{+}$. Assume $d\geq 3$ and $k\geq 2$. It is easy to see
that there exists $t$ such that $\nu(\mathcal{B}^{-}(t))=\lfloor k/2\rfloor$
by the assumption that the boxes are in general position. But then we must
have $\nu(\mathcal{B}^{+}(t))\leq\lceil k/2\rceil$, as no member of
$\mathcal{B}^{-}(t)$ intersects a member of $\mathcal{B}^{+}(t)$. Finally, we
have $\nu(\mathcal{B}(t))=\nu(\mathcal{B}^{0}(t))\leq k$ and
$\tau(\mathcal{B}^{0}(t))=\tau(\mathcal{B}(t))\leq f_{d-1}(k)$. From this, we
get

$\displaystyle\tau(\mathcal{B})$
$\displaystyle\leq\tau(\mathcal{B}^{-}(t))+\tau(\mathcal{B}^{+}(t))+\tau(\mathcal{B}^{0}(t))$
$\displaystyle\leq f_{d}(\lfloor k/2\rfloor)+f_{d}(\lceil
k/2\rceil)+f_{d-1}(k)$ $\displaystyle\leq cf_{d-1}(k)\log k\leq c_{d}k(\log
k)^{d-2}(\log\log k)^{2},$

where $c$ is some absolute constant, and $c_{d}$ only depends on $c_{d-1}$. ∎

With slight abuse of notation, write $\chi(\mathcal{B})$ and
$\omega(\mathcal{B})$ for $\chi(G)$ and $\omega(G)$, respectively, where $G$
is the intersection graph of the family of boxes $\mathcal{B}$.

######  Theorem 4.2.

For every $d\geq 2$ there exists a constant $c_{d}$ such that if $\mathcal{B}$
is a family of $n$ boxes in $\mathbb{R}^{d}$ satisfying
$\omega(\mathcal{B})\leq\omega$, then $\chi(\mathcal{B})\leq
c_{d}\omega(\log\omega)(\log n)^{d-2}$.

###### Proof.

Let $f_{d,\omega}(n)$ denote the maximum chromatic number of a family of $n$
boxes in $\mathbb{R}^{d}$ with clique number at most $\omega$, and let
$\mathcal{B}$ be family of $n$ boxes realizing it. We proceed by induction on
$d$ to show that $f_{d,\omega}(n)\leq c_{d}\omega(\log\omega)(\log n)^{d-2}$
with some suitable constant $c_{d}$. This holds for $d=2$ and every
$n,\omega\in\mathbb{Z}^{+}$ by [5]. Also, we have $f_{d,\omega}(1)=1$ for
every $d\in\mathbb{Z}^{+}$. Assume $d\geq 3$ and $n\geq 2$. It is easy to see
that there exists $t$ such that $|\mathcal{B}^{-}(t)|=\lfloor n/2\rfloor$ by
the assumption that the boxes are in general position. But then
$|\mathcal{B}^{+}(t))|\leq\lceil n/2\rceil$. Moreover, we have
$\omega(\mathcal{B}(t))=\omega(\mathcal{B}^{0}(t))\leq\omega$ and
$\chi(\mathcal{B}^{0}(t))=\chi(\mathcal{B}(t))\leq f_{d-1,\omega}(n)$.
Consider the coloring in which we use the same set of at most
$f_{d,\omega}(\lceil n/2\rceil)$ colors to color both $\mathcal{B}^{-}(t)$ and
$\mathcal{B}^{+}(t)$, and use a different set of at most $f_{d-1,\omega}(n)$
colors to color $\mathcal{B}^{0}(t)$. This shows that

$\displaystyle\chi(\mathcal{B})$ $\displaystyle\leq f_{d,\omega}(\lceil
n/2\rceil)+f_{d-1,\omega}(n)$ $\displaystyle\leq cf_{d-1,\omega}(n)\log n\leq
c_{d}\omega(\log\omega)(\log n)^{d-2},$

where $c$ is some absolute constant, and $c_{d}$ only depends on $c_{d-1}$. ∎

##  5 Concluding remarks

János Pach and Gábor Tardos brought to my attention that there is more
straightforward way of dealing with independent sets in the proof of Theorem
2.1, which does not rely on the container method.

It follows form the proof of Lemma 3.1 that the graph $G$ is the edge disjoint
union of $q=O(\frac{M|T|^{2}}{s})$ complete bipartite graphs. Let
$X_{i},Y_{i}$ be the vertex classes of these bipartite graphs, where
$i=1,\dots,q$. Define the collection $\mathcal{I}$ of subsets of $V(G)$ as
follows. For every $i\in[q]$, let $Z_{i}$ be equal to either $X_{i}$ or
$Y_{i}$, and let $I=I(Z_{1},\dots,Z_{q})$ be the set of vertices $x\in V(G)$
such that whenever $x\in X_{i}\cup Y_{i}$, we have $x\in Z_{i}$. Let
$\mathcal{I}$ be the collection of the $2^{q}$ such sets $I$, then
$|\mathcal{I}|\leq 2^{O(M|T|^{2}/s)}$. Observe that every element of
$\mathcal{I}$ is an independent set, and $\mathcal{I}$ contains every
_maximal_ independent set of $G$ (with respect to containment). Therefore, in
the proof of Theorem 2.1, instead of working with the collection of containers
$\mathcal{C}$, one can work with $\mathcal{I}$ directly. However, this does
not effect the quantitative bounds in Theorem 2.1.

Acknowledgements. We would like to thank János Pach and Gábor Tardos for their
valuable remarks.

## References

  * [1] A. Akopyan. “On point coverings of boxes in $\mathbb{R}^{d}$.” arXiv preprint, arXiv:0706.3405, 2007.
  * [2] E. Asplund, and B. Grünbaum. “On a coloring problem.” Math. Scand. 8, 181–188, 1960.
  * [3] J. P. Burling. “On Coloring Problems of Families of Prototypes (PhD thesis).” University of Colorado, Boulder, 1965.
  * [4] M. Caoduro. “Packing and coloring r-bounded axis-parallel rectangles.” arXiv preprint, arXiv:2012.13201, 2020.
  * [5] P. Chalermsook, and B. Walczak. “Coloring and Maximum Weight Independent Set of Rectangles.” In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), 860–868, 2021.
  * [6] T. M. Chan, and S. Har-Peled. “Approximation algorithms for maximum independent set of pseudo-disks.” Discrete Comput. Geom. 48 (2), 373–392, 2012
  * [7] K. Chen, A. Dumitrescu. “On Wegner’s inequality for axis-parallel rectangles.” Discrete Math. 343 (12), 112091, 2020.
  * [8] M. Chudnovsky, S. Spirkl, and S. Zherbib. “Piercing Axis-Parallel Boxes.” The Electronic Journal of Combinatorics 25 (1), P1.70, 2018
  * [9] J. Correa, L. Feuilloley, P. Pérez-Lantero, and J. A. Soto. “Independent and Hitting Sets of Rectangles Intersecting a Diagonal Line: Algorithms and Complexity.” Discrete Comput. Geom. 53, 344–365, 2015.
  * [10] J. Eckhoff. “A survey of the Hadwiger-Debrunner $(p,q)$-problem.” Discrete Comput. Geom. 347–377; Algorithms and Combinatorics, Vol. 25, Springer, Berlin, 2003.
  * [11] D. Fon-Der-Flaass, and A. Kostochka. “Covering boxes by points.” Discrete mathematics, 120 (1-3), 269–275, 1993.
  * [12] A. Gyárfás, and J. Lehel. “Covering and coloring problems for relatives of intervals.” Discrete Math. 55 (2), 167–180, 1985.
  * [13] A. Hajnal, and J. Surányi. “Über die Auflösung von Graphen in vollständige Teilgraphen.” Ann. Univ. Sci. Budapest, Eötvös Sect. Math 1, 113–121, 1958.
  * [14] Gy. Károlyi. “On point covers of parallel rectangles.” Periodica Mathematica Hungarica 23.2, 105–107, 1991.
  * [15] D. J. Kleitman, and K. J. Winston. “On the number of graphs without 4-cycles.” Discrete Math., 6: 167–172, 1982.
  * [16] D. Larman, J. Matoušek, J. Pach, and J. Törőcsik. “A Ramsey-type result for convex sets.” Bull. Lond. Math. Soc., 26: 132–136, 1994.
  * [17] F. Nielsen. “Fast stabbing of boxes in high dimensions.” Theoretical Computer Science 246 (1-2), 53–72, 2000.
  * [18] J. Pach, and G. Tardos. “Tight lower bounds for the size of epsilon-nets.” Journal of Amer. Math. Soc. 26 (3), 645–658, 2012.
  * [19] B. Reed, and D. Allwright. “Painting the office.” MICS Journal 1, 1–8, 2008.
  * [20] A. Sapozhenko. “Systems of containers and enumeration problems.” Stochastic Algorithms: Foundations and Applications, Springer Berlin Heidelberg, 1–13, 2005.
  * [21] I. Tomon. “String graphs have the Erdős-Hajnal property.” arXiv preprint, arXiv:2002.10350, 2020.
  * [22] G. Wegner. “Über eine kombinatorisch-geometrische Frage von Hadwiger und Debrunner.” Israel J. Math. 3, 187–198, 1965.