BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv5.4.0//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
BEGIN:VTIMEZONE
TZID:Asia/Seoul
BEGIN:STANDARD
TZOFFSETFROM:+0900
TZOFFSETTO:+0900
TZNAME:KST
DTSTART:20210101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;VALUE=DATE:20220320
DTEND;VALUE=DATE:20220328
DTSTAMP:20210301T223753
CREATED:20210121T020148Z
LAST-MODIFIED:20210121T020554Z
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;VALUE=DATE:20210614
DTEND;VALUE=DATE:20210619
DTSTAMP:20210301T223753
CREATED:20190607T162650Z
LAST-MODIFIED:20210119T061301Z
UID:947-1623628800-1624060799@dimag.ibs.re.kr
SUMMARY:Seymour is Seventy
DESCRIPTION:A conference honouring the seventieth birthday of Paul Seymour \n\nTo be held in ENS de Lyon\, France\, June 15 – 19\, 2020. \nDue to the COVID-19\, the organizers decided to postpone the conference “Seymour is Seventy”. We hope to run this event in the summer of 2022 instead. Specific decisions on the dates are to be posted at https://dimag.ibs.re.kr/seymour70/ when the situation clarifies. \nConference Website: https://dimag.ibs.re.kr/seymour70/ \nSponsors: \n\nIBS Discrete Mathematics Group.\nLIP\, ENS de Lyon\, France.\nDepartment of Mathematics\, Princeton University.
URL:https://dimag.ibs.re.kr/event/seymour-is-seventy/
LOCATION:ENS de Lyon\, Lyon\, France
CATEGORIES:Workshops and Conferences
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210401T100000
DTEND;TZID=Asia/Seoul:20210401T110000
DTSTAMP:20210301T223753
CREATED:20210218T001134Z
LAST-MODIFIED:20210218T001134Z
UID:3642-1617271200-1617274800@dimag.ibs.re.kr
SUMMARY:Sophie Spirkl\, TBA
DESCRIPTION:
URL:https://dimag.ibs.re.kr/event/2021-04-01/
LOCATION:Zoom ID: 934 3222 0374 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210324T170000
DTEND;TZID=Asia/Seoul:20210324T180000
DTSTAMP:20210301T223753
CREATED:20210219T024236Z
LAST-MODIFIED:20210222T132118Z
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: 934 3222 0374 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210317T170000
DTEND;TZID=Asia/Seoul:20210317T180000
DTSTAMP:20210301T223753
CREATED:20210228T115822Z
LAST-MODIFIED:20210228T115822Z
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:20210316T163000
DTEND;TZID=Asia/Seoul:20210316T173000
DTSTAMP:20210301T223753
CREATED:20210225T090612Z
LAST-MODIFIED:20210225T090612Z
UID:3676-1615912200-1615915800@dimag.ibs.re.kr
SUMMARY:Casey Tompkins\, TBA
DESCRIPTION:
URL:https://dimag.ibs.re.kr/event/2021-03-16/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210309T163000
DTEND;TZID=Asia/Seoul:20210309T173000
DTSTAMP:20210301T223753
CREATED:20210225T090525Z
LAST-MODIFIED:20210226T044255Z
UID:3674-1615307400-1615311000@dimag.ibs.re.kr
SUMMARY:Debsoumya Chakraborti\, Some classical problems in graph saturation
DESCRIPTION:Graph 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$. The function $\operatorname{sat}(n\,F)$ is defined to be the minimum number of edges in an $n$-vertex $F$-saturated graph. \nIn the first half of the talk\, we will discuss a generalization of Erdős-Hajnal-Moon theorem (1964)\, which determined the value of $\operatorname{sat}(n\,K_s)$. We resolve one of the fundamental questions of minimizing the number of cliques of size $r$ in a $K_s$-saturated graph for all sufficiently large number of vertices\, confirming a conjecture of Kritschgau\, Methuku\, Tait\, and Timmons. We further establish a corresponding stability result. \nIn the second half\, we will focus on a central conjecture in graph saturation made by Tuza (1986)\, which states that for every graph $F$\, the limit $\lim_{n \rightarrow \infty} \frac{\operatorname{sat}(n\,F)}{n}$ exists. We make progress in the negative direction of this conjecture. \nThis talk will be based on a joint work with Po-Shen Loh.
URL:https://dimag.ibs.re.kr/event/2021-03-09/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210302T163000
DTEND;TZID=Asia/Seoul:20210302T173000
DTSTAMP:20210301T223753
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
END:VCALENDAR