BEGIN:VCALENDAR

VERSION:2.0

PRODID:-//wp-events-plugin.com//7.4.2//EN

TZID:Asia/Jerusalem

X-WR-TIMEZONE:Asia/Jerusalem
BEGIN:VEVENT

UID:176@math.technion.ac.il

DTSTART;TZID=Asia/Jerusalem:20240313T143000

DTEND;TZID=Asia/Jerusalem:20240313T152000

DTSTAMP:20250109T093658Z

URL:https://math.technion.ac.il/events/chaya-keller/

SUMMARY:Chaya Keller (Ariel) -- New Bounds for Zarankiewicz's Problem via e
 psilon-t-Nets
DESCRIPTION:Lecturer:Chaya Keller \n Location:814 Amado\n The classical Zar
 ankiewicz's problem asks for the maximum number of edges in a bipartite gr
 aph on n vertices which does not contain the complete bipartite graph K_{t
 \,t}. In one of the cornerstones of extremal graph theory\, Kővari\, Sós
  and Turán proved an upper bound of O(n^{2-1/t}). In a celebrated result\
 , Fox\, Pach\, Sheffer\, Suk and Zahl obtained an improved bound of O(n^{2
 -1/d}) for graphs of VC-dimension d (where d&lt\;t). Recently\, Chan and H
 ar-Peled presented (quasi-)linear upper bounds for several classes of geom
 etrically-defined incidence graphs\, including a bound of O(n log log n) f
 or the incidence graph of points and pseudo-discs in the plane.\n\nIn this
  talk we present a new approach to Zarankiewicz's problem\, via epsilon-t-
 nets -- a recently introduced generalization of the classical notion of ep
 silon-nets. We show that the existence of `small'-sized epsilon-t-nets imp
 lies upper bounds for Zarankiewicz's problem. Using the new approach\, we 
 obtain a new proof of the O(n^{2-1/d}) bound of Fox et al.\, and a sharp b
 ound of O(n) for the intersection graph of two families of pseudo-discs\, 
 thus both improving and generalizing the result of Chan and Har-Peled from
  incidence graphs to intersection graphs.\n\nWe also obtain improved bound
 s for several other classes of geometric intersection graphs\, including a
  sharp O(n log n / log log n) bound for the intersection graph of two fami
 lies of axis-parallel rectangles.\n\nJoint work with Shakhar Smorodinsky.\
 n 
CATEGORIES:Combinatorics Seminar,Seminars
LOCATION:814 Amado

END:VEVENT

BEGIN:VTIMEZONE

TZID:Asia/Jerusalem

X-LIC-LOCATION:Asia/Jerusalem

BEGIN:STANDARD

DTSTART:20231029T010000

TZOFFSETFROM:+0300

TZOFFSETTO:+0200

TZNAME:IST

END:STANDARD

END:VTIMEZONE
END:VCALENDAR