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:20210101T000000 END:STANDARD END:VTIMEZONE BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220906T163000 DTEND;TZID=Asia/Seoul:20220906T173000 DTSTAMP:20260420T002513 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:20220907T163000 DTEND;TZID=Asia/Seoul:20220907T173000 DTSTAMP:20260420T002513 CREATED:20220614T112030Z LAST-MODIFIED:20240705T171148Z UID:5853-1662568200-1662571800@dimag.ibs.re.kr SUMMARY:Dömötör Pálvölgyi\, C-P3O: Orientation of convex sets and other good covers DESCRIPTION:We introduce a novel definition of orientation on the triples of a family of pairwise intersecting planar convex sets and study its properties. In particular\, we compare it to other systems of orientations on triples that satisfy a natural interiority condition. Such systems\, P3O (partial 3-order)\, are a natural generalization of posets\, and include the order types of planar point sets. Our main result is that P3O that emerge from points sets\, p-P3O\, and P3O that emerge from convex sets\, C-P3O\, do not contain each other. We also extend our orientation to other good covers from convex sets and study the resulting P3O’s.\nBased on joint work with Agoston\, Damasdi\, and Keszegh:\nhttps://arxiv.org/abs/2206.01721\nhttps://arxiv.org/abs/2206.01723 URL:https://dimag.ibs.re.kr/event/2022-09-07/ LOCATION:Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED] CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220913T163000 DTEND;TZID=Asia/Seoul:20220913T173000 DTSTAMP:20260420T002513 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:20220921T163000 DTEND;TZID=Asia/Seoul:20220921T173000 DTSTAMP:20260420T002513 CREATED:20220818T013812Z LAST-MODIFIED:20240707T074721Z UID:6050-1663777800-1663781400@dimag.ibs.re.kr SUMMARY:Mehtaab Sawhney\, Anticoncentration in Ramsey graphs and a proof of the Erdős-McKay conjecture DESCRIPTION:An $n$-vertex graph is called $C$-Ramsey if it has no clique or independent set of size $C\log_2 n$ (i.e.\, if it has near-optimal Ramsey behavior). We study edge-statistics in Ramsey graphs\, in particular obtaining very precise control of the distribution of the number of edges in a random vertex subset of a $C$-Ramsey graph. One of the consequences of our result is the resolution of an old conjecture of Erdős and McKay\, for which Erdős offered one of his notorious monetary prizes and the proof involves a wide range of different tools from Fourier analysis\, random matrix theory\, the theory of Boolean functions\, probabilistic combinatorics\, and low-rank approximation. \nJoint w. Matthew Kwan\, Ashwin Sah\, and Lisa Sauermann URL:https://dimag.ibs.re.kr/event/2022-09-21/ LOCATION:Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED] CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220927T163000 DTEND;TZID=Asia/Seoul:20220927T173000 DTSTAMP:20260420T002513 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