BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
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:20190101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20211125T163000
DTEND;TZID=Asia/Seoul:20211125T173000
DTSTAMP:20260418T024919
CREATED:20211125T073000Z
LAST-MODIFIED:20240705T181009Z
UID:4552-1637857800-1637861400@dimag.ibs.re.kr
SUMMARY:Tuukka Korhonen\, Fast FPT-Approximation of Branchwidth
DESCRIPTION:Branchwidth determines how graphs\, and more generally\, arbitrary connectivity (basically symmetric and submodular) functions could be decomposed into a tree-like structure by specific cuts. We develop a general framework for designing fixed-parameter tractable (FPT) 2-approximation algorithms for branchwidth of connectivity functions. The first ingredient of our framework is combinatorial. We prove a structural theorem establishing that either a sequence of particular refinement operations could decrease the width of a branch decomposition or that the width of the decomposition is already within a factor of 2 from the optimum. The second ingredient is an efficient implementation of the refinement operations for branch decompositions that support efficient dynamic programming. We present two concrete applications of our general framework. \n\nAn algorithm that for a given n-vertex graph G and integer k in time $2^{2^{O(k)}} n^2$ either constructs a rank decomposition of G of width at most 2k or concludes that the rankwidth of G is more than $k$. It also yields a $(2^{2k+1}−1)$-approximation algorithm for cliquewidth within the same time complexity\, which in turn\, improves to $f(k) n^2$ the running times of various algorithms on graphs of cliquewidth $k$. Breaking the “cubic barrier” for rankwidth and cliquewidth was an open problem in the area.\nAn algorithm that for a given n-vertex graph G and integer k in time $2^{O(k)} n$ either constructs a branch decomposition of G of width at most $2k$ or concludes that the branchwidth of G is more than $k$. This improves over the 3-approximation that follows from the recent treewidth 2-approximation of Korhonen [FOCS 2021].\n\nThis is joint work with Fedor Fomin.
URL:https://dimag.ibs.re.kr/event/2021-11-25/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20211111T163000
DTEND;TZID=Asia/Seoul:20211111T173000
DTSTAMP:20260418T024919
CREATED:20211111T073000Z
LAST-MODIFIED:20240705T181024Z
UID:4668-1636648200-1636651800@dimag.ibs.re.kr
SUMMARY:Sebastian Wiederrecht\, Matching Minors in Bipartite Graphs
DESCRIPTION:Matching minors are a specialisation of minors which preserves the existence and elementary structural properties of perfect matchings. They were first discovered as part of the study of the Pfaffian recognition problem on bipartite graphs (Polya’s Permanent Problem) and acted as a major inspiration for the definition of butterfly minors in digraphs. In this talk we consider the origin and motivation behind the study of matching minors\, the current state of the art\, and their relation to structural digraph theory. The main result is a generalisation of the structure theorem by Robertson et al. and McCuaig for $K_{3\,3}$-matching minor free bipartite graphs to bipartite graphs excluding $K_{t\,t}$ as a matching minor for general t. This generalisation can be seen as a matching theoretic version of the Flat Wall Theorem by Robertson and Seymour.
URL:https://dimag.ibs.re.kr/event/2021-11-11/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20211105T163000
DTEND;TZID=Asia/Seoul:20211105T173000
DTSTAMP:20260418T024919
CREATED:20211105T073000Z
LAST-MODIFIED:20240707T080839Z
UID:4555-1636129800-1636133400@dimag.ibs.re.kr
SUMMARY:Martin Milanič\, Tree Decompositions with Bounded Independence Number
DESCRIPTION:The independence number of a tree decomposition $\mathcal{T}$ of a graph is the smallest integer $k$ such that each bag of $\mathcal{T}$ induces a subgraph with independence number at most $k$. If a graph $G$ is given together with a tree decomposition with bounded independence number\, then the Maximum Weight Independent Set (MWIS) problem can be solved in polynomial time. Motivated by this observation\, we consider six graph containment relations—the subgraph\, topological minor\, and minor relations\, as well as their induced variants—and for each of them characterize the graphs $H$ for which any graph excluding $H$ with respect to the relation admits a tree decomposition with bounded independence number. Furthermore\, using a variety of tools including SPQR trees and potential maximal cliques\, we show how to obtain such tree decompositions efficiently. \nAs an immediate consequence\, we obtain that the MWIS problem can be solved in polynomial time in an infinite family of graph classes that properly contain the class of chordal graphs. In fact\, our approach shows that the Maximum Weight Independent $\mathcal{H}$-Packing problem\, a common generalization of the MWIS and the Maximum Weight Induced Matching problems\, can be solved in polynomial time in these graph classes. \nThis is joint work with Clément Dallard and Kenny Štorgel.
URL:https://dimag.ibs.re.kr/event/2021-11-05/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20211008T100000
DTEND;TZID=Asia/Seoul:20211008T110000
DTSTAMP:20260418T024919
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:20210930T163000
DTEND;TZID=Asia/Seoul:20210930T173000
DTSTAMP:20260418T024919
CREATED:20210930T073000Z
LAST-MODIFIED:20240707T080948Z
UID:4460-1633019400-1633023000@dimag.ibs.re.kr
SUMMARY:Péter Pál Pach\, The Alon-Jaeger-Tarsi conjecture via group ring identities
DESCRIPTION:The Alon-Jaeger-Tarsi conjecture states that for any finite field $\mathbb{F}$ of size at least 4  and any nonsingular matrix $M$ over $\mathbb{F}$ there exists a vector $x$ such that neither $x$ nor $Mx$ has a 0 component. In joint work with János Nagy we proved this conjecture when the size of the field is sufficiently large\, namely\, when $61
URL:https://dimag.ibs.re.kr/event/2021-09-30/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210818T170000
DTEND;TZID=Asia/Seoul:20210818T180000
DTSTAMP:20260418T024919
CREATED:20210818T080000Z
LAST-MODIFIED:20240705T182104Z
UID:4353-1629306000-1629309600@dimag.ibs.re.kr
SUMMARY:Petr Hliněný\, Twin-width is linear in the poset width
DESCRIPTION:Twin-width is a new parameter informally measuring how diverse are the neighbourhoods of the graph vertices\, and it extends also to other binary relational structures\, e.g. to digraphs and posets. It was introduced quite recently\, in 2020 by Bonnet\, Kim\, Thomassé\, and Watrigant. One of the core results of these authors is that FO model checking on graph classes of bounded twin-width is in FPT. With that result\, they also claimed that posets of bounded width have bounded twin-width\, thus capturing a prior result on FO model checking of posets of bounded width in FPT. However\, their translation from poset width to twin-width was indirect and giving only a very loose double-exponential bound. \nWe prove that posets of width d have twin-width at most 9d with a direct and elementary argument\, and show that this bound is tight up to a constant factor. Specifically\, for posets of width 2\, we prove that in the worst case their twin-width is also equal to 2. These two theoretical results are complemented with straightforward algorithms to construct the respective contraction sequence for a given poset. \n(Joint work with my student Jakub Balaban who obtained the main ideas in his bachelor thesis.)
URL:https://dimag.ibs.re.kr/event/2021-08-18/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210728T150000
DTEND;TZID=Asia/Seoul:20210728T160000
DTSTAMP:20260418T024919
CREATED:20210607T135955Z
LAST-MODIFIED:20240705T184022Z
UID:4228-1627484400-1627488000@dimag.ibs.re.kr
SUMMARY:Maria Chudnovsky\, Induced subgraphs and tree decompositions
DESCRIPTION:Tree decompositions are a powerful tool in structural graph theory; they are traditionally used in the context of forbidden graph minors. Connecting tree decompositions and forbidden induced subgraphs has until recently remained out of reach. \nTree decompositions are closely related to the existence of  “laminar collections of separations” in a graph\, which roughly means that the separations in the collection “cooperate” with each other\, and the pieces that are obtained when the graph is simultaneously decomposed by all the separations in the collection “line up” to form a tree structure. Such collections of separations come up naturally in the context of forbidden minors. \nIn the case of families where induced subgraphs are excluded\, while there are often natural separations\, they are  usually very far from forming a laminar collection. In what follows we mostly focus on families of graphs of bounded degree. It turns out that due to the bound on the degree\, these collections of natural separations can be partitioned into a bounded number of laminar collections. This in turn allows to us obtain a wide variety of structural and algorithmic results\, which we will survey in this talk.
URL:https://dimag.ibs.re.kr/event/2021-07-28/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210714T170000
DTEND;TZID=Asia/Seoul:20210714T180000
DTSTAMP:20260418T024919
CREATED:20210615T091821Z
LAST-MODIFIED:20240705T184018Z
UID:4257-1626282000-1626285600@dimag.ibs.re.kr
SUMMARY:Stefan Weltge\, Integer programs with bounded subdeterminants and two nonzeros per row
DESCRIPTION:We give a strongly polynomial-time algorithm for integer linear programs defined by integer coefficient matrices whose subdeterminants are bounded by a constant and that contain at most two nonzero entries in each row. The core of our approach is the first polynomial-time algorithm for the weighted stable set problem on graphs that do not contain more than k vertex-disjoint odd cycles\, where k is any constant. Previously\, polynomial-time algorithms were only known for k=0 (bipartite graphs) and for k=1. \nWe observe that integer linear programs defined by coefficient matrices with bounded subdeterminants and two nonzeros per column can be also solved in strongly polynomial-time\, using a reduction to b-matching. \nThis is joint work with Samuel Fiorini\, Gwenaël Joret\, and Yelena Yuditsky.
URL:https://dimag.ibs.re.kr/event/2021-07-14/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210630T170000
DTEND;TZID=Asia/Seoul:20210630T180000
DTSTAMP:20260418T024919
CREATED:20210617T062135Z
LAST-MODIFIED:20240707T081259Z
UID:4277-1625072400-1625076000@dimag.ibs.re.kr
SUMMARY:Florian Gut and Attila Joó\, Large vertex-flames in uncountable digraphs
DESCRIPTION:The local connectivity  $ \kappa_D(r\,v) $ from $ r $ to $ v $ is defined to be the maximal number of internally disjoint $r\rightarrow v $ paths in $ D $. A spanning subdigraph $ L $ of $ D $ with $  \kappa_L(r\,v)=\kappa_D(r\,v) $ for every $ v\in V-r $ must have at least $ \sum_{v\in V-r}\kappa_D(r\,v) $ edges. It was shown by Lovász that\, maybe surprisingly\, this lower bound is sharp for every finite digraph. The optimality of an $ L $ can be captured by the following characterization: For every $ v\in V-r $ there is a system $ \mathcal{P}_v $ of internally disjoint $ r\rightarrow v $ paths in $ L $ covering all the ingoing edges of $ v $ in $ L $ such that one can choose from  each $ P\in \mathcal{P}_v $ either an edge or an internal vertex in such a way that the resulting set meets every $ r\rightarrow v $ path of $ D $. We prove that every digraph of size at most $ \aleph_1 $  admits such a spanning subdigraph $ L $. The question if this remains true for larger digraphs remains open.
URL:https://dimag.ibs.re.kr/event/2021-06-30/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210616T170000
DTEND;TZID=Asia/Seoul:20210616T180000
DTSTAMP:20260418T024919
CREATED:20210428T010009Z
LAST-MODIFIED:20240705T184215Z
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: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210602T170000
DTEND;TZID=Asia/Seoul:20210602T180000
DTSTAMP:20260418T024919
CREATED:20210506T022454Z
LAST-MODIFIED:20240705T184206Z
UID:4042-1622653200-1622656800@dimag.ibs.re.kr
SUMMARY:Adam Zsolt Wagner\, Constructions in combinatorics via neural networks
DESCRIPTION:Recently\, significant progress has been made in the area of machine learning algorithms\, and they have quickly become some of the most exciting tools in a scientist’s toolbox. In particular\, recent advances in the field of reinforcement learning have led computers to reach superhuman level play in Atari games and Go\, purely through self-play. In this talk\, I will give a very basic introduction to neural networks and reinforcement learning algorithms. I will also indicate how these methods can be adapted to the “game” of trying to find a counterexample to a mathematical conjecture\, and show some examples where this approach was successful.
URL:https://dimag.ibs.re.kr/event/2021-06-02/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210526T170000
DTEND;TZID=Asia/Seoul:20210526T180000
DTSTAMP:20260418T024919
CREATED:20210424T122241Z
LAST-MODIFIED:20240707T081338Z
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: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210521T170000
DTEND;TZID=Asia/Seoul:20210521T180000
DTSTAMP:20260418T024919
CREATED:20210319T050153Z
LAST-MODIFIED:20240705T190024Z
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: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210512T170000
DTEND;TZID=Asia/Seoul:20210512T180000
DTSTAMP:20260418T024919
CREATED:20210319T045925Z
LAST-MODIFIED:20240705T190026Z
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: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210506T100000
DTEND;TZID=Asia/Seoul:20210506T110000
DTSTAMP:20260418T024919
CREATED:20210319T045807Z
LAST-MODIFIED:20240705T190027Z
UID:3813-1620295200-1620298800@dimag.ibs.re.kr
SUMMARY:Raul Lopes\, Adapting the Directed Grid Theorem into an FPT Algorithm
DESCRIPTION:The Grid Theorem of Robertson and Seymour [JCTB\, 1986] is one of the most important tools in the field of structural graph theory\, finding numerous applications in the design of algorithms for undirected graphs. An analogous version of the Grid Theorem in digraphs was conjectured by Johnson et al. [JCTB\, 2001] \, and proved by Kawarabayashi and Kreutzer [STOC\, 2015]. They showed that there is a function f(k) such that every digraph of directed tree-width at least f(k) contains a cylindrical grid of order k as a butterfly minor and stated that their proof can be turned into an XP algorithm\, with parameter k\, that either constructs a decomposition of the appropriate width\, or finds the claimed large cylindrical grid as a butterfly minor. \nIn this talk\, we present the ideas used in our adaptation of the Directed Grid Theorem into an FPT algorithm. We provide two FPT algorithms with parameter k. The first one either produces an arboreal decomposition of width 3k-2 or finds a haven of order k in a digraph D. The second one uses a bramble B that naturally occurs in digraphs of large directed tree-width to find a well-linked set of order k that is contained in the set of vertices of a path hitting all elements of B. As tools to prove these results\, we show how to solve a generalized version of the problem of finding balanced separators for a given set of vertices T in FPT time with parameter |T|. \nJoint work with Victor Campos\, Ana Karolinna Maia\, and Ignasi Sau.
URL:https://dimag.ibs.re.kr/event/2021-05-06/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210421T170000
DTEND;TZID=Asia/Seoul:20210421T180000
DTSTAMP:20260418T024919
CREATED:20210414T142646Z
LAST-MODIFIED:20240705T185049Z
UID:3936-1619024400-1619028000@dimag.ibs.re.kr
SUMMARY:Reinhard Diestel\, Tangles of set separations: a novel clustering method and type recognition in machine learning
DESCRIPTION:Traditional clustering identifies groups of objects that share certain qualities. Tangles do the converse: they identify groups of qualities that typically occur together. They can thereby discover\, relate\, and structure types: of behaviour\, political views\, texts\, or proteins. Tangles offer a new\, quantitative\, paradigm for grouping phenomena rather than things. They can identify key phenomena that allow predictions of others. Tangles also offer a new paradigm for clustering in large data sets.  \nThe mathematical theory of tangles has its origins in the theory of graph minors developed by Robertson and Seymour. It has recently been axiomatized in a way that makes it applicable to a wide range of contexts outside mathematics: from clustering in data science to predicting customer behaviour in economics\, from DNA sequencing and drug development to text analysis and machine learning. \nThis very informal talk will not show you the latest intricacies of abstract tangle theory (for which you can find links on the tangle pages of my website)\, but to win you over to join our drive to develop real tangle applications in areas as indicated above. We have some software to share\, but are looking for people to try it out with us on real-world examples! \nHere are some introductory pages from a book I am writing on this\, which may serve as an extended abstract: https://arxiv.org/abs/2006.01830
URL:https://dimag.ibs.re.kr/event/2021-04-21/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210414T170000
DTEND;TZID=Asia/Seoul:20210414T180000
DTSTAMP:20260418T024919
CREATED:20210301T235620Z
LAST-MODIFIED:20240707T081558Z
UID:3698-1618419600-1618423200@dimag.ibs.re.kr
SUMMARY:István Tomon\, Ramsey properties of semilinear graphs
DESCRIPTION:A graph $G$ is semilinear of bounded complexity if the vertices of $G$ are elements of $\mathbb{R}^{d}$\, and the edges of $G$ are defined by the sign patterns of $t$ linear functions\, where $d$ and $t$ are constants. In this talk\, I will present several results about the symmetric and asymmetric Ramsey properties of semilinear graphs. Some interesting instances of such graphs are intersection graphs of boxes\, interval overlap graphs\, and shift graphs\, so our results extend several well known theorems about the Ramsey and coloring properties of these geometrically defined graphs.
URL:https://dimag.ibs.re.kr/event/2021-04-14/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210407T170000
DTEND;TZID=Asia/Seoul:20210407T180000
DTSTAMP:20260418T024919
CREATED:20210301T235812Z
LAST-MODIFIED:20240705T190042Z
UID:3701-1617814800-1617818400@dimag.ibs.re.kr
SUMMARY:Michał Pilipczuk\, Structural properties of powers of sparse graphs
DESCRIPTION:For a graph G and an integer d\, the dth power of G is the graph $G^d$ on the same vertex set as G where two vertices are considered adjacent if and only if they are at distance at most d in G. Assuming that G is sparse\, what can we say about the structure in $G^d$? Certainly $G^d$ can be dense\, as the square of a star is a complete graph\, but $G^d$ still retains many properties that can be derived from the sparsity of G. We will present some recent results in this spirit\, in particular connected to colorings and to the Erdős-Hajnal property\, assuming that G is drawn from a fixed class of bounded expansion or from a fixed nowhere dense class. The talk will be based on the recent papers: “Clustering Powers of Sparse Graphs” (with J. Nešetřil\, P. Ossona de Mendez\, and X. Zhu) and “Erdős-Hajnal properties for powers of sparse graphs” (with M. Briański\, P. Micek\, and M. Seweryn).
URL:https://dimag.ibs.re.kr/event/2021-04-07/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210401T100000
DTEND;TZID=Asia/Seoul:20210401T110000
DTSTAMP:20260418T024919
CREATED:20210218T001134Z
LAST-MODIFIED:20240705T191014Z
UID:3642-1617271200-1617274800@dimag.ibs.re.kr
SUMMARY:Sophie Spirkl\, Pure pairs in ordered graphs
DESCRIPTION:A pure pair in a graph G is a pair of subsets A\, B of the vertex set of G such that in G\, either all of the edges or none of the edges between A and B are present. Pure pairs have been studied recently motivated by their connections to the Erdos-Hajnal conjecture. \nIn this talk\, I will discuss the topic of pure pairs in ordered graphs\, that is\, graphs with a linear ordering on their vertex set. If we exclude a graph H as an ordered induced subgraph\, how large a pure pair can we guarantee? I will talk about how the answer differs from the case of unordered graphs and show some of the techniques used. \nBased on joint work with Maria Chudnovsky\, Jacob Fox\, Alex Scott\, and Paul Seymour.
URL:https://dimag.ibs.re.kr/event/2021-04-01/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210324T170000
DTEND;TZID=Asia/Seoul:20210324T180000
DTSTAMP:20260418T024919
CREATED:20210219T024236Z
LAST-MODIFIED:20240705T191012Z
UID:3649-1616605200-1616608800@dimag.ibs.re.kr
SUMMARY:Édouard Bonnet\, Twin-width and ordered binary structures
DESCRIPTION:The twin-width of a graph G can be defined as the least integer d such that there is a sequence of length |V(G)| of (strictly) coarser and coarser partitions of its vertex set V(G)\, and every part X of every partition P of the sequence has at most d other parts Y of P with both at least one edge and at least one non-edge between X and Y.  Twin-width is closely tied to total orders on the vertices\, and can be extended to general binary structures. We will thus consider the twin-width of ordered binary structures\, or if you prefer\, matrices on a finite alphabet. This turns out to be key in understanding combinatorial\, algorithmic\, and model-theoretic properties of (hereditary) classes of those objects. We will see several characterizations of bounded twin-width for these classes. The main consequences in the three domains read as follows. \n\nEnumerative combinatorics: All the classes of 0\,1-matrices with superexponential growth have growth at least n! (in turn resolving a conjecture of Balogh\, Bollobás\, and Morris on the growth of hereditary classes of ordered graphs).\nAlgorithms: First-order model checking of ordered binary structures is tractable exactly when the twin-width is bounded.\nFinite model theory: Monadically-dependent and dependent hereditary classes of ordered binary structures are the same.\n\nIn addition we get a fixed-parameter algorithm approximating matrix twin-width within a function of the optimum\, which is still missing for unordered graphs. \nJoint work with Ugo Giocanti\, Patrice Ossona de Mendez\, and Stéphan Thomassé. Similar results have been obtained independently by Pierre Simon and Szymon Toruńczyk.
URL:https://dimag.ibs.re.kr/event/2021-03-24/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210317T170000
DTEND;TZID=Asia/Seoul:20210317T180000
DTSTAMP:20260418T024919
CREATED:20210228T115822Z
LAST-MODIFIED:20240705T190042Z
UID:3692-1616000400-1616004000@dimag.ibs.re.kr
SUMMARY:Yixin Cao (操宜新)\, Recognizing (unit) interval graphs by zigzag graph searches
DESCRIPTION:Corneil\, Olariu\, and Stewart [SODA 1998; SIAM Journal on Discrete Mathematics 2009] presented a recognition algorithm for interval graphs by six graph searches. Li and Wu [Discrete Mathematics & Theoretical Computer Science 2014] simplified it to only four. The great simplicity of the latter algorithm is however eclipsed by the complicated and long proofs. The main purpose of this paper is to present a new and significantly shorter proof for Li and Wu’s algorithm\, as well as a simpler implementation. We also give a self-contained presentation of the recognition algorithm of Corneil [Discrete Applied Mathematics 2004] for unit interval graphs\, based on three sweeps of graph searches. Moreover\, we show that two sweeps are already sufficient. Toward the proofs of the main results\, we make several new structural observations that might be of independent interests.
URL:https://dimag.ibs.re.kr/event/2021-03-17/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210217T100000
DTEND;TZID=Asia/Seoul:20210217T110000
DTSTAMP:20260418T024919
CREATED:20201231T022333Z
LAST-MODIFIED:20240707T081843Z
UID:3423-1613556000-1613559600@dimag.ibs.re.kr
SUMMARY:David Wood\, Tree densities of sparse graph classes
DESCRIPTION:This talk considers the following question at the intersection of extremal and structural graph theory: What is the maximum number of copies of a fixed forest $T$ in an $n$-vertex graph in a graph class $\mathcal{G}$ as $n\to \infty$? I will answer this question for a variety of sparse graph classes $\mathcal{G}$. In particular\, we show that the answer is $\Theta(n^{\alpha_d(T)})$ where $\alpha_d(T)$ is the size of the largest stable set in the subforest of $T$ induced by the vertices of degree at most $d$\, for some integer $d$ that depends on $\mathcal{G}$. For example\, when $\mathcal{G}$ is the class of $k$-degenerate graphs then $d=k$; when $\mathcal{G}$ is the class of graphs containing no $K_{s\,t}$-minor ($t\geq s$) then $d=s-1$; and when $\mathcal{G}$ is the class of $k$-planar graphs then $d=2$. All these results are in fact consequences of a single lemma in terms of a finite set of excluded subgraphs. This is joint work with Tony Huynh (arXiv:2009.12989).
URL:https://dimag.ibs.re.kr/event/2021-02-17/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210210T163000
DTEND;TZID=Asia/Seoul:20210210T173000
DTSTAMP:20260418T024919
CREATED:20201231T073729Z
LAST-MODIFIED:20240705T191150Z
UID:3428-1612974600-1612978200@dimag.ibs.re.kr
SUMMARY:Jie Ma (马杰)\, Non-repeated cycle lengths and Sidon sequences
DESCRIPTION:We prove a conjecture of Boros\, Caro\, Furedi and Yuster on the maximum number of edges in a 2-connected graph without repeated cycle lengths\, which is a restricted version of a longstanding problem of Erdos. Our proof together with the matched lower bound construction of Boros\, Caro\, Furedi and Yuster show that this problem can be conceptually reduced to the seminal problem of finding the maximum Sidon sequences in number theory. Joint work with Tianchi Yang.
URL:https://dimag.ibs.re.kr/event/2021-02-10/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210203T163000
DTEND;TZID=Asia/Seoul:20210203T173000
DTSTAMP:20260418T024919
CREATED:20201106T054235Z
LAST-MODIFIED:20240705T193028Z
UID:3241-1612369800-1612373400@dimag.ibs.re.kr
SUMMARY:Ron Aharoni\, Colorful KKM and multiple cakes division
DESCRIPTION:In the “cake partition” problem n players have each a list of preferred parts for any partition of the [0\,1] interval (“cake”) into n sub-intervals. Woodall\, Stromquist and Gale proved independently that under mild conditions on the list of preferences (like continuity) there is always a partition and assignment of parts to the players\, in which every player gets a piece belonging to her list of preferred parts. In fact\, Gale proved a colorful version of the famous KKM theorem\, not realizing that this is the same problem\, but on the other hand\, proved the problem its proper setting. I will discuss the case of partitioning more than one cake – how many players can you make happy\, when there is a general number of cakes\, and general number of players. \nJoint work with Eli Berger\, Joseph Briggs\, Erel Segal-Halevi and Shira Zerbib.
URL:https://dimag.ibs.re.kr/event/2021-02-03/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210127T100000
DTEND;TZID=Asia/Seoul:20210127T110000
DTSTAMP:20260418T024919
CREATED:20210114T124234Z
LAST-MODIFIED:20240705T191135Z
UID:3500-1611741600-1611745200@dimag.ibs.re.kr
SUMMARY:Dong Yeap Kang (강동엽)\, A proof of the Erdős-Faber-Lovász conjecture
DESCRIPTION:A hypergraph is linear if every pair of two distinct edges shares at most one vertex. A longstanding conjecture by Erdős\, Faber\, and Lovász in 1972\, states that the chromatic index of any linear hypergraph on $n$ vertices is at most $n$. \nIn this talk\, I will present the ideas to prove the conjecture for all large $n$. This is joint work with Tom Kelly\, Daniela Kühn\, Abhishek Methuku\, and Deryk Osthus.
URL:https://dimag.ibs.re.kr/event/2021-01-27/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210120T163000
DTEND;TZID=Asia/Seoul:20210120T173000
DTSTAMP:20260418T024919
CREATED:20201211T084524Z
LAST-MODIFIED:20240707T081951Z
UID:3358-1611160200-1611163800@dimag.ibs.re.kr
SUMMARY:Yusuke Kobayashi (小林 佑輔)\, An FPT Algorithm for Minimum Additive Spanner Problem
DESCRIPTION:For a positive integer t and a graph G\, an additive t-spanner of G is a spanning subgraph in which the distance between every pair of vertices is at most the original distance plus t. Minimum Additive t-Spanner Problem is to find an additive t-spanner with the minimum number of edges in a given graph\, which is known to be NP-hard. Since we need to care about global properties of graphs when we deal with additive t-spanners\, Minimum Additive t-Spanner Problem is hard to handle\, and hence only few results are known for it. In this talk\, we study Minimum Additive t-Spanner Problem from the viewpoint of parameterized complexity. We formulate a parameterized version of the problem in which the number of removed edges is regarded as a parameter\, and give a fixed-parameter algorithm for it. We also extend our result to (α\,β)-spanners.
URL:https://dimag.ibs.re.kr/event/2021-01-20/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210113T100000
DTEND;TZID=Asia/Seoul:20210113T110000
DTSTAMP:20260418T024919
CREATED:20201126T045239Z
LAST-MODIFIED:20240705T192124Z
UID:3318-1610532000-1610535600@dimag.ibs.re.kr
SUMMARY:Rose McCarty\, Vertex-minors and flooding immersions
DESCRIPTION:An immersion of a graph H into a graph G sends edges of H into edge-disjoint trails of G. We say the immersion is flooding if every edge of G is in one of the trails. Flooding immersions are interesting for Eulerian group-labelled graphs; in this context they behave quite differently from regular immersions. Moreover\, understanding such flooding immersions is a vital step towards understanding the structure of graphs with a forbidden vertex-minor. \nI will focus on explaining the connection to vertex-minors\, and on recent progress in this direction from ongoing joint work with Jim Geelen and Paul Wollan.
URL:https://dimag.ibs.re.kr/event/2021-01-13/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201230T100000
DTEND;TZID=Asia/Seoul:20201230T110000
DTSTAMP:20260418T024919
CREATED:20201220T231608Z
LAST-MODIFIED:20240707T082035Z
UID:3389-1609322400-1609326000@dimag.ibs.re.kr
SUMMARY:Paul Seymour\, The Erdős-Hajnal conjecture is true for excluding a five-cycle
DESCRIPTION:In an n-vertex graph\, there must be a clique or stable set of size at least $C\log n$\, and there are graphs where this bound is attained. But if we look at graphs not containing a fixed graph H as an induced subgraph\, the largest clique or stable set is bigger. \nErdős and Hajnal conjectured in 1977 that for every graph H\, there exists c>0 such that every H-free graph has a clique or stable set of size at least $|G|^c$ (“H-free” means not containing H as an induced subgraph\, and |G| means the number of vertices of G). This is still open\, even for some five-vertex graphs H; and the case that has attracted most attention is when H is a cycle of length five. \nIt is true in that case. We will give a sketch of the proof\, which is via applying a lemma about bipartite graphs\, a variant of a theorem of I. Tomon. \nThis lemma has several other applications to the Erdős-Hajnal conjecture. For instance\, it implies that for every cycle C and forest T\, there exists c>0 such that every graph that is both C-free and T’-free (where T’ is the complement of T) has a clique or stable set of size $|G|^c$. (Until now this was open when C has length five and T is a 5-vertex path.) \nJoint work with Maria Chudnovsky\, Alex Scott and Sophie Spirkl.
URL:https://dimag.ibs.re.kr/event/2020-12-30/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201217T100000
DTEND;TZID=Asia/Seoul:20201217T110000
DTSTAMP:20260418T024919
CREATED:20201028T010135Z
LAST-MODIFIED:20240707T082135Z
UID:3210-1608199200-1608202800@dimag.ibs.re.kr
SUMMARY:Jaiung Jun (전재웅)\, On the Hopf algebra of multi-complexes
DESCRIPTION:In combinatorics\, Hopf algebras appear naturally when studying various classes of combinatorial objects\, such as graphs\, matroids\, posets or symmetric functions. Given such a class of combinatorial objects\, basic information on these objects regarding assembly and disassembly operations are encoded in the algebraic structure of a Hopf algebra. One then hopes to use algebraic identities of a Hopf algebra to return to combinatorial identities of combinatorial objects of interest. \nIn this talk\, I introduce a general class of combinatorial objects\, which we call multi-complexes\, which simultaneously generalizes graphs\, hypergraphs and simplicial and delta complexes. I also introduce a combinatorial Hopf algebra obtained from multi-complexes. Then\, I describe the structure of the Hopf algebra of multi-complexes by finding an explicit basis of the space of primitives\, which is of combinatorial relevance. If time permits\, I will illustrate some potential applications. \nThis is joint work with Miodrag Iovanov.
URL:https://dimag.ibs.re.kr/event/2020-12-17/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201209T163000
DTEND;TZID=Asia/Seoul:20201209T173000
DTSTAMP:20260418T024919
CREATED:20201013T135938Z
LAST-MODIFIED:20240705T193042Z
UID:3125-1607531400-1607535000@dimag.ibs.re.kr
SUMMARY:Karl Heuer\, Even Circuits in Oriented Matroids
DESCRIPTION:In this talk I will state a generalisation of the even directed cycle problem\, which asks whether a given digraph contains a directed cycle of even length\, to orientations of regular matroids. Motivated by this problem\, I will define non-even oriented matroids generalising non-even digraphs\, which played a central role in resolving the computational complexity of the even dicycle problem. Then I will present and discuss our two results regarding these notions: \nFirst we shall see that the problem of detecting an even directed circuit in a regular matroid is polynomially equivalent to the recognition of non-even oriented matroids. \nSecond and with the main focus for this talk\, we shall characterise the class of non-even oriented bond matroids in terms of forbidden minors\, which complements an existing characterisation of non-even oriented graphic matroids by Seymour and Thomassen. The second result makes use of a new concept of minors for oriented matroids\, which generalises butterfly minors for digraphs to oriented matroids. \nThe part of this talk regarding the second result will be mostly graph theoretical and does not require much knowledge about Matroid Theory. \nThis talk is about joint work [1] with Raphael Steiner and Sebastian Wiederrecht. \n[1] K. Heuer\, R. Steiner and S. Wiederrecht\, Even Circuits in Oriented Matroids\, arxiv:2010.08988
URL:https://dimag.ibs.re.kr/event/2020-12-09/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
END:VCALENDAR