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:20240101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20251208T163000
DTEND;TZID=Asia/Seoul:20251208T173000
DTSTAMP:20260506T091642
CREATED:20250812T235815Z
LAST-MODIFIED:20251206T235635Z
UID:11359-1765211400-1765215000@dimag.ibs.re.kr
SUMMARY:Matthew Kwan\, Exponential anticoncentration of the permanent
DESCRIPTION:Let A be a random n×n matrix with independent entries\, and suppose that the entries are “uniformly anticoncentrated” (for example\, A could be a uniformly random n×n matrix with ±1 entries). We prove that the permanent of A is exponentially anticoncentrated\, significantly improving previous bounds of Tao and Vu. Our proof also works for the determinant\, giving an alternative proof of a classical theorem of Kahn\, Komlós and Szemerédi. Joint work with Zach Hunter and Lisa Sauermann.
URL:https://dimag.ibs.re.kr/event/2025-12-08/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20251209T163000
DTEND;TZID=Asia/Seoul:20251209T173000
DTSTAMP:20260506T091642
CREATED:20250716T135828Z
LAST-MODIFIED:20251031T171121Z
UID:11244-1765297800-1765301400@dimag.ibs.re.kr
SUMMARY:Tuukka Korhonen\, Dynamic Treewidth in Logarithmic Time
DESCRIPTION:We present a dynamic data structure that maintains a tree decomposition of width at most 9k+8 of a dynamic graph with treewidth at most k\, which is updated by edge insertions and deletions. The amortized update time of our data structure is $2^{O(k)} \log n$\, where n is the number of vertices. The data structure also supports maintaining any “dynamic programming scheme” on the tree decomposition\, providing\, for example\, a dynamic version of Courcelle’s theorem with $O_k(\log n)$ amortized update time; the $O_k(⋅)$ notation hides factors that depend on k. This improves upon a result of Korhonen\, Majewski\, Nadara\, Pilipczuk\, and Sokołowski [FOCS 2023]\, who gave a similar data structure but with amortized update time $2^{k^{O(1)}} n^{o(1)}$. Furthermore\, our data structure is arguably simpler. Our main novel idea is to maintain a tree decomposition that is “downwards well-linked”\, which allows us to implement local rotations and analysis similar to those for splay trees. \nThis talk is based on arXiv:2504.02790.
URL:https://dimag.ibs.re.kr/event/2025-12-09/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20251216T163000
DTEND;TZID=Asia/Seoul:20251216T173000
DTSTAMP:20260506T091642
CREATED:20251128T074641Z
LAST-MODIFIED:20251128T074641Z
UID:11891-1765902600-1765906200@dimag.ibs.re.kr
SUMMARY:Chi Hoi Yip\, Cliques in Paley graphs and cyclotomic graphs
DESCRIPTION:Given a prime power $q \equiv 1 \pmod 4$\, the Paley graph of order $q$ is the graph defined over $\mathbb{F}_q$ (the finite field with $q$ elements)\, such that two vertices are adjacent if and only if their difference is a square in $\mathbb{F}_q$. In this talk\, I will present some recent progress on the clique number of Paley graphs of non-square order\, the characterization of maximum cliques in Paley graphs of square order\, as well as their extensions to cyclotomic graphs. In particular\, I will highlight a new proof of the Van Lint–MacWilliams’ conjecture using ideas from arithmetic combinatorics.
URL:https://dimag.ibs.re.kr/event/2025-12-16/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20251226T163000
DTEND;TZID=Asia/Seoul:20251226T173000
DTSTAMP:20260506T091642
CREATED:20251002T131231Z
LAST-MODIFIED:20251127T040716Z
UID:11684-1766766600-1766770200@dimag.ibs.re.kr
SUMMARY:Donggyu Kim (김동규)\, Grassmann-Plücker functions for orthogonal matroids
DESCRIPTION:We present a new cryptomorphic definition of orthogonal matroids with coefficients using Grassmann-Plücker functions. The equivalence is motivated by Cayley’s identities expressing principal and almost-principal minors of a skew-symmetric matrix in terms of its pfaffians. As a corollary of the new cryptomorphism\, we deduce that each component of the orthogonal Grassmannian is parameterized by certain part of the Plücker coordinates. \nThis is joint work with Changxin Ding.
URL:https://dimag.ibs.re.kr/event/2025-12-26/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20251230T163000
DTEND;TZID=Asia/Seoul:20251230T173000
DTSTAMP:20260506T091642
CREATED:20251126T141109Z
LAST-MODIFIED:20251126T141109Z
UID:11882-1767112200-1767115800@dimag.ibs.re.kr
SUMMARY:Yunbum Kook (국윤범)\, Sampling and volume computation
DESCRIPTION:Since the development of the first randomized polynomial-time algorithm for volume computation by Dyer\, Frieze\, and Kannan in 1989\, convex-body sampling has been a central problem at the intersection of algorithms\, geometry\, and probability. A major milestone came in 1997\, when Kannan\, Lovász\, and Simonovits analyzed the Ball Walk and formulated the influential KLS conjecture. This was extended to log-concave distributions by Lovász and Vempala in 2006\, and further accelerated by Cousins and Vempala in 2015 through warm-start generation techniques. \nIn this talk\, I will present a gentle introduction to these milestones and how they have been streamlined and improved in the past few years. The talk is based on joint work with Santosh Vempala.
URL:https://dimag.ibs.re.kr/event/2025-12-30/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR