BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv5.6.0//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
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:20210512T170000
DTEND;TZID=Asia/Seoul:20210512T180000
DTSTAMP:20210507T103606
CREATED:20210319T045925Z
LAST-MODIFIED:20210319T050304Z
UID:3816-1620838800-1620842400@dimag.ibs.re.kr
SUMMARY:Johannes Carmesin\, A Whitney type theorem for surfaces: characterising graphs with locally planar embeddings
DESCRIPTION:Given a graph\, how do we construct a surface so that the graph embeds in that surface in an optimal way? Thomassen showed that for minimum genus as optimality criterion\, this problem would be NP-hard. Instead of minimum genus\, here we use local planarity — and provide a polynomial algorithm. \nOur embedding method is based on Whitney’s trick to use matroids to construct embeddings in the plane. Consequently we obtain a characterisation of the graphs admitting locally planar embeddings in surfaces in terms of a certain matroid being co-graphic.
URL:https://dimag.ibs.re.kr/event/2021-05-12/
LOCATION:Zoom ID: 934 3222 0374 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210521T170000
DTEND;TZID=Asia/Seoul:20210521T180000
DTSTAMP:20210507T103606
CREATED:20210319T050153Z
LAST-MODIFIED:20210324T233711Z
UID:3818-1621616400-1621620000@dimag.ibs.re.kr
SUMMARY:Benjamin Bumpus\, Directed branch-width: A directed analogue of tree-width
DESCRIPTION:Many problems that are NP-hard in general become tractable on `structurally recursive’ graph classes. For example\, consider classes of bounded tree- or clique-width. Since the 1990s\, many directed analogues of tree-width have been proposed. However\, many natural problems (e.g. directed HamiltonPath and MaxCut) remain intractable on such digraph classes of `bounded width’. \nIn this talk\, I will introduce a new tree-width analogue for digraphs called directed branch-width which allows us to define digraph classes for which many problems (including directed HamiltonPath and MaxCut) become linear-time solvable. Furthermore\, via the definition of directed branch-width\, I will obtain a generalisation to digraphs of Gurski and Wanke’s characterization of graph classes of bounded tree-width in terms of their line graphs. \nThis is joint work with Kitty Meeks and William Pettersson.
URL:https://dimag.ibs.re.kr/event/2021-05-21/
LOCATION:Zoom ID: 934 3222 0374 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210526T170000
DTEND;TZID=Asia/Seoul:20210526T180000
DTSTAMP:20210507T103606
CREATED:20210424T122241Z
LAST-MODIFIED:20210426T123541Z
UID:3986-1622048400-1622052000@dimag.ibs.re.kr
SUMMARY:Dimitrios M. Thilikos\, Bounding Obstructions sets: the cases of apices of minor closed classes
DESCRIPTION:Given a minor-closed graph class ${\cal G}$\, the (minor) obstruction of ${\cal G}$ is the set of all minor-minimal graphs not in ${\cal G}$. Given a non-negative integer $k$\, we define the $k$-apex of ${\cal A}$ as the class containing every graph $G$ with a set $S$ of vertices whose removal from $G$ gives a graph on ${\cal G}$. We prove that every obstruction of the $k$-apex of ${\cal G}$ has size bounded by some 4-fold exponential function of $p(k)$ where p is a polynomial function whose degree depends on the size of the minor-obstructions of ${\cal G}$. This bound drops to a 2-fold exponential one when ${\cal G}$ excludes some apex graph as a minor (i.e.\, a graph in the $1$-apex of planar graphs). \nJoint work with Ignasi Sau and Giannos Stamoulis.
URL:https://dimag.ibs.re.kr/event/2021-05-26/
LOCATION:Zoom ID: 934 3222 0374 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210602T170000
DTEND;TZID=Asia/Seoul:20210602T180000
DTSTAMP:20210507T103606
CREATED:20210506T022454Z
LAST-MODIFIED:20210506T022454Z
UID:4042-1622653200-1622656800@dimag.ibs.re.kr
SUMMARY:Adam Zsolt Wagner\, TBA
DESCRIPTION:
URL:https://dimag.ibs.re.kr/event/adam-zsolt-wagner-tba/
LOCATION:Zoom ID: 934 3222 0374 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210616T170000
DTEND;TZID=Asia/Seoul:20210616T180000
DTSTAMP:20210507T103606
CREATED:20210428T010009Z
LAST-MODIFIED:20210428T010136Z
UID:4020-1623862800-1623866400@dimag.ibs.re.kr
SUMMARY:Alan Lew\, Representability and boxicity of simplicial complexes
DESCRIPTION:An interval graph is the intersection graph of a family of intervals in the real line. Motivated by problems in ecology\, Roberts defined the boxicity of a graph G to be the minimal k such that G can be written as the intersection of k interval graphs. \nA natural higher-dimensional generalization of interval graphs is the class d-representable complexes. These are simplicial complexes that carry the information on the intersection patterns of a family of convex sets in $\mathbb R^d$. We define the d-boxicity of a simplicial complex X to be the minimal k such that X can be written as the intersection of k d-representable complexes. \nA classical result of Roberts\, later rediscovered by Witsenhausen\, asserts that the boxicity of a graph with n vertices is at most n/2. Our main result is the following high dimensional extension of Roberts’ theorem: Let X be a simplicial complex on n vertices with minimal non-faces of dimension at most d. Then\, the d-boxicity of X is at most $\frac{1}{d+1}\binom{n}{d}$. \nExamples based on Steiner systems show that our result is sharp. The proofs combine geometric and topological ideas.
URL:https://dimag.ibs.re.kr/event/2021-06-16/
LOCATION:Zoom ID: 934 3222 0374 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
END:VCALENDAR