Lower bounds for piercing and coloring boxes

DOI10.1016/J.AIM.2023.109360MaRDI QIDQ6187716zbMATH OpenOpenAlexFDO

Authors István Tomon

Publication date 1 February 2024

Published in Advances in Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2209.09887

zbMATH Keywords

boxeshitting setRamsey theory

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55) Ramsey theory (05D10)

Abstract: Given a family $mathcalB$ of axis-parallel boxes in $mathbb{R}^d$, let $au$ denote its piercing number, and $u$ its independence number. It is an old question whether $au/u$ can be arbitrarily large for given $dgeq2$. Here, for every $u$, we construct a family of axis-parallel boxes achieving ${\displaystyle }$ augeq Omega_d(

u)cdotleft(frac{log u}{loglog

u} ight)^{d-2}.${\displaystyle }$ This not only answers the previous question for every $dgeq3$ 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})cdotleft(fraclognloglognight{)}^{-(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 $fraclognloglognllomegall{n}^{1-varepsilon}$, we construct an intersection graph of $n$ boxes with clique number at most $omega$, and chromatic number $Omeg{a}_{d,varepsilon}(omega)cdotleft(fraclognloglognight{)}^{d-2}.$ This matches the best known upper bound up to a factor of $O_d((logw)(loglogn{)}^{d-2})$.

Recommendations

• Piercing axis-parallel boxes
• On partitions of two-dimensional discrete boxes
• Coloring lines and Delaunay graphs with respect to boxes
• Piercing random boxes
• From a \((p, 2)\)-theorem to a tight \((p, q)\)-theorem

Cites work

• A Ramsey-Type Result for Convex Sets
• Approximation algorithms for maximum independent set of pseudo-disks
• Covering and coloring problems for relatives of intervals
• Covering boxes by points
• Fast stabbing of boxes in high dimensions
• scientific article; zbMATH DE number 3152801 (Why is no real title available?)
• scientific article; zbMATH DE number 2209723 (Why is no real title available?)
• Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity
• On a Coloring Problem.
• On point covers of parallel rectangles
• On the number of graphs without 4-cycles
• On Wegner's inequality for axis-parallel rectangles
• Piercing axis-parallel boxes
• Stochastic Algorithms: Foundations and Applications
• The probabilistic method
• Tight lower bounds for the size of epsilon-nets
• Über eine kombinatorisch-geometrische Frage von Hadwiger und Debrunner

Cited in

(3)

• On partitions of two-dimensional discrete boxes
• Coloring lines and Delaunay graphs with respect to boxes
• Stabbing boxes with finitely many axis-parallel lines and flats

This page was built for publication: Lower bounds for piercing and coloring boxes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6187716)