heightadjust=all, floatrowsep=columnsep figureboxfigure[][] tableboxtable[][]

# TopoMLP: A Simple yet Strong Pipeline
for Driving Topology Reasoning

Dongming Wu1 , Jiahao Chang2⋆, Fan Jia3, Yingfei Liu3, Tiancai Wang3‡,
Jianbing Shen4†
1 Beijing Institute of Technology, 2 University of Science and Technology of
China,
3 MEGVII Technology, 4 SKL-IOTSC, University of Macau
{wudongming97<EMAIL_ADDRESS><EMAIL_ADDRESS>
This work was done during internship at MEGVII. ‡Project leader.
†Corresponding author: Jianbing Shen.

###### Abstract

Topology reasoning aims to comprehensively understand road scenes and present
drivable routes in autonomous driving. It requires detecting road centerlines
(lane) and traffic elements, further reasoning their topology relationship,
i.e., lane-lane topology, and lane-traffic topology. In this work, we first
present that the topology score relies heavily on detection performance on
lane and traffic elements. Therefore, we introduce a powerful 3D lane detector
and an improved 2D traffic element detector to extend the upper limit of
topology performance. Further, we propose TopoMLP, a simple yet high-
performance pipeline for driving topology reasoning. Based on the impressive
detection performance, we develop two simple MLP-based heads for topology
generation. TopoMLP achieves state-of-the-art performance on OpenLane-V2
benchmark, i.e., 41.2% OLS with ResNet-50 backbone. It is also the 1st
solution for 1st OpenLane Topology in Autonomous Driving Challenge. We hope
such simple and strong pipeline can provide some new insights to the
community. Code is at https://github.com/wudongming97/TopoMLP.

##  1 Introduction

Understanding the topology in road scenes is an important task for autonomous
driving, since it provides the information about the drivable region as well
as the traffic signal. Recently, the topology reasoning task has raised great
attention in the community thanks to its crucial application in ego planning
(Chai et al., 2020; Casas et al., 2021; Hu et al., 2023). In specific, given
multi-view images, topology reasoning aims to learn vectorized road graphs
between the centerlines and traffic elements (Li et al., 2023; Wang et al.,
2023). It consists of four primary tasks, centerline detection, traffic
element detection, lane-lane topology, and lane-traffic topology reasoning.

Different from the conventional perception pipelines that include multiple
independent tasks (Li et al., 2022b; Liu et al., 2023b), these four tasks
naturally have a logical order, i.e., first-detect-then-reason. If some lane
and traffic instances are not detected, the corresponding topology connection
will be missed, as illustrated in the right of Fig. 1. It naturally leads to a
question: What is the extent of the quantitative effect of basic detection on
topology reasoning? To answer this question, we conduct detailed ablation
studies on detection performance by varying the backbones. It shows that the
topology performances are constantly improved with stronger detection. When
the basic detection is freezed, we find that replacing the topology prediction
with the ground truth (GT) introduces minor improvements. For example, when
using Swin-B backbone, the TOPll and TOPlt scores with topology GT are 10.0%
and 30.9%, which are only higher than using topology prediction by 0.5% and
2.6%, respectively. This phenomenon encourages us to prioritize the design of
two detectors.

In specific, we employ two query-based detection branches: one (Liu et al.,
2023b) dedicated to the detection of 3D centerlines, and another one (Zhu et
al., 2021) for 2D traffic detection. The 3D lane detector utilizes a smooth
lane representation and interprets each lane query as a set of control points
of a Bézier curve. Inspired by MOTRv2 (Zhang et al., 2023), the performance of
2D traffic detector can be further enhanced by adding an additional YOLOv8
(optional) object detector thanks to its advantage on detecting small objects,
such as traffic lights.

Despite the basic detection, another challenge in driving topology reasoning
is how to effectively model the connection between lanes and traffic elements.
Prior works (Langenberg et al., 2019; Can et al., 2021; 2022) employ a
straightforward method, which uses a multi-layer perceptron (MLP) to predict
the topology relationship. However, they mainly focus on associating different
lanes in image domain. To cope with the 3D space, some follow-up methods (Li
et al., 2023; Xu et al., 2023) tend to utilize graph-based modeling to predict
topology structure.

In this paper, we develop a simple yet effective framework, termed TopoMLP,
for topology reasoning. Our work is inspired by the pairwise representation in
human-object interaction detection (Gao et al., 2018; Chao et al., 2018; Wang
et al., 2019), similar to topology reasoning. The pairwise representation is
constructed by encoding the human/object pair boxes into two mask embeddings.
These embeddings are concatenated together and further used to perform action
classification by a simple MLP. We wonder if it is possible to develop a
simple MLP-based framework for sufficiently understanding the relationships in
driving topology reasoning. Taking lane-lane topology as an example, if the
lanes are accurately predicted, the intersection points (see Fig. 2) between
lanes can be easily reasoned to be overlapped. As for the lane-traffic
topology, the traffic elements can be easily matched with the corresponding
centerlines by the relative location between traffic bounding boxes and lane
points. Therefore, a simple MLP seems enough for efficient topology reasoning.
Specifically, we convert the query representations of both traffic elements
and centerlines into two embeddings and concatenate them together for topology
classification by an appended MLP.

Moreover, we notice that the topology metrics of OpenLane-V2 have some
drawbacks. It uses graph-based mAP, while it focuses more on the order of
predictions. Some false positives from unmatched lanes or traffic elements are
defaulted to a high confidence score, i.e., 1.0. Accordingly, manually
decreasing the priority of these false positive predictions (or increasing the
priority of true positive predictions) enables to improve the overall mAP
score by a large margin. To tackle this problem, we suggest to include a
correctness factor based on existing topology metric to correct the drawback.

Our contributions are summarized as four-fold. First, we provide an in-depth
analysis of the nature of driving topology reasoning. It requires following a
“first-detect-then-reason” philosophy for better topology prediction. Second,
we propose a simple but strong model, named TopoMLP. It includes two well-
designed high-performance detectors and two elegant MLP networks with position
embedding for topology reasoning. Third, we claim that the current topology
reasoning evaluation possesses a significant loophole. To rectify this, we
enhance the topology metric by incorporating a correctness factor. Fourth, all
experiments are conducted on the popular driving topology reasoning benchmark,
OpenLane-V2, showing TopoMLP reaches state-of-the-art performance. Besides,
TopoMLP ranks 1st of 1st OpenLane Topology in Autonomous Driving Challenge.

Backbone | DETl | DETt | Topo GT | TOPll | TOPlt | OLS
---|---|---|---|---|---|---
ResNet-50 | 28.3 | 50.0 |  | 7.2 | 22.8 | 38.2
✓ | 7.5 (+0.3) | 24.4 (+1.6) | 38.3 (+0.1)
VOV | 29.7 | 52.1 |  | 7.9 | 25.6 | 40.1
✓ | 8.5 (+0.6) | 27.5 (+1.9) | 40.8 (+0.9)
Swin-B | 30.7 | 54.3 |  | 9.5 | 28.3 | 42.2
✓ | 10.0 (+0.5) | 30.9 (+2.6) | 43.1 (+0.9)
|  |  |  |  |  |

Figure 1: Left: The evaluation of topology when using ground-truth topology
(represented as “Topo GT”) to replace predicted topology while retaining the
detection results. Right: The illustration of how missing detections
(represented by dashed lines) influence topology reasoning. They uncover an
essential truth: the fundamental detections are paramount to the topology
reasoning.

##  2 Related Works

###  2.1 Lane Detection Method

For a long time, detecting lane markings has been one of the most important
topics in autonomous driving. Prior works usually use appearance and geometric
cues to detect the road (Tan et al., 2006; Alvarez & Ĺopez, 2010; Paz et al.,
2015). With the advancement of deep learning, the development of lane
detection has made great progress. Among them, some methods attempt to use a
segmentation map to describe road lane (Batra et al., 2019; Can et al., 2022;
He & Balakrishnan, 2022). Currently, vector-based methods have become
mainstream because they can deal well with 3D lane detection (Garnett et al.,
2019; Guo et al., 2020; Yan et al., 2022; Chen et al., 2022). However, these
methods base a set of predefined Y-axis points in the query to predict 3D
lanes, which fail to make the 3D lane prediction only across the Y axis. More
recently, TopoNet (Li et al., 2023) models each lane into an anchor query, but
it misses the lane prior with a smoothed curve. In our study, we make full use
of this prior to providing a smoother representation.

###  2.2 Lane Topology Learning

Learning lane topology plays an important role in scene understanding for
autonomous driving. Earlier works (Chu et al., 2019; Homayounfar et al., 2019;
He et al., 2020; Bandara et al., 2022) focus on generating road graphs from
aerial images. However, using aerial images is unreasonable for ongoing
vehicles. Therefore, directly using vehicle-mounted sensors to detect lane
topology has become popular due to their valuable application. STSU (Can et
al., 2021) uses a Transformer-based model to detect centerlines and objects
together, and then predict centerline association formatted to a directed
graph by an MLP. TopoRoad (Can et al., 2022) further introduces additional
minimal cycle queries to ensure the preservation of the order of
intersections. Can et al. (Can et al., 2023) also provide additional
supervision of the relationship by considering the centerlines as cluster
centers to assign objects and greatly improve the lane graph estimation.
LaneGAP (Liao et al., 2023) designs a heuristic-based algorithm to recover the
graph from a set of lanes. CenterLineDet (Xu et al., 2023) and TopoNet (Li et
al., 2023) regard centerlines as vertices and design a graph model to update
centerline topology. In this work, we focus on lane topology nature and employ
a simple and elegant position embedding to enhance topology modeling.

###  2.3 HD Map Perception

HD Map Perception aims to comprehend the layout of the driving scene, such as
lanelines, pedestrian crossing, and drivable areas, mirroring the concept of
driving scene reasoning. The recent research focuses on learning HD maps using
segmentation and vectorization techniques to meet low-cost requirements.
HDMapNet (Li et al., 2022a) explores grouping and vectorizing the segmented
map with complicated post-processings. VectorMapNet (Liu et al., 2023a)
directly uses a sequence of points to represent each map element, further
decoding laneline locations. Some follow-up methods propose different modeling
strategies to represent the sequence of points, such as the permutation-based
(Liao et al., 2022), the piecewise Bézier curve (Qiao et al., 2023), the
pivot-based map (Ding et al., 2023). Different from the aforementioned
approaches, our method employs simple and elegant modeling, each query
referring to a lane.

##  3 Method

Figure 2: The overall architecture of TopoMLP. The lane decoder depicts each
centerline as a Bézier curve for a smooth representation. The traffic decoder
is optionally enhanced by additional YOLOv8 proposals. The prediction of lane-
traffic (LT) and lane-lane (LL) topology is accomplished by an MLP with
position embedding. “Topology” means an operation in § 3.3.

In this section, we elaborate on TopoMLP, a unified query-based framework for
driving topology reasoning. It is able to effectively accomplish four
different tasks in a single framework, including lane detection, traffic
element detection, lane-lane topology, and lane-traffic topology prediction.
The overall pipeline of TopoMLP is shown in Fig. 2. More details are described
as follows.

###  3.1 Lane Detector

Our lane detector is inspired by the advanced 3D multi-view object detector
PETR (Liu et al., 2022; 2023b), which first introduces 3D position embedding
(3D PE) into the query-based framework DETR (Carion et al., 2020; Zhu et al.,
2021). In this work, we represent each centerline as a smooth Bézier curve
with $M$ control points within 3D space and each curve refers to a lane query.
Our lane detector performs direct interaction between lane queries with multi-
view visual features in transformer decoder and outputs control points,
further transformed to lane coordinates.

Formally, given multi-view images from camera sensors, we first employ a
backbone (e.g., ResNet-50 (He et al., 2016)) to generate feature maps
$\bm{F}\\!\in\\!\mathbb{R}^{V\times C\times H\times W}$, where $V$, $C$, $H$,
and $W$ represent the view number, channel, height, and width of the features,
respectively. The 3D PE is encoded into the visual features to generate
position-aware features following (Liu et al., 2022). Then we initialize
$N_{L}$ learnable 3D lane anchor points, denoted as
$\bm{Q}^{L}\\!\in\\!\mathbb{R}^{N_{L}\times 3}$. After projecting the feature
dimension of anchor points from $3$ to $C$ using a position encoding and a
linear layer, we further feed it into transformer decoder to update the lane
query features $\hat{\bm{Q}}^{L}$:

$\hat{\bm{Q}}^{L}=\textbf{LaneDecoder}(\bm{F},\textbf{Linear}(\bm{Q}^{L}))\\!\in\\!\mathbb{R}^{N_{L}\times
C}.$ (1)

where the LaneDecoder is a stack of Transformer decoder layers. On top of the
transformer decoder, we adopt two independent MLPs to predict the offset of
control points and the classification scores, respectively. The final control
point outputs are ordered and obtained by adding basic anchor points with the
relative offsets. The control points are transformed into lane points for
training and testing.

###  3.2 Traffic Element Detector

The prevalent approaches for traffic element detection in driving topology
reasoning are mainly query-based and end-to-end deployed (Li et al., 2023;
Kalfaoglu et al., 2023; Lu et al., 2023). Although such straightforward end-
to-end implementation is appealing, the detection performance is much inferior
to the specialized 2D detectors, such as YOLO series, due to small objects and
class imbalance problems. To address these limitations, we propose to
optionally improve the query-based detectors by elegantly incorporating an
extra object detector YOLOv8.

Our traffic element detector typically follows the head design in Deformable
DETR (Zhu et al., 2021) to predict bounding boxes and classification scores.
It adopts query embeddings to generate a set of reference points as anchors.
We modify the reference format into reference boxes with the center points,
height, and width. As an alternative, the high-quality proposals from YOLOv8
can serve as an anchor box initialization, providing better local priors. It
greatly eases the trade-off between topology reasoning and traffic detection.

Specifically, we first collect the multi-scale feature maps of the front view
from multi-view features $\bm{F}$, denoted as $\bm{F}^{0}$. YOLOv8 takes
$\bm{F}^{0}$ as input and generates multiple proposals, which are concatenated
with a set of reference boxes produced from randomized queries, denoted as
$\bm{R}^{T}$. The generated boxes by YOLOv8 are encoded by sine-cosine
embedding to generate query features, which are concatenated with the
randomized queries, denoted as $\bm{Q}^{T}$. The query features as well as the
reference boxes are fed into the deformable decoder:

$\hat{\bm{Q}}^{T}=\textbf{TrafficDecoder}(\bm{F}^{0},\bm{Q}^{T},\bm{R}^{T})\\!\in\\!\mathbb{R}^{N_{T}\times
C},$ (2)

where the TrafficDecoder is a stack of Deformable decoder layers. Based on the
decoded traffic features $\hat{\bm{Q}}^{T}$, we implement two independent MLPs
for bounding box classification and regression.

###  3.3 Lane-Lane Topology Reasoning

Lane-lane topology reasoning branch aims to predict the lane-lane connection
relationship. To incorporate the discriminative lane information, we integrate
the predicted lane points into the lane query features. In specific, we
implement MLP to embed the lane coordinates and then add them into the decoded
lane query features
$\hat{\bm{Q}}^{L}\\!\in\\!\mathbb{R}^{N_{L}\\!\times\\!C}$. For notion
simplicity, we still use $\hat{\bm{Q}}^{L}$ to represent the integrated query
features. They are repeated $N_{L}$ times, generating two features with sizes
$N_{L}\\!\times\\!(N_{L})\\!\times\\!C$ and
$(N_{L})\\!\times\\!N_{L}\\!\times\\!C$, where $(N_{L})$ defines different
repeating directions. After concatenation operation generating
$\hat{\bm{Q}}^{LL}\\!\in\\!\mathbb{R}^{N_{L}\times N_{L}\times 2C}$, we apply
MLP to perform binary classification:

$\bm{G}^{LL}=\textbf{MLP}(\hat{\bm{Q}}^{LL})\\!\in\\!\mathbb{R}^{N_{L}\times
N_{L}},$ (3)

where the $\bm{G}^{LL}$ is lane-lane topology prediction.

###  3.4 Lane-Traffic Topology Reasoning

The key idea of our lane-traffic topology reasoning is to project two kinds of
features into the same space. Given the lane query embedding
$\hat{\bm{Q}}^{L}\\!\in\\!\mathbb{R}^{N_{L}\times C}$ from 3D space, we sum
the view transformation matrix $\bm{A}\\!\in\\!\mathbb{R}^{3\times 3}$ from 3D
to perspective view with it, i.e., $\hat{\bm{Q}}^{L}+\text{MLP}(\bm{A})$.
Here, the view transformation matrix $\bm{A}$ is formulated in terms of camera
intrinsic and extrinsic. Similar to lane-lane topology, the transformed lane
query features and the traffic query embedding
$\hat{\bm{Q}}^{T}\\!\in\\!\mathbb{R}^{N_{T}\times C}$ are transformed into
$\hat{\bm{Q}}^{LT}\\!\in\\!\mathbb{R}^{N_{L}\\!\times\\!N_{T}\times 2C}$
through repeating and concatenating operations. An MLP network is used to
generate lane-traffic topology prediction $\bm{G}^{LT}$:

$\bm{G}^{LT}=\textbf{MLP}(\hat{\bm{Q}}^{LT})\\!\in\\!\mathbb{R}^{N_{L}\times
N_{T}}.$ (4)

###  3.5 Loss Function

Our final loss function is defined as follows:

$\mathcal{L}=\mathcal{L}_{det_{l}}+\mathcal{L}_{det_{t}}+\mathcal{L}_{top_{ll}}+\mathcal{L}_{top_{lt}},$
(5)

where $\mathcal{L}_{det_{l}}$ is lane detection loss, which includes a focal
loss (Lin et al., 2017) supervising classification and an L1 loss for lane
regression. $\mathcal{L}_{det_{t}}$ is traffic element detection loss, which
has a focal loss for classification, a $\mathcal{L}_{1}$ loss and a GIoU loss
for bounding box regression. The lane-lane topology loss
$\mathcal{L}_{top_{ll}}$ contains a focal loss for binary classification and
an L1 loss between the matched lane points in terms of the topology ground-
truth. The lane-traffic topology loss $\mathcal{L}_{top_{lt}}$ is a focal loss
for binary classification. Since our TopoMLP is a query-based method, it
requires the matching between the predictions and ground-truth. In this work,
we only use bipartite matching on the basic lane and traffic element
detection. The matching is directly used in topology reasoning loss as well.

##  4 Experiments

###  4.1 Dataset and Metric

Dataset. The experiments are conducted on the OpenLane-V2 (Wang et al., 2023).
OpenLane-V2 is a large-scale perception and reasoning dataset for scene
structure in autonomous driving. It has two subsets, i.e. $subset\\_A$ and
$subset\\_B$, developed from Argoverse 2 (Wilson et al., 2021) and nuScenes
(Caesar et al., 2020), respectively. Each subset comprises 1,000 scenes with
annotations at 2$Hz$. Note that the $subset\\_A$ contains seven views and
$subset\\_B$ contains six views.

Evaluation Metric. These two basic detections require measuring instance-level
performance. Therefore, the perception metrics, including $\text{DET}_{l}$ and
$\text{DET}_{t}$, are mean average precision (mAP) following the work (Wang et
al., 2023). Specifically, $\text{DET}_{l}$ employs the Fréchet distance for
quantifying similarity and is averaged over match thresholds set at {1.0, 2.0,
3.0}. On the other hand, $\text{DET}_{t}$ employs Intersection over Union
(IoU) as the similarity measure, with averages calculated over various traffic
categories. For topology metrics, the TOP score also employs an mAP metric,
which is designed specifically for graph data. To summarize the overall effect
of primary detection and topology reasoning, the OpenLane-V2 Score (OLS) is
conducted as:

$\text{OLS}=\frac{1}{4}[\text{DET}_{l}+\text{DET}_{t}+f(\text{TOP}_{ll})+f(\text{TOP}_{lt})],$
(6)

where $f$ is the square root function.

Method | Backbone | Epoch | DETl | DETt | TOPll | TOPlt | OLS
---|---|---|---|---|---|---|---
STSU (Can et al., 2021) | ResNet-50 | 24 | 12.7 | 43.0 | 0.5 | 15.1 | 25.4
VectorMapNet (Liu et al., 2023a) | ResNet-50 | 24 | 11.1 | 41.7 | 0.4 | 5.9 | 20.8
MapTR (Liao et al., 2022) | ResNet-50 | 24 | 17.7 | 43.5 | 1.1 | 10.4 | 26.0
TopoNet (Li et al., 2023) | ResNet-50 | 24 | 28.5 | 48.1 | 4.1 | 20.8 | 35.6
TopoMLP | ResNet-50 | 24 | 28.3 | 50.0 | 7.2 | 22.8 | 38.2
TopoMLP* | ResNet-50 | 24 | 28.8 | 53.3 | 7.8 | 30.1 | 41.2
TopoMLP | VOV | 24 | 29.7 | 52.1 | 7.9 | 25.6 | 40.1
TopoMLP | Swin-B | 24 | 30.7 | 54.3 | 9.5 | 28.3 | 42.2
TopoMLP* | Swin-B | 24 | 30.0 | 55.8 | 9.4 | 31.7 | 43.3
TopoMLP | Swin-B | 48 | 32.5 | 53.5 | 11.9 | 29.4 | 43.7
|  |  |  |  |  |  |

Table 1: Performance comparison with state-of-the-art methods on OpenLane-V2
$subset\\_A$ set. Results for existing methods are from TopoNet. TopoMLP is
trained end-to-end, while ‘*’ indicates using extra YOLOv8 proposals. The best
is in bold.

Method | Backbone | Epoch | DETl | DETt | TOPll | TOPlt | OLS
---|---|---|---|---|---|---|---
STSU (Can et al., 2021) | ResNet-50 | 24 | 8.2 | 43.9 | 0.0 | 9.4 | 21.2
VectorMapNet (Liu et al., 2023a) | ResNet-50 | 24 | 3.5 | 49.1 | 0.0 | 1.4 | 16.3
MapTR (Liao et al., 2022) | ResNet-50 | 24 | 15.2 | 54.0 | 0.5 | 6.1 | 25.2
TopoNet (Li et al., 2023) | ResNet-50 | 24 | 24.3 | 55.0 | 2.5 | 14.2 | 33.2
TopoMLP | ResNet-50 | 24 | 26.6 | 58.3 | 7.6 | 17.8 | 38.7
TopoMLP | VOV | 24 | 29.6 | 62.2 | 8.9 | 20.5 | 41.7
TopoMLP | Swin-B | 24 | 32.3 | 65.5 | 10.5 | 23.2 | 44.6
|  |  |  |  |  |  |

Table 2: Performance comparison with state-of-the-art methods on OpenLane-V2
$subset\\_B$ set. Results for existing methods are from TopoNet.

###  4.2 Implementation Details

Feature Extractor. All images are resized into the same resolution of
1550$\times$2048, and are downsampled with a ratio of 0.5. We implement
different backbones, i.e., ResNet-50 (He et al., 2016), VOV (Lee et al.,
2019), and Swin-B (Liu et al., 2021) for feature extraction. The number of
output channels is set to $C\\!=\\!256$. For lane detection, the C5 feature is
upsampled and fused with C4 feature using FPN. For traffic detection, the C3,
C4, and C5 features are used as the feature pyramid.

Lane Detector. The lane query number is set to $N_{L}\\!=\\!300$, and the
number of control points is 4. During training, the control points are
transformed into 11 lane points for calculating loss. We set the region to
$[-51.2m,51.2m]$ on the X-axis, $[-25.6m,25.6m]$ on the Y-axis, and $[-8m,4m]$
on the Z-axis. The lane detection head is composed of 6 transformer decoder
layers. The MLP heads contain two fully connected layers with ReLU activation.
For lane detection loss $\mathcal{L}_{det_{l}}$, the weight of the
classification part is 1.5, and the weight of the regression part is 0.2.

Figure 3: Qualitative results for lane detection and lane-lane topology of
TopoMLP. Given the multi-view images, our method can predict the most lanes
and connect them correctly under various challenges, like occluded lanes and
complicated intersections. The green lanes are ground-truth and the red lanes
are predictions, which are projected into images and BEV map.

Traffic Detector. The decoder architecture follows the original designs of
Deformable DETR (Zhu et al., 2021). The number of random queries in the
traffic decoder is 100. The detection results from YOLOv8111The official codes
we adopt are available at https://github.com/ultralytics/ultralytics. are
stored in advance. The weight of the classification loss is 1.0, the weight of
L1 loss is 2.5, and the weight of GIoU loss is 1.0.

Topology Head. The MLP network used in two topology heads consists of three
linear layers with ReLU activation. We represent the lane-lane topology loss
with L1 loss and classification loss as
$\mathcal{L}_{top_{ll}}\\!=\\!\lambda_{L1}\mathcal{L}_{L1}+\lambda_{cls}\mathcal{L}_{cls}$,
where $\lambda_{L1}=0.1$ and $\lambda_{cls}=5$. The loss coefficient of lane-
traffic topology loss $\mathcal{L}_{top_{ll}}$ is 0.5.

Training and Inference. The overall model TopoMLP is trained by AdamW
optimizer (Loshchilov & Hutter, 2017) with a weight decay of 0.01. The
learning rate is initialized with 2.0$\times 10^{-4}$ and decayed with cosine
annealing policy (Loshchilov & Hutter, 2016). We adopt the HSV augmentation
and grid mask strategy for training. All the experiments are trained for 24
epochs on 8 Tesla A100 GPUs with a batch size of 8 if not specified. During
the inference time, our model outputs at most 300 lanes for evaluation. Other
post-processing techniques are not implemented.

###  4.3 State-of-the-art Comparison

We compare TopoMLP with the state-of-the-art approaches, such as STSU (Can et
al., 2021), VectorMapNet (Liu et al., 2023a), MapTR (Liao et al., 2022),
TopoNet (Li et al., 2023). Table 1 shows the results on $subset\\_A$ of
OpenLane-V2. Without bells and whistles, our method achieves 38.2 OLS using
ResNet-50 backbone, surpassing other state-of-the-art methods. Compared to
TopoNet, our approach shows a much better topology reasoning accuracy (7.2
v.s. 4.1 on TOPll, 22.8 v.s. 20.8 on TOPlt) while also achieves decent
detection accuracy (28.3 v.s. 28.5 on DETl, 50.0 v.s. 48.1 on DETt). For a
better performance, we apply a more powerful backbone and more training time:
when using Swin-B for training 48 epochs, the OLS score rises to 43.7.

Table 2 shows the performance comparison on OpenLane-V2 $subset\\_B$. Our
proposed TopoMLP exceeds other models in all metrics when using the same
ResNet-50 backbone. Particularly in terms of topology performance, it
surpasses TopoNet by a large margin (7.6 v.s. 2.5 on TOPll, 17.8 v.s. 14.2 on
TOPlt). Moreover, the performance boost is also observed when integrating more
powerful backbones. Overall, these results significantly highlight the
efficacy of our TopoMLP model.

###  4.4 Ablation Study

In this section, we study several important components of our method and
conduct ablation experiments on OpenLane-V2 $subset\\_A$.

Analysis on Lane Detection. We investigate the effect of different settings in
lane detection. i) In Table 3(d) (a), the improvement in lane detection and
lane-lane topology performance is clear when the lane query increases from 200
to 300. However, it is observed that any further increase does not contribute
to additional improvement. To balance the model efficiency and performance,
the number of lane query is set to 300. ii) Table 3(d) (b) illustrates the
influence of a control point in Bézier modeling. Empirically, we choose 4
control points for better performance.

YOLOv8 Proposal on Traffic Detection. To study the benefit of using YOLOv8
proposals, we test its effect under two settings: using ResNet-50 and Swin-B
backbone. The main results are shown in Table 1, marked by “*”. It is well
seen that using YOLOv8 predictions as proposal queries consistently improves
the detection performance, indicating the effectiveness of YOLOv8 proposals.
Moreover, it is worth noticing that TopoMLP without YOLOv8 still achieves
higher traffic detection scores than other counterparts.

Representation Way in Topology Reasoning. It is also of interest to analyze
the impact of different lane and traffic element representation methods in
topology reasoning. i) We first analyze the lane representation in lane-lane
topology, which additionally integrates lane coordinates. As shown in Table
3(d) (c), removing it leads to a minor performance degradation on TOPll, which
indicates that the explicit lane position is useful for topology reasoning.
Moreover, abandoning L1 loss for intersection point supervision also causes a
score decrease. ii) Table 3(d) (d) explores the impact of incorporating the
view transformation matrix into the lane feature for lane-traffic topology. It
suggests that the integration of this matrix into lane representation improves
the reasoning of lane-traffic topology (22.8 v.s. 21.4 on TOPlt). iii) Using
the bounding boxes of traffic elements to replace traffic features results in
a drop on TOPlt (22.8 v.s. 22.0), as shown in the last row of Table 3(d) (d).
This is because only adopting boxes lacks category information. Despite the
advantages of position embedding, a single MLP network proves sufficient for
achieving high-performance topology reasoning.

Figure 4: Traffic detection and lane-traffic topology from TopoMLP. Our method
can detect the traffic elements in the front view and associate them with
lanes. The green represents GT, while the red means our prediction. Traffic
predictions are grounded by different colors in terms of category.  Table 3:
The ablation studies of different components in the proposed TopoMLP. The
experiments are conducted on OpenLane-V2 $subset\\_A$. We bold the best
scores.

Lane Queries | DETl | DETt | TOPll | TOPlt | OLS
---|---|---|---|---|---
200 | 28.2 | 49.9 | 6.1 | 20.2 | 36.9
300 | 28.3 | 50.0 | 7.2 | 22.8 | 38.2
500 | 27.9 | 49.6 | 7.3 | 22.4 | 38.0
|  |  |  |  |
(a) Different number of lane queries.

Control Points | DETl | DETt | TOPll | TOPlt | OLS
---|---|---|---|---|---
3 | 26.6 | 49.9 | 7.0 | 21.5 | 37.3
4 | 28.3 | 50.0 | 7.2 | 22.8 | 38.2
5 | 27.8 | 48.5 | 6.6 | 21.5 | 37.1
|  |  |  |  |
(b) Different number of control points.

LL Topo | DETl | DETt | TOPll | TOPlt | OLS
---|---|---|---|---|---
Ours | 28.3 | 50.0 | 7.2 | 22.8 | 38.2
w/o position | 27.9 | 50.9 | 6.9 | 21.6 | 37.9
w/o L1 loss | 26.6 | 50.9 | 6.5 | 22.1 | 37.5
|  |  |  |  |
(c)  LL Topo is the short name for lane-lane topology. “ w/o position” means
removing lane coordinate embedding. “w/o L1 loss” means removing the
supervision of interaction points.

LT Topo | DETl | DETt | TOPll | TOPlt | OLS
---|---|---|---|---|---
Ours | 28.3 | 50.0 | 7.2 | 22.8 | 38.2
w/o transform | 28.4 | 49.3 | 7.2 | 21.4 | 37.7
w only box | 28.2 | 49.6 | 7.1 | 22.0 | 37.8
|  |  |  |  |
(d)  LT Topo is the short name for lane-traffic topology. “transform” means
using view transformation matrix on lane feature. “only box” means using
bounding box as traffic representation.

###  4.5 Visualization

We visualize the lane detection and lane-lane topology reasoning results in
Fig. 3 by projecting 3D lanes into images. Despite potential challenges like
intricate intersections or occluded centerlines, TopoMLP well predicts the
centerlines and constructs a lane graph in BEV. Fig. 4 displays the results of
traffic detection as well as lane-traffic topology reasoning. As clearly
shown, TopoMLP identifies the majority of traffic elements, even small
objects, and allocates them to the appropriate lanes.

###  4.6 More Discussion

Before stepping into our thorough analysis, let’s revisit the definition of
the topology metric. Given the ground-truth graph $G\\!=\\!(V,E)$ and the
predicted one $\hat{G}\\!=\\!(\hat{V},\hat{E})$, we establish a projection on
the vertices such that $V\\!=\\!\hat{V}^{\prime}\\!\subseteq\\!\hat{V}$. This
projection utilizes the Fréchet and IoU distances to measure similarity among
lane centerlines and traffic elements respectively. Within the predicted
$\hat{V}^{\prime}$, we consider two vertices as being connected if the
confidence of the edge surpasses 0.5. Subsequently, the TOP score is derived
by averaging vertice mAP between $(V,E)$ and
$(\hat{V}^{\prime},\hat{E}^{\prime})$ overall all vertices:

$\text{TOP}=\frac{1}{|V|}\sum_{v\in
V}\frac{\sum_{\hat{n}^{\prime}\in\hat{N}^{\prime}(v)}P(\hat{n}^{\prime})\displaystyle\bm{1}_{\mathrm{condition}}(\hat{n}^{\prime}\in
N(v))}{|N(v)|},$ (7)

where $N(v)$ is the ordered list of neighbors of vertex $v$ ranked by
confidence and $P(v)$ is the precision of the $i$-th vertex $v$ in the ordered
list.

Figure 5: The illustration of loophole on TOP metric. Enhancing the prediction
scores leads to true positives prior to some false positives from unmatched
instances, further improving precision.

|  |  | Original Prediction |  Enhanced Prediction
---|---|---|---|---
Method | DETl | DETt | TOPll | TOPlt | OLS | TOPll | TOPlt | OLS
TopoNet (Li et al., 2023) | 27.1 | 44.8 | 4.0 | 20.6 | 34.4 | 11.5(+7.5) | 21.6(+1.0) | 38.1(+3.7)
TopoMLP (Ours) | 28.3 | 50.0 | 7.2 | 22.8 | 38.2 | 19.0(+11.8) | 23.4(+0.6) | 42.2(+4.0)
Method | DETl | DETt | TOP${}_{ll}^{\dagger}$ | TOP${}_{lt}^{\dagger}$ | OLS† | TOP${}_{ll}^{\dagger}$ | TOP${}_{lt}^{\dagger}$ | OLS†
TopoNet (Li et al., 2023) | 27.1 | 44.8 | 2.0 | 20.4 | 32.8 | 1.0 | 20.9 | 32.0
TopoMLP (Ours) | 28.3 | 50.0 | 4.5 | 22.1 | 36.3 | 1.9 | 22.5 | 34.5
|  |  |  |  |  |  |  |

Table 4: The comparison on the original TOP metric and our adjusted TOP
(marked by $\dagger$) when using enhanced prediction or not. TopoNet is
reimplemented by ours using the same backbone ResNet-50 with our TopoMLP. The
experiments are conducted on OpenLane-V2 $subset\\_A$.

We provide a toy example of the important loophole in Fig. 5. A crucial point
hinges on the precision of the ordered list. For those unmatched instances
that our detector cannot identify, their confidence scores are defaulted to
1.0. That is, there are lots of false positives with high confidence. Suppose
we push the prediction confidence into 1.0/0.0 in terms of 0.5, our prediction
with true positives will have a higher confidence, hence, leading to enhanced
precision. The quantitative results are shown in the first two rows of Table
4. Using this strategy to enhance prediction leads to consistent performance
improvement, including TopoNet and our method TopoMLP.

To tackle this issue, we suggest a novel TOP metric incorporated with a
correctness factor. Let’s symbolize the enhanced precision as
$P(v)^{\dagger}$. The adjusted TOP metric $\text{TOP}^{\dagger}$ is formulated
as:

$\text{TOP}^{\dagger}=\frac{1}{|V|}\sum_{v\in
V}\frac{\sum_{\hat{n}^{\prime}\in\hat{N}^{\prime}(v)}P(\hat{n}^{\prime})\displaystyle\bm{1}_{\mathrm{condition}}.(\hat{n}^{\prime}\in
N(v))\frac{N_{TP}}{(N_{TP}+N_{FP})}}{|N(v)|},$ (8)

where $N_{TP}$ is the number of true positives and $N_{FP}$ is the number of
false positives. In the last two rows of Table 4, we evaluate TopoNet and
TopoMLP on the adjusted topology metric, demonstrating its capability to
effectively shield against the “attack”. Despite the alteration in the metric,
TopoMLP still surpasses other methods such as TopoNet in performance.

##  5 Conclusion

In this paper, we propose a simple yet strong pipeline for driving scene
topology, named TopoMLP. It starts a significant observation that the
reasoning performance is limited by the detection scores. Therefore, we first
focus on designing two powerful detectors for 3D lane detection and 2D traffic
detection, respectively. As for topology reasoning, combining the appreciated
position embedding and an elegant MLP network is enough to achieve impressive
performance. TopoMLP is the 1st solution for 1st OpenLane Topology in
Autonomous Driving Challenge. We hope our work opens up new insights into
exploring driving topology reasoning.

## References

  * Alvarez & Ĺopez (2010) José M Álvarez Alvarez and Antonio M Ĺopez.  Road detection based on illuminant invariance.  _IEEE T-ITS_ , 2010.
  * Bandara et al. (2022) Wele Gedara Chaminda Bandara, Jeya Maria Jose Valanarasu, and Vishal M Patel.  Spin road mapper: Extracting roads from aerial images via spatial and interaction space graph reasoning for autonomous driving.  In _ICRA_ , 2022.
  * Batra et al. (2019) Anil Batra, Suriya Singh, Guan Pang, Saikat Basu, CV Jawahar, and Manohar Paluri.  Improved road connectivity by joint learning of orientation and segmentation.  In _CVPR_ , 2019.
  * Caesar et al. (2020) Holger Caesar, Varun Bankiti, Alex H Lang, Sourabh Vora, Venice Erin Liong, Qiang Xu, Anush Krishnan, Yu Pan, Giancarlo Baldan, and Oscar Beijbom.  nuscenes: A multimodal dataset for autonomous driving.  In _CVPR_ , 2020.
  * Can et al. (2021) Yigit Baran Can, Alexander Liniger, Danda Pani Paudel, and Luc Van Gool.  Structured bird’s-eye-view traffic scene understanding from onboard images.  In _ICCV_ , 2021.
  * Can et al. (2022) Yigit Baran Can, Alexander Liniger, Danda Pani Paudel, and Luc Van Gool.  Topology preserving local road network estimation from single onboard camera image.  In _CVPR_ , 2022.
  * Can et al. (2023) Yigit Baran Can, Alexander Liniger, Danda Pani Paudel, and Luc Van Gool.  Improving online lane graph extraction by object-lane clustering.  In _ICCV_ , 2023.
  * Carion et al. (2020) Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko.  End-to-end object detection with transformers.  In _ECCV_ , 2020.
  * Casas et al. (2021) Sergio Casas, Abbas Sadat, and Raquel Urtasun.  Mp3: A unified model to map, perceive, predict and plan.  In _CVPR_ , 2021.
  * Chai et al. (2020) Yuning Chai, Benjamin Sapp, Mayank Bansal, and Dragomir Anguelov.  Multipath: Multiple probabilistic anchor trajectory hypotheses for behavior prediction.  In _CoRL_ , 2020.
  * Chao et al. (2018) Yu-Wei Chao, Yunfan Liu, Xieyang Liu, Huayi Zeng, and Jia Deng.  Learning to detect human-object interactions.  In _WACV_ , 2018.
  * Chen et al. (2022) Li Chen, Chonghao Sima, Yang Li, Zehan Zheng, Jiajie Xu, Xiangwei Geng, Hongyang Li, Conghui He, Jianping Shi, Yu Qiao, et al.  Persformer: 3d lane detection via perspective transformer and the openlane benchmark.  In _ECCV_ , 2022.
  * Chu et al. (2019) Hang Chu, Daiqing Li, David Acuna, Amlan Kar, Maria Shugrina, Xinkai Wei, Ming-Yu Liu, Antonio Torralba, and Sanja Fidler.  Neural turtle graphics for modeling city road layouts.  In _ICCV_ , 2019.
  * Ding et al. (2023) Wenjie Ding, Limeng Qiao, Xi Qiu, and Chi Zhang.  Pivotnet: Vectorized pivot learning for end-to-end hd map construction.  In _ICCV_ , 2023.
  * Gao et al. (2018) Chen Gao, Yuliang Zou, and Jia-Bin Huang.  ican: Instance-centric attention network for human-object interaction detection.  In _BMVC_ , 2018.
  * Garnett et al. (2019) Noa Garnett, Rafi Cohen, Tomer Pe’er, Roee Lahav, and Dan Levi.  3d-lanenet: end-to-end 3d multiple lane detection.  In _ICCV_ , 2019.
  * Guo et al. (2020) Yuliang Guo, Guang Chen, Peitao Zhao, Weide Zhang, Jinghao Miao, Jingao Wang, and Tae Eun Choe.  Gen-lanenet: A generalized and scalable approach for 3d lane detection.  In _ECCV_ , 2020.
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _CVPR_ , 2016.
  * He & Balakrishnan (2022) Songtao He and Hari Balakrishnan.  Lane-level street map extraction from aerial imagery.  In _WACV_ , 2022.
  * He et al. (2020) Songtao He, Favyen Bastani, Satvat Jagwani, Mohammad Alizadeh, Hari Balakrishnan, Sanjay Chawla, Mohamed M Elshrif, Samuel Madden, and Mohammad Amin Sadeghi.  Sat2graph: Road graph extraction through graph-tensor encoding.  In _ECCV_ , 2020.
  * Homayounfar et al. (2019) Namdar Homayounfar, Wei-Chiu Ma, Justin Liang, Xinyu Wu, Jack Fan, and Raquel Urtasun.  Dagmapper: Learning to map by discovering lane topology.  In _ICCV_ , 2019.
  * Hu et al. (2023) Yihan Hu, Jiazhi Yang, Li Chen, Keyu Li, Chonghao Sima, Xizhou Zhu, Siqi Chai, Senyao Du, Tianwei Lin, Wenhai Wang, et al.  Planning-oriented autonomous driving.  In _CVPR_ , 2023.
  * Kalfaoglu et al. (2023) M Kalfaoglu, Halil Ibrahim Ozturk, Ozsel Kilinc, and Alptekin Temizel.  Topomask: Instance-mask-based formulation for the road topology problem via transformer-based architecture.  _arXiv preprint arXiv:2306.05419_ , 2023.
  * Langenberg et al. (2019) Tristan Langenberg, Timo Lüddecke, and Florentin Wörgötter.  Deep metadata fusion for traffic light to lane assignment.  _IEEE RA-L_ , 2019.
  * Lee et al. (2019) Youngwan Lee, Joong-won Hwang, Sangrok Lee, Yuseok Bae, and Jongyoul Park.  An energy and gpu-computation efficient backbone network for real-time object detection.  In _CVPRW_ , 2019.
  * Li et al. (2022a) Qi Li, Yue Wang, Yilun Wang, and Hang Zhao.  Hdmapnet: An online hd map construction and evaluation framework.  In _ICRA_ , 2022a.
  * Li et al. (2023) Tianyu Li, Li Chen, Huijie Wang, Yang Li, Jiazhi Yang, Xiangwei Geng, Shengyin Jiang, Yuting Wang, Hang Xu, Chunjing Xu, Junchi Yan, Ping Luo, and Hongyang Li.  Graph-based topology reasoning for driving scenes.  _arXiv preprint arXiv:2304.05277_ , 2023.
  * Li et al. (2022b) Zhiqi Li, Wenhai Wang, Hongyang Li, Enze Xie, Chonghao Sima, Tong Lu, Yu Qiao, and Jifeng Dai.  Bevformer: Learning bird’s-eye-view representation from multi-camera images via spatiotemporal transformers.  In _ECCV_ , 2022b.
  * Liao et al. (2022) Bencheng Liao, Shaoyu Chen, Xinggang Wang, Tianheng Cheng, Qian Zhang, Wenyu Liu, and Chang Huang.  Maptr: Structured modeling and learning for online vectorized hd map construction.  _arXiv preprint arXiv:2208.14437_ , 2022.
  * Liao et al. (2023) Bencheng Liao, Shaoyu Chen, Bo Jiang, Tianheng Cheng, Qian Zhang, Wenyu Liu, Chang Huang, and Xinggang Wang.  Lane graph as path: Continuity-preserving path-wise modeling for online lane graph construction.  _arXiv preprint arXiv:2303.08815_ , 2023.
  * Lin et al. (2017) Tsung-Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár.  Focal loss for dense object detection.  In _ICCV_ , 2017.
  * Liu et al. (2023a) Yicheng Liu, Tianyuan Yuan, Yue Wang, Yilun Wang, and Hang Zhao.  Vectormapnet: End-to-end vectorized hd map learning.  In _ICML_ , 2023a.
  * Liu et al. (2022) Yingfei Liu, Tiancai Wang, Xiangyu Zhang, and Jian Sun.  Petr: Position embedding transformation for multi-view 3d object detection.  In _ECCV_ , 2022.
  * Liu et al. (2023b) Yingfei Liu, Junjie Yan, Fan Jia, Shuailin Li, Aqi Gao, Tiancai Wang, Xiangyu Zhang, and Jian Sun.  Petrv2: A unified framework for 3d perception from multi-camera images.  In _ICCV_ , 2023b.
  * Liu et al. (2021) Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo.  Swin transformer: Hierarchical vision transformer using shifted windows.  In _ICCV_ , 2021.
  * Loshchilov & Hutter (2016) Ilya Loshchilov and Frank Hutter.  Sgdr: Stochastic gradient descent with warm restarts.  _arXiv preprint arXiv:1608.03983_ , 2016.
  * Loshchilov & Hutter (2017) Ilya Loshchilov and Frank Hutter.  Decoupled weight decay regularization.  _arXiv preprint arXiv:1711.05101_ , 2017.
  * Lu et al. (2023) Mingjie Lu, Yuanxian Huang, Ji Liu, Jinzhang Peng, Lu Tian, and Ashish Sirasao.  Separated roadtopoformer.  _arXiv preprint arXiv:2307.01557_ , 2023.
  * Paz et al. (2015) Lina Maria Paz, Pedro Piniés, and Paul Newman.  A variational approach to online road and path segmentation with monocular vision.  In _ICRA_ , 2015.
  * Qiao et al. (2023) Limeng Qiao, Wenjie Ding, Xi Qiu, and Chi Zhang.  End-to-end vectorized hd-map construction with piecewise bezier curve.  In _CVPR_ , 2023.
  * Tan et al. (2006) Ceryen Tan, Tsai Hong, Tommy Chang, and Michael Shneier.  Color model-based real-time learning for road following.  In _IEEE ITS_ , 2006.
  * Wang et al. (2023) Huijie Wang, Tianyu Li, Yang Li, Li Chen, Chonghao Sima, Zhenbo Liu, Yuting Wang, Shengyin Jiang, Peijin Jia, Bangjun Wang, Feng Wen, Hang Xu, Ping Luo, Junchi Yan, Wei Zhang, and Hongyang Li.  Openlane-v2: A topology reasoning benchmark for scene understanding in autonomous driving.  _arXiv preprint arXiv:2304.10440_ , 2023.
  * Wang et al. (2019) Tiancai Wang, Rao Muhammad Anwer, Muhammad Haris Khan, Fahad Shahbaz Khan, Yanwei Pang, Ling Shao, and Jorma Laaksonen.  Deep contextual attention for human-object interaction detection.  In _ICCV_ , 2019.
  * Wilson et al. (2021) Benjamin Wilson, William Qi, Tanmay Agarwal, John Lambert, Jagjeet Singh, Siddhesh Khandelwal, Bowen Pan, Ratnesh Kumar, Andrew Hartnett, Jhony Kaesemodel Pontes, et al.  Argoverse 2: Next generation datasets for self-driving perception and forecasting.  In _NeurIPS_ , 2021.
  * Xu et al. (2023) Zhenhua Xu, Yuxuan Liu, Yuxiang Sun, Ming Liu, and Lujia Wang.  Centerlinedet: Road lane centerline graph detection with vehicle-mounted sensors by transformer for high-definition map creation.  In _ICRA_ , 2023.
  * Yan et al. (2022) Fan Yan, Ming Nie, Xinyue Cai, Jianhua Han, Hang Xu, Zhen Yang, Chaoqiang Ye, Yanwei Fu, Michael Bi Mi, and Li Zhang.  Once-3dlanes: Building monocular 3d lane detection.  In _CVPR_ , 2022.
  * Zhang et al. (2023) Yuang Zhang, Tiancai Wang, and Xiangyu Zhang.  Motrv2: Bootstrapping end-to-end multi-object tracking by pretrained object detectors.  In _CVPR_ , 2023.
  * Zhu et al. (2021) Xizhou Zhu, Weijie Su, Lewei Lu, Bin Li, Xiaogang Wang, and Jifeng Dai.  Deformable detr: Deformable transformers for end-to-end object detection.  In _ICLR_ , 2021.


# On the hat guessing number and guaranteed subgraphs

Peter Bradshaw  Department of Mathematics, Simon Fraser University, Burnaby,
Canada<EMAIL_ADDRESS>
###### Abstract.

The _hat guessing number_ of a graph is a parameter related to the hat
guessing game for graphs introduced by Winkler. In this paper, we show that
graphs of sufficiently large hat guessing number must contain arbitrary trees
and arbitrarily long cycles as subgraphs. More precisely, for each tree $T$,
there exists a value $N=N(T)$ such that every graph that does not contain $T$
as a subgraph has hat guessing number at most $N$, and for each integer $c\geq
3$, there exists a value $N^{\prime}=N^{\prime}(c)$ such that every graph with
no cycle of length greater than $c$ has hat guessing number at most
$N^{\prime}$.

##  1\. Introduction

We consider the _hat guessing game_ , a game played on a graph111All graphs
considered in this paper are finite. $G$ between two parties. One party
consists of a set of _players_ , with exactly one player occupying each vertex
of $G$, and the other party consists of a single _adversary_. A player at a
vertex $v\in V(G)$ can see exactly those players at the neighbors of $v$, and
importantly, no player can see himself. At the beginning of the game, the
adversary gives each player a hat of some color chosen from the set
$\\{1,\dots,q\\}$. Then, each player observes the hat colors of the players at
neighboring vertices and guesses the color of his own hat. A player cannot
hear the guesses of other players. The players win if at least one player
correctly guesses the color of his hat; otherwise, the adversary wins. Before
the game begins, the players communicate in order to devise a guessing
strategy, but the players’ guessing strategy is known to the adversary. It is
assumed that the players always follow a deterministic guessing strategy, so
that the guess of the player at a vertex $v$ is uniquely determined by the
colors of the hats at the neighbors of $v$. If the players have a guessing
strategy that guarantees at least one correct guess regardless of the
adversary’s hat assignment, then we say that the hat guessing number of $G$,
written $\operatorname{HG}(G)$, is at least $q$. In other words,
$\operatorname{HG}(G)$ is the maximum integer $q$ for which the players have a
winning guessing strategy in the hat guessing game played on $G$ with $q$ hat
colors. The hat guessing game was first considered by Winkler [14] with hats
of only two colors, and the game was first considered in its full generality
by Butler, Hajiaghayi, Kleinberg, and Leighton [4].

We give a short and classical example from Winkler [14] of a winning strategy
for the players in the hat guessing game. Suppose that Alice and Bob play the
hat guessing game on $K_{2}$ against an adversary who has red hats and blue
hats. Before the game begins, Alice agrees to guess the color of the hat that
she sees on Bob’s head, and Bob agrees to guess the color opposite to the
color of Alice’s hat. Then, when the adversary assigns hats to Alice and Bob,
Alice will guess correctly if the two hats assigned have the same color, and
Bob will guess correctly if the two hats assigned have different colors. Thus,
we see that the players Alice and Bob have a winning strategy on $K_{2}$
against an adversary with two hat colors, implying that
$\operatorname{HG}(K_{2})\geq 2$. In fact, Winkler [14] showed that
$\operatorname{HG}(K_{2})=2$, and more generally, Feige [8] showed that
$\operatorname{HG}(K_{n})=n$ for all $n\geq 1$.

The description of the hat guessing game as a game is somewhat misleading,
since the so-called game ends after each party has only taken one turn, and
furthermore, the players make a critical decision about their guessing
strategy before the game has even started. Perhaps a more suitable description
of the hat guessing game is the following equivalent characterization as a
graph coloring problem. Let $G$ be a graph, and let $q$ be a positive integer.
For each vertex $v\in V(G)$, let $\Gamma_{v}$ be a function that maps each
(not necessarily proper) $q$-coloring of $N(v)$ to an element of the set
$\\{1,\dots,q\\}$; that is, $\Gamma_{v}:[q]^{N(v)}\rightarrow[q]$. The goal in
this problem is to give $G$ a (not necessarily proper) $q$-coloring $\varphi$
such that for each vertex $v\in V(G)$, $\Gamma_{v}$ does not map
$\varphi(N(v))$ to $\varphi(v)$, where $\varphi(N(v))$ is the coloring of
$N(v)$ under $\varphi$. If such a $q$-coloring $\varphi$ exists for each set
of functions $\\{\Gamma_{v}:v\in V(G)\\}$, then we say that
$\operatorname{HG}(G)<q$. It is easy to check that in the graph coloring
setting, our $q$-coloring of $G$ corresponds to a hat assignment by the
adversary in the game setting, and the functions $\Gamma_{v}$ correspond to
the individual guessing strategies of the players. In this paper we will
describe the hat guessing game as a game so as not to break tradition, but due
to the natural description of the hat guessing game as a graph coloring
problem, we will often identify a player with the vertex she occupies, and we
will often refer to a hat assignment as a graph coloring.

Determining bounds for the hat guessing numbers of large graph classes is a
particularly difficult problem. Constant upper bounds are known for the hat
guessing numbers of graphs belonging to certain restricted graph classes, such
as trees [4], graphs of bounded degree [7], and graphs of bounded treedepth
[12]. It has been asked frequently whether the hat guessing number of planar
graphs is bounded above by a constant [2, 11], and stronger still, whether all
$k$-degenerate graphs have hat guessing number bounded above by a function of
$k$ [7, 12]. While both of these questions are still open, some progress was
recently made toward the first question when the author showed that
outerplanar graphs have hat guessing number less than $2^{250000}$ and that
the more general class of _layered planar graphs_ has bounded hat guessing
number [3].

In this paper, we will present two more graph classes with bounded hat
guessing number. We will show that those graphs with a certain forbidden tree
subgraph also have a constant upper bound for their hat guessing numbers, as
do those graphs whose cycles are of bounded length. Equivalently, we may say
that in a graph family $\mathcal{G}$ whose members have unbounded hat guessing
number, every tree must appear as a subgraph of some graph $G\in\mathcal{G}$,
and for each integer $c\geq 3$, a cycle of length at least $c$ must also
appear as a subgraph of some graph $G\in\mathcal{G}$.

######  Theorem 1.1.

Let $T$ be a tree. There exists a value $N=N(T)$ such that every graph $G$
with no subgraph isomorphic to $T$ satisfies $\operatorname{HG}(G)\leq N$.

######  Theorem 1.2.

If a graph $G$ has no cycle of length greater than $c$, then

$\operatorname{HG}(G)<\left(\frac{64}{25}\right)^{2^{\lfloor\frac{1}{2}c^{2}\rfloor-1}}+\frac{1}{2}.$

Theorems 1.1 and 1.2 are analogues of the well-known facts that if a graph has
a forbidden tree subgraph or only has cycles of bounded lengths, then that
graph has a bounded chromatic number (see e.g. [1, 6]).

##  2\. Graphs with a forbidden tree subgraph

In this section, we prove Theorem 1.1. Our main tool will be the following
lemma, which is a special case of a lemma of Bosek et al. [2] showing that
graphs admitting certain partitions have bounded hat guessing number. We give
a full proof of the lemma, since it is short and elegant.

######  Lemma 2.1.

Let $r\geq 1$ and $\ell\geq 2$ be integers. Let $G$ be a graph, and let
$U\subseteq V(G)$ be an independent set in $G$ such that for each vertex $u\in
U$, $\deg(u)\leq r$. If $\operatorname{HG}(G\setminus U)<\ell$, then

$\operatorname{HG}(G)\leq\ell^{r}.$

###### Proof.

We show that the adversary can win the hat guessing game on $G$ when
$\ell^{r}+1$ hat colors are available at each vertex. Let the players have a
fixed guessing strategy on $G$. First, the adversary commits to using a color
from $\\{1,\dots,\ell\\}$ at each vertex in $V(G)\setminus U$. Then, for each
vertex $u\in U$, since $\deg(u)\leq r$, and since $U$ is an independent set,
the neighborhood of $u$ will be colored in one of at most $\ell^{r}$ ways, and
hence $u$ will guess one of at most $\ell^{r}$ colors. Therefore, with
$\ell^{r}+1$ available colors at $u$, the adversary can assign a hat color to
$u$ that will not be guessed. After assigning a color to each vertex $u\in U$,
a unique guessing strategy on $G\setminus U$ is determined, and since
$\operatorname{HG}(G\setminus U)<\ell$, the adversary can complete a winning
hat assignment on $G\setminus U$ using only the colors $\\{1,\dots,\ell\\}$. ∎

Given a rooted tree $T$ with root $r$, we say that the _height_ of $T$ is the
maximum distance $\operatorname{dist}(r,v)$ taken over all vertices $v$ in
$T$. Furthermore, given integers $t,h\geq 1$, we say that a _$t$ -ary tree of
height $h$_ is a rooted tree of height $h$ in which every non-leaf vertex has
exactly $t$ children. Observe that every tree $T$ is a subtree of some $t$-ary
tree $T^{\prime}$ of some height $h$, so if $T$ is a forbidden subgraph of a
graph $G$, then a fortiori, $T^{\prime}$ is also a forbidden subgraph.
Therefore, in order to prove Theorem 1.1, we may instead prove the following
equivalent theorem.

######  Theorem 2.2.

Let $h\geq 1$ and $t\geq 2$ be integers. There exists a value $N=N(h,t)$ such
that every graph $G$ with no subgraph isomorphic to a $t$-ary tree of height
$h$ satisfies $\operatorname{HG}(G)<N$.

###### Proof.

We prove the theorem by induction on $h$. When $h=1$, the theorem states that
there exists a value $N$ such that every graph $G$ with no $K_{1,t}$ subgraph
satisfies $\operatorname{HG}(G)<N$. Since such a graph $G$ must have maximum
degree $t-1$, it follows from a simple argument using the Lovász Local Lemma
that $\operatorname{HG}(G)<et$ (see [7] for details). Therefore, it is
sufficient to set $N(1,t)=et$.

Now, suppose that $h>1$. Let $G$ be a graph containing no subgraph isomorphic
to a $t$-ary tree of height $h$. Since a graph of chromatic number $\chi$ must
contain every tree on $\chi$ vertices as a subgraph, it follows that the
chromatic number of $G$ is less than the number of vertices in a $t$-ary tree
of height $h$, which is

$1+t+t^{2}+t^{3}+\dots+t^{h}<2t^{h}=:k.$

We let $U\subseteq V(G)$ be the set of all vertices in $G$ of degree less than
$k$. Since $G$ has chromatic number at most $k-1$, $U$ can be partitioned into
$k^{\prime}$ independent sets for some value $k^{\prime}<k$. We write
$f(x)=x^{k}$ and observe $f(x)\geq x^{k-1}+1$ for $x\geq 1$. Hence, by Lemma
2.1,

$\operatorname{HG}(G)<f^{k}(\operatorname{HG}(G\setminus U)+1).$

Now, we claim that $G\setminus U$ contains no subgraph isomorphic to a $t$-ary
tree of height $h-1$. Indeed, suppose that $T\subseteq G\setminus U$ is a
$t$-ary tree of height $h-1$. Since no leaf of $T$ was added to $U$, it must
follow that every leaf of $T$ had degree at least $k$ in $G$. However, this
implies that a $t$-ary tree of height $h$ can be found in $G$ by greedily
choosing $t$ neighbors, for each of the $t^{h-1}$ leaves of $T$, that are not
in $T$ and that were not chosen as neighbors of another leaf of $T$. This is
possible, since

$k=2t^{h}>(t^{h-1}-1)t+2t^{h-1}>(t^{h-1}-1)t+|V(T)|.$

Since we assumed that $G$ has no $t$-ary tree of height $h$ as a subgraph, we
have reached a contradiction. Therefore, we conclude that $G\setminus U$ has
no subgraph isomorphic to a $t$-ary tree of height $h-1$, and by the induction
hypothesis, $\operatorname{HG}(G\setminus U)<N(h-1,t)$. Since $f$ is an
increasing function, we may let $N(h,t)=f^{k}(N(h-1,t))$, and then
$\operatorname{HG}(G)<N(h,t)$. This completes induction and the proof. ∎

Note that in the proof of Theorem 2.2, the constant $N(h,t)$ grows very large
very quickly due to the repeated applications of Lemma 2.1. We do not attempt
to optimize this constant, because we suspect that our method is not best
possible. By following the method in the proof of Theorem 2.2, one may show
that

(1) $\displaystyle N(h,t)$ $\displaystyle\leq$
$\displaystyle(et)^{2^{2t^{2}+2t^{3}+\dots+2t^{h}}t^{4t^{2}+6t^{3}+\dots+2ht^{h}}}$
$\displaystyle<$ $\displaystyle(et)^{2^{4t^{h}}t^{4ht^{h}}},$

which is more than triple exponential in $h$ with $t$ fixed and more than
double exponential in $t$ with $h$ fixed. While we do not have a guess for the
correct value of $N(h,t)$, we believe that it is much smaller than the value
in (1).

##  3\. Graphs with bounded circumference

In this section, we prove Theorem 1.2. For a graph $G$, we say that the
_circumference_ of $G$ is the length of the longest cycle in $G$. Hence, by
proving Theorem 1.2, we will show that a graph with a bounded circumference
also has a bounded hat guessing number. Our strategy for proving Theorem 1.2
will be as follows. For a graph $G$, recall that a _block_ of $G$ is a maximal
two-connected subgraph of $G$. First, we will show that the hat guessing
number of a graph $G$ can be estimated just by considering each block of $G$
individually. Then, we will show that each block of a graph of bounded
circumference must also have bounded treedepth, and we will use this fact to
obtain an upper bound for $\operatorname{HG}(G)$. While there may exist a more
direct way to show that graphs of bounded circumference also have bounded hat
guessing number, we believe that some of our intermediate techniques may have
other applications in the study of the hat guessing game.

In our proof, we will sometimes consider a modified version of the hat
guessing game in which each player makes two guesses. The essential rules of
this modified game are the same as those of the original game, so that a
player at a vertex $v$ only sees the players at the neighbors of $v$, and so
that players still do not hear each other’s guesses. However, in this modified
game, each player guesses his hat color twice, and the players win if and only
if at least one player makes a correct guess. Given a graph $G$, we write
$\operatorname{HG}_{2}(G)$ for the maximum integer $q$ such that the players
have a winning strategy in the hat guessing game with two guesses played on
$G$ with $q$ colors. In [2], Bosek et al. show that the modified hat guessing
game in which players make multiple guesses is a useful tool for bounding the
hat guessing number of graphs that admit a vertex partition with certain
properties. In some of our intermediate results, we will also restrict the set
of hat colors available to the adversary at certain vertices. It was shown in
[13] that when the hat color set available to the adversary differs between
vertices, only the number of hat colors available to the adversary at each
vertex affects whether or not the players have a winning strategy on $G$.

###  3.1. Using block decompositions to bound hat guessing number

In this subsection, we show that in order to bound $\operatorname{HG}(G)$ for
a graph $G$, it is enough to bound $\operatorname{HG}_{2}(B)$ for each block
$B$ of $G$. We believe that this idea has potential for broad application in
the study of the hat guessing game.

The key result (Lemma 3.3) of this subsection will follow from two lemmas:
Lemma 3.1 and Lemma 3.2. Lemma 3.1 is a special case of a lemma from [2], and
Lemma 3.2 comes directly from [13] with minor changes. We give a full proof
for each lemma, since Lemma 3.1 has a short and elegant proof, and since the
original proof of Lemma 3.2 uses the somewhat complicated notation of
constructors.

######  Lemma 3.1.

Let $G$ be a graph, let $v\in V(G)$, and let $\ell=\operatorname{HG}_{2}(G)$.
If the adversary has $2$ available hat colors at $v$ and $\ell+1$ available
hat colors at each other vertex of $G$, then the adversary has a winning
strategy in the hat guessing game on $G$.

###### Proof.

We write $H=G\setminus\\{v\\}$, and we assume without loss of generality that
the hat color set available to the adversary at each vertex of $V(H)$ is
$\\{1,\dots,\ell+1\\}$. We fix a guessing strategy $\Gamma=\\{\Gamma_{v}:v\in
V(G)\\}$ on $G$ and a set of exactly $2$ colors at $v$. For each of the two
possible colors at $v$, $\Gamma$ determines a unique guessing strategy on $H$.
Therefore, for each hat assignment on $H$, each vertex $u\in V(H)$ will guess
one of $2$ possible colors. Since
$\operatorname{HG}_{2}(H)\leq\operatorname{HG}_{2}(G)\leq\ell$, we may assign
each vertex of $H$ a hat from the color set $\\{1,\dots,\ell+1\\}$ in such a
way that for each vertex $u\in V(H)$, neither of the two possible colors
guessed at $u$ is correct. We give $V(H)$ such a hat assignment, and hence no
vertex of $H$ guesses its hat color correctly.

Now, with hat colors at $V(H)$ assigned, $\Gamma$ uniquely determines a guess
at $v$, so we may assign $v$ a color that does not match it guess. Therefore,
the adversary has a winning hat assignment with $2$ colors available at $v$
and $\ell+1$ colors available at every other vertex of $G$. ∎

######  Lemma 3.2.

Let $G$ be a graph with two subgraphs $G_{1}$ and $G_{2}$ and with a cut-
vertex $v$, such that $G=G_{1}\cup G_{2}$ and $V(G_{1})\cap V(G_{2})=\\{v\\}$.
If $\operatorname{HG}(G_{1})\leq\ell$ and
$\operatorname{HG}_{2}(G_{2})\leq\ell$, then $\operatorname{HG}(G)\leq\ell$.

###### Proof.

We show that the adversary wins the hat guessing game on $G$ when $\ell+1$
colors are available at each vertex. Let $\Gamma=\\{\Gamma_{v}:v\in V(G)\\}$
be a fixed guessing strategy on $G$. Note that since $v$ is a cut-vertex, the
guess of each vertex of $V(G_{1})\setminus\\{v\\}$ depends entirely on the
colors assigned to $V(G_{1})$. Since $\operatorname{HG}(G_{1})\leq\ell$, the
adversary must have at least one hat assignment on $G_{1}$ that causes all
players at $V(G_{1})\setminus\\{v\\}$ to guess incorrectly when following
$\Gamma$. Let $K$ be the set of all such hat assignments on $G_{1}$ that cause
all players at $V(G_{1})\setminus\\{v\\}$ to guess incorrectly.

Now, let $A$ be the set of colorings of $N_{G_{1}}(v)$ that can be extended to
a coloring in $K$. (In other words, $A$ is the set of colorings in $K$
restricted to $N_{G_{1}}(v)$.) We claim that for some coloring $\alpha\in A$,
there are at least two colors $\gamma$ such that the coloring $\alpha$ can be
extended to a coloring $\varphi\in K$ for which $\varphi(v)=\gamma$. Indeed,
suppose that for every $\alpha\in A$, there is a unique color
$\gamma_{\alpha}$ such that $\alpha$ can be extended to an assignment
$\varphi\in K$ for which $\varphi(v)=\gamma_{\alpha}$. Then we claim that the
players have a winning strategy on $G_{1}$ with $\ell+1$ colors, as follows.
Given a hat assignment $\varphi$ on $G_{1}$, the players at
$V(G_{1})\setminus\\{v\\}$ follow the strategy $\Gamma$. We write $\alpha$ for
the coloring of $N_{G_{1}}(v)$ under $\varphi$, and if $\alpha\in A$, then $v$
guesses $\gamma_{\alpha}$; otherwise, $v$ guesses the least-valued available
color. If $\varphi$ is winning for the adversary, then every player at
$V(G_{1})\setminus\\{v\\}$ must guess incorrectly, so $\varphi\in K$, and
$\varphi$ determines a coloring $\alpha\in A$. Then, there exists a unique
color $\gamma_{\alpha}$ such that $\alpha$ can be extended to a coloring in
$K$ in which $\varphi(v)=\gamma_{\alpha}$; hence, it must hold that
$\varphi(v)=\gamma_{\alpha}$, and the player at $v$ guesses correctly. Since
the players have a winning strategy on $G_{1}$ with $\ell+1$ colors, the
assumption that $\operatorname{HG}(G_{1})\leq\ell$ is contradicted. Therefore,
for some coloring $\alpha\in A$, there are two colors $\gamma_{1},\gamma_{2}$
such that the coloring $\alpha$ can be extended to colorings
$\varphi_{1},\varphi_{2}\in K$ for which $\varphi_{1}(v)=\gamma_{1}$ and
$\varphi_{2}(v)=\gamma_{2}$.

We can now show a winning hat assignment for the adversary. First, the
adversary chooses two hat assignments $\varphi_{1},\varphi_{2}\in K$ for
$V(G_{1})$ so that $\varphi_{1}$ and $\varphi_{2}$ agree on $N_{G_{1}}(v)$ but
not on $v$ and so that both assignments cause every player in
$V(G_{1})\setminus\\{v\\}$ guesses incorrectly. We write
$\varphi_{1}(v)=\gamma_{1}$ and $\varphi_{2}(v)=\gamma_{2}$. The adversary
commits to using either $\varphi_{1}$ or $\varphi_{2}$ on $V(G_{1})$. Next, we
observe that now that a coloring $\alpha$ of $N_{G_{1}}(v)$ has been fixed by
$\varphi_{1}$ and $\varphi_{2}$, $\Gamma$ determines a unique guessing
strategy for the vertices of $G_{2}$ that depends only on the hat colors at
$V(G_{2})$. We also observe that two colors are available to the adversary at
$v$ and that $\ell+1$ colors are available to the adversary at each other
vertex of $V(G_{2})\setminus\\{v\\}$. Since
$\operatorname{HG}_{2}(G_{2})\leq\ell$, it follows from Lemma 3.1 that the
adversary may choose some hat assignment $\psi$ on $V(G_{2})$ so that
$\psi(v)\in\\{\gamma_{1},\gamma_{2}\\}$ and so that all vertices of $G_{2}$
guess incorrectly. Writing $\psi(v)=\gamma_{i}$, we then see that
$\psi\cup\varphi_{i}$ is a consistent hat assignment on $G$ that causes all
players in $V(G)$ to make an incorrect guess.

Hence, the adversary has a winning hat assignment on $G$ when $\ell+1$
vertices are available at each vertex, and thus $\operatorname{HG}(G)<\ell+1$.
This completes the proof. ∎

Now, we are ready for the key result of this subsection.

######  Lemma 3.3.

Let $G$ be a graph with blocks $B_{1},\dots,B_{k}$. If
$\operatorname{HG}_{2}(B_{i})\leq\ell$ for each block $B_{i}$, then
$\operatorname{HG}(G)\leq\ell$.

###### Proof.

If $G$ is two-connected, then by the assumption,
$\operatorname{HG}(G)\leq\operatorname{HG}_{2}(G)\leq\ell$, and we are done.
Otherwise, we assume without loss of generality that $G$ is connected and
induct on the number of blocks in $G$. Suppose that $G$ has $k>1$ blocks. Let
$B$ be a terminal block of $G$, that is, a block of $G$ containing a single
cut-vertex $v$. Let $A_{1},\dots,A_{t}$ be maximal connected subgraphs of $G$
in which $v$ is not a cut-vertex, and write $A_{t}=B$. Since $v$ is a cut-
vertex of $G$, we must have $t\geq 2$, and $V(A_{i})\cap V(A_{j})=\\{v\\}$ for
any distinct pair $i,j\in\\{1,\dots,t\\}$. We let
$G^{\prime}=A_{1}\cup\dots\cup A_{t-1}$, and clearly $G^{\prime}$ is connected
with fewer than $k$ blocks.

By the induction hypothesis, $\operatorname{HG}(G^{\prime})\leq\ell$, and by
our assumption, $\operatorname{HG}_{2}(B)\leq\ell$. Thus, by Lemma 3.2, the
hat guessing number of $G$ is at most $\ell$. This completes induction and the
proof. ∎

Lemma 3.3 seems to have the potential for broad application in the study of
the hat guessing game. For instance, one can use the lemma to prove that a
cactus graph $G$ satisfies $\operatorname{HG}(G)\leq 16$ after observing that
$\operatorname{HG}_{2}(C)<6e$ for any cycle $C$, using a simple application of
the Lovász Local Lemma (see [7] for details).

###  3.2. Proof of Theorem 1.2

With Lemma 3.3 in place, we are ready to begin the proof of Theorem 1.2. In
our proof, we will repeatedly use the notion of _treedepth_ , defined as
follows. Given a rooted tree $T$ with root $r$, recall that the _height_ of a
vertex $v\in V(T)$ is the distance in $T$ from $r$ to $v$, and observe that
the height of $T$ is the maximum height of a vertex in $T$. We say that the
_closure_ of $T$ is the graph on $V(T)$ obtained by adding an edge between
every ancestor-descendant pair in $T$. We write $\operatorname{\sf{cl}}(T)$
for the closure of $T$. Then, we say that a graph $G$ has treedepth at most
$d$ if $G$ is a subgraph of $\operatorname{\sf{cl}}(T)$ for some rooted tree
$T$ of height $d-1$. The reason for this “off by one” discrepancy is that in a
rooted tree of height $d-1$, a maximum length path from the root to a leaf
contains exactly $d$ vertices. In [12], He and Li show that graphs of bounded
treedepth also have bounded hat guessing number, and we will be able to use
their ideas to our advantage.

First, we will use two lemmas to establish a connection between the
circumference of a graph and the treedepth of that graph. The first of these
lemmas is a classical lemma of Dirac that follows straightforwardly from
Menger’s theorem.

######  Lemma 3.4 ([5]).

If $G$ is a two-connected graph with a path of length $\ell$, then $G$
contains a cycle of length greater than $\sqrt{2\ell}$.

From Lemma 3.4, we see that in a two-connected graph of circumference $c$,
every path must have length less than $\frac{1}{2}c^{2}$. Using this fact, we
can prove our next lemma.

######  Lemma 3.5.

If $G$ is a two-connected graph of circumference $c$, then the treedepth of
$G$ is at most $\frac{1}{2}c^{2}$.

###### Proof.

We choose a vertex $r\in V(G)$, and we obtain a rooted tree $T\subseteq G$ by
performing a depth-first search from $r$. Since $T$ is obtained from a depth-
first search, every edge of $G$ joins an ancestor-descendant pair in $T$.
Hence, $G$ is a subgraph of $\operatorname{\sf{cl}}(T)$. By Lemma 3.4, the
maximum distance in $T$ from $r$ to a leaf of $T$ is at most
$\frac{1}{2}c^{2}-1$, so the treedepth of $G$ is at most $\frac{1}{2}c^{2}$. ∎

From Lemma 3.5, it follows that in a graph $G$ of bounded circumference, every
block $B$ of $G$ has bounded treedepth. If we can conclude that
$\operatorname{HG}_{2}(B)$ is bounded for each block $B$ of $G$, then it will
follow from Lemma 3.3 that $\operatorname{HG}(G)$ is bounded.

With this in mind, we aim to show that for graphs $H$ of bounded treedepth,
$\operatorname{HG}_{2}(H)$ is also bounded. Luckily, this can be achieved by
following a method of He and Li [12], originally used to bound the hat
guessing number of graphs of bounded treedepth in the traditional hat guessing
game with single guesses. He and Li consider the recursively defined sequence

$s_{n+1}=1+\prod_{i=0}^{n}s_{n},\indent s_{0}=1,$

which is commonly known as Sylvester’s sequence, and they show that given a
rooted tree $T$, in order for the adversary to defeat the players on
$\operatorname{\sf{cl}}(T)$, it is enough for the adversary to have $s_{t+1}$
colors available for each vertex at height $t$, for each $t\geq 0$. Since a
graph of treedepth $d$ is a subgraph of the closure of a rooted tree $T$ whose
vertices achieve a maximum height of $d-1$, it then follows that the hat
guessing number of a graph of treedepth $d$ is less than $s_{d}$.

For the modified game in which each player is allowed two guesses, we consider
the recursively defined sequence

$a_{n+1}=1+2\prod_{i=0}^{n}a_{n},\indent a_{0}=1.$

By closely following the methods of [10], one may show that for all $n\geq 1$,

(2) $a_{n}\leq\theta^{2^{n-1}}+\frac{1}{2},$

where $\theta\approx 2.5533$ is a constant. Also, by following the method of
He and Li [12] almost exactly, we may show that a graph of treedepth $d$ has
hat guessing number less than $a_{d}$ in the game with two guesses, as
follows.

######  Theorem 3.6.

If $G$ is a graph of treedepth $d$, then $\operatorname{HG}_{2}(G)<a_{d}$.

###### Proof.

We will aim to show that if $T$ is a rooted tree of height $d-1$, then
$\operatorname{HG}_{2}(\operatorname{\sf{cl}}(T))<a_{d}$. In order to do this,
we will actually prove a stronger result. We will show by induction on
$|V(T)|$ that the adversary has a winning hat assignment on
$\operatorname{\sf{cl}}(T)$ as long as there are $a_{t+1}$ colors available at
each vertex of height $t$, for each $t\geq 0$. Since the vertices of $T$
achieve a height of at most $d-1$, this will be enough to prove the theorem.

If $|V(T)|=1$, then $T=\operatorname{\sf{cl}}(T)$ has a single vertex $r$ at
height $0$. Since $a_{1}=3$ and since $r$ only has two guesses, the adversary
can assign a color to $r$ that is not guessed and win the game.

Next, suppose that $|V(T)|>1$. Assume that a hat guessing strategy is fixed on
$\operatorname{\sf{cl}}(T)$. For each $t\geq 0$, we fix a list of $a_{t+1}$
colors at each vertex of $T$ at height $t$. Now, let $v$ be a leaf of $T$ at
height $k\geq 1$. We write $u_{1},\dots,u_{k}$ for the descendants of $v$ at
heights $0,\dots,k-1$, respectively. Since $v$ is adjacent in
$\operatorname{\sf{cl}}(T)$ exactly to $u_{1},\dots,u_{k}$, and since the
total number of colorings of the set $\\{u_{1},\dots,u_{k}\\}$ is at most
$P:=a_{1}\dots a_{k}$, each of which determines two guesses at $v$, it follows
that the two guesses made at $v$ must come from a set of at most $2P$ colors.
However, since the adversary has $a_{k+1}=1+2P$ colors available at $v$, the
adversary can assign $v$ a color $\gamma$ that $v$ will not guess. Hence, the
adversary colors $v$ with $\gamma$, and $v$ does not guess its hat color
correctly.

Now, with $\gamma$ fixed at $v$, the players have a unique hat guessing
strategy on $\operatorname{\sf{cl}}(T\setminus\\{v\\})$. However, by the
induction hypothesis, the adversary has a winning hat assignment on
$\operatorname{\sf{cl}}(T\setminus\\{v\\})$ with the available colors at each
vertex. Therefore, the adversary can complete a winning coloring on $V(T)$ and
win the game, and it follows that
$\operatorname{HG}_{2}(\operatorname{\sf{cl}}(T))<a_{d}$. ∎

With all of these tools in place, we can now finish the proof of Theorem 1.2.
Let $B$ be a block of $G$. Since $B$ is two-connected, the treedepth of $B$ is
at most $\lfloor\frac{1}{2}c^{2}\rfloor$ by Lemma 3.5. Therefore, by Theorem
3.6, $\operatorname{HG}_{2}(B)<a_{d}$, with
$d=\lfloor\frac{1}{2}c^{2}\rfloor$. Then, by applying Lemma 3.3, we know that
$\operatorname{HG}(G)<a_{d}$, and by (2), the proof is complete.

##  4\. Open questions

While we were able to show that the graphs that forbid a tree $T$ as a
subgraph have bounded hat guessing number, it is still open whether the graphs
that forbid a general subgraph $H$ as a subgraph have bounded hat guessing
number. We suspect that if $H$ contains a cycle, then there exists a graph $G$
with no subgraph isomorphic to $H$ for which the hat guessing number of $G$ is
arbitrarily large, and we pose the following question:

######  Question 4.1.

Is it true that the graphs with $H$ as forbidden subgraph have bounded hat
guessing number if and only if $H$ is acyclic?

If Question 4.1 has a positive answer, then it would be analagous to the well-
known fact that the graphs that forbid $H$ as a subgraph have bounded
chromatic number if and only if $H$ is acyclic (see e.g. [1]). One possible
way to settle Question 4.1 would be to show an affirmative answer to the
following question, which was asked by He, Ido, and Przybocki in [11]:

######  Question 4.2.

Do there exist graphs with arbitrarily large girth and hat guessing number?

If Question 4.2 has an affirmative answer, then for any graph $H$ with at
least one cycle, one can construct a family of graphs with no copy of $H$ as a
subgraph and with arbitrarily large hat guessing number by considering those
graphs $G$ with girth larger than the girth of $H$, which would give a
positive answer to Question 4.1.

On the other hand, if Question 4.2 has a negative answer, it would be natural
to ask if any particular cycle length is necessary in a graph family of
unbounded hat guessing number. For instance, must a graph of sufficiently
large hat guessing number contain a $4$-cycle? Gadouleau and Georgiou [9] have
shown that $\operatorname{HG}(K_{n,n^{n}})>n$, so evidently no odd cycle is
necessary in a family of graphs of unbounded hat guessing number, but to the
best of our knowledge, no construction exists for graphs of arbitrarily large
hat guessing number that contain no $4$-cycle. In fact, based on current
knowledge, it may be true that a graph of sufficiently large hat guessing
number must contain a cycle of every even length up to some value.

## References

  * [1] Maria Axenovich, Jonathan Rollin, and Torsten Ueckerdt.  Chromatic number of ordered graphs with forbidden ordered subgraphs.  Combinatorica, 38(5):1021–1043, 2018.
  * [2] Bartłomiej Bosek, Andrzej Dudek, Michał Farnik, Jarosław Grytczuk, and Przemysław Mazur.  Hat chromatic number of graphs, 2019.
  * [3] Peter Bradshaw.  On the hat guessing number of a planar graph class, 2021.
  * [4] Steve Butler, Mohammad T. Hajiaghayi, Robert D. Kleinberg, and Tom Leighton.  Hat guessing games.  SIAM J. Discrete Math., 22(2):592–605, 2008.
  * [5] G. A. Dirac.  Some theorems on abstract graphs.  Proc. London Math. Soc. (3), 2:69–81, 1952.
  * [6] P. Erdős and T. Gallai.  On maximal paths and circuits of graphs.  Acta Math. Acad. Sci. Hungar., 10:337–356 (unbound insert), 1959\.
  * [7] Michał Farnik.  A hat guessing game.  PhD thesis, Jagiellonian University, 2015.
  * [8] Uriel Feige.  You can leave your hat on (if you guess its color).  Technical report, Weizmann Institute, 2004.
  * [9] Maximilien Gadouleau and Nicholas Georgiou.  New constructions and bounds for Winkler’s hat game.  SIAM J. Discrete Math., 29(2):823–834, 2015.
  * [10] Solomon W. Golomb.  On certain nonlinear recurring sequences.  Amer. Math. Monthly, 70:403–405, 1963.
  * [11] Xiaoyu He, Yuzu Ido, and Benjamin Przybocki.  Hat guessing on books and windmills, 2020.
  * [12] Xiaoyu He and Ray Li.  Hat guessing numbers of degenerate graphs.  Electron. J. Combin., 27(3):Paper No. 3.58, 8, 2020.
  * [13] K. P. Kokhas and A. S. Latyshev.  Cliques and constructors in the “hats” game. I.  Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI), 488(Kombinatorika i Teoriya Grafov. XI):66–96, 2019.
  * [14] P. Winkler.  Games people don’t play.  In David Wolfe and Tom Rodgers, editors, Puzzlers’ Tribute: A Feast for the Mind, chapter 10, pages 301–313. A K Peters, Baltimore, 2002.