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:20260423T153327
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:20260423T153327
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:20260423T153327
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:20210317T170000
DTEND;TZID=Asia/Seoul:20210317T180000
DTSTAMP:20260423T153327
CREATED:20210228T115822Z
LAST-MODIFIED:20240705T190042Z
UID:3692-1616000400-1616004000@dimag.ibs.re.kr
SUMMARY:Yixin Cao (操宜新)\, Recognizing (unit) interval graphs by zigzag graph searches
DESCRIPTION:Corneil\, Olariu\, and Stewart [SODA 1998; SIAM Journal on Discrete Mathematics 2009] presented a recognition algorithm for interval graphs by six graph searches. Li and Wu [Discrete Mathematics & Theoretical Computer Science 2014] simplified it to only four. The great simplicity of the latter algorithm is however eclipsed by the complicated and long proofs. The main purpose of this paper is to present a new and significantly shorter proof for Li and Wu’s algorithm\, as well as a simpler implementation. We also give a self-contained presentation of the recognition algorithm of Corneil [Discrete Applied Mathematics 2004] for unit interval graphs\, based on three sweeps of graph searches. Moreover\, we show that two sweeps are already sufficient. Toward the proofs of the main results\, we make several new structural observations that might be of independent interests.
URL:https://dimag.ibs.re.kr/event/2021-03-17/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210322T163000
DTEND;TZID=Asia/Seoul:20210322T173000
DTSTAMP:20260423T153327
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:20210324T170000
DTEND;TZID=Asia/Seoul:20210324T180000
DTSTAMP:20260423T153327
CREATED:20210219T024236Z
LAST-MODIFIED:20240705T191012Z
UID:3649-1616605200-1616608800@dimag.ibs.re.kr
SUMMARY:Édouard Bonnet\, Twin-width and ordered binary structures
DESCRIPTION:The twin-width of a graph G can be defined as the least integer d such that there is a sequence of length |V(G)| of (strictly) coarser and coarser partitions of its vertex set V(G)\, and every part X of every partition P of the sequence has at most d other parts Y of P with both at least one edge and at least one non-edge between X and Y.  Twin-width is closely tied to total orders on the vertices\, and can be extended to general binary structures. We will thus consider the twin-width of ordered binary structures\, or if you prefer\, matrices on a finite alphabet. This turns out to be key in understanding combinatorial\, algorithmic\, and model-theoretic properties of (hereditary) classes of those objects. We will see several characterizations of bounded twin-width for these classes. The main consequences in the three domains read as follows. \n\nEnumerative combinatorics: All the classes of 0\,1-matrices with superexponential growth have growth at least n! (in turn resolving a conjecture of Balogh\, Bollobás\, and Morris on the growth of hereditary classes of ordered graphs).\nAlgorithms: First-order model checking of ordered binary structures is tractable exactly when the twin-width is bounded.\nFinite model theory: Monadically-dependent and dependent hereditary classes of ordered binary structures are the same.\n\nIn addition we get a fixed-parameter algorithm approximating matrix twin-width within a function of the optimum\, which is still missing for unordered graphs. \nJoint work with Ugo Giocanti\, Patrice Ossona de Mendez\, and Stéphan Thomassé. Similar results have been obtained independently by Pierre Simon and Szymon Toruńczyk.
URL:https://dimag.ibs.re.kr/event/2021-03-24/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210330T163000
DTEND;TZID=Asia/Seoul:20210330T173000
DTSTAMP:20260423T153327
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