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:20210511T163000
DTEND;TZID=Asia/Seoul:20210511T173000
DTSTAMP:20210507T105156
CREATED:20210420T015716Z
LAST-MODIFIED:20210423T113504Z
UID:3969-1620750600-1620754200@dimag.ibs.re.kr
SUMMARY:Mark Siggers\, The list switch homomorphism problem for signed graphs
DESCRIPTION:A signed graph is a graph in which each edge has a positive or negative sign. Calling two graphs switch equivalent if one can get from one to the other by the iteration of the local action of switching all signs on edges incident to a given vertex\, we say that there is a switch homomorphism from a signed graph $G$ to a signed graph $H$ if there is a sign preserving homomorphism from $G’$ to $H$ for some graph $G’$ that is switch equivalent to $G$. By reductions to CSP this problem\, and its list version\, are known to be either polynomial time solvable or NP-complete\, depending on $H$. Recently those signed graphs $H$ for which the switch homomorphism problem is in $P$ were characterised. Such a characterisation is yet unknown for the list version of the problem. \nWe talk about recent work towards such a characterisation and about how these problems fit in with bigger questions that still remain around the recent CSP dichotomy theorem.
URL:https://dimag.ibs.re.kr/event/2021-05-11/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210512T170000
DTEND;TZID=Asia/Seoul:20210512T180000
DTSTAMP:20210507T105156
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:20210518T163000
DTEND;TZID=Asia/Seoul:20210518T173000
DTSTAMP:20210507T105156
CREATED:20210420T015329Z
LAST-MODIFIED:20210422T050236Z
UID:3967-1621355400-1621359000@dimag.ibs.re.kr
SUMMARY:Pascal Gollin\, TBA
DESCRIPTION:
URL:https://dimag.ibs.re.kr/event/2021-05-18/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210521T170000
DTEND;TZID=Asia/Seoul:20210521T180000
DTSTAMP:20210507T105156
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:20210507T105156
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:20210507T105156
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:20210615T163000
DTEND;TZID=Asia/Seoul:20210615T173000
DTSTAMP:20210507T105156
CREATED:20210430T062352Z
LAST-MODIFIED:20210430T062352Z
UID:4028-1623774600-1623778200@dimag.ibs.re.kr
SUMMARY:Hongseok Yang (양홍석)\, DAG-symmetries and Symmetry-Preserving Neural Networks
DESCRIPTION:The preservation of symmetry is one of the key tools for designing data-efficient neural networks. A representative example is convolutional neural networks (CNNs); they preserve translation symmetries\, and this symmetry preservation is often attributed to their success in real-world applications. In the machine-learning community\, there is a growing body of work that explores a new type of symmetries\, both discrete and continuous\, and studies neural networks that preserve those symmetries. \nIn this talk\, I will explain what I call DAG-symmetries and our preliminary results on the shape of neural networks that preserve these symmetries. DAG-symmetries are finite variants of DAG-exchangeability developed by Jung\, Lee\, Staton\, and Yang (2020) in the context of probabilistic symmetries. Using these symmetries\, we can express that when a neural network works on\, for instance\, sets of bipartite graphs whose edges are labelled with reals\, the network depends on neither the order of elements in the set nor the identities of vertices of the graphs. I will explain how a group of specific DAG-symmetries is constructed by applying a form of wreath product over a given finite DAG. Then\, I will explain what linear layers of neural networks preserving these symmetries should look like. \nThis is joint work with Dongwoo Oh.
URL:https://dimag.ibs.re.kr/event/2021-06-15/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210616T170000
DTEND;TZID=Asia/Seoul:20210616T180000
DTSTAMP:20210507T105156
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
BEGIN:VEVENT
DTSTART;VALUE=DATE:20220320
DTEND;VALUE=DATE:20220328
DTSTAMP:20210507T105156
CREATED:20210121T020148Z
LAST-MODIFIED:20210121T020554Z
UID:3527-1647734400-1648425599@dimag.ibs.re.kr
SUMMARY:MATRIX-IBS Workshop: Structural Graph Theory Downunder II
DESCRIPTION:This program consists of a short intensive workshop\, where mathematicians from across the globe will come together to work on open problems in structural graph theory. We will consider the following research themes: graph minors\, graph colouring\, Hadwiger’s Conjecture\, bounded expansion classes\, graph product structure theory\, generalised colouring numbers\, VC dimension\, induced subgraphs\, Erdös-Hajnal conjecture\, Gyárfás-Sumner conjecture\, twin-width\, asymptotic dimension. The majority of the time will be allocated to collaborative research (with only a few talks). The goal is to create an environment where mathematicians at all career stages work side-by-side. We anticipate that open problems will be solved\, and lasting collaborations will be initiated. \nURL: https://www.matrix-inst.org.au/events/structural-graph-theory-downunder-ll/ \nRegistration is by invitation only. If you are interested to participate in this research program\, please contact one of the organisers with your CV and research background. \n
URL:https://dimag.ibs.re.kr/event/2022-03-20/
LOCATION:MATRIX\, Australia
CATEGORIES:Workshops and Conferences
END:VEVENT
BEGIN:VEVENT
DTSTART;VALUE=DATE:20220620
DTEND;VALUE=DATE:20220625
DTSTAMP:20210507T105156
CREATED:20190607T162650Z
LAST-MODIFIED:20210402T115110Z
UID:947-1655683200-1656115199@dimag.ibs.re.kr
SUMMARY:Seymour is Seventy
DESCRIPTION:A conference honouring the seventieth birthday of Paul Seymour \n\nTo be held in ENS de Lyon\, France\, June 15 – 19\, 2020. \nDue to the COVID-19\, the organizers decided to postpone the conference “Seymour is Seventy”. We hope to run this event in the summer of 2022 instead. Specific decisions on the dates are to be posted at https://dimag.ibs.re.kr/seymour70/ when the situation clarifies. \nConference Website: https://dimag.ibs.re.kr/seymour70/ \nSponsors: \n\nIBS Discrete Mathematics Group.\nLIP\, ENS de Lyon\, France.\nDepartment of Mathematics\, Princeton University.
URL:https://dimag.ibs.re.kr/event/seymour-is-seventy/
LOCATION:ENS de Lyon\, Lyon\, France
CATEGORIES:Workshops and Conferences
END:VEVENT
END:VCALENDAR