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:20210302T163000
DTEND;TZID=Asia/Seoul:20210302T173000
DTSTAMP:20260419T063220
CREATED:20210217T044249Z
LAST-MODIFIED:20240707T081721Z
UID:3639-1614702600-1614706200@dimag.ibs.re.kr
SUMMARY:Kevin Hendrey\, A unified half-integral Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups
DESCRIPTION:Erdős and Pósa proved in 1965 that there is a duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. Such a duality does not hold if we restrict to odd cycles.  However\, in 1999\, Reed proved an analogue for odd cycles by relaxing packing to half-integral packing. We prove a far-reaching generalisation of the theorem of Reed; if the edges of a graph are labelled by finitely many abelian groups\, then there is a duality between the maximum size of a half-integral packing of cycles whose values avoid a fixed finite set for each abelian group and the minimum size of a vertex set hitting all such cycles. \nA multitude of natural properties of cycles can be encoded in this setting\, for example cycles of length at least $\ell$\, cycles of length $p$ modulo $q$\, cycles intersecting a prescribed set of vertices at least $t$ times\, and cycles contained in given $\mathbb{Z}_2$-homology classes in a graph embedded on a fixed surface. Our main result allows us to prove a duality theorem for cycles satisfying a fixed set of finitely many such properties. \nThis is joint work with J. Pascal Gollin\, Ken-ichi Kawarabayashi\, O-joung Kwon\, and Sang-il Oum.
URL:https://dimag.ibs.re.kr/event/2021-03-02/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210309T163000
DTEND;TZID=Asia/Seoul:20210309T173000
DTSTAMP:20260419T063220
CREATED:20210225T090525Z
LAST-MODIFIED:20240707T081706Z
UID:3674-1615307400-1615311000@dimag.ibs.re.kr
SUMMARY:Debsoumya Chakraborti\, Some classical problems in graph saturation
DESCRIPTION:Graph saturation is one of the oldest areas of investigation in extremal combinatorics. A graph $G$ is called $F$-saturated if $G$ does not contain a subgraph isomorphic to $F$\, but the addition of any edge creates a copy of $F$. The function $\operatorname{sat}(n\,F)$ is defined to be the minimum number of edges in an $n$-vertex $F$-saturated graph. \nIn the first half of the talk\, we will discuss a generalization of Erdős-Hajnal-Moon theorem (1964)\, which determined the value of $\operatorname{sat}(n\,K_s)$. We resolve one of the fundamental questions of minimizing the number of cliques of size $r$ in a $K_s$-saturated graph for all sufficiently large number of vertices\, confirming a conjecture of Kritschgau\, Methuku\, Tait\, and Timmons. We further establish a corresponding stability result. \nIn the second half\, we will focus on a central conjecture in graph saturation made by Tuza (1986)\, which states that for every graph $F$\, the limit $\lim_{n \rightarrow \infty} \frac{\operatorname{sat}(n\,F)}{n}$ exists. We make progress in the negative direction of this conjecture. \nThis talk will be based on a joint work with Po-Shen Loh.
URL:https://dimag.ibs.re.kr/event/2021-03-09/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210316T163000
DTEND;TZID=Asia/Seoul:20210316T173000
DTSTAMP:20260419T063220
CREATED:20210304T000046Z
LAST-MODIFIED:20240705T190041Z
UID:3717-1615912200-1615915800@dimag.ibs.re.kr
SUMMARY:Se-Young Yun (윤세영)\, Regret in Online Recommendation Systems
DESCRIPTION:We propose a theoretical analysis of recommendation systems in an online setting\, where items are sequentially recommended to users over time. In each round\, a user\, randomly picked from a population of m users\, requests a recommendation. The decision-maker observes the user and selects an item from a catalogue of n items. Importantly\, an item cannot be recommended twice to the same user. The probabilities that a user likes each item are unknown. The performance of the recommendation algorithm is captured through its regret\, considering as a reference an Oracle algorithm aware of these probabilities. We investigate various structural assumptions on these probabilities: we derive for each structure regret lower bounds\, and devise algorithms achieving these limits. Interestingly\, our analysis reveals the relative weights of the different components of regret: the component due to the constraint of not presenting the same item twice to the same user\, that due to learning the chances users like items\, and finally that arising when learning the underlying structure. \nThis is joint work with Kaito Ariu\, Narae Ryu\, and Alexandre Proutière.
URL:https://dimag.ibs.re.kr/event/2021-03-16/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210322T163000
DTEND;TZID=Asia/Seoul:20210322T173000
DTSTAMP:20260419T063220
CREATED:20210307T042041Z
LAST-MODIFIED:20240705T190041Z
UID:3721-1616430600-1616434200@dimag.ibs.re.kr
SUMMARY:Hong Liu (刘鸿)\, Nested cycles with no geometric crossing
DESCRIPTION:In 1975\, Erdős asked the following question: what is the smallest function $f(n)$ for which all graphs with $n$ vertices and $f(n)$ edges contain two edge-disjoint cycles $C_1$ and $C_2$\, such that the vertex set of $C_2$ is a subset of the vertex set of $C_1$ and their cyclic orderings of the vertices respect each other? We prove the optimal linear bound $f(n)=O(n)$ using sublinear expanders. \nThis is joint work with Irene Gil Fernández\, Jaehoon Kim and Younjin Kim.
URL:https://dimag.ibs.re.kr/event/2021-03-22/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210330T163000
DTEND;TZID=Asia/Seoul:20210330T173000
DTSTAMP:20260419T063220
CREATED:20210225T090612Z
LAST-MODIFIED:20240707T081638Z
UID:3676-1617121800-1617125400@dimag.ibs.re.kr
SUMMARY:Casey Tompkins\, 3-uniform hypergraphs avoiding a cycle of length four
DESCRIPTION:We show that that the maximum number of of edges in a $3$-uniform hypergraph without a Berge-cycle of length four is at most $(1+o(1)) \frac{n^{3/2}}{\sqrt{10}}$. This improves earlier estimates by Győri and Lemons and by Füredi and Özkahya. Joint work with Ergemlidze\, Győri\, Methuku\, Salia.
URL:https://dimag.ibs.re.kr/event/2021-03-30/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR