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:20211207T163000
DTEND;TZID=Asia/Seoul:20211207T173000
DTSTAMP:20260418T051043
CREATED:20211207T073000Z
LAST-MODIFIED:20240707T080616Z
UID:4804-1638894600-1638898200@dimag.ibs.re.kr
SUMMARY:Eun-Kyung Cho (조은경)\, Independent domination of graphs with bounded maximum degree
DESCRIPTION:The independent domination number of a graph $G$\, denoted $i(G)$\, is the minimum size of an independent dominating set of $G$. In this talk\, we prove a series of results regarding independent domination of graphs with bounded maximum degree. \nLet $G$ be a graph with maximum degree at most $k$ where $k \ge 1$. We prove that if $k = 4$\, then $i(G) \le \frac{5}{9}|V(G)|$\, which is tight. Generalizing this result and a result by Akbari et al.\, we suggest a conjecture on the upper bound of $i(G)$ for $k \ge 1$\, which is tight if true. \nLet $G’$ be a connected $k$-regular graph that is not $K_{k\, k}$ where $k\geq 3$. We prove that $i(G’)\le \frac{k-1}{2k-1}|V(G’)|$\, which is tight for $k \in \{3\, 4\}$\, generalizing a result by Lam\, Shiu\, and Sun. This result also answers a question by Goddard et al. in the affirmative. \nIn addition\, we show that $\frac{i(G’)}{\gamma(G’)} \le \frac{k^3-3k^2+2}{2k^2-6k+2}$\, strengthening upon a result of Knor\, Škrekovski\, and Tepeh\, where $\gamma(G’)$ is the domination number of $G’$. \nMoreover\, if we restrict $G’$ to be a cubic graph without $4$-cycles\, then we prove that $i(G’) \le \frac{4}{11}|V(G’)|$\, which improves a result by Abrishami and Henning. \nThis talk is based on joint work with Ilkyoo Choi\, Hyemin Kwon\, and Boram Park.
URL:https://dimag.ibs.re.kr/event/2021-12-07/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20211130T163000
DTEND;TZID=Asia/Seoul:20211130T173000
DTSTAMP:20260418T051043
CREATED:20211130T073000Z
LAST-MODIFIED:20240707T080630Z
UID:4852-1638289800-1638293400@dimag.ibs.re.kr
SUMMARY:Seonghyuk Im (임성혁)\, Large clique subdivisions in graphs without small dense subgraphs
DESCRIPTION:What is the largest number $f(d)$ where every graph with average degree at least $d$ contains a subdivision of $K_{f(d)}$? Mader asked this question in 1967 and $f(d) = \Theta(\sqrt{d})$ was proved by Bollobás and Thomason and independently by Komlós and Szemerédi. This is best possible by considering a disjoint union of $K_{d\,d}$. However\, this example contains a much smaller subgraph with the almost same average degree\, for example\, one copy of $K_{d\,d}$. \nIn 2017\, Liu and Montgomery proposed the study on the parameter $c_{\varepsilon}(G)$ which is the order of the smallest subgraph of $G$ with average degree at least $\varepsilon d(G)$. In fact\, they conjectured that for small enough $\varepsilon>0$\, every graph $G$ of average degree $d$ contains a clique subdivision of size $\Omega(\min\{d\, \sqrt{\frac{c_{\varepsilon}(G)}{\log c_{\varepsilon}(G)}}\})$. We prove that this conjecture holds up to a multiplicative $\min\{(\log\log d)^6\,(\log \log c_{\varepsilon}(G))^6\}$-term. \nAs a corollary\, for every graph $F$\, we determine the minimum size of the largest clique subdivision in $F$-free graphs with average degree $d$ up to multiplicative polylog$(d)$-term. \nThis is joint work with Jaehoon Kim\, Youngjin Kim\, and Hong Liu.
URL:https://dimag.ibs.re.kr/event/2021-11-30/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20211125T163000
DTEND;TZID=Asia/Seoul:20211125T173000
DTSTAMP:20260418T051043
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:20211123T163000
DTEND;TZID=Asia/Seoul:20211123T173000
DTSTAMP:20260418T051043
CREATED:20211123T073000Z
LAST-MODIFIED:20240707T080759Z
UID:4798-1637685000-1637688600@dimag.ibs.re.kr
SUMMARY:Casey Tompkins\, Ramsey numbers of Boolean lattices
DESCRIPTION:The poset Ramsey number $R(Q_{m}\,Q_{n})$ is the smallest integer $N$ such that any blue-red coloring of the elements of the Boolean lattice $Q_{N}$ has a blue induced copy of $Q_{m}$ or a red induced copy of $Q_{n}$. Axenovich and Walzer showed that $n+2\le R(Q_{2}\,Q_{n})\le2n+2$. Recently\, Lu and Thompson\nimproved the upper bound to $\frac{5}{3}n+2$. In this paper\, we solve this problem asymptotically by showing that $R(Q_{2}\,Q_{n})=n+O(n/\log n)$.\nJoint work with Dániel Grósz and Abhishek Methuku.
URL:https://dimag.ibs.re.kr/event/2021-11-23/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;VALUE=DATE:20211123
DTEND;VALUE=DATE:20211127
DTSTAMP:20260418T051043
CREATED:20211122T150000Z
LAST-MODIFIED:20240705T181013Z
UID:4872-1637625600-1637971199@dimag.ibs.re.kr
SUMMARY:Graph Product Structure Theory: Gathering of Participants from Korea
DESCRIPTION:On November 22-26\, 2021\, there is a “Graph Product Structure Theory” workshop in BIRS Centre in Banff (https://www.birs.ca/events/2021/5-day-workshops/21w5235)\, organized in a hybrid manner with 15 onsite participants and around 50 remote participants. We would like to meet in a group of 5-10 remote participants from Korea in one place\, creating a secondary workshop site in Korea. This would allow joint participation in online talks and in-person discussions between local participants.
URL:https://dimag.ibs.re.kr/event/2021-11-22/
LOCATION:Room B223\, IBS (기초과학연구원)
CATEGORIES:Workshops and Conferences
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20211111T163000
DTEND;TZID=Asia/Seoul:20211111T173000
DTSTAMP:20260418T051043
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:20211109T163000
DTEND;TZID=Asia/Seoul:20211109T173000
DTSTAMP:20260418T051043
CREATED:20211109T073000Z
LAST-MODIFIED:20240705T181024Z
UID:4588-1636475400-1636479000@dimag.ibs.re.kr
SUMMARY:Jaehoon Kim (김재훈)\, 2-complexes with unique embeddings in 3-space
DESCRIPTION:A well-known theorem of Whitney states that a 3-connected planar graph admits an essentially unique embedding into the 2-sphere. We prove a 3-dimensional analogue: a simply-connected 2-complex every link graph of which is 3-connected admits an essentially unique locally flat embedding into the 3-sphere\, if it admits one at all. This can be thought of as a generalisation of the 3-dimensional Schoenflies theorem. This is joint work with Agelos Georgakopoulos.
URL:https://dimag.ibs.re.kr/event/2021-11-09/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20211105T163000
DTEND;TZID=Asia/Seoul:20211105T173000
DTSTAMP:20260418T051043
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:20211102T163000
DTEND;TZID=Asia/Seoul:20211102T173000
DTSTAMP:20260418T051043
CREATED:20211109T073000Z
LAST-MODIFIED:20240707T080853Z
UID:4780-1635870600-1635874200@dimag.ibs.re.kr
SUMMARY:Ben Lund\, Maximal 3-wise intersecting families
DESCRIPTION:A family $\mathcal F$ of subsets of {1\,2\,…\,n} is called maximal k-wise intersecting if every collection of at most k members from $\mathcal F$ has a common element\, and moreover\, no set can be added to $\mathcal F$ while preserving this property. In 1974\, Erdős and Kleitman asked for the smallest possible size of a maximal k-wise intersecting family\, for k≥3. We resolve this problem for k=3 and n even and sufficiently large. \nThis is joint work with Kevin Hendrey\, Casey Tompkins\, and Tuan Tran.
URL:https://dimag.ibs.re.kr/event/2021-11-02/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20211026T163000
DTEND;TZID=Asia/Seoul:20211026T173000
DTSTAMP:20260418T051043
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
BEGIN:VEVENT
DTSTART;VALUE=DATE:20211020
DTEND;VALUE=DATE:20211023
DTSTAMP:20260418T051043
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:20211012T163000
DTEND;TZID=Asia/Seoul:20211012T173000
DTSTAMP:20260418T051043
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;TZID=Asia/Seoul:20211008T100000
DTEND;TZID=Asia/Seoul:20211008T110000
DTSTAMP:20260418T051043
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:20211005T163000
DTEND;TZID=Asia/Seoul:20211005T173000
DTSTAMP:20260418T051043
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:20210930T163000
DTEND;TZID=Asia/Seoul:20210930T173000
DTSTAMP:20260418T051043
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:20210928T163000
DTEND;TZID=Asia/Seoul:20210928T173000
DTSTAMP:20260418T051043
CREATED:20210928T073000Z
LAST-MODIFIED:20240707T080955Z
UID:4452-1632846600-1632850200@dimag.ibs.re.kr
SUMMARY:Kevin Hendrey\, Extremal functions for sparse minors
DESCRIPTION:The extremal function $c(H)$ of a graph $H$ is the supremum of densities of graphs not containing $H$ as a minor\, where the density of a graph is the ratio of the number of edges to the number of vertices. Myers and Thomason (2005)\, Norin\, Reed\, Thomason and Wood (2020)\, and Thomason and Wales (2019) determined the asymptotic behaviour of $c(H)$ for all polynomially dense graphs $H$\, as well as almost all graphs of constant density. We explore the asymptotic behavior of the extremal function in the regime not covered by the above results\, where in addition to having constant density the graph $H$ is in a graph class admitting strongly sublinear separators. We establish asymptotically tight bounds in many cases. For example\, we prove that for every planar graph $H$\, \[c(H) = (1+o(1))\max (v(H)/2\, v(H)-\alpha(H))\,\] extending recent results of Haslegrave\, Kim and Liu (2020). Joint work with Sergey Norin and David R. Wood.
URL:https://dimag.ibs.re.kr/event/2021-09-28/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210907T163000
DTEND;TZID=Asia/Seoul:20210907T173000
DTSTAMP:20260418T051043
CREATED:20210907T073000Z
LAST-MODIFIED:20240705T182054Z
UID:4495-1631032200-1631035800@dimag.ibs.re.kr
SUMMARY:Dabeen Lee (이다빈)\, Mixing sets\, submodularity\, and chance-constrained optimization
DESCRIPTION:A particularly important substructure in modeling joint linear chance-constrained programs with random right-hand sides and finite sample space is the intersection of mixing sets with common binary variables (and possibly a knapsack constraint). In this talk\, we first explain basic mixing sets by establishing a strong and previously unrecognized connection to submodularity. In particular\, we show that mixing inequalities with binary variables are nothing but the polymatroid inequalities associated with a specific submodular function. This submodularity viewpoint enables us to unify and extend existing results on valid inequalities and convex hulls of the intersection of multiple mixing sets with common binary variables. Then\, we study such intersections under an additional linking constraint lower bounding a linear function of the continuous variables. This is motivated from the desire to exploit the information encoded in the knapsack constraint arising in joint linear CCPs via the quantile cuts. We propose a new class of valid inequalities and characterize when this new class along with the mixing inequalities are sufficient to describe the convex hull. This is based on joint work with Fatma Fatma Kılınç-Karzan and Simge Küçükyavuz.
URL:https://dimag.ibs.re.kr/event/2021-09-07/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210831T163000
DTEND;TZID=Asia/Seoul:20210831T173000
DTSTAMP:20260418T051043
CREATED:20210831T073000Z
LAST-MODIFIED:20240707T081024Z
UID:4341-1630427400-1630431000@dimag.ibs.re.kr
SUMMARY:Cheolwon Heo (허철원)\, Representations of even-cycle matroids
DESCRIPTION:A signed graph is a pair $(G\,\Sigma)$ where $G$ is a graph and $\Sigma$ is a subset of edges of $G$. A cycle $C$ of $G$ is a subset of edges of $G$ such that every vertex of the subgraph of $G$ induced by $C$ has an even degree. We say that $C$ is even in $(G\,\Sigma)$ if $|C \cap \Sigma|$ is even; otherwise\, $C$ is odd. A matroid $M$ is an even-cycle matroid if there exists a signed graph $(G\,\Sigma)$ such that circuits of $M$ precisely corresponds to inclusion-wise minimal non-empty even cycles of $(G\,\Sigma)$. For even-cycle matroids\, two fundamental questions arise:\n(1) what is the relationship between two signed graphs representing the same even-cycle matroids?\n(2) how many signed graphs can an even-cycle matroid have?\nFor (a)\, we characterize two signed graphs $(G_1\,\Sigma_1)$ and $(G_2\,\Sigma_2)$ where $G_1$ and $G_2$ are $4$-connected that represent the same even-cycle matroids.\nFor (b)\, we introduce pinch-graphic matroids\, which can generate exponentially many representations even when the matroid is $3$-connected. An even-cycle matroid is a pinch-graphic matroid if there exists a signed graph with a pair of vertices such that every odd cycle intersects with at least one of them. We prove that there exists a constant $c$ such that if a matroid is even-cycle matroid that is not pinch-graphic\, then the number of representations is bounded by $c$. This is joint work with Bertrand Guenin and Irene Pivotto.
URL:https://dimag.ibs.re.kr/event/2021-08-31/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210824T163000
DTEND;TZID=Asia/Seoul:20210824T173000
DTSTAMP:20260418T051043
CREATED:20210810T073000Z
LAST-MODIFIED:20240707T081032Z
UID:4212-1629822600-1629826200@dimag.ibs.re.kr
SUMMARY:Eun Jung Kim (김은정)\, A Constant-factor Approximation for Weighted Bond Cover
DESCRIPTION:The Weighted $\mathcal F$-Vertex Deletion for a class $\mathcal F$ of graphs asks\, given a weighted graph $G$\, for a minimum weight vertex set $S$ such that $G-S\in\mathcal F$. The case when $\mathcal F$ is minor-closed and excludes some graph as a minor has received particular attention but a constant-factor approximation remained elusive for Weighted $\mathcal F$-Vertex Deletion. Only three cases of minor-closed $\mathcal F$ are known to admit constant-factor approximations\, namely Vertex Cover\, Feedback Vertex Set and Diamond Hitting Set. \nWe study the problem for the class $\mathcal F$ of $\theta_c$-minor-free graphs\, under the equivalent setting of the Weighted c-Bond Cover\, and present a constant-factor approximation algorithm using the primal-dual method. For this\, we leverage a structure theorem implicit in [Joret et al.\, SIDMA’14] which states the following: any graph $G$ containing a $\theta_c$-minor-model either contains a large two-terminal protrusion\, or contains a constant-size $\theta_c$-minor-model\, or a collection of pairwise disjoint constant-sized connected sets that can be contracted simultaneously to yield a dense graph. In the first case\, we tame the graph by replacing the protrusion with a special-purpose weighted gadget. For the second and third case\, we provide a weighting scheme which guarantees a local approximation ratio. Besides making an important step in the quest of (dis)proving a constant-factor approximation for Weighted $\mathcal F$-Vertex Deletion\, our result may be useful as a template for algorithms for other minor-closed families. \nThis is joint work with Euiwoong Lee and Dimitrios M. Thilikos.
URL:https://dimag.ibs.re.kr/event/2021-08-24/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210818T170000
DTEND;TZID=Asia/Seoul:20210818T180000
DTSTAMP:20260418T051043
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:20210817T163000
DTEND;TZID=Asia/Seoul:20210817T173000
DTSTAMP:20260418T051043
CREATED:20210817T073000Z
LAST-MODIFIED:20240707T081153Z
UID:4242-1629217800-1629221400@dimag.ibs.re.kr
SUMMARY:Linda Cook\, Two results on graphs with holes of restricted lengths
DESCRIPTION:We call an induced cycle of length at least four a hole. The parity of a hole is the parity of its length. Forbidding holes of certain types in a graph has deep structural implications. In 2006\, Chudnovksy\, Seymour\, Robertson\, and Thomas famously proved that a graph is perfect if and only if it does not contain an odd hole or a complement of an odd hole. In 2002\, Conforti\, Cornuéjols\, Kapoor\, and Vuškovíc provided a structural description of the class of even-hole-free graphs. I will describe the structure of all graphs that contain only holes of length $\ell$ for every $\ell \geq 7$ (joint work with Jake Horsfield\, Myriam Preissmann\, Paul Seymour\, Ni Luh Dewi Sintiari\, Cléophée Robin\, Nicolas Trotignon\, and Kristina Vuškovíc. \nAnalysis of how holes interact with graph structure has yielded detection algorithms for holes of various lengths and parities. In 1991\, Bienstock showed it is NP-Hard to test whether a graph G has an even (or odd) hole containing a specified vertex $v \in V(G)$. In 2002\, Conforti\, Cornuéjols\, Kapoor\, and Vuškovíc gave a polynomial-time algorithm to recognize even-hole-free graphs using their structure theorem. In 2003\, Chudnovsky\, Kawarabayashi\, and Seymour provided a simpler and slightly faster algorithm to test whether a graph contains an even hole. In 2019\, Chudnovsky\, Scott\, Seymour\, and Spirkl provided a polynomial-time algorithm to test whether a graph contains an odd hole. Later that year\, Chudnovsky\, Scott\, and Seymour strengthened this result by providing a polynomial-time algorithm to test whether a graph contains an odd hole of length at least $\ell$ for any fixed integer $\ell \geq 5$. I will present a polynomial-time algorithm (joint work with Paul Seymour) to test whether a graph contains an even hole of length at least $\ell$ for any fixed integer $\ell \geq 4$.
URL:https://dimag.ibs.re.kr/event/2021-08-17/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210810T163000
DTEND;TZID=Asia/Seoul:20210810T173000
DTSTAMP:20260418T051043
CREATED:20210817T073000Z
LAST-MODIFIED:20240705T183002Z
UID:4408-1628613000-1628616600@dimag.ibs.re.kr
SUMMARY:Duksang Lee (이덕상)\, Intertwining connectivities for vertex-minors and pivot-minors
DESCRIPTION:We show that for pairs (Q\,R) and (S\,T) of disjoint subsets of vertices of a graph G\, if G is sufficiently large\, then there exists a vertex v in V(G)−(Q∪R∪S∪T) such that there are two ways to reduce G by a vertex-minor operation while preserving the connectivity between Q and R and the connectivity between S and T. Our theorem implies an analogous theorem of Chen and Whittle (2014) for matroids restricted to binary matroids. Joint work with Sang-il Oum.
URL:https://dimag.ibs.re.kr/event/2021-08-10/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210728T150000
DTEND;TZID=Asia/Seoul:20210728T160000
DTSTAMP:20260418T051043
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:20210727T150000
DTEND;TZID=Asia/Seoul:20210727T160000
DTSTAMP:20260418T051043
CREATED:20210623T055635Z
LAST-MODIFIED:20240707T081214Z
UID:4288-1627398000-1627401600@dimag.ibs.re.kr
SUMMARY:Euiwoong Lee (이의웅)\, The Karger-Stein algorithm is optimal for k-cut
DESCRIPTION:In the k-cut problem\, we are given an edge-weighted graph and want to find the least-weight set of edges whose deletion breaks the graph into k connected components. It is easy to see that the elegant randomized contraction algorithm of Karger and Stein for global mincut (k=2) can be naturally extended for general k with the running time of $O(n^{2k-2})$. Using tree packings\, Thorup gave a deterministic algorithm that has the same running time. \nIn this work\, we show that for any fixed $k\ge 2$\, the Karger-Stein algorithm outputs any fixed minimum k-cut with probability at least $\Omega(n^{-k})$. This also gives an extremal bound of $O(n^k)$ on the number of minimum k-cuts in an n-vertex graph and an algorithm to compute a minimum k-cut in similar runtime. Both are essentially tight. The first main ingredient in our result is a fine-grained analysis of how the graph shrinks—and how the average degree evolves—under the Karger-Stein process. The second ingredient is an extremal result bounding the number of cuts of size at most $(2-\delta)OPT/k$\, using the Sunflower lemma. \nJoint work with Anupam Gupta\, David G. Harris\, and Jason Li.
URL:https://dimag.ibs.re.kr/event/2021-07-27/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210720T163000
DTEND;TZID=Asia/Seoul:20210720T173000
DTSTAMP:20260418T051043
CREATED:20210601T234138Z
LAST-MODIFIED:20240707T081226Z
UID:4190-1626798600-1626802200@dimag.ibs.re.kr
SUMMARY:Semin Yoo (유세민)\, Combinatorics of Euclidean spaces over finite fields
DESCRIPTION:$q$-analogues of quantities in mathematics involve perturbations of classical quantities using the parameter $q$\, and revert to the original quantities when $q$ goes $1$. An important example is the $q$-analogues of binomial coefficients\, denoted by $\binom{n}{k}_{q}$\, which give the number of $k$-dimensional subspaces in $\mathbb{F}_{q}^{n}$. When $q$ goes to $1$\, this reverts to the binomial coefficients which measure the number of $k$-sets in $\left [ n \right ]$. \nIn this talk\, we add one more structure in $\mathbb{F}_{q}^{n}$\, which is the Euclidean quadratic form: $\text{dot}_{n}:=x_{1}^{2}+x_{2}^{2}+\cdots+x_{n}^{2}$. It turns out that the number of quadratic subspaces of Euclidean type in $(\mathbb{F}_{q}^{n}\,\text{dot}_{n})$ can be described as the form of the analogue of binomial coefficients. The main goal of this talk is to define the dot-analogues of the binomial coefficients and to study related combinatorics. No prior knowledge about the theory of quadratic form is required.
URL:https://dimag.ibs.re.kr/event/2021-07-20/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210714T170000
DTEND;TZID=Asia/Seoul:20210714T180000
DTSTAMP:20260418T051043
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:20210713T163000
DTEND;TZID=Asia/Seoul:20210713T173000
DTSTAMP:20260418T051043
CREATED:20210519T133727Z
LAST-MODIFIED:20240707T081244Z
UID:4110-1626193800-1626197400@dimag.ibs.re.kr
SUMMARY:Jaehoon Kim (김재훈)\, $K_{r+1}$-saturated graphs with small spectral radius
DESCRIPTION:For a graph $H$\, a graph $G$ is $H$-saturated if $G$ does not contain $H$ as a subgraph but for any $e\in E(\overline G)$\, $G+e$ contains $H$. In this note\, we prove a sharp lower bound for the number of paths and walks on length 2 in $n$-vertex $K_{r+1}$-saturated graphs. We then use this bound to give a lower bound on the spectral radii of such graphs which is asymptotically tight for each fixed $r$ and $n\to \infty$.
URL:https://dimag.ibs.re.kr/event/2021-07-13/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210706T163000
DTEND;TZID=Asia/Seoul:20210706T173000
DTSTAMP:20260418T051043
CREATED:20210518T100610Z
LAST-MODIFIED:20240707T081252Z
UID:4101-1625589000-1625592600@dimag.ibs.re.kr
SUMMARY:Suil O (오수일)\, Eigenvalues and [a\, b]-factors in regular graphs
DESCRIPTION:For positive integers\, $r \ge 3\, h \ge 1\,$ and $k \ge 1$\, Bollobás\, Saito\, and Wormald proved some sufficient conditions for an $h$-edge-connected $r$-regular graph to have a k-factor in 1985. Lu gave an upper bound for the third-largest eigenvalue in a connected $r$-regular graph to have a $k$-factor in 2010. Gu found an upper bound for certain eigenvalues in an $h$-edge-connected $r$-regular graph to have a $k$-factor in 2014. For positive integers $a \le b$\, an even (or odd) $[a\, b]$-factor of a graph $G$ is a spanning subgraph $H$ such that for each vertex $v \in V (G)$\, $d_H(v)$ is even (or odd) and $a \le d_H(v) \le b$. In this talk\, we provide best upper bounds (in terms of $a\, b$\, and $r$) for certain eigenvalues (in terms of $a\, b\, r$\, and $h$) in an $h$-edge-connected $r$-regular graph $G$ to guarantee the existence of an even $[a\, b]$-factor or an odd $[a\, b]$-factor. This result extends the one of Bollobás\, Saito\, and Wormald\, the one of Lu\, and the one of Gu.
URL:https://dimag.ibs.re.kr/event/2021-07-06/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210630T170000
DTEND;TZID=Asia/Seoul:20210630T180000
DTSTAMP:20260418T051043
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:20210629T163000
DTEND;TZID=Asia/Seoul:20210629T173000
DTSTAMP:20260418T051043
CREATED:20210614T232723Z
LAST-MODIFIED:20240707T081306Z
UID:4251-1624984200-1624987800@dimag.ibs.re.kr
SUMMARY:Jeong Ok Choi (최정옥)\, Invertibility of circulant matrices of arbitrary size
DESCRIPTION:In this talk\, we present sufficient conditions to guarantee the invertibility of rational circulant matrices with any given size. These sufficient conditions consist of linear combinations in terms of the entries in the first row with integer coefficients. Using these conditions we show the invertibility of some family of circulant matrices with particular forms of integers generated by a primitive element in $\mathbb{Z}_p$. Also\, the invertibility of circulant 0\, 1-matrices can be argued combinatorially by applying sufficient conditions. This is joint work with Youngmi Hur.
URL:https://dimag.ibs.re.kr/event/2021-06-29/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR