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:20210101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20221004T163000
DTEND;TZID=Asia/Seoul:20221004T173000
DTSTAMP:20260419T224807
CREATED:20220825T224353Z
LAST-MODIFIED:20240707T074613Z
UID:6077-1664901000-1664904600@dimag.ibs.re.kr
SUMMARY:Zixiang Xu (徐子翔)\, On the degenerate Turán problems
DESCRIPTION:For a graph $F$\, the Turán number is the maximum number of edges in an $n$-vertex simple graph not containing $F$. The celebrated Erdős-Stone-Simonovits Theorem gives that \[ \text{ex}(n\,F)=\bigg(1-\frac{1}{\chi(F)-1}+o(1)\bigg)\binom{n}{2}\,\] where $\chi(F)$ is the chromatic number of $H$. This theorem asymptotically solves the problem when $\chi(F)\geqslant 3$. In case of bipartite graphs $F$\, not even the order of magnitude is known in general. In this talk\, I will introduce some recent progress on Turán numbers of bipartite graphs and related generalizations and discuss several methods developed in recent years. Finally\, I will introduce some interesting open problems on this topic.
URL:https://dimag.ibs.re.kr/event/2022-10-04/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20221006T100000
DTEND;TZID=Asia/Seoul:20221006T110000
DTSTAMP:20260419T224807
CREATED:20221002T082503Z
LAST-MODIFIED:20240705T171138Z
UID:6236-1665050400-1665054000@dimag.ibs.re.kr
SUMMARY:Konstantin Tikhomirov\, A remark on the Ramsey number of the hypercube
DESCRIPTION:A well-known conjecture of Burr and Erdős asserts that the Ramsey number $r(Q_n)$ of the hypercube $Q_n$ on $2^n$ vertices is of the order $O(2^n)$. In this paper\, we show that $r(Q_n)=O(2^{2n−cn})$ for a universal constant $c>0$\, improving upon the previous best-known bound $r(Q_n)=O(2^{2n})$\, due to Conlon\, Fox\, and Sudakov.
URL:https://dimag.ibs.re.kr/event/2022-10-06/
LOCATION:Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED]
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20221011T163000
DTEND;TZID=Asia/Seoul:20221011T173000
DTSTAMP:20260419T224807
CREATED:20220824T132239Z
LAST-MODIFIED:20240707T074556Z
UID:6067-1665505800-1665509400@dimag.ibs.re.kr
SUMMARY:Nika Salia\, Exact results for generalized extremal problems forbidding an even cycle
DESCRIPTION:We determine the maximum number of copies of $K_{s\,s}$ in a $C_{2s+2}$-free $n$-vertex graph for all integers $s \ge 2$ and sufficiently large $n$. Moreover\, for $s\in\{2\,3\}$ and any integer $n$ we obtain the maximum number of cycles of length $2s$ in an $n$-vertex $C_{2s+2}$-free bipartite graph. \nThis is joint work with Ervin Győri (Renyi Institute)\, Zhen He (Tsinghua University)\, Zequn Lv (Tsinghua University)\, Casey Tompkins (Renyi Institute)\, Kitti Varga (Technical University of Budapest BME)\, and Xiutao Zhu (Nanjing University).
URL:https://dimag.ibs.re.kr/event/2022-10-11/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20221013T161500
DTEND;TZID=Asia/Seoul:20221013T171500
DTSTAMP:20260419T224807
CREATED:20221006T054719Z
LAST-MODIFIED:20240705T171138Z
UID:6264-1665677700-1665681300@dimag.ibs.re.kr
SUMMARY:Xavier Goaoc\, Order types and their symmetries
DESCRIPTION:Order types are a combinatorial classification of finite point sets used in discrete and computational geometry. This talk will give an introduction to these objects and their analogue for the projective plane\, with an emphasis on their symmetry groups. \nThis is joint work with Emo Welzl.
URL:https://dimag.ibs.re.kr/event/2022-10-13/
LOCATION:Room 1501\, Bldg. E6-1\, KAIST
CATEGORIES:Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20221018T163000
DTEND;TZID=Asia/Seoul:20221018T173000
DTSTAMP:20260419T224807
CREATED:20220824T133830Z
LAST-MODIFIED:20240705T171142Z
UID:6071-1666110600-1666114200@dimag.ibs.re.kr
SUMMARY:Florent Koechlin\, Uniform random expressions lack expressivity
DESCRIPTION:In computer science\, random expressions are commonly used to analyze algorithms\, either to study their average complexity\, or to generate benchmarks to test them experimentally. In general\, these approaches only consider the expressions as purely syntactic trees\, and completely ignore their semantics — i.e. the mathematical object represented by the expression. \nHowever\, two different expressions can be equivalent (for example “0*(x+y)” and “0” represent the same expression\, the null expression). Can these redundancies question the relevance of the analyses and tests that do not take into account the semantics of the expressions? \nI will present how the uniform distribution over syntactic expression becomes completely degenerate when we start taking into account their semantics\, in a very simple but common case where there is an absorbing element. If time permits it\, I will briefly explain why the BST distribution offers more hope. \nThis is a joint work with Cyril Nicaud and Pablo Rotondo.
URL:https://dimag.ibs.re.kr/event/2022-10-18/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20221027T161500
DTEND;TZID=Asia/Seoul:20221027T171500
DTSTAMP:20260419T224807
CREATED:20221012T134118Z
LAST-MODIFIED:20240705T171136Z
UID:6311-1666887300-1666890900@dimag.ibs.re.kr
SUMMARY:Dabeen Lee (이다빈)\, Non-smooth and Hölder-smooth submodular optimization
DESCRIPTION:We study the problem of maximizing a continuous DR-submodular function that is not necessarily smooth. We prove that the continuous greedy algorithm achieves an [(1−1/e)OPT−ϵ] guarantee when the function is monotone and Hölder-smooth\, meaning that it admits a Hölder-continuous gradient. For functions that are non-differentiable or non-smooth\, we propose a variant of the mirror-prox algorithm that attains an [(1/2)OPT−ϵ] guarantee. We apply our algorithmic frameworks to robust submodular maximization and distributionally robust submodular maximization under Wasserstein ambiguity. In particular\, the mirror-prox method applies to robust submodular maximization to obtain a single feasible solution whose value is at least (1/2)OPT−ϵ. For distributionally robust maximization under Wasserstein ambiguity\, we deduce and work over a submodular-convex maximin reformulation whose objective function is Hölder-smooth\, for which we may apply both the continuous greedy method and the mirror-prox method.\nJoint work with Duksang Lee and Nam Ho-Ngyuen.
URL:https://dimag.ibs.re.kr/event/2022-10-27/
LOCATION:Room 1501\, Bldg. E6-1\, KAIST
CATEGORIES:Colloquium
END:VEVENT
END:VCALENDAR