BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Yelena Yuditsky (Université libre de Bruxelles) DTSTART:20220512T141500Z DTEND:20220512T160000Z DTSTAMP:20260422T065907Z UID:CJCS/67 DESCRIPTION:Title: We ak Coloring Numbers of Intersection Graphs\nby Yelena Yuditsky (Univer sité libre de Bruxelles) as part of Copenhagen-Jerusalem Combinatorics Se minar\n\n\nAbstract\nWeak and strong coloring numbers are generalizations of the degeneracy of a graph\, where for a positive integer $k$\,\nwe seek a vertex ordering such every vertex can (weakly respectively strongly) re ach in $k$ steps only few vertices that precede it in the ordering.\nBoth notions capture the sparsity of a graph or a graph class\, and have intere sting applications in the structural and algorithmic graph theory.\nRecent ly\, Dvoràk\, McCarty\, and Norin observed a natural volume-based upper b ound for the strong coloring numbers\nof intersection graphs of well-behav ed objects in $\\mathbb{R}^d$\, such as homothets of a compact convex obje ct\, or comparable axis-aligned boxes.\n \nWe prove upper and lower bounds for the $k$-th weak coloring numbers of these classes of intersection gra phs.\nAs a consequence\, we describe a natural graph class whose strong co loring numbers are polynomial in $k$\, but the weak coloring numbers\nare exponential. We also observe a surprising difference in terms of the depen dence of the weak coloring numbers on the dimension\nbetween touching grap hs of balls (single-exponential) and hypercubes (double-exponential).\n LOCATION:https://researchseminars.org/talk/CJCS/67/ END:VEVENT END:VCALENDAR