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:20210101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220307T163000
DTEND;TZID=Asia/Seoul:20220307T173000
DTSTAMP:20260420T121247
CREATED:20220307T073000Z
LAST-MODIFIED:20240705T174154Z
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:20220310T163000
DTEND;TZID=Asia/Seoul:20220310T173000
DTSTAMP:20260420T121247
CREATED:20220310T073000Z
LAST-MODIFIED:20240705T174146Z
UID:5176-1646929800-1646933400@dimag.ibs.re.kr
SUMMARY:Fedor Fomin\, Long cycles in graphs: Extremal Combinatorics meets Parameterized Algorithms
DESCRIPTION:We examine algorithmic extensions of two classic results of extremal combinatorics. First\, the theorem of Dirac from 1952 asserts that a 2-connected graph G with the minimum vertex degree d>1\, is either Hamiltonian or contains a cycle of length at least 2d. Second\, the theorem of Erdős-Gallai from 1959\, states that a 2-connected graph G with the average vertex degree D>1\, contains a cycle of length at least D. \nWe discuss the recent progress in parameterized complexity of computing long cycles “above” the guarantees established by these classical theorems: cycles of lengths at least 2d+k and D+k. \nThe talk is based on the joint works with Petr Golovach\, Danil Sagunov\, and Kirill Simonov.
URL:https://dimag.ibs.re.kr/event/2022-03-10/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220314T163000
DTEND;TZID=Asia/Seoul:20220314T173000
DTSTAMP:20260420T121247
CREATED:20220314T073000Z
LAST-MODIFIED:20240705T174136Z
UID:5218-1647275400-1647279000@dimag.ibs.re.kr
SUMMARY:Tuan Anh Do\, Rank- and tree-width of supercritical random graphs
DESCRIPTION:It is known that the rank- and tree-width of the random graph $G(n\,p)$ undergo a phase transition at $p = 1/n$; whilst for subcritical $p$\, the rank- and tree-width are bounded above by a constant\, for supercritical $p$\, both parameters are linear in $n$. The known proofs of these results use as a black box an important theorem of Benjamini\, Kozma\, and Wormald on the expansion of supercritical random graphs. We give a new\, short\, and direct proof of these results\, leading to more explicit bounds on these parameters\, and also consider the rank- and tree-width of supercritical random graphs closer to the critical point\, showing that this phase transition is smooth. \nThis is joint work with Joshua Erde and Mihyun Kang.
URL:https://dimag.ibs.re.kr/event/2022-03-14/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;VALUE=DATE:20220320
DTEND;VALUE=DATE:20220328
DTSTAMP:20260420T121247
CREATED:20220131T150000Z
LAST-MODIFIED:20240705T175059Z
UID:3527-1647734400-1648425599@dimag.ibs.re.kr
SUMMARY:MATRIX-IBS Workshop: Structural Graph Theory Downunder II
DESCRIPTION:This program consists of a short intensive workshop\, where mathematicians from across the globe will come together to work on open problems in structural graph theory. We will consider the following research themes: graph minors\, graph colouring\, Hadwiger’s Conjecture\, bounded expansion classes\, graph product structure theory\, generalised colouring numbers\, VC dimension\, induced subgraphs\, Erdős-Hajnal conjecture\, Gyárfás-Sumner conjecture\, twin-width\, asymptotic dimension. The majority of the time will be allocated to collaborative research (with only a few talks). The goal is to create an environment where mathematicians at all career stages work side-by-side. We anticipate that open problems will be solved\, and lasting collaborations will be initiated. \nURL: https://www.matrix-inst.org.au/events/structural-graph-theory-downunder-ll/ \nRegistration is by invitation only. If you are interested to participate in this research program\, please contact one of the organisers with your CV and research background. \n 
URL:https://dimag.ibs.re.kr/event/2022-03-20/
LOCATION:MATRIX\, Australia
CATEGORIES:Workshops and Conferences
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220321T163000
DTEND;TZID=Asia/Seoul:20220321T173000
DTSTAMP:20260420T121247
CREATED:20220321T073000Z
LAST-MODIFIED:20240707T080150Z
UID:5277-1647880200-1647883800@dimag.ibs.re.kr
SUMMARY:Jaehoon Kim (김재훈)\, Ramsey numbers of cycles versus general graphs
DESCRIPTION:The Ramsey number $R(F\,H)$ is the minimum number $N$ such that any $N$-vertex graph either contains a copy of $F$ or its complement contains $H$. Burr in 1981 proved a pleasingly general result that for any graph $H$\, provided $n$ is sufficiently large\, a natural lower bound construction gives the correct Ramsey number involving cycles: $R(C_n\,H)=(n-1)(\chi(H)-1)+\sigma(H)$\, where $\sigma(H)$ is the minimum possible size of a colour class in a $\chi(H)$-colouring of $H$. Allen\, Brightwell and Skokan conjectured that the same should be true already when $n\geq |H|\chi(H)$. \nWe improve this 40-year-old result of Burr by giving quantitative bounds of the form $n\geq C|H|\log^4\chi(H)$\, which is optimal up to the logarithmic factor. In particular\, this proves a strengthening of the Allen-Brightwell-Skokan conjecture for all graphs $H$ with large chromatic number. \nThis is joint work with John Haslegrave\, Joseph Hyde and Hong Liu
URL:https://dimag.ibs.re.kr/event/2022-03-21/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220328T163000
DTEND;TZID=Asia/Seoul:20220328T173000
DTSTAMP:20260420T121247
CREATED:20220314T051725Z
LAST-MODIFIED:20240707T080143Z
UID:5383-1648485000-1648488600@dimag.ibs.re.kr
SUMMARY:Ben Lund\, Thresholds for incidence properties in finite vector spaces
DESCRIPTION:Suppose that $E$ is a subset of $\mathbb{F}_q^n$\, so that each point is contained in $E$ with probability $\theta$\, independently of all other points. Then\, what is the probability that there is an $m$-dimensional affine subspace that contains at least $\ell$ points of $E$? What is the probability that $E$ intersects all $m$-dimensional affine subspaces? We give Erdős-Renyi threshold functions for these properties\, in some cases sharp thresholds. Our results improve previous work of Chen and Greenhill. This is joint work with Jeong Han Kim\, Thang Pham\, and Semin Yoo.
URL:https://dimag.ibs.re.kr/event/2022-03-28/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220330T163000
DTEND;TZID=Asia/Seoul:20220330T173000
DTSTAMP:20260420T121247
CREATED:20220330T073000Z
LAST-MODIFIED:20240707T080136Z
UID:5270-1648657800-1648661400@dimag.ibs.re.kr
SUMMARY:Jean-Florent Raymond\, Long induced paths in minor-closed graph classes and beyond
DESCRIPTION:In 1982 Galvin\, Rival\, and Sands proved that in $K_{t\,t}$-subgraph free graphs (t being fixed)\, the existence of a path of order n guarantees the existence of an induced path of order f(n)\, for some (slowly) increasing function f. The problem of obtaining good lower-bounds for f for specific graph classes was investigated decades later and logarithmic bounds have been obtained for planar graphs (more generally for graphs of bounded genus) and for interval graphs. \nIn this talk I will show that every graph of pathwidth less than k that has a path of order n also has an induced path of order $Ω(n^{1/k})$. I will then explain how this result can be used to prove the two following generalizations: \n\nevery graph of treewidth less than k that has a path of order n contains an induced path of order $Ω((\log n)^{1/k})$;\nfor every non-trivial graph class that is closed under topological minors there is a constant d∈(0\,1) such that every graph from this class that has a path of order n contains an induced path of order $Ω((\log n)^d)$.\n\nJoint work with Claire Hilaire.
URL:https://dimag.ibs.re.kr/event/2022-03-30/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
END:VCALENDAR