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:20220101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20230307T163000
DTEND;TZID=Asia/Seoul:20230307T173000
DTSTAMP:20260419T094601
CREATED:20230111T063520Z
LAST-MODIFIED:20240707T074009Z
UID:6655-1678206600-1678210200@dimag.ibs.re.kr
SUMMARY:Eunjin Oh (오은진)\, Parameterized algorithms for the planar disjoint paths problem
DESCRIPTION:Given an undirected planar graph $G$ with $n$ vertices and a set $T$ of $k$ pairs $(s_i\,t_i)_{i=1}^k$ of vertices\, the goal of the planar disjoint paths problem is to find a set $\mathcal P$ of $k$ pairwise vertex-disjoint paths connecting $s_i$ and $t_i$ for all indices $i\in\{1\,\ldots\,k\}$. This problem has been studied extensively due to its numerous applications such as VLSI layout and circuit routing. However\, this problem is NP-complete even for grid graphs. This motivates the study of this problem from the viewpoint of parameterized algorithms. \nIn this talk\, I will present a $2^{O(k^2)}n$-time algorithm for the planar disjoint paths problem. This improves the two previously best-known algorithms: $2^{2^{O(k)}}n$-time algorithm [Discrete Applied Mathematics 1995] and $2^{O(k^2)}n^6$-time algorithm [STOC 2020]. \nThis is joint work with Kyungjin Cho and Seunghyeok Oh.
URL:https://dimag.ibs.re.kr/event/2023-03-07/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20230309T100000
DTEND;TZID=Asia/Seoul:20230309T110000
DTSTAMP:20260419T094601
CREATED:20230118T233622Z
LAST-MODIFIED:20240707T074003Z
UID:6685-1678356000-1678359600@dimag.ibs.re.kr
SUMMARY:Marcelo Sales\, On Pisier type problems
DESCRIPTION:A subset $A\subseteq \mathbb Z$ of integers is free if for every two distinct subsets $B\, B’\subseteq A$ we have \[ \sum_{b\in B}b\neq \sum_{b’\in B’} b’.\]Pisier asked if for every subset $A\subseteq \mathbb Z$ of integers the following two statement are equivalent: \n(i) $A$ is a union of finitely many free sets.\n(ii) There exists $\epsilon>0$ such that every finite subset $B\subseteq A$ contains a free subset $C\subseteq B$ with $|C|\geq \epsilon |B|$. \nIn a more general framework\, the Pisier question can be seen as the problem of determining if statements (i) and (ii) are equivalent for subsets of a given structure with prescribed property. We study the problem for several structures including $B_h$-sets\, arithmetic progressions\, independent sets in hypergraphs and configurations in the euclidean space. This is joint work with Jaroslav Nešetřil and Vojtech Rödl.
URL:https://dimag.ibs.re.kr/event/2023-03-09/
LOCATION:Zoom ID: 224 221 2686 (ibsecopro)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20230314T163000
DTEND;TZID=Asia/Seoul:20230314T173000
DTSTAMP:20260419T094601
CREATED:20230120T011459Z
LAST-MODIFIED:20240707T073956Z
UID:6701-1678811400-1678815000@dimag.ibs.re.kr
SUMMARY:Stijn Cambie\, Recent progress on the Union-closed conjecture and related
DESCRIPTION:We give a summary on the work of the last months related to Frankl’s Union-Closed conjecture and its offsprings. The initial conjecture is stated as a theorem in extremal set theory; when a family F is union-closed (the union of sets of F is itself a set of $\mathcal F$)\, then $\mathcal F$ contains an (abundant) element that belongs to at least half of the sets. Meanwhile\, there are many related versions of the conjecture due to Frankl. For example\, graph theorists may prefer the equivalent statement that every bipartite graph has a vertex that belongs to no more than half of the maximal independent sets. While even proving the ε-Union-Closed Sets Conjecture was out of reach\, Poonen and Cui & Hu conjectured already stronger forms. \nAt the end of last year\, progress was made on many of these conjectures. Gilmer proved the ε-Union-Closed Sets Conjecture using an elegant entropy-based method which was sharpened by many others. Despite a sharp approximate form of the union-closed conjecture as stated by Chase and Lovett\, a further improvement was possible. In a different direction\, Kabela\, Polak and Teska constructed union-closed family sets with large sets and few abundant elements. \nThis talk will keep the audience up-to-date and give them insight in the main ideas. \nPeople who would like more details\, can join the Ecopro-reading session on the 14th of March (10 o’clock\, B332) as well. Here we go deeper in the core of the proofs and discuss possible directions for the full resolution.
URL:https://dimag.ibs.re.kr/event/2023-03-14/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20230316T100000
DTEND;TZID=Asia/Seoul:20230316T110000
DTSTAMP:20260419T094601
CREATED:20230213T121859Z
LAST-MODIFIED:20240707T073949Z
UID:6788-1678960800-1678964400@dimag.ibs.re.kr
SUMMARY:Paul Seymour\, A loglog step towards the Erdős-Hajnal conjecture
DESCRIPTION:In 1977\, Erdős and Hajnal made the conjecture that\, for every graph $H$\, there exists $c>0$ such that every $H$-free graph $G$ has a clique or stable set of size at least $|G|^c$; and they proved that this is true with $|G|^c$ replaced by $2^{c\sqrt{\log |G|}}$. \nThere has no improvement on this result (for general $H$) until now\, but now we have an improvement: that for every graph $H$\, there exists $c>0$ such that every $H$-free graph $G$ with $|G|\ge 2$ has a clique or stable set of size at least $$2^{c\sqrt{\log |G|\log\log|G|}}.$$ This talk will outline the proof. \nJoint work with Matija Bucić\, Tung Nguyen and Alex Scott.
URL:https://dimag.ibs.re.kr/event/2023-03-16/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20230321T163000
DTEND;TZID=Asia/Seoul:20230321T173000
DTSTAMP:20260419T094601
CREATED:20230204T071556Z
LAST-MODIFIED:20240705T170008Z
UID:6762-1679416200-1679419800@dimag.ibs.re.kr
SUMMARY:Younjin Kim (김연진)\, Problems on Extremal Combinatorics
DESCRIPTION:Extremal Combinatorics studies the maximum or minimum size of finite objects (numbers\, sets\, graphs) satisfying certain properties. In this talk\, I introduce the conjectures I solved on Extremal Combinatorics\, and also introduce recent extremal problems.
URL:https://dimag.ibs.re.kr/event/2023-03-21/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20230322T163000
DTEND;TZID=Asia/Seoul:20230322T173000
DTSTAMP:20260419T094601
CREATED:20230118T233720Z
LAST-MODIFIED:20240707T092054Z
UID:6688-1679502600-1679506200@dimag.ibs.re.kr
SUMMARY:Qizhong Lin\, Two classical Ramsey-Turán numbers involving triangles
DESCRIPTION:In 1993\, Erdős\, Hajnal\, Simonovits\, Sós and Szemerédi proposed to determine the value of Ramsey-Turán density $\rho(3\,q)$ for $q\ge3$. Erdős et al. (1993) and Kim\, Kim and Liu (2019) proposed two corresponding conjectures. However\, we only know four values of this Ramsey-Turán density by Erdős et al. (1993). There is no progress on this classical Ramsey-Turán density since then. In this talk\, I will introduce two new values of this classical Ramsey-Turán density. Moreover\, the corresponding asymptotically extremal structures are weakly stable\, which answers a problem of Erdős et al. (1993) for the two cases. Joint work with Xinyu Hu.
URL:https://dimag.ibs.re.kr/event/2023-03-22/
LOCATION:Zoom ID: 224 221 2686 (ibsecopro)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20230328T163000
DTEND;TZID=Asia/Seoul:20230328T173000
DTSTAMP:20260419T094601
CREATED:20230223T141945Z
LAST-MODIFIED:20240705T165050Z
UID:6831-1680021000-1680024600@dimag.ibs.re.kr
SUMMARY:Tianchi Yang\, On the maximum number of edges in k-critical graphs
DESCRIPTION:In this talk\, we will discuss the problem of determining the maximum number of edges in an n-vertex k-critical graph. A graph is considered k-critical if its chromatic number is k\, but any proper subgraph has a chromatic number less than k. The problem remains open for any integer k ≥ 4. Our presentation will showcase an improvement on previous results achieved by employing a combination of extremal graph theory and structural analysis. We will introduce a key lemma\, which may be of independent interest\, as it sheds light on the partial structure of dense k-critical graphs. This is joint work with Cong Luo and Jie Ma.
URL:https://dimag.ibs.re.kr/event/2023-03-28/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR