Piercing boxes and products of trees

Abstract

We give a new upper bound on the piercing number τ(ℱ) of a finite family ℱ of axis-parallel rectangles in the plane when every p members contain an intersecting pair. Namely, we prove τ(ℱ) = O(p(loglog p)(logloglog p)), improving the factor (loglog p)² in the best previously known bound to (loglog p)(logloglog p). For each d>2, when ℱ is a finite family of axis-parallel boxes in ℝ^d, this yields τ(ℱ) = O(p(log p)^d−2(loglog p)(logloglog p)). We also study an analogous problem replacing ℝ^d=ℝ×⋯×ℝ with the Cartesian product T₁□⋯□ T_d of trees T₁,…,T_d, and boxes with objects of the form S₁□⋯□ S_d where S_i is a subtree of T_i. For a finite family of such objects under the same intersection assumption as above, we establish an upper bound τ(ℱ)=O(p(log p)^d−1) for each d. We also construct examples showing that this upper bound cannot be improved in order of magnitude.

Horocyclic products of trees
Laurent Bartholdi, Markus Neuhauser, Wolfgang Woess
J. Eur. Math. Soc. (JEMS)3 Nov 2026Peer-reviewedLicence not statedFull text56 citedCombinatorics & discrete mathematicsHAL
CAT(0) square complexes that do not embed into finite products of trees
James Davies, Harry Petyt
arXiv15 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematics Geometry & topologyarXiv
Vaught's Conjecture for Sums of Products of Rooted Trees
Miloš S. Kurilić
arXiv23 Sep 2026PreprintarXiv licenceFull textLogic & foundationsarXiv
Sharp Gromov Hyperbolicity Constants for Cartesian Products of Finitely Many Trees
Junior Michel, Anier Soria Lorente, Jean Marie-Vilaire
arXiv16 Oct 2026PreprintCC BY 4.0Full textGeometry & topologyarXiv
Piercing spanned lines and hyperplanes
Ben Lund
arXiv19 Oct 2026PreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeX RIS

BibTeX

@misc{rao2026piercing,
  title = {{Piercing boxes and products of trees}},
  author = {Wei Rao and Taehyun Eom and Minki Kim},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.16703},
  eprint = {2610.16703},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.16703},
}

RIS

TY  - UNPB
TI  - Piercing boxes and products of trees
AU  - Wei Rao
AU  - Taehyun Eom
AU  - Minki Kim
PY  - 2026
DA  - 2026/10/12
PB  - arXiv
DO  - 10.48550/arxiv.2610.16703
UR  - https://arxiv.org/abs/2610.16703
AB  - We give a new upper bound on the piercing number τ(ℱ) of a finite family ℱ of axis-parallel rectangles in the plane when every p members contain an intersecting pair. Namely, we prove τ(ℱ) = O(p(loglog p)(logloglog p)), improving the factor (loglog p)^2 in the best previously known bound to (loglog p)(logloglog p). For each d>2, when ℱ is a finite family of axis-parallel boxes in ℝ^d, this yields τ(ℱ) = O(p(log p)^d−2(loglog p)(logloglog p)). We also study an analogous problem replacing ℝ^d=ℝ×⋯×ℝ with the Cartesian product T_1□⋯□ T_d of trees T_1,…,T_d, and boxes with objects of the form S_1□⋯□ S_d where S_i is a subtree of T_i. For a finite family of such objects under the same intersection assumption as above, we establish an upper bound τ(ℱ)=O(p(log p)^d−1) for each d. We also construct examples showing that this upper bound cannot be improved in order of magnitude.
ER  -

Abstract

Related

Cite