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:20250103T163000
DTEND;TZID=Asia/Seoul:20250103T173000
DTSTAMP:20260417T083334
CREATED:20241119T145133Z
LAST-MODIFIED:20241204T064732Z
UID:10203-1735921800-1735925400@dimag.ibs.re.kr
SUMMARY:Huy Tuan Pham\, Random Cayley graphs and Additive combinatorics without groups
DESCRIPTION:A major goal of additive combinatorics is to understand the structures of subsets A of an abelian group G which has a small doubling K = |A+A|/|A|. Freiman’s celebrated theorem first provided a structural characterization of sets with small doubling over the integers\, and subsequently Ruzsa in 1999 proved an analog for abelian groups with bounded exponent. Ruzsa further conjectured the correct quantitative dependence on the doubling K in his structural result\, which has attracted several interesting developments over the next two decades. I will discuss a complete resolution of (a strengthening of) Ruzsa’s conjecture. \nSurprisingly\, our approach is crucially motivated by purely graph-theoretic insights\, where we find that the group structure is superfluous and can be replaced by much more general combinatorial structures. Using this general approach\, we also obtain combinatorial and nonabelian generalizations of classical results in additive combinatorics\, and solve longstanding open problems around Cayley graphs and random Cayley graphs motivated by Ramsey theory\, information theory and computer science. \nBased on joint work with David Conlon\, Jacob Fox and Liana Yepremyan.
URL:https://dimag.ibs.re.kr/event/2025-01-03/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20250114T163000
DTEND;TZID=Asia/Seoul:20250114T173000
DTSTAMP:20260417T083334
CREATED:20241226T072931Z
LAST-MODIFIED:20241230T145546Z
UID:10322-1736872200-1736875800@dimag.ibs.re.kr
SUMMARY:Tony Huynh\, The Peaceable Queens Problem
DESCRIPTION:The peaceable queens problem asks to determine the maximum number $a(n)$ such that there is a placement of $a(n)$ white queens and $a(n)$ black queens on an $n \times n$ chessboard so that no queen can capture any queen of the opposite color. \nWe consider the peaceable queens problem and its variant on the toroidal board.  For the regular board\, we show that $a(n) \leq 0.1716n^2$\, for all sufficiently large $n$.  This improves on the bound $a(n) \leq 0.25n^2$ of van Bommel and MacEachern. \nFor the toroidal board\, we provide new upper and lower bounds.  Somewhat surprisingly\, our bounds show that there is a sharp contrast in behaviour between the odd torus and the even torus.  Our lower bounds are given by explicit constructions.  For the upper bounds\, we formulate the problem as a non-linear optimization problem with at most 100 variables\, regardless of the size of the board. We solve our non-linear program exactly using modern optimization software. \nWe also provide a local search algorithm and a software implementation which converges very rapidly to solutions which appear optimal.  Our algorithm is sufficiently robust that it works on both the regular and toroidal boards.  For example\, for the regular board\, the algorithm quickly finds the so-called Ainley construction. \nThis is joint work with Katie Clinch\, Matthew Drescher\, and Abdallah Saffidine.
URL:https://dimag.ibs.re.kr/event/2025-01-14/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20250121T163000
DTEND;TZID=Asia/Seoul:20250121T173000
DTSTAMP:20260417T083334
CREATED:20241213T151545Z
LAST-MODIFIED:20241213T151545Z
UID:10270-1737477000-1737480600@dimag.ibs.re.kr
SUMMARY:Laure Morelle\, Bounded size modifications in time $2^{{\sf poly}(k)}\cdot n^2$
DESCRIPTION:A replacement action is a function $\mathcal L$ that maps each graph to a collection of subgraphs of smaller size. \nGiven a graph class $\mathcal H$\, we consider a general family of graph modification problems\, called “$\mathcal L$-Replacement to $\mathcal H$”\, where the input is a graph $G$ and the question is whether it is possible to replace some induced subgraph $H_1$ of $G$ on at most $k$ vertices by a graph $H_2$ in ${\mathcal L}(H_1)$ so that the resulting graph belongs to $\mathcal H$. \n“$\mathcal L$-Replacement to $\mathcal H$” can simulate many graph modification problems including vertex deletion\, edge deletion/addition/edition/contraction\, vertex identification\, subgraph complementation\, independent set deletion\, (induced) matching deletion/contraction\, etc. \nWe prove here that\, for any minor-closed graph class $\mathcal H$ and for any action $\mathcal L$ that is hereditary\, there is an algorithm that solves “$\mathcal L$-Replacement to $\mathcal H$” in time $2^{{\sf poly}(k)}\cdot |V(G)|^2$\, where $\sf poly$ is a polynomial whose degree depends on $\mathcal H$.
URL:https://dimag.ibs.re.kr/event/2025-01-21/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR