SFU Operations Research Seminar: Marco Caoduro

Given a family R of rectangles in the plane, the packing number of R, denoted by $\nu$(R), is the maximum size of a set of pairwise disjoint rectangles in R, and the hitting number, denoted by $\tau$(R), is the minimum size of a set of points having a non-empty intersection with each rectangle in R. Clearly, $\tau \ge \nu$.

Wegner (1965), and independently, Gyárfás and Lehel (1985), asked whether the hitting number $\tau$ could be bounded by a linear function of the packing number $\nu$. In addition, Wegner proposed a multiplicative constant of 2. This problem is still wide open and even if linear bounds are known for several particular cases, almost none of them are paired with lower bound examples showing their optimality.

For a family of axis-parallel line segments, it is easy to show that $\tau \le 2\nu$, as suggested by Wegner. During the talk, we will consider families of axis-parallel segments with the additional property that no three of them meet at a point (that is, the intersection graph is triangle-free). We show that, in this restricted setting, the packing number of a family is at least $n/4+C_1\sqrt{n}$ where $n$ is the size of the considered family and $C_1$ is a fixed positive constant. In addition, we construct examples with packing number at most $n/4 + C_2\sqrt{n}$ for a different constant $C_2 > C_1$ showing that the previous bound is essentially optimal. As a consequence of these results, we settle the Wegner-Gyárfás-Lehel’s problem for axis-parallel segments showing that the multiplicative constant of 2 is optimal and deduce that $\tau \le 2\nu − C_3 \sqrt{\nu}$ for triangle-free axis-parallel segments. This bound cannot be achieved for triangle-free axis-parallel rectangles, marking a substantial difference in the behavior of segments and rectangles.

At the end of the talk, we will present several open problems, in particular, linking our work with the recent developments on the computation of the packing number for axis-parallel rectangles of Mitchell (2021) and Gálvez, Khan, Mari, Mömke, Pittu, and Wiese (2022). This is joint work with Jana Cslovjecsek, Michał Pilipczuk, and Karol Węgrzycki.