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:20210608T150000
DTEND;TZID=Asia/Seoul:20210608T160000
DTSTAMP:20260418T060833
CREATED:20210514T092018Z
LAST-MODIFIED:20240707T081316Z
UID:4080-1623164400-1623168000@dimag.ibs.re.kr
SUMMARY:O-joung Kwon (권오정)\, Classes of intersection digraphs with good algorithmic properties
DESCRIPTION:An intersection digraph is a digraph where every vertex $v$ is represented by an ordered pair $(S_v\, T_v)$ of sets such that there is an edge from $v$ to $w$ if and only if $S_v$ and $T_w$ intersect. An intersection digraph is reflexive if $S_v\cap T_v\neq \emptyset$ for every vertex $v$. Compared to well-known undirected intersection graphs like interval graphs and permutation graphs\, not many algorithmic applications on intersection digraphs have been developed. \nMotivated by the successful story on algorithmic applications of intersection graphs using a graph width parameter called mim-width\, we introduce its directed analogue called `bi-mim-width’ and prove that various classes of reflexive intersection digraphs have bounded bi-mim-width. In particular\, we show that as a natural extension of $H$-graphs\, reflexive $H$-digraphs have linear bi-mim-width at most $12|E(H)|$\, which extends a bound on the linear mim-width of $H$-graphs [On the Tractability of Optimization Problems on $H$-Graphs. Algorithmica 2020] \nFor applications\, we introduce a novel framework of directed versions of locally checkable problems\, that streamlines the definitions and the study of many problems in the literature and facilitates their common algorithmic treatment. We obtain unified polynomial-time algorithms for these problems on digraphs of bounded bi-mim-width\, when a branch decomposition is given. Locally checkable problems include Kernel\, Dominating Set\, and Directed $H$-Homomorphism. \nThis seminar is a part of the\n“Round the World Relay in Combinatorics”\non June 8\, 2021.\nhttp://people.maths.ox.ac.uk/scott/relay.htm \n\n2:00 UTC\, 11:00 KST Melbourne (Australia) Monash University\nDavid Wood (Monash University)\, Universality in Minor-Closed Graph Classes\n3:00 UTC\, 12:00 KST Shanghai (China) Shanghai Center for Mathematical Sciences\nBaogang Xu (Nanjing Normal University\, China)\, On coloring of graphs of girth 2l+1 without longer odd holes\n4:00 UTC\, 13:00 KST Auckland (New Zealand) The University of Auckland\nJeroen Schillewaert (University of Auckland)\, Constructing highly regular expanders from hyperbolic Coxeter groups\n5:00 UTC\, 14:00 KST Sydney (Australia) Combinatorial Mathematics Society of Australasia\nGordon Royle (University of Western Australia (UWA))\, Real chromatic roots of planar graphs\n6:00 UTC\, 15:00 KST Daejeon (Korea) IBS Discrete Mathematics Group\nO-joung Kwon (Incheon National University and IBS Discrete Mathematics Group)\, Classes of intersection digraphs with good algorithmic properties\n7:00 UTC\, 16:00 KST Krakow (Poland) Jagiellonian University\nBartosz Walczak (Jagiellonian)\, Coloring polygon visibility graphs and their generalizations\n8:00 UTC\, 17:00 KST Glasgow (UK) University of Glasgow\nHeng Guo (University of Edinburgh)\, A Markov chain approach towards the sampling Lovász local lemma\n9:00 UTC\, 18:00 KST London (UK) London School of Economics\nAnnika Heckel (LMU)\, How does the chromatic number of a random graph vary?\n10:00 UTC\, 19:00 KST Moscow (Russia) Moscow Institute of Physics and Technology\nNoga Alon (Princeton and Tel Aviv)\n11:00 UTC\, 20:00 KST Budapest (Hungary) Hungarian Academy of Sciences + Eötvös Loránd University\nLászló Lovász (Eotvos University\, Budapest)\n12:00 UTC\, 21:00 KST Bordeaux (France) LaBRI\nCarla Groenland (Utrecht University)\, Universal Graphs and Labelling Schemes\n13:00 UTC\, 22:00 KST New York (USA) City University of New York + Montclair State University + Hofstra University\nDeepak Bal (Montclair State University)\n14:00 UTC\, 23:00 KST Prague (Czech) Czech Academy of Sciences + Czech Technical University + London School of Economics\nDhruv Mubayi (University of Illinois at Chicago)\, The feasible region of hypergraphs\n15:00 UTC\, 00:00 KST Brno (Czech) Masaryk University\nJames Davies (University of Waterloo)\, Colouring circle graphs and their generalisations\n16:00 UTC\, 01:00 KST Oxford (UK) University of Oxford\nJacob Fox (Stanford University)\, Removal lemmas\n17:00 UTC\, 02:00 KST Columbus (USA) Ohio State University\nAllan Sly (Princeton University)\n18:00 UTC\, 03:00 KST Rio (Brazil) Instituto de Matemática Pura e Aplicada\nMarcelo Campos (IMPA)\, The singularity probability of a random symmetric matrix is exponentially small\n19:00 UTC\, 04:00 KST Atlanta (USA) Georgia Institute of Technology\nJim Geelen (University of Waterloo)\, Homomorphisms and colouring for graphs and binary matroids\n20:00 UTC\, 05:00 KST Santiago (Chile) Universidad de Chile\nDavid Conlon (Caltech)\n21:00 UTC\, 06:00 KST Burnaby (Canada) Simon Fraser University\nFan Chung (UCSD)\, Trees and forests in Green’s functions of a graph\n22:00 UTC\, 07:00 KST Victoria (Canada) University of Victoria\nAndrew Suk (UCSD)\, Turán-type problems for point-line incidences\n23:00 UTC\, 08:00 KST Fairbanks (USA) University of Alaska\nRon Gould (Emory)\, Chorded cycles\n\n 
URL:https://dimag.ibs.re.kr/event/2021-06-08/
LOCATION:Zoom ID: 875 9395 3555 (relay) [CLOSED]
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR