BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Marco Caoduro (UBC Vancouver) DTSTART:20230406T223000Z DTEND:20230406T233000Z DTSTAMP:20260513T185432Z UID:SFUOR/21 DESCRIPTION:Title: O n the Packing and Hitting Numbers of Axis-parallel Segments\nby Marco Caoduro (UBC Vancouver) as part of PIMS-CORDS SFU Operations Research Semi nar\n\nLecture held in ASB 10908.\n\nAbstract\nGiven a family R of rectang les 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 hitt ing number\, denoted by $\\tau$(R)\, is the minimum size of a set of point s having a non-empty intersection with each rectangle in R. Clearly\, $\\t au \\ge \\nu$.\n\nWegner (1965)\, and independently\, Gyárfás and Lehel (1985)\, asked whether the hitting number $\\tau$ could be bounded by a li near function of the packing number $\\nu$. In addition\, Wegner proposed a multiplicative constant of 2. This problem is still wide open and even i f linear bounds are known for several particular cases\, almost none of th em are paired with lower bound examples showing their optimality.\n\nFor 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 fam ilies of axis-parallel segments with the additional property that no three of them meet at a point (that is\, the intersection graph is triangle-fre e). We show that\, in this restricted setting\, the packing number of a fa mily is at least $n/4+C_1\\sqrt{n}$ where $n$ is the size of the considere d family and $C_1$ is a fixed positive constant. In addition\, we construc t examples with packing number at most $n/4 + C_2\\sqrt{n}$ for a differen t constant $C_2 > C_1$ showing that the previous bound is essentially opti mal.\nAs a consequence of these results\, we settle the Wegner-Gyárfás-L ehel’s problem for axis-parallel segments showing that the multiplicativ e constant of 2 is optimal and deduce that $\\tau \\le 2\\nu − C_3 \\sqr t{\\nu}$ for triangle-free axis-parallel segments. This bound cannot be ac hieved for triangle-free axis-parallel rectangles\, marking a substantial difference in the behavior of segments and rectangles.\n\nAt the end of th e talk\, we will present several open problems\, in particular\, linking o ur work with the recent developments on the computation of the packing num ber for axis-parallel rectangles of Mitchell (2021) and Gálvez\, Khan\, M ari\, Mömke\, Pittu\, and Wiese (2022). This is joint work with Jana Cslo vjecsek\, Michał Pilipczuk\, and Karol Węgrzycki.\n LOCATION:https://researchseminars.org/talk/SFUOR/21/ END:VEVENT END:VCALENDAR