BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Discrete Mathematics Group
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:20200101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210203T163000
DTEND;TZID=Asia/Seoul:20210203T173000
DTSTAMP:20260423T203110
CREATED:20201106T054235Z
LAST-MODIFIED:20240705T193028Z
UID:3241-1612369800-1612373400@dimag.ibs.re.kr
SUMMARY:Ron Aharoni\, Colorful KKM and multiple cakes division
DESCRIPTION:In the “cake partition” problem n players have each a list of preferred parts for any partition of the [0\,1] interval (“cake”) into n sub-intervals. Woodall\, Stromquist and Gale proved independently that under mild conditions on the list of preferences (like continuity) there is always a partition and assignment of parts to the players\, in which every player gets a piece belonging to her list of preferred parts. In fact\, Gale proved a colorful version of the famous KKM theorem\, not realizing that this is the same problem\, but on the other hand\, proved the problem its proper setting. I will discuss the case of partitioning more than one cake – how many players can you make happy\, when there is a general number of cakes\, and general number of players. \nJoint work with Eli Berger\, Joseph Briggs\, Erel Segal-Halevi and Shira Zerbib.
URL:https://dimag.ibs.re.kr/event/2021-02-03/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210209T163000
DTEND;TZID=Asia/Seoul:20210209T173000
DTSTAMP:20260423T203110
CREATED:20210203T050722Z
LAST-MODIFIED:20240705T191023Z
UID:3581-1612888200-1612891800@dimag.ibs.re.kr
SUMMARY:Doowon Koh (고두원)\, On the cone restriction conjecture in four dimensions and applications in incidence geometry
DESCRIPTION:Main purpose of this talk is to introduce a connection between restriction estimates for cones and point-sphere incidence theorems in the finite field setting. First\, we review the finite field restriction problem for cones and address new results on the conical restriction problems. In particular\, we establish the restriction conjecture for the cone in four dimensions. Second\, we study how to apply the conical restriction results to the point-sphere incidence bounds. As a consequence\, we obtain sharp point-sphere incidence bounds when sphere sets are not too big.
URL:https://dimag.ibs.re.kr/event/2021-02-09/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210210T163000
DTEND;TZID=Asia/Seoul:20210210T173000
DTSTAMP:20260423T203110
CREATED:20201231T073729Z
LAST-MODIFIED:20240705T191150Z
UID:3428-1612974600-1612978200@dimag.ibs.re.kr
SUMMARY:Jie Ma (马杰)\, Non-repeated cycle lengths and Sidon sequences
DESCRIPTION:We prove a conjecture of Boros\, Caro\, Furedi and Yuster on the maximum number of edges in a 2-connected graph without repeated cycle lengths\, which is a restricted version of a longstanding problem of Erdos. Our proof together with the matched lower bound construction of Boros\, Caro\, Furedi and Yuster show that this problem can be conceptually reduced to the seminal problem of finding the maximum Sidon sequences in number theory. Joint work with Tianchi Yang.
URL:https://dimag.ibs.re.kr/event/2021-02-10/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210216T163000
DTEND;TZID=Asia/Seoul:20210216T173000
DTSTAMP:20260423T203110
CREATED:20210205T012237Z
LAST-MODIFIED:20240705T191023Z
UID:3594-1613493000-1613496600@dimag.ibs.re.kr
SUMMARY:Martin Ziegler\, Quantitative Coding and Complexity Theory of Continuous Data
DESCRIPTION:Specifying a computational problem requires fixing encodings for input and output: encoding graphs as adjacency matrices\, characters as integers\, integers as bit strings\, and vice versa. For such discrete data\, the actual encoding is usually straightforward and/or complexity-theoretically inessential (up to polynomial time\, say). \nBut concerning continuous data\, already real numbers naturally suggest various encodings with very different computational properties. \nWe recall the existing qualitative theory of computably ‘sensible’ encodings of topological spaces; and we newly develop the quantitative theory of complexity-theoretically ‘sensible’ encodings of metric spaces. \nJoint work with Donghyun Lim.
URL:https://dimag.ibs.re.kr/event/2021-02-16/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210217T100000
DTEND;TZID=Asia/Seoul:20210217T110000
DTSTAMP:20260423T203110
CREATED:20201231T022333Z
LAST-MODIFIED:20240707T081843Z
UID:3423-1613556000-1613559600@dimag.ibs.re.kr
SUMMARY:David Wood\, Tree densities of sparse graph classes
DESCRIPTION:This talk considers the following question at the intersection of extremal and structural graph theory: What is the maximum number of copies of a fixed forest $T$ in an $n$-vertex graph in a graph class $\mathcal{G}$ as $n\to \infty$? I will answer this question for a variety of sparse graph classes $\mathcal{G}$. In particular\, we show that the answer is $\Theta(n^{\alpha_d(T)})$ where $\alpha_d(T)$ is the size of the largest stable set in the subforest of $T$ induced by the vertices of degree at most $d$\, for some integer $d$ that depends on $\mathcal{G}$. For example\, when $\mathcal{G}$ is the class of $k$-degenerate graphs then $d=k$; when $\mathcal{G}$ is the class of graphs containing no $K_{s\,t}$-minor ($t\geq s$) then $d=s-1$; and when $\mathcal{G}$ is the class of $k$-planar graphs then $d=2$. All these results are in fact consequences of a single lemma in terms of a finite set of excluded subgraphs. This is joint work with Tony Huynh (arXiv:2009.12989).
URL:https://dimag.ibs.re.kr/event/2021-02-17/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210223T163000
DTEND;TZID=Asia/Seoul:20210223T173000
DTSTAMP:20260423T203110
CREATED:20210217T043908Z
LAST-MODIFIED:20240707T081835Z
UID:3637-1614097800-1614101400@dimag.ibs.re.kr
SUMMARY:Minki Kim (김민기)\, Rainbow paths and rainbow matchings
DESCRIPTION:We prove that if $n \geq 3$\, then any family of $3n-3$ sets of matchings of size $n$ in any graph has a rainbow matching of size $n$. This improves on a previous result\, in which $3n-3$ is replaced by $3n-2$. We also prove a “cooperative” generalization: for $t > 0$ and $n \geq 3$\, any $3n-4+t$ sets of edges\, the union of every $t$ of which contains a matching of size $n$\, have rainbow matching of size $n$. This is joint work with Ron Aharoni\, Joseph Briggs\, and Jinha Kim.
URL:https://dimag.ibs.re.kr/event/2021-02-23/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR