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:20200602T163000
DTEND;TZID=Asia/Seoul:20200602T173000
DTSTAMP:20260420T030918
CREATED:20200528T061536Z
LAST-MODIFIED:20240705T200043Z
UID:2491-1591115400-1591119000@dimag.ibs.re.kr
SUMMARY:Huy-Tung Nguyen\, The average cut-rank of graphs
DESCRIPTION:The cut-rank of a set X of vertices in a graph G is defined as the rank of the X×(V(G)∖X) matrix over the binary field whose (i\,j)-entry is 1 if the vertex i in X is adjacent to the vertex j in V(G)∖X and 0 otherwise. We introduce the graph parameter called the average cut-rank of a graph\, defined as the expected value of the cut-rank of a random set of vertices. We show that this parameter does not increase when taking vertex-minors of graphs and a class of graphs has bounded average cut-rank if and only if it has bounded neighborhood diversity. This allows us to deduce that for each real α\, the list of induced-subgraph-minimal graphs having average cut-rank larger than (or at least) α is finite. We further refine this by providing an upper bound on the size of obstruction and a lower bound on the number of obstructions for average cut-rank at most (or smaller than) α for each real α≥0. Finally\, we describe explicitly all graphs of average cut-rank at most 3/2 and determine up to 3/2 all possible values that can be realized as the average cut-rank of some graph. This is joint work with Sang-il Oum.
URL:https://dimag.ibs.re.kr/event/2020-06-02/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200609T163000
DTEND;TZID=Asia/Seoul:20200609T173000
DTSTAMP:20260420T030918
CREATED:20200529T052601Z
LAST-MODIFIED:20240705T200042Z
UID:2498-1591720200-1591723800@dimag.ibs.re.kr
SUMMARY:Jiseung Kim (김지승)\, Hardness and concrete security in cryptography
DESCRIPTION:Computationally hard problems have been widely used to construct cryptographic primitives such as encryptions\, digital signatures. For example\, provably secure primitives are based on a reduction from the hardness problems. However\, the concrete instantiation of primitives does not follow the results of hardness problems due to its efficiency. In this talk\, we introduce cryptographic hardness problems widely used in cryptography and the gap between hardness results and concrete security of cryptographic primitives based on our recent works.
URL:https://dimag.ibs.re.kr/event/2020-06-09/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200616T163000
DTEND;TZID=Asia/Seoul:20200616T173000
DTSTAMP:20260420T030918
CREATED:20200525T080845Z
LAST-MODIFIED:20240707T083941Z
UID:2478-1592325000-1592328600@dimag.ibs.re.kr
SUMMARY:Andreas Holmsen\, Fractional Helly and topological complexity
DESCRIPTION:The fractional Helly theorem is a simple yet remarkable generalization of Helly’s classical theorem on the intersection of convex sets\, and it is of considerable interest to extend the fractional Helly theorem beyond the setting of convexity. In this talk I will discuss a recent result which shows that the fractional Helly theorem holds for families of subsets of $\mathbb R^d$ which satisfy only very weak topological assumptions. The proofs combine a number of tools such as homological minors\, stair-convexity\, supersaturation in hypergraphs\, Radon dimension\, and Ramsey-type arguments. This is joint work with Xavier Goaoc and Zuzana Patáková.
URL:https://dimag.ibs.re.kr/event/2020-06-16/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200623T163000
DTEND;TZID=Asia/Seoul:20200623T173000
DTSTAMP:20260420T030918
CREATED:20200611T051100Z
LAST-MODIFIED:20240707T083929Z
UID:2529-1592929800-1592933400@dimag.ibs.re.kr
SUMMARY:Jaehoon Kim (김재훈)\, A resilience version of Pósa's theorem
DESCRIPTION:Pósa’s theorem states that any graph G whose degree sequence $d_1\leq \dots \leq d_n$ satisfies $d_i \geq i+1$ for all $i< n/2$ has a Hamilton cycle. This degree condition is best possible. We show that a similar result holds for suitable subgraphs $G$ of random graphs. This is joint work with Padraig Condon\, Alberto Espuny Diaz\, Daniela Kühn and Deryk Osthus.
URL:https://dimag.ibs.re.kr/event/2020-06-23/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200630T163000
DTEND;TZID=Asia/Seoul:20200630T173000
DTSTAMP:20260420T030918
CREATED:20200617T222504Z
LAST-MODIFIED:20240705T200042Z
UID:2542-1593534600-1593538200@dimag.ibs.re.kr
SUMMARY:Dennis Wong\, Generating Gray codes and universal cycles for weak orders
DESCRIPTION:A weak order is a way to rank n objects where ties are allowed. Weak orders have applications in diverse areas such as linguistics\, designing combination locks\, and even in horse racing. In this talk\, we present new and simple algorithms to generate Gray codes and universal cycles for weak orders.
URL:https://dimag.ibs.re.kr/event/2020-06-30/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR