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:20211005T163000
DTEND;TZID=Asia/Seoul:20211005T173000
DTSTAMP:20260424T061956
CREATED:20211005T073000Z
LAST-MODIFIED:20240707T080940Z
UID:4503-1633451400-1633455000@dimag.ibs.re.kr
SUMMARY:Eunjin Oh (오은진)\, Feedback Vertex Set on Geometric Intersection Graphs
DESCRIPTION:I am going to present an algorithm for computing a feedback vertex set of a unit disk graph of size k\, if it exists\, which runs in time $2^{O(\sqrt{k})}(n + m)$\, where $n$ and $m$ denote the numbers of vertices and edges\, respectively. This improves the $2^{O(\sqrt{k}\log k)}(n + m)$-time algorithm for this problem on unit disk graphs by Fomin et al. [ICALP 2017].
URL:https://dimag.ibs.re.kr/event/2021-10-05/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20211008T100000
DTEND;TZID=Asia/Seoul:20211008T110000
DTSTAMP:20260424T061956
CREATED:20211008T010000Z
LAST-MODIFIED:20240707T080932Z
UID:4450-1633687200-1633690800@dimag.ibs.re.kr
SUMMARY:Paul Seymour\, Polynomial bounds for chromatic number
DESCRIPTION:The Gyárfás-Sumner conjecture says that for every forest $H$\, there is a function $f$ such that the chromatic number $\chi(G)$ is at most $f(\omega(G))$ for every $H$-free graph $G$ (“$H$-free” means with no induced subgraph isomorphic to $H$\, and $\omega(G)$ is the size of the largest clique of $G$). This well-known conjecture has been proved only for a few types of forest. \nNevertheless\, there is a much stronger conjecture\, due to Esperet: that for every forest $H$\, there is a polynomial function $f$ as above. As one might expect\, this has been proved for even fewer types of forest; and the smallest tree $H$ for which Esperet’s conjecture is not known is the five-vertex path $P_5$. \nA third notorious conjecture is the Erdős-Hajnal conjecture\, that for every graph $H$\, there exists $c>0$ such that $\alpha(G)\omega(G)\ge |G|^c$ for every $H$-free graph $G$ (where $\alpha(G)$ is the size of the largest stable set of $G$). The smallest graph $H$ for which this is not known is also $P_5$\, which\, conveniently\, is a forest; and every forest that satisfies Esperet’s conjecture also satisfies the Erdős-Hajnal conjecture. So there is substantial interest in the chromatic numbers of $P_5$-free graphs. The best upper bound that was previously known\, due to Esperet\, Lemoine\, Maffray\, and Morel\, was that $\chi(G)\le (5/27)3^\omega(G)$ for every $P_5$-free graph $G$ with $\omega(G) > 2$. In recent work with Alex Scott and Sophie Spirkl\, we have proved several results related to Esperet’s conjecture\, including proofs of its truth for some new types of forest $H$\, and a “near-polynomial” bound when $H = P_5$\, that $\chi(G) \le \omega(G)^{\log_2(\omega(G))}$ for every $P_5$-free graph $G$ with $\omega(G) > 2$. We survey these results and give a proof of the new bound for $P_5$.
URL:https://dimag.ibs.re.kr/event/2021-10-08/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20211012T163000
DTEND;TZID=Asia/Seoul:20211012T173000
DTSTAMP:20260424T061956
CREATED:20211012T073000Z
LAST-MODIFIED:20240707T080915Z
UID:4374-1634056200-1634059800@dimag.ibs.re.kr
SUMMARY:Joonkyung Lee (이준경)\, Majority dynamics on sparse random graphs
DESCRIPTION:Majority dynamics on a graph $G$ is a deterministic process such that every vertex updates its $\pm 1$-assignment according to the majority assignment on its neighbor simultaneously at each step. Benjamini\, Chan\, O’Donnell\, Tamuz and Tan conjectured that\, in the Erdős-Rényi random graph $G(n\,p)$\, the random initial $\pm 1$-assignment converges to a $99\%$-agreement with high probability whenever $p=\omega(1/n)$. \nThis conjecture was first confirmed for $p\geq\lambda n^{-1/2}$ for a large constant $\lambda$ by Fountoulakis\, Kang and Makai. Although this result has been reproved recently by Tran and Vu and by Berkowitz and Devlin\, it was unknown whether the conjecture holds for $p< \lambda n^{-1/2}$. We break this $\Omega(n^{-1/2})$-barrier by proving the conjecture for sparser random graphs $G(n\,p)$\, where $\lambda’ n^{-3/5}\log n \leq p \leq \lambda n^{-1/2}$ with a large constant $\lambda’>0$. \nJoint work with Debsoumya Chakraborti\, Jeong Han Kim and Tuan Tran.
URL:https://dimag.ibs.re.kr/event/2021-10-12/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20211026T163000
DTEND;TZID=Asia/Seoul:20211026T173000
DTSTAMP:20260424T061956
CREATED:20211026T073000Z
LAST-MODIFIED:20240707T080901Z
UID:4709-1635265800-1635269400@dimag.ibs.re.kr
SUMMARY:Donggyu Kim (김동규)\, 𝝘-graphic delta-matroids and their applications
DESCRIPTION:Bouchet (1987) defined delta-matroids by relaxing the base exchange axiom of matroids. Oum (2009) introduced a graphic delta-matroid from a pair of a graph and its vertex subset. We define a $\Gamma$-graphic delta-matroid for an abelian group $\Gamma$\, which generalizes a graphic delta-matroid. \nFor an abelian group $\Gamma$\, a $\Gamma$-labelled graph is a graph whose vertices are labelled by elements of $\Gamma$. We prove that a certain collection of edge sets of a $\Gamma$-labelled graph forms a delta-matroid\, which we call a $\Gamma$-graphic delta-matroid\, and provide a polynomial-time algorithm to solve the separation problem\, which allows us to apply the symmetric greedy algorithm of Bouchet (1987) to find a maximum weight feasible set in such a delta-matroid. We also prove that a $\Gamma$-graphic delta-matroid is a graphic delta-matroid if and only if it is even. We prove that every $\mathbb{Z}_p^k$-graphic delta matroid is represented by some symmetric matrix over a field of characteristic of order $p^k$\, and if every $\Gamma$-graphic delta-matroid is representable over a finite field $\mathbb{F}$\, then $\Gamma$ is isomorphic to $\mathbb{Z}_p^k$ and $\mathbb{F}$ is a field of order $p^\ell$ for some prime $p$ and positive integers $k$ and $\ell$. \nThis is joint work with Duksang Lee and Sang-il Oum.
URL:https://dimag.ibs.re.kr/event/2021-10-26/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR