BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.16.2//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:20210101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220104T163000
DTEND;TZID=Asia/Seoul:20220104T173000
DTSTAMP:20260525T142940
CREATED:20211210T230406Z
LAST-MODIFIED:20240707T080549Z
UID:5000-1641313800-1641317400@dimag.ibs.re.kr
SUMMARY:Seunghun Lee (이승훈)\, Transversals and colorings of simplicial spheres
DESCRIPTION:Motivated from the surrounding property of a point set in $\mathbb{R}^d$ introduced by Holmsen\, Pach and Tverberg\, we consider the transversal number and chromatic number of a simplicial sphere. As an attempt to give a lower bound for the maximum transversal ratio of simplicial $d$-spheres\, we provide two infinite constructions. The first construction gives infinitely many $(d+1)$-dimensional simplicial polytopes with the transversal ratio exactly $\frac{2}{d+2}$ for every $d\geq 2$. In the case of $d=2$\, this meets the previously well-known upper bound $1/2$ tightly. The second gives infinitely many simplicial 3-spheres with the transversal ratio greater than $1/2$. This was unexpected from what was previously known about the surrounding property. Moreover\, we show that\, for $d\geq 3$\, the facet hypergraph $\mathcal{F}(\mathbf{P})$ of a $(d+1)$-dimensional simplicial polytope $\mathbf{P}$ has the chromatic number $\chi(\mathcal{F}(\mathbf{P})) \in O(n^{\frac{\lceil d/2\rceil-1}{d}})$\, where $n$ is the number of vertices of $\mathbf{P}$. This slightly improves the upper bound previously obtained by Heise\, Panagiotou\, Pikhurko\, and Taraz. This is a joint work with Joseph Briggs and Michael Gene Dobbins.
URL:https://dimag.ibs.re.kr/event/2022-01-04/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220111T163000
DTEND;TZID=Asia/Seoul:20220111T173000
DTSTAMP:20260525T142940
CREATED:20220111T073000Z
LAST-MODIFIED:20240707T080542Z
UID:5083-1641918600-1641922200@dimag.ibs.re.kr
SUMMARY:Andreas Holmsen\, Some recent results on geometric transversals
DESCRIPTION:A geometric transversal to a family of convex sets in $\mathbb R^d$ is an affine flat that intersects the members of the family. While there exists a far-reaching theory concerning 0-dimensional transversals (intersection patterns of convex sets)\, much less is known when it comes to higher-dimensional transversals. In this talk\, I will present some new and old results and problems regarding geometric transversals\, based on joint work with Otfried Cheong and Xavier Goaoc.
URL:https://dimag.ibs.re.kr/event/2022-01-11/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220118T163000
DTEND;TZID=Asia/Seoul:20220118T173000
DTSTAMP:20260525T142940
CREATED:20220118T073000Z
LAST-MODIFIED:20240707T080518Z
UID:5105-1642523400-1642527000@dimag.ibs.re.kr
SUMMARY:Jaehyeon Seo (서재현)\, A rainbow Turán problem for color-critical graphs
DESCRIPTION:For given $k$ graphs $G_1\,\dots\, G_k$ over a common vertex set of size $n$\, what conditions on $G_i$ ensures a ‘colorful’ copy of $H$\, i.e. a copy of $H$ containing at most one edge from each $G_i$? \nKeevash\, Saks\, Sudakov\, and Verstraëte defined $\operatorname{ex}_k(n\,H)$ to be the maximum total number of edges of the graphs $G_1\,\dots\, G_k$ on a common vertex set of size $n$ having no colorful copy of $H$. They completely determined $\operatorname{ex}_k(n\,K_r)$ for large $n$ by showing that\, depending on the value of $k$\, one of the two natural constructions is always the extremal construction. Moreover\, they conjectured the same holds for every color-critical graphs and proved it for $3$-color-critical graphs. \nWe prove their conjecture for $4$-color-critical graphs and for almost all $r$-color-critical graphs when $r > 4$. Moreover\, we show that for every non-color-critical non-bipartite graphs\, none of the two natural constructions is extremal for certain values of $k$. This is a joint work with Debsoumya Chakraborti\, Jaehoon Kim\, Hyunwoo Lee\, and Hong Liu.
URL:https://dimag.ibs.re.kr/event/2022-01-18/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220125T163000
DTEND;TZID=Asia/Seoul:20220125T173000
DTSTAMP:20260525T142940
CREATED:20220125T073000Z
LAST-MODIFIED:20240705T175100Z
UID:5129-1643128200-1643131800@dimag.ibs.re.kr
SUMMARY:O-joung Kwon (권오정)\, Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond)
DESCRIPTION:In a reduction sequence of a graph\, vertices are successively identified until the graph has one vertex. At each step\, when identifying $u$ and $v$\, each edge incident to exactly one of $u$ and $v$ is coloured red. Bonnet\, Kim\, Thomassé\, and Watrigant [FOCS 2020] defined the twin-width of a graph $G$ to be the minimum integer $k$ such that there is a reduction sequence of $G$ in which every red graph has maximum degree at most $k$. For any graph parameter $f$\, we define the reduced-$f$ of a graph $G$ to be the minimum integer $k$ such that there is a reduction sequence of $G$ in which every red graph has $f$ at most $k$. Our focus is on graph classes with bounded reduced-bandwidth\, which implies and is stronger than bounded twin-width (reduced-maximum-degree). \nWe show that every proper minor-closed class has bounded reduced-bandwidth\, which is qualitatively stronger than a result of Bonnet et al. for bounded twin-width. In many instances\, we also make quantitative improvements. For example\, all previous upper bounds on the twin-width of planar graphs were at least $2^{1000}$. We show that planar graphs have reduced-bandwidth at most $466$ and twin-width at most $583$; moreover\, the witnessing reduction sequence can be constructed in polynomial time. We show that $d$-powers of graphs in a proper minor-closed class have bounded reduced-bandwidth (irrespective of the degree of the vertices). \nThis is joint work with Édouard bonnet and David Wood.
URL:https://dimag.ibs.re.kr/event/2022-01-25/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR