BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.16.1//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:20260514T185207
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:20260514T185207
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:20260514T185207
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;VALUE=DATE:20211020
DTEND;VALUE=DATE:20211023
DTSTAMP:20260514T185207
CREATED:20211019T150000Z
LAST-MODIFIED:20240707T092447Z
UID:4324-1634688000-1634947199@dimag.ibs.re.kr
SUMMARY:Young Researchers in Extremal and Probabilistic Combinatorics
DESCRIPTION:The aim of the Young Researchers in Extremal and Probabilistic Combinatorics is to bring together early career researchers working on these topics.  The workshop will consist of several  25 minute talks across three days from October 20 to 22\, 2021.  Due to Covid the workshop will be held online. \n \nInvited Speakers & Program\nOct. 20 Wednesday 4 PM (KST) – 8 PM (KST)\n\nAndrzej Grzesik (Jagiellonian University): Degenerated generalized Turán numbers of cycles\, 4:00-4:25\nJan Volec (Czech Technical University): Existence of common graphs with large chromatic number\, 4:30-4:55\nBalázs Patkós (Rényi Institute): Vector sum-intersection theorems\, 5:00-5:25\nIstván Tomon (ETH Zurich): Small doubling\, atomic structure and $\ell$-divisible set families\, 5:30-5:55\nMichael Anastos (Freie Universität Berlin): Longest Cycles in Sparse Random Graphs and Where to Find Them\, 6:30-6:55\nAdam Zsolt Wagner (Tel Aviv University): Constructions in combinatorics via neural networks\, 7:00-7:25\nYelena Yuditsky (Université libre de Bruxelles): On multicolor Ramsey numbers and subset-coloring of hypergraphs\, 7:30-7:55\n\nOct. 21 Thursday 4 PM (KST) – 8 PM (KST)\n\nKevin Hendrey (IBS Discrete Mathematics Group): Extremal functions for sparse minors\, 4:00-4:25\nSimona Boyadzhiyska (Freie Universität Berlin): Ramsey simplicity of random graphs\, 4:30-4:55\nShagnik Das (National Taiwan University): Schur’s Theorem in randomly perturbed sets\, 5:00-5:25\nTony Huynh (Monash University): Subgraph densities in minor-closed classes (and beyond)\, 5:30-5:55\nAnder Lamaison (Masaryk University): Hypergraphs with minimum uniform Turán density\, 6:30-6:55\nBen Lund (IBS Discrete Mathematics Group): Maximal 3-wise intersecting families\, 7:00-7:25\nLiana Yepremyan (London School of Economics): Enumerating independent sets in Abelian Cayley graphs\, 7:30-7:55\n\nOct. 22 Friday 4 PM (KST) – 8 PM (KST)\n\nAndrey Kupavskii (CNRS): Binary scalar products\, 4:00-4:25\nDániel Gerbner (Rényi Institute): Exact results for generalized Turán problems\, 4:30-4:55\nOliver Janzer (University of Cambridge): Tiling with monochromatic bipartite graphs of bounded maximum degree\, 5:00-5:25\nNika Salia (Rényi Institute): Pósa-type results for Berge Hypergraphs\, 5:30-5:55\nDebsoumya Chakraborti (IBS Discrete Mathematics Group): Mixing time and expanders\, 6:30-6:55\nWei-Tian Li (National Chung Hsing University): Ramsey Properties for $V$-shaped Posets in the Boolean Lattices\, 7:00-7:25\nDimitry Zakharov (Moscow Institute of Physics and Technology): Zero subsums in vector spaces over finite fields\, 7:30-7:55\n\nAbstracts (pdf file) \n 
URL:https://dimag.ibs.re.kr/event/2021-10-20/
LOCATION:Zoom ID: 554 788 7710 (507464)
CATEGORIES:Workshops and Conferences
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20211026T163000
DTEND;TZID=Asia/Seoul:20211026T173000
DTSTAMP:20260514T185207
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