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:20220906T163000 DTEND;TZID=Asia/Seoul:20220906T173000 DTSTAMP:20260525T112143 CREATED:20220719T105944Z LAST-MODIFIED:20240707T074750Z UID:5974-1662481800-1662485400@dimag.ibs.re.kr SUMMARY:Bjarne Schülke\, A local version of Katona's intersection theorem DESCRIPTION:Katona’s intersection theorem states that every intersecting family $\mathcal F\subseteq[n]^{(k)}$ satisfies $\vert\partial\mathcal F\vert\geq\vert\mathcal F\vert$\, where $\partial\mathcal F=\{F\setminus x:x\in F\in\mathcal F\}$ is the shadow of $\mathcal F$.\nFrankl conjectured that for $n>2k$ and every intersecting family $\mathcal F\subseteq [n]^{(k)}$\, there is some $i\in[n]$ such that $\vert \partial \mathcal F(i)\vert\geq \vert\mathcal F(i)\vert$\, where $\mathcal F(i)=\{F\setminus i:i\in F\in\mathcal F\}$ is the link of $\mathcal F$ at $i$. \nHere\, we prove this conjecture in a very strong form for $n> \binom{k+1}{2}$. \nIn particular\, our result implies that for any $j\in[k]$\, there is a $j$-set $\{a_1\,\dots\,a_j\}\in[n]^{(j)}$ such that \[ \vert \partial \mathcal F(a_1\,\dots\,a_j)\vert\geq \vert\mathcal F(a_1\,\dots\,a_j)\vert.\]A similar statement is also obtained for cross-intersecting families. URL:https://dimag.ibs.re.kr/event/2022-09-06/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220913T163000 DTEND;TZID=Asia/Seoul:20220913T173000 DTSTAMP:20260525T112143 CREATED:20220720T105001Z LAST-MODIFIED:20240707T074732Z UID:5990-1663086600-1663090200@dimag.ibs.re.kr SUMMARY:Sebastian Wiederrecht\, Killing a vortex DESCRIPTION:The Structural Theorem of the Graph Minors series of Robertson and Seymour asserts that\, for every $t\in\mathbb{N}\,$ there exists some constant $c_{t}$ such that every $K_{t}$-minor-free graph admits a tree decomposition whose torsos can be transformed\, by the removal of at most $c_{t}$ vertices\, to graphs that can be seen as the union of some graph that is embeddable to some surface of Euler genus at most $c_{t}$ and “at most $c_{t}$ vortices of depth $c_{t}$”. Our main combinatorial result is a “vortex-free” refinement of the above structural theorem as follows: we identify a (parameterized) graph $H_{t}$\, called shallow vortex grid\, and we prove that if in the above structural theorem we replace $K_{t}$ by $H_{t}\,$ then the resulting decomposition becomes “vortex-free”. Up to now\, the most general classes of graphs admitting such a result were either bounded Euler genus graphs or the so called single-crossing minor-free graphs. Our result is tight in the sense that\, whenever we minor-exclude a graph that is not a minor of some $H_{t}\,$ the appearance of vortices is unavoidable. Using the above decomposition theorem\, we design an algorithm that\, given an $H_{t}$-minor-free graph $G$\, computes the generating function of all perfect matchings of $G$ in polynomial time. This algorithm yields\, on $H_{t}$-minor-free graphs\, polynomial algorithms for computational problems such as the {dimer problem\, the exact matching problem}\, and the computation of the permanent. Our results\, combined with known complexity results\, imply a complete characterization of minor-closed graphs classes where the number of perfect matchings is polynomially computable: They are exactly those graph classes that do not contain every $H_{t}$ as a minor. This provides a sharp complexity dichotomy for the problem of counting perfect matchings in minor-closed classes. \nThis is joint work with Dimitrios M. Thilikos. URL:https://dimag.ibs.re.kr/event/2022-09-13/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220927T163000 DTEND;TZID=Asia/Seoul:20220927T173000 DTSTAMP:20260525T112143 CREATED:20220825T021718Z LAST-MODIFIED:20240707T074701Z UID:6074-1664296200-1664299800@dimag.ibs.re.kr SUMMARY:Alexander Clifton\, Ramsey Theory for Diffsequences DESCRIPTION:Van der Waerden’s theorem states that any coloring of $\mathbb{N}$ with a finite number of colors will contain arbitrarily long monochromatic arithmetic progressions. This motivates the definition of the van der Waerden number $W(r\,k)$ which is the smallest $n$ such that any $r$-coloring of $\{1\,2\,\cdots\,n\}$ guarantees the presence of a monochromatic arithmetic progression of length $k$. \nIt is natural to ask what other arithmetic structures exhibit van der Waerden-type results. One notion\, introduced by Landman and Robertson\, is that of a $D$-diffsequence\, which is an increasing sequence $a_1