BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.0.5//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:20220711T163000
DTEND;TZID=Asia/Seoul:20220711T173000
DTSTAMP:20221209T154336
CREATED:20220711T073000Z
LAST-MODIFIED:20220706T054910Z
UID:5896-1657557000-1657560600@dimag.ibs.re.kr
SUMMARY:Kevin Hendrey\, Product Structure of Graph Classes with Bounded Treewidth
DESCRIPTION:The strong product $G\boxtimes H$ of graphs $G$ and $H$ is the graph on the cartesian product $V(G)\times V(H)$ such that vertices $(v\,w)$ and $(x\,y)$ are adjacent if and only if $\max\{d_G(v\,x)\,d_H(w\,y)\}=1$. Graph product structure theory aims to describe complicated graphs in terms of subgraphs of strong products of simpler graphs. This area of research was initiated by Dujmović\, Joret\, Micek\, Morin\, Ueckerdt and Wood\, who showed that every planar graph is a subgraph of the strong product of a $H\boxtimes P\boxtimes K_3$ for some path $P$ and some graph $H$ of treewidth at most $3$. In this talk\, I will discuss the product structure of various graph classes of bounded treewidth. As an example\, we show that there is a function $f:\mathbb{N}\rightarrow \mathbb{N}$ such that every planar graph of treewidth at most $k$ is a subgraph of $H\boxtimes K_{f(k)}$ for some graph $H$ of treewidth at most $3$. \nThis is based on joint work with Campbell\, Clinch\, Distel\, Gollin\, Hickingbotham\, Huynh\, Illingworth\, Tamitegama\, Tan and Wood.
URL:https://dimag.ibs.re.kr/event/2022-07-11/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220307T163000
DTEND;TZID=Asia/Seoul:20220307T173000
DTSTAMP:20221209T154336
CREATED:20220307T073000Z
LAST-MODIFIED:20220302T101458Z
UID:5315-1646670600-1646674200@dimag.ibs.re.kr
SUMMARY:Kevin Hendrey\, A unified Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups (revisited)
DESCRIPTION:This talk follows on from the recent talk of Pascal Gollin in this seminar series\, but will aim to be accessible for newcomers. \nErdős and Pósa proved in 1965 that there is a duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. By relaxing `packing’ to `half-integral packing’\, Reed obtained an analogous result for odd cycles\, and gave a structural characterisation of when the (integral) packing version fails. \nWe prove some far-reaching generalisations of these theorems. First\, we show that if the edges of a graph are labelled by finitely many abelian groups\, then the cycles whose values avoid a fixed finite set for each abelian group satisfy the half-integral Erdős-Pósa property. Similarly to Reed\, we give a structural characterisation for the failure of the integral Erdős-Pósa property in this setting. This allows us to deduce the full Erdős-Pósa property for many natural classes of cycles. \nWe will look at applications of these results to graphs embedded on surfaces\, and also discuss some possibilities and obstacles for extending these results. \nThis is joint work with Kevin Hendrey\, Ken-ichi Kawarabayashi\, O-joung Kwon\, Sang-il Oum\, and Youngho Yoo.
URL:https://dimag.ibs.re.kr/event/2022-03-07/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210928T163000
DTEND;TZID=Asia/Seoul:20210928T173000
DTSTAMP:20221209T154336
CREATED:20210928T073000Z
LAST-MODIFIED:20210831T095827Z
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:20210302T163000
DTEND;TZID=Asia/Seoul:20210302T173000
DTSTAMP:20221209T154336
CREATED:20210217T044249Z
LAST-MODIFIED:20210217T044740Z
UID:3639-1614702600-1614706200@dimag.ibs.re.kr
SUMMARY:Kevin Hendrey\, A unified half-integral Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups
DESCRIPTION:Erdős and Pósa proved in 1965 that there is a duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. Such a duality does not hold if we restrict to odd cycles. However\, in 1999\, Reed proved an analogue for odd cycles by relaxing packing to half-integral packing. We prove a far-reaching generalisation of the theorem of Reed; if the edges of a graph are labelled by finitely many abelian groups\, then there is a duality between the maximum size of a half-integral packing of cycles whose values avoid a fixed finite set for each abelian group and the minimum size of a vertex set hitting all such cycles. \nA multitude of natural properties of cycles can be encoded in this setting\, for example cycles of length at least $\ell$\, cycles of length $p$ modulo $q$\, cycles intersecting a prescribed set of vertices at least $t$ times\, and cycles contained in given $\mathbb{Z}_2$-homology classes in a graph embedded on a fixed surface. Our main result allows us to prove a duality theorem for cycles satisfying a fixed set of finitely many such properties. \nThis is joint work with J. Pascal Gollin\, Ken-ichi Kawarabayashi\, O-joung Kwon\, and Sang-il Oum.
URL:https://dimag.ibs.re.kr/event/2021-03-02/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200324T163000
DTEND;TZID=Asia/Seoul:20200324T173000
DTSTAMP:20221209T154336
CREATED:20200311T074415Z
LAST-MODIFIED:20200629T005903Z
UID:2186-1585067400-1585071000@dimag.ibs.re.kr
SUMMARY:Kevin Hendrey\, Covering radius in the Hamming permutation space
DESCRIPTION:Our problem can be described in terms of a two player game\, played with the set $\mathcal{S}_n$ of permutations on $\{1\,2\,\dots\,n\}$. First\, Player 1 selects a subset $S$ of $\mathcal{S}_n$ and shows it to Player 2. Next\, Player 2 selects a permutation $p$ from $\mathcal{S}_n$ as different as possible from the permutations in $S$\, and shows it to Player 1. Finally\, Player 1 selects a permutation $q$ from $S$\, and they compare $p$ and $q$. The aim of Player 1 is to ensure that $p$ and $q$ differ in few positions\, while keeping the size of $S$ small. The function $f(n\,s)$ can be defined as the minimum size of a set $S\subseteq \mathcal{S}_n$ that Player 1 can select in order to gaurantee that $p$ and $q$ will differ in at most $s$ positions. \nI will present some recent results on the function $f(n\,s)$. We are particularly interested in determining the value $f(n\,2)$\, which would resolve a conjecture of Kézdy and Snevily that implies several famous conjectures for Latin squares. Here we improve the best known lower bound\, showing that $f(n\,2)\geqslant 3n/4$. This talk is based on joint work with Ian M. Wanless.
URL:https://dimag.ibs.re.kr/event/2020-03-24/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20190910T163000
DTEND;TZID=Asia/Seoul:20190910T173000
DTSTAMP:20221209T154336
CREATED:20190903T042102Z
LAST-MODIFIED:20200629T010137Z
UID:1337-1568133000-1568136600@dimag.ibs.re.kr
SUMMARY:Kevin Hendrey\, The minimum connectivity forcing forest minors in large graphs
DESCRIPTION:Given a graph $G$\, we define $\textrm{ex}_c(G)$ to be the minimum value of $t$ for which there exists a constant $N(t\,G)$ such that every $t$-connected graph with at least $N(t\,G)$ vertices contains $G$ as a minor. The value of $\textrm{ex}_c(G)$ is known to be tied to the vertex cover number $\tau(G)$\, and in fact $\tau(G)\leq \textrm{ex}_c(G)\leq \frac{31}{2}(\tau(G)+1)$. We give the precise value of $\textrm{ex}_c(G)$ when $G$ is a forest. In particular we find that $\textrm{ex}_c(G)\leq \tau(G)+2$ in this setting\, which is tight for infinitely many forests.
URL:https://dimag.ibs.re.kr/event/2019-09-10/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR