BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-ORIGINAL-URL:https://dimag.ibs.re.kr
X-WR-CALDESC:Events for Discrete Mathematics Group
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Seoul
BEGIN:STANDARD
TZOFFSETFROM:+0900
TZOFFSETTO:+0900
TZNAME:KST
DTSTART:20190101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201126T100000
DTEND;TZID=Asia/Seoul:20201126T110000
DTSTAMP:20260423T043520
CREATED:20201027T002159Z
LAST-MODIFIED:20240705T193041Z
UID:3195-1606384800-1606388400@dimag.ibs.re.kr
SUMMARY:Da Qi Chen\, Bipartite Saturation
DESCRIPTION:In extremal graph theory\, a graph G is H-saturated if G does not contain a copy of H but adding any missing edge to G creates a copy of H. The saturation number\, sat(n\, H)\, is the minimum number of edges in an n-vertex H-saturated graph. This class of problems was first studied by Zykov and Erdős\, Hajnal\, and Moon. They also determined the saturation number when H is a clique and classified the extremal structures. \nIn this talk\, we will focus mainly on the bipartite saturation problem (which was also first introduced by Erdős\, Hajnal\, and Moon). Here\, we always assume that both G and H are bipartite graphs. Then\, G is H-saturated if G does not contain H but adding any missing edge across the bipartition creates a copy of H. We can then similarly define sat(n\, H) as the minimum number of edges of an n-by-n bipartite graph that is also H-saturated. One of the most interesting and natural questions here is to determine the saturation number for the complete bipartite graph $K_{s\, t}$. When s=t\, the saturation number and its extremal structures were determined long ago but nothing else is known for the general case. Half a decade ago\, Gan\, Korandi\, and Sudakov gave an asymptotically tight bound that was only off by an additive constant.  We will highlight the main ideas behind that proof and show\, with some additional techniques\, how the bound can be improved to achieve tightness for the case when s=t-1. \nThis talk is based on collaborative work with Debsoumya Chakraborti and Mihir Hasabnis. See arXiv: https://arxiv.org/abs/2009.07651 for the full paper.
URL:https://dimag.ibs.re.kr/event/2020-11-26/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
END:VCALENDAR