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:20220602T103000 DTEND;TZID=Asia/Seoul:20220602T113000 DTSTAMP:20260420T070625 CREATED:20220602T013000Z LAST-MODIFIED:20240707T075917Z UID:5595-1654165800-1654169400@dimag.ibs.re.kr SUMMARY:Jeck Lim\, Sums of linear transformations DESCRIPTION:We show that if $L_1$ and $L_2$ are linear transformations from $\mathbb{Z}^d$ to $\mathbb{Z}^d$ satisfying certain mild conditions\, then\, for any finite subset $A$ of $\mathbb{Z}^d$\, \[ |L_1 A+L_2 A|\geq (|\det(L_1)|^{1/d}+|\det(L_2)|^{1/d})^d |A|- o(|A|).\] This result corrects and confirms the two-summand case of a conjecture of Bukh and is best possible up to the lower-order term for many choices of $L_1$ and $L_2$. As an application\, we prove a lower bound for $|A + \lambda \cdot A|$ when $A$ is a finite set of real numbers and $\lambda$ is an algebraic number.\nJoint work with David Conlon. URL:https://dimag.ibs.re.kr/event/2022-06-02/ LOCATION:Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED] CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220602T161500 DTEND;TZID=Asia/Seoul:20220602T171500 DTSTAMP:20260420T070625 CREATED:20220602T071500Z LAST-MODIFIED:20240705T172222Z UID:5763-1654186500-1654190100@dimag.ibs.re.kr SUMMARY:O-joung Kwon (권오정)\, Graph minor theory and beyond DESCRIPTION:[Colloquium\, Department of Mathematical Sciences\, KAIST] \nOne of the important work in graph theory is the graph minor theory developed by Robertson and Seymour in 1980-2010. This provides a complete description of the class of graphs that do not contain a fixed graph H as a minor. Later on\, several generalizations of H-minor free graphs\, which are sparse\, have been defined and studied. Also\, similar topics on dense graph classes have been deeply studied. In this talk\, I will survey topics in graph minor theory\, and discuss related topics in structural graph theory. URL:https://dimag.ibs.re.kr/event/2022-06-02-kwon/ LOCATION:Room 1501\, Bldg. E6-1\, KAIST CATEGORIES:Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220613T163000 DTEND;TZID=Asia/Seoul:20220613T173000 DTSTAMP:20260420T070625 CREATED:20220613T073000Z LAST-MODIFIED:20240707T075724Z UID:5578-1655137800-1655141400@dimag.ibs.re.kr SUMMARY:Amadeus Reinald\, Twin-width and forbidden subdivisions DESCRIPTION:Twin-width is a recently introduced graph parameter based on vertex contraction sequences. On classes of bounded twin-width\, problems expressible in FO logic can be solved in FPT time when provided with a sequence witnessing the bound. Classes of bounded twin-width are very diverse\, notably including bounded rank-width\, $\Omega ( \log (n) )$-subdivisions of graphs of size $n$\, and proper minor closed classes. In this talk\, we look at developing a structural understanding of twin-width in terms of induced subdivisions. \nStructural characterizations of graph parameters have mostly looked at graph minors\, for instance\, bounded tree-width graphs are exactly those forbidding a large wall minor. An analogue in terms of induced subgraphs could be that\, for sparse graphs\, large treewidth implies the existence of an induced subdivision of a large wall. However\, Sintiari and Trotignon have ruled out such a characterization by showing the existence of graphs with arbitrarily large girth avoiding any induced subdivision of a theta ($K_{2\,3}$). Abrishami\, Chudnovsky\, Hajebi and Spirkl have recently shown that such (theta\, triangle)-free classes have nevertheless logarithmic treewidth. \nAfter an introduction to twin-width and its ties to vertex orderings\, we show that theta-free graphs of girth at least 5 have bounded twin-width. \nJoint work with Édouard Bonnet\, Eun Jung Kim\, Stéphan Thomassé and Rémi Watrigant. URL:https://dimag.ibs.re.kr/event/2022-06-13/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220622T163000 DTEND;TZID=Asia/Seoul:20220622T173000 DTSTAMP:20260420T070625 CREATED:20220622T073000Z LAST-MODIFIED:20240707T075717Z UID:5846-1655915400-1655919000@dimag.ibs.re.kr SUMMARY:Chengfei Xie\, On the packing densities of superballs in high dimensions DESCRIPTION:The sphere packing problem asks for the densest packing of nonoverlapping equal-sized balls in the space. This is an old and difficult problem in discrete geometry. In this talk\, we give a new proof for the result that for $ 1