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:20210401T100000
DTEND;TZID=Asia/Seoul:20210401T110000
DTSTAMP:20260423T134231
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:20210406T163000
DTEND;TZID=Asia/Seoul:20210406T173000
DTSTAMP:20260423T134231
CREATED:20210308T061306Z
LAST-MODIFIED:20240705T190041Z
UID:3731-1617726600-1617730200@dimag.ibs.re.kr
SUMMARY:Rutger Campbell\, Matroid orientability and representability
DESCRIPTION:In this talk we will have a brief introduction to oriented matroids and their relation to real-representability.
URL:https://dimag.ibs.re.kr/event/2021-04-06/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210407T170000
DTEND;TZID=Asia/Seoul:20210407T180000
DTSTAMP:20260423T134231
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:20210413T163000
DTEND;TZID=Asia/Seoul:20210413T173000
DTSTAMP:20260423T134231
CREATED:20210329T063026Z
LAST-MODIFIED:20240705T190013Z
UID:3866-1618331400-1618335000@dimag.ibs.re.kr
SUMMARY:William Overman\, Some Ordered Ramsey Numbers of Graphs on Four Vertices
DESCRIPTION:Ordered Ramsey numbers were introduced in 2014 by Conlon\, Fox\, Lee\, and Sudakov. Their results included upper bounds for general graphs and lower bounds showing separation from classical Ramsey numbers. We show the first nontrivial results for ordered Ramsey numbers of specific small graphs. In particular we prove upper bounds for orderings of graphs on four vertices\, and determine some numbers exactly using  SAT solvers for lower bounds. These results are in the spirit of exact calculations for classical Ramsey numbers and use only elementary combinatorial arguments. \nThis is joint work with Jeremy Alm\, Kayla Coffey\, and Carolyn Langhoff.
URL:https://dimag.ibs.re.kr/event/2021-04-13/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210414T170000
DTEND;TZID=Asia/Seoul:20210414T180000
DTSTAMP:20260423T134231
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:20210420T163000
DTEND;TZID=Asia/Seoul:20210420T173000
DTSTAMP:20260423T134231
CREATED:20210416T123209Z
LAST-MODIFIED:20240705T185049Z
UID:3946-1618936200-1618939800@dimag.ibs.re.kr
SUMMARY:Sang-il Oum (엄상일)\, What is an isotropic system?
DESCRIPTION:Bouchet introduced isotropic systems in 1983 unifying some combinatorial features of binary matroids and 4-regular graphs. The concept of isotropic system is a useful tool to study vertex-minors of graphs and yet it is not well  known. I will give an introduction to isotropic systems.
URL:https://dimag.ibs.re.kr/event/2021-04-20/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210421T170000
DTEND;TZID=Asia/Seoul:20210421T180000
DTSTAMP:20260423T134231
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:20210427T163000
DTEND;TZID=Asia/Seoul:20210427T173000
DTSTAMP:20260423T134231
CREATED:20210419T130854Z
LAST-MODIFIED:20240705T185048Z
UID:3961-1619541000-1619544600@dimag.ibs.re.kr
SUMMARY:Jungho Ahn (안정호)\, Well-partitioned chordal graphs with the obstruction set and applications
DESCRIPTION:We introduce a new subclass of chordal graphs that generalizes split graphs\, which we call well-partitioned chordal graphs. Split graphs are graphs that admit a partition of the vertex set into cliques that can be arranged in a star structure\, the leaves of which are of size one. Well-partitioned chordal graphs are a generalization of this concept in the following two ways. First\, the cliques in the partition can be arranged in a tree structure\, and second\, each clique is of arbitrary size. We mainly provide a characterization of well-partitioned chordal graphs by forbidden induced subgraphs and give a polynomial-time algorithm that given any graph\, either finds an obstruction or outputs a partition of its vertex set that asserts that the graph is well-partitioned chordal. We demonstrate the algorithmic use of this graph class by showing that two variants of the problem of finding pairwise disjoint paths between k given pairs of vertices are in FPT\, parameterized by k\, on well-partitioned chordal graphs\, while on chordal graphs\, these problems are only known to be in XP. From the other end\, we introduce some problems that are polynomial-time solvable on split graphs but become NP-complete on well-partitioned chordal graphs. \nThis is joint work with Lars Jaffke\, O-joung Kwon\, and Paloma T. Lima.
URL:https://dimag.ibs.re.kr/event/2021-04-27/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210430T090000
DTEND;TZID=Asia/Seoul:20210430T122000
DTSTAMP:20260423T134231
CREATED:20210315T005534Z
LAST-MODIFIED:20240707T081537Z
UID:3794-1619773200-1619785200@dimag.ibs.re.kr
SUMMARY:Extremal and Probabilistic Combinatorics (2021 KMS Spring Meeting)
DESCRIPTION:A special session “Extremal and Probabilistic Combinatorics” at the 2021 KMS Spring Meeting is organized by Tuan Tran. \nURL: https://www.kms.or.kr/meetings/spring2021/ \nSpeakers and Schedule\nAll talks are on April 30. \n\n[9:00 am] Joonkyung Lee (이준경)\, University College London\n\nMajority dynamics on sparse random graphs\n\n\n[9:30 am] Dong Yeap Kang (강동엽)\, Unversity of Birmingham\n\nThe Erdős-Faber-Lovász conjecture and related results\n\n\n[10:00 am] Jinyoung Park (박진영)\, IAS\n\nThe threshold for the square of a Hamilton cycle\n\n\n[10:50 am] Debsoumya Chakraborti\, IBS Discrete Mathematics Group\n\nGeneralized graph saturation\n\n\n[11:20 am] Jaehoon Kim (김재훈)\, KAIST\n\nResolution of the Oberwolfach problem\n\n\n[11:50 am] Hong Liu\, University of Warwick\n\nSublinear expanders and its applications\n\n\n\n\n\n\nAbstracts\nDebsoumya Chakraborti\, Generalized graph saturation\nGraph saturation is one of the oldest areas of investigation in extremal combinatorics. A graph G is called F-saturated if G does not contain a subgraph isomorphic to F\, but the addition of any edge creates a copy of F. We resolve one of the most fundamental questions of minimizing the number of cliques of size r in a $K_s$-saturated graph for all sufficiently large numbers of vertices\, confirming a conjecture of Kritschgau\, Methuku\, Tait and Timmons. We further prove a corresponding stability result. This talk will be based on joint work with Po-Shen Loh. \nJaehoon Kim (김재훈)\, Resolution of the Oberwolfach problem\nThe Oberwolfach problem\, posed by Ringel in 1967\, asks for a decomposition of $K_{2n+1}$ into edge-disjoint copies of a given 2-factor. We show that this can be achieved for all large n. We actually prove a significantly more general result\, which allows for decompositions into more general types of factors. \nDong Yeap Kang (강동엽)\, The Erdős-Faber-Lovász conjecture and related results\nA 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. \n  \nJoonkyung Lee (이준경)\, Majority dynamics on sparse random graphs\nMajority dynamics on a graph G is a deterministic process such that every vertex updates its {-1\,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 {-1\,1}-assignment converges to the unanimity with high probability whenever p>> 1/n. \nThis conjecture was firstly confirmed for $p>Cn^{-1/2}$ for a large constant C>0 by Fountoulakis\, Kang and Makai. Although this result has been reproved recently by Tran and Vu and by Berkowitz and Devlin\, none of them managed to extend it beyond the barrier $p>Cn^{-1/2}$. We prove the conjecture for sparser random graphs G(n\,p)\, where $Dn^{-3/5}\log n < p < C n^{-1/2}$ with a large constant D>0. \nJoint work with Debsoumya Chakraborti\, Jeong Han Kim and Tuan Tran. \nHong Liu\, Sublinear expanders and its applications\nI will review the history of sublinear expander and present some recent applications\, which lead to resolutions of several long-standing problems in sparse graphs embeddings. \nJinyoung Park (박진영)\, The threshold for the square of a Hamilton cycle\nWe will talk about a recent result of Jeff Kahn\, Bhargav Narayanan\, and myself stating that the threshold for the random graph G(n\,p) to contain the square of a Hamilton cycle is $1/\sqrt n$\, resolving a conjecture of Kühn and Osthus from 2012. The proof idea is motivated by the recent work of Frankston and the three aforementioned authors on a conjecture of Talagrand — “a fractional version of Kahn-Kalai expectation threshold conjecture.”
URL:https://dimag.ibs.re.kr/event/2021-04-30/
CATEGORIES:Workshops and Conferences
END:VEVENT
END:VCALENDAR