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:20221115T163000 DTEND;TZID=Asia/Seoul:20221115T173000 DTSTAMP:20260506T120258 CREATED:20221011T041240Z LAST-MODIFIED:20240705T171137Z UID:6283-1668529800-1668533400@dimag.ibs.re.kr SUMMARY:Sebastian Wiederrecht\, Excluding single-crossing matching minors in bipartite graphs DESCRIPTION:By a seminal result of Valiant\, computing the permanent of (0\, 1)-matrices is\, in general\, #P-hard. In 1913 Pólya asked for which (0\, 1)-matrices A it is possible to change some signs such that the permanent of A equals the determinant of the resulting matrix. In 1975\, Little showed these matrices to be exactly the biadjacency matrices of bipartite graphs excluding $K_{3\,3}$ as a matching minor. This was turned into a polynomial time algorithm by McCuaig\, Robertson\, Seymour\, and Thomas in 1999. However\, the relation between the exclusion of some matching minor in a bipartite graph and the tractability of the permanent extends beyond K3\,3. Recently it was shown that the exclusion of any planar bipartite graph as a matching minor yields a class of bipartite graphs on which the permanent of the corresponding (0\, 1)-matrices can be computed efficiently. \nIn this paper we unify the two results above into a single\, more general result in the style of the celebrated structure theorem for single-crossing minor-free graphs. We identify a class of bipartite graphs strictly generalising planar bipartite graphs and $K_{3\,3}$ which includes infinitely many non-Pfaffian graphs. The exclusion of any member of this class as a matching minor yields a structure that allows for the efficient evaluation of the permanent. Moreover\, we show that the evaluation of the permanent remains #P-hard on bipartite graphs which exclude $K_{5\,5}$ as a matching minor. This establishes a first computational lower bound for the problem of counting perfect matchings on matching minor closed classes. As another application of our structure theorem\, we obtain a strict generalisation of the algorithm for the k-vertex disjoint directed paths problem on digraphs of bounded directed treewidth. \nThis is joint work with Archontia Giannopoulou and Dimitrios Thilikos. URL:https://dimag.ibs.re.kr/event/2022-11-15/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20221108T163000 DTEND;TZID=Asia/Seoul:20221108T173000 DTSTAMP:20260506T120258 CREATED:20221018T044028Z LAST-MODIFIED:20240707T074529Z UID:6364-1667925000-1667928600@dimag.ibs.re.kr SUMMARY:Jungho Ahn (안정호)\, Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes DESCRIPTION:Let $\mathcal{F}$ be a family of graphs\, and let $p$ and $r$ be nonnegative integers.\nThe $(p\,r\,\mathcal{F})$-Covering problem asks whether for a graph $G$ and an integer $k$\, there exists a set $D$ of at most $k$ vertices in $G$ such that $G^p\setminus N_G^r[D]$ has no induced subgraph isomorphic to a graph in $\mathcal{F}$\, where $G^p$ is the $p$-th power of $G$ and $N^r_G[D]$ is the set of all vertices in $G$ at distance at most $r$ from $D$ in $G$. The $(p\,r\,\mathcal{F})$-Packing problem asks whether for a graph $G$ and an integer $k$\, $G^p$ has $k$ induced subgraphs $H_1\,\ldots\,H_k$ such that each $H_i$ is isomorphic to a graph in $\mathcal{F}$\, and for distinct $i\,j\in \{1\, \ldots\, k\}$\, the distance between $V(H_i)$ and $V(H_j)$ in $G$ is larger than $r$. The $(p\,r\,\mathcal{F})$-Covering problem generalizes Distance-$r$ Dominating Set and Distance-$r$ Vertex Cover\, and the $(p\,r\,\mathcal{F})$-Packing problem generalizes Distance-$r$ Independent Set and Distance-$r$ Matching. By taking $(p’\,r’\,\mathcal{F}’)=(pt\, rt\, \mathcal{F})$\, we may formulate the $(p\,r\,\mathcal{F})$-Covering and $(p\, r\, \mathcal{F})$-Packing problems on the $t$-th power of a graph. Moreover\, $(1\,0\,\mathcal{F})$-Covering is the $\mathcal{F}$-Free Vertex Deletion problem\, and $(1\,0\,\mathcal{F})$-Packing is the Induced-$\mathcal{F}$-Packing problem. \nWe show that for every fixed nonnegative integers $p\,r$ and every fixed nonempty finite family $\mathcal{F}$ of connected graphs\, the $(p\,r\,\mathcal{F})$-Covering problem with $p\leq2r+1$ and the $(p\,r\,\mathcal{F})$-Packing problem with $p\leq2\lfloor r/2\rfloor+1$ admit almost linear kernels on every nowhere dense class of graphs\, and admit linear kernels on every class of graphs with bounded expansion\, parameterized by the solution size $k$. We obtain the same kernels for their annotated variants. As corollaries\, we prove that Distance-$r$ Vertex Cover\, Distance-$r$ Matching\, $\mathcal{F}$-Free Vertex Deletion\, and Induced-$\mathcal{F}$-Packing for any fixed finite family $\mathcal{F}$ of connected graphs admit almost linear kernels on every nowhere dense class of graphs and linear kernels on every class of graphs with bounded expansion. Our results extend the results for Distance-$r$ Dominating Set by Drange et al. (STACS 2016) and Eickmeyer et al. (ICALP 2017)\, and the result for Distance-$r$ Independent Set by Pilipczuk and Siebertz (EJC 2021). \nThis is joint work with Jinha Kim and O-joung Kwon. URL:https://dimag.ibs.re.kr/event/2022-11-08/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20221018T163000 DTEND;TZID=Asia/Seoul:20221018T173000 DTSTAMP:20260506T120258 CREATED:20220824T133830Z LAST-MODIFIED:20240705T171142Z UID:6071-1666110600-1666114200@dimag.ibs.re.kr SUMMARY:Florent Koechlin\, Uniform random expressions lack expressivity DESCRIPTION:In computer science\, random expressions are commonly used to analyze algorithms\, either to study their average complexity\, or to generate benchmarks to test them experimentally. In general\, these approaches only consider the expressions as purely syntactic trees\, and completely ignore their semantics — i.e. the mathematical object represented by the expression. \nHowever\, two different expressions can be equivalent (for example “0*(x+y)” and “0” represent the same expression\, the null expression). Can these redundancies question the relevance of the analyses and tests that do not take into account the semantics of the expressions? \nI will present how the uniform distribution over syntactic expression becomes completely degenerate when we start taking into account their semantics\, in a very simple but common case where there is an absorbing element. If time permits it\, I will briefly explain why the BST distribution offers more hope. \nThis is a joint work with Cyril Nicaud and Pablo Rotondo. URL:https://dimag.ibs.re.kr/event/2022-10-18/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20221011T163000 DTEND;TZID=Asia/Seoul:20221011T173000 DTSTAMP:20260506T120258 CREATED:20220824T132239Z LAST-MODIFIED:20240707T074556Z UID:6067-1665505800-1665509400@dimag.ibs.re.kr SUMMARY:Nika Salia\, Exact results for generalized extremal problems forbidding an even cycle DESCRIPTION:We determine the maximum number of copies of $K_{s\,s}$ in a $C_{2s+2}$-free $n$-vertex graph for all integers $s \ge 2$ and sufficiently large $n$. Moreover\, for $s\in\{2\,3\}$ and any integer $n$ we obtain the maximum number of cycles of length $2s$ in an $n$-vertex $C_{2s+2}$-free bipartite graph. \nThis is joint work with Ervin Győri (Renyi Institute)\, Zhen He (Tsinghua University)\, Zequn Lv (Tsinghua University)\, Casey Tompkins (Renyi Institute)\, Kitti Varga (Technical University of Budapest BME)\, and Xiutao Zhu (Nanjing University). URL:https://dimag.ibs.re.kr/event/2022-10-11/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20221004T163000 DTEND;TZID=Asia/Seoul:20221004T173000 DTSTAMP:20260506T120258 CREATED:20220825T224353Z LAST-MODIFIED:20240707T074613Z UID:6077-1664901000-1664904600@dimag.ibs.re.kr SUMMARY:Zixiang Xu (徐子翔)\, On the degenerate Turán problems DESCRIPTION:For a graph $F$\, the Turán number is the maximum number of edges in an $n$-vertex simple graph not containing $F$. The celebrated Erdős-Stone-Simonovits Theorem gives that \[ \text{ex}(n\,F)=\bigg(1-\frac{1}{\chi(F)-1}+o(1)\bigg)\binom{n}{2}\,\] where $\chi(F)$ is the chromatic number of $H$. This theorem asymptotically solves the problem when $\chi(F)\geqslant 3$. In case of bipartite graphs $F$\, not even the order of magnitude is known in general. In this talk\, I will introduce some recent progress on Turán numbers of bipartite graphs and related generalizations and discuss several methods developed in recent years. Finally\, I will introduce some interesting open problems on this topic. URL:https://dimag.ibs.re.kr/event/2022-10-04/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220927T163000 DTEND;TZID=Asia/Seoul:20220927T173000 DTSTAMP:20260506T120258 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_12k$ 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:20220830T163000 DTEND;TZID=Asia/Seoul:20220830T173000 DTSTAMP:20260506T120258 CREATED:20220830T073000Z LAST-MODIFIED:20240707T075520Z UID:6018-1661877000-1661880600@dimag.ibs.re.kr SUMMARY:Jun Gao\, Number of (k-1)-cliques in k-critical graph DESCRIPTION:We prove that for $n>k\geq 3$\, if $G$ is an $n$-vertex graph with chromatic number $k$ but any its proper subgraph has smaller chromatic number\, then $G$ contains at most $n-k+3$ copies of cliques of size $k-1$. This answers a problem of Abbott and Zhou and provides a tight bound on a conjecture of Gallai. \nThis is joint work with Jie Ma. URL:https://dimag.ibs.re.kr/event/2022-08-30/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220823T163000 DTEND;TZID=Asia/Seoul:20220823T173000 DTSTAMP:20260506T120258 CREATED:20220823T073000Z LAST-MODIFIED:20240705T171142Z UID:5971-1661272200-1661275800@dimag.ibs.re.kr SUMMARY:Raul Lopes\, Temporal Menger and related problems DESCRIPTION:A temporal graph is a graph whose edges are available only at specific times. In this scenario\, the only valid walks are the ones traversing adjacent edges respecting their availability\, i.e. sequence of adjacent edges whose appearing times are non-decreasing. \nGiven a graph G and vertices s and t of G\, Menger’s Theorem states that the maximum number of (internally) vertex disjoint s\,t-paths is equal to the minimum size of a subset X for which G-X contains no s\,t-path. This is a classical result in Graph Theory\, taught in most basic Graph Theory courses\, and it holds also when G is directed and when edge disjoint paths and edge cuts are considered instead. A direct translation of Menger’s Theorem to the temporal context has been known not to hold since an example was shown in the seminal paper by Kempe\, Kleinberg and Kumar (STOC’00). In this talk\, an overview of possible temporal versions of Menger’s Theorem will be discussed\, as well as the complexity of the related problems. URL:https://dimag.ibs.re.kr/event/2022-08-23/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220816T163000 DTEND;TZID=Asia/Seoul:20220816T173000 DTSTAMP:20260506T120258 CREATED:20220718T235006Z LAST-MODIFIED:20240705T171145Z UID:5967-1660667400-1660671000@dimag.ibs.re.kr SUMMARY:Noleen Köhler\, Testing first-order definable properties on bounded degree graphs DESCRIPTION:Property testers are probabilistic algorithms aiming to solve a decision problem efficiently in the context of big-data. A property tester for a property P has to decide (with high probability correctly) whether a given input graph has property P or is far from having property P while having local access to the graph. We study property testing of properties that are definable in first-order logic (FO) in the bounded-degree model. We show that any FO property that is defined by a formula with quantifier prefix ∃*∀* is testable\, while there exists an FO property that is expressible by a formula with quantifier prefix ∀*∃* that is not testable. In the dense graph model\, a similar picture is long known (Alon\, Fischer\, Krivelevich\, Szegedy\, Combinatorica 2000)\, despite the very different nature of the two models. In particular\, we obtain our lower bound by a first-order formula that defines a class of bounded-degree expanders\, based on zig-zag products of graphs. \nThis is joint work with Isolde Adler and Pan Peng. URL:https://dimag.ibs.re.kr/event/2022-08-16/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220809T163000 DTEND;TZID=Asia/Seoul:20220809T173000 DTSTAMP:20260506T120258 CREATED:20220808T073000Z LAST-MODIFIED:20240707T075550Z UID:5821-1660062600-1660066200@dimag.ibs.re.kr SUMMARY:Eun Jung Kim (김은정)\, Directed flow-augmentation DESCRIPTION:We show a flow-augmentation algorithm in directed graphs: There exists a polynomial-time algorithm that\, given a directed graph G\, two integers $s\,t\in V(G)$\, and an integer $k$\, adds (randomly) to $G$ a number of arcs such that for every minimal st-cut $Z$ in $G$ of size at most $k$\, with probability $2^{−\operatorname{poly}(k)}$ the set $Z$ becomes a minimum $st$-cut in the resulting graph.\nThe directed flow-augmentation tool allows us to prove fixed-parameter tractability of a number of problems parameterized by the cardinality of the deletion set\, whose parameterized complexity status was repeatedly posed as open problems:\n(1) Chain SAT\, defined by Chitnis\, Egri\, and Marx [ESA’13\, Algorithmica’17]\,\n(2) a number of weighted variants of classic directed cut problems\, such as Weighted st-Cut\, Weighted Directed Feedback Vertex Set\, or Weighted Almost 2-SAT.\nBy proving that Chain SAT is FPT\, we confirm a conjecture of Chitnis\, Egri\, and Marx that\, for any graph H\, if the List H-Coloring problem is polynomial-time solvable\, then the corresponding vertex-deletion problem is fixed-parameter tractable. \nJoint work with Stefan Kratsch\, Marcin Pilipczuk\, Magnus Wahlström. URL:https://dimag.ibs.re.kr/event/2022-08-09/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220801T163000 DTEND;TZID=Asia/Seoul:20220801T173000 DTSTAMP:20260506T120258 CREATED:20220801T073000Z LAST-MODIFIED:20240707T075606Z UID:5867-1659371400-1659375000@dimag.ibs.re.kr SUMMARY:Seunghun Lee (이승훈)\, Inscribable order types DESCRIPTION:We call an order type inscribable if it is realized by a point configuration where all extreme points are all on a circle. In this talk\, we investigate inscribability of order types. We first show that every simple order type with at most 2 interior points is inscribable\, and that the number of such order types is $\Theta(\frac{4^n}{n^{3/2}})$. We further construct an infinite family of minimally uninscribable order types. The proof of uninscribability mainly uses Möbius transformations. We also suggest open problems around inscribability. This is a joint work with Michael Gene Dobbins. URL:https://dimag.ibs.re.kr/event/2022-08-01/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220719T140000 DTEND;TZID=Asia/Seoul:20220719T160000 DTSTAMP:20260506T120258 CREATED:20220719T050000Z LAST-MODIFIED:20240705T171145Z UID:5880-1658239200-1658246400@dimag.ibs.re.kr SUMMARY:Jinyoung Park (박진영)\, Thresholds 2/2 DESCRIPTION:Thresholds for increasing properties of random structures are a central concern in probabilistic combinatorics and related areas. In 2006\, Kahn and Kalai conjectured that for any nontrivial increasing property on a finite set\, its threshold is never far from its “expectation-threshold\,” which is a natural (and often easy to calculate) lower bound on the threshold. \nIn the first talk on Monday\, I will introduce the Kahn-Kalai Conjecture with some motivating examples and then briefly talk about the recent resolution of the Kahn-Kalai Conjecture due to Huy Pham and myself. \nIn the second talk on Tuesday\, I will discuss our proof of the conjecture in detail. URL:https://dimag.ibs.re.kr/event/2022-07-19/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220718T163000 DTEND;TZID=Asia/Seoul:20220718T173000 DTSTAMP:20260506T120258 CREATED:20220622T073000Z LAST-MODIFIED:20240705T171147Z UID:5878-1658161800-1658165400@dimag.ibs.re.kr SUMMARY:Jinyoung Park (박진영)\, Thresholds 1/2 DESCRIPTION:Thresholds for increasing properties of random structures are a central concern in probabilistic combinatorics and related areas. In 2006\, Kahn and Kalai conjectured that for any nontrivial increasing property on a finite set\, its threshold is never far from its “expectation-threshold\,” which is a natural (and often easy to calculate) lower bound on the threshold. \nIn the first talk on Monday\, I will introduce the Kahn-Kalai Conjecture with some motivating examples and then briefly talk about the recent resolution of the Kahn-Kalai Conjecture due to Huy Pham and myself. \nIn the second talk on Tuesday\, I will discuss our proof of the conjecture in detail. URL:https://dimag.ibs.re.kr/event/2022-07-18/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220711T163000 DTEND;TZID=Asia/Seoul:20220711T173000 DTSTAMP:20260506T120258 CREATED:20220711T073000Z LAST-MODIFIED:20240707T075632Z UID:5896-1657557000-1657560600@dimag.ibs.re.kr SUMMARY:Kevin Hendrey\, Product Structure of Graph Classes with Bounded Treewidth DESCRIPTION:The strong product $G\boxtimes H$ of graphs $G$ and $H$ is the graph on the cartesian product $V(G)\times V(H)$ such that vertices $(v\,w)$ and $(x\,y)$ are adjacent if and only if $\max\{d_G(v\,x)\,d_H(w\,y)\}=1$. Graph product structure theory aims to describe complicated graphs in terms of subgraphs of strong products of simpler graphs. This area of research was initiated by Dujmović\, Joret\, Micek\, Morin\, Ueckerdt and Wood\, who showed that every planar graph is a subgraph of the strong product of a $H\boxtimes P\boxtimes K_3$ for some path $P$ and some graph $H$ of treewidth at most $3$. In this talk\, I will discuss the product structure of various graph classes of bounded treewidth. As an example\, we show that there is a function $f:\mathbb{N}\rightarrow \mathbb{N}$ such that every planar graph of treewidth at most $k$ is a subgraph of $H\boxtimes K_{f(k)}$ for some graph $H$ of treewidth at most $3$. \nThis is based on joint work with Campbell\, Clinch\, Distel\, Gollin\, Hickingbotham\, Huynh\, Illingworth\, Tamitegama\, Tan and Wood. URL:https://dimag.ibs.re.kr/event/2022-07-11/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220704T163000 DTEND;TZID=Asia/Seoul:20220704T173000 DTSTAMP:20260506T120258 CREATED:20220704T073000Z LAST-MODIFIED:20240707T075651Z UID:5797-1656952200-1656955800@dimag.ibs.re.kr SUMMARY:Eric Vigoda\, Computational phase transition and MCMC algorithms DESCRIPTION:This talk will highlight recent results establishing a beautiful computational phase transition for approximate counting/sampling in (binary) undirected graphical models (such as the Ising model or on weighted independent sets). The computational problem is to sample from the equilibrium distribution of the model or equivalently approximate the corresponding normalizing factor known as the partition function. We show that when correlations die off on the infinite D-regular tree then the Gibbs sampler has optimal mixing time of $O(n \log n)$ on any graph of maximum degree D\, whereas when the correlations persist (in the limit) then the sampling/counting problem are NP-hard to approximate.  The Gibbs sampler is a simple Markov Chain Monte Carlo (MCMC) algorithm. Key to these mixing results are a new technique known as spectral independence which considers the pairwise influence of vertices. We show that spectral independence implies an optimal convergence rate for a variety of MCMC algorithms. URL:https://dimag.ibs.re.kr/event/2022-07-04/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220627T163000 DTEND;TZID=Asia/Seoul:20220627T173000 DTSTAMP:20260506T120258 CREATED:20220627T073000Z LAST-MODIFIED:20240707T075705Z UID:5733-1656347400-1656351000@dimag.ibs.re.kr SUMMARY:Ben Lund\, Radial projections in finite space DESCRIPTION:Given a set $E$ and a point $y$ in a vector space over a finite field\, the radial projection $\pi_y(E)$ of $E$ from $y$ is the set of lines that through $y$ and points of $E$. Clearly\, $|\pi_y(E)|$ is at most the minimum of the number of lines through $y$ and $|E|$. I will discuss several results on the general question: For how many points $y$ can $|\pi_y(E)|$ be much smaller than this maximum? \nThis is motivated by an analogous question in fractal geometry. The Hausdorff dimension of a radial projection of a set $E$ in $n$ dimensional real space will typically be the minimum of $n-1$ and the Hausdorff dimension of $E$. Several recent papers by authors including Matilla\, Orponen\, Liu\, Shmerikin\, and Wang consider the question: How large can the set of points with small radial projections be? This body of work has several important applications\, including recent progress on the Falconer distance conjecture. \nThis is joint with Thang Pham and Vu Thi Huong Thu. URL:https://dimag.ibs.re.kr/event/2022-06-27/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220613T163000 DTEND;TZID=Asia/Seoul:20220613T173000 DTSTAMP:20260506T120258 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:20220530T163000 DTEND;TZID=Asia/Seoul:20220530T173000 DTSTAMP:20260506T120258 CREATED:20220530T073000Z LAST-MODIFIED:20240705T172232Z UID:5495-1653928200-1653931800@dimag.ibs.re.kr SUMMARY:Hongseok Yang (양홍석)\, Learning Symmetric Rules with SATNet DESCRIPTION:SATNet is a differentiable constraint solver with a custom backpropagation algorithm\, which can be used as a layer in a deep-learning system. It is a promising proposal for bridging deep learning and logical reasoning. In fact\, SATNet has been successfully applied to learn\, among others\, the rules of a complex logical puzzle\, such as Sudoku\, just from input and output pairs where inputs are given as images. In this paper\, we show how to improve the learning of SATNet by exploiting symmetries in the target rules of a given but unknown logical puzzle or more generally a logical formula. We present SymSATNet\, a variant of SATNet that translates the given symmetries of the target rules to a condition on the parameters of SATNet and requires that the parameters should have a particular parametric form that guarantees the condition. The requirement dramatically reduces the number of parameters to learn for the rules with enough symmetries\, and makes the parameter learning of SymSATNet much easier than that of SATNet. We also describe a technique for automatically discovering symmetries of the target rules from examples. Our experiments with Sudoku and Rubik’s cube show the substantial improvement of SymSATNet over the baseline SATNet. \nThis is joint work with Sangho Lim and Eungyeol Oh. URL:https://dimag.ibs.re.kr/event/2022-05-30/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220523T163000 DTEND;TZID=Asia/Seoul:20220523T173000 DTSTAMP:20260506T120258 CREATED:20220523T073000Z LAST-MODIFIED:20240705T172235Z UID:5451-1653323400-1653327000@dimag.ibs.re.kr SUMMARY:Stijn Cambie\, The precise diameter of reconfiguration graphs DESCRIPTION:Reconfiguration is about changing instances in small steps. For example\, one can perform certain moves on a Rubik’s cube\, each of them changing its configuration a bit. In this case\, in at most 20 steps\, one can end up with the preferred result. One could construct a graph with as nodes the possible configurations of the Rubik’s cube (up to some isomorphism) and connect two nodes if one can be obtained by applying only one move to the other. Finding an optimal solution\, i.e. a minimum number of moves to solve a Rubik’s cube is now equivalent to finding the distance in the graph. \nWe will wonder about similar problems in reconfiguration\, but applied to list- and DP-colouring. In this case\, the small step consists of recolouring precisely one vertex. Now we will be interested in the diameter of the reconfiguration graph and show that sometimes we can determine the precise diameters of these. \nAs such\, during this talk\, we present some main ideas of [arXiv:2204.07928]. URL:https://dimag.ibs.re.kr/event/2022-05-23/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220516T163000 DTEND;TZID=Asia/Seoul:20220516T173000 DTSTAMP:20260506T120258 CREATED:20220516T073000Z LAST-MODIFIED:20240707T080014Z UID:5553-1652718600-1652722200@dimag.ibs.re.kr SUMMARY:Andreas Holmsen\, A colorful version of the Goodman-Pollack-Wenger transversal theorem DESCRIPTION:Hadwiger’s transversal theorem gives necessary and sufficient conditions for the existence of a line transversal to a family of pairwise disjoint convex sets in the plane. These conditions were subsequently generalized to hyperplane transversals in $\mathbb{R}^d$ by Goodman\, Pollack\, and Wenger. Here we establish a colorful extension of their theorem\, which proves a conjecture of Arocha\, Bracho\, and Montejano. The proof uses topological methods\, in particular the Borsuk-Ulam theorem. The same methods also allow us to generalize some colorful transversal theorems of Montejano and Karasev. URL:https://dimag.ibs.re.kr/event/2022-05-16/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220509T163000 DTEND;TZID=Asia/Seoul:20220509T173000 DTSTAMP:20260506T120258 CREATED:20220509T073000Z LAST-MODIFIED:20240705T173026Z UID:5524-1652113800-1652117400@dimag.ibs.re.kr SUMMARY:Kyeongsik Nam (남경식)\, Large deviations for subgraph counts in random graphs DESCRIPTION:The upper tail problem for subgraph counts in the Erdos-Renyi graph\, introduced by Janson-Ruciński\, has attracted a lot of attention. There is a class of Gibbs measures associated with subgraph counts\, called exponential random graph model (ERGM). Despite its importance\, lots of fundamental questions have remained unanswered owing to the lack of exact solvability. In this talk\, I will talk about a brief overview on the upper tail problem and the concentration of measure results for the ERGM. Joint work with Shirshendu Ganguly and Ella Hiesmayr. URL:https://dimag.ibs.re.kr/event/2022-05-09/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220502T163000 DTEND;TZID=Asia/Seoul:20220502T173000 DTSTAMP:20260506T120258 CREATED:20220502T073000Z LAST-MODIFIED:20240707T080029Z UID:5511-1651509000-1651512600@dimag.ibs.re.kr SUMMARY:Cheolwon Heo (허철원)\, The complexity of the matroid-homomorphism problems DESCRIPTION:In this talk\, we introduce homomorphisms between binary matroids that generalize graph homomorphisms. For a binary matroid $N$\, we prove a complexity dichotomy for the problem $\rm{Hom}_\mathbb{M}(N)$ of deciding if a binary matroid $M$ admits a homomorphism to $N$. The problem is polynomial-time solvable if $N$ has a loop or has no circuits of odd length\, and is otherwise $\rm{NP}$-complete. We also get dichotomies for the list\, extension\, and retraction versions of the problem.\nThis is joint work with Hyobin Kim and Mark Siggers at Kyungpook National University. URL:https://dimag.ibs.re.kr/event/2022-05-02/ LOCATION:Room B332\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220425T163000 DTEND;TZID=Asia/Seoul:20220425T173000 DTSTAMP:20260506T120258 CREATED:20220425T073000Z LAST-MODIFIED:20240707T080049Z UID:5322-1650904200-1650907800@dimag.ibs.re.kr SUMMARY:Boram Park (박보람)\, Odd coloring of sparse graphs DESCRIPTION:We introduce an odd coloring of a graph\, which was introduced very recently\, motivated by parity type colorings of graphs. A proper vertex coloring of graph $G$ is said to be odd if for each non-isolated vertex $x \in V (G)$ there exists a color $c$ such that $c$ is used an odd number of times in the neighborhood of $x$. The recent work on this topic will be presented\, and the work is based on Eun-Kyung Cho\, Ilkyoo Choi\, and Hyemin Kown. URL:https://dimag.ibs.re.kr/event/2022-04-25/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220411T163000 DTEND;TZID=Asia/Seoul:20220411T173000 DTSTAMP:20260506T120258 CREATED:20220401T073000Z LAST-MODIFIED:20240707T080114Z UID:5326-1649694600-1649698200@dimag.ibs.re.kr SUMMARY:Younjin Kim (김연진)\, On the extremal problems related to Szemerédi's theorem DESCRIPTION:In 1975\, Szemerédi proved that for every real number $\delta > 0 $ and every positive integer $k$\, there exists a positive integer $N$ such that every subset $A$ of the set $\{1\, 2\, \cdots\, N \}$ with $|A| \geq \delta N$ contains an arithmetic progression of length $k$. There has been a plethora of research related to Szemerédi’s theorem in many areas of mathematics. In 1990\, Cameron and Erdős proposed a conjecture about counting the number of subsets of the set $\{1\,2\, \dots\, N\}$ which do not contain an arithmetic progression of length $k$. In the talk\, we study a natural higher dimensional version of this conjecture\, and also introduce recent extremal problems related to Szemerédi’s theorem. URL:https://dimag.ibs.re.kr/event/2022-04-11/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220328T163000 DTEND;TZID=Asia/Seoul:20220328T173000 DTSTAMP:20260506T120258 CREATED:20220314T051725Z LAST-MODIFIED:20240707T080143Z UID:5383-1648485000-1648488600@dimag.ibs.re.kr SUMMARY:Ben Lund\, Thresholds for incidence properties in finite vector spaces DESCRIPTION:Suppose that $E$ is a subset of $\mathbb{F}_q^n$\, so that each point is contained in $E$ with probability $\theta$\, independently of all other points. Then\, what is the probability that there is an $m$-dimensional affine subspace that contains at least $\ell$ points of $E$? What is the probability that $E$ intersects all $m$-dimensional affine subspaces? We give Erdős-Renyi threshold functions for these properties\, in some cases sharp thresholds. Our results improve previous work of Chen and Greenhill. This is joint work with Jeong Han Kim\, Thang Pham\, and Semin Yoo. URL:https://dimag.ibs.re.kr/event/2022-03-28/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220321T163000 DTEND;TZID=Asia/Seoul:20220321T173000 DTSTAMP:20260506T120258 CREATED:20220321T073000Z LAST-MODIFIED:20240707T080150Z UID:5277-1647880200-1647883800@dimag.ibs.re.kr SUMMARY:Jaehoon Kim (김재훈)\, Ramsey numbers of cycles versus general graphs DESCRIPTION:The Ramsey number $R(F\,H)$ is the minimum number $N$ such that any $N$-vertex graph either contains a copy of $F$ or its complement contains $H$. Burr in 1981 proved a pleasingly general result that for any graph $H$\, provided $n$ is sufficiently large\, a natural lower bound construction gives the correct Ramsey number involving cycles: $R(C_n\,H)=(n-1)(\chi(H)-1)+\sigma(H)$\, where $\sigma(H)$ is the minimum possible size of a colour class in a $\chi(H)$-colouring of $H$. Allen\, Brightwell and Skokan conjectured that the same should be true already when $n\geq |H|\chi(H)$. \nWe improve this 40-year-old result of Burr by giving quantitative bounds of the form $n\geq C|H|\log^4\chi(H)$\, which is optimal up to the logarithmic factor. In particular\, this proves a strengthening of the Allen-Brightwell-Skokan conjecture for all graphs $H$ with large chromatic number. \nThis is joint work with John Haslegrave\, Joseph Hyde and Hong Liu URL:https://dimag.ibs.re.kr/event/2022-03-21/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220314T163000 DTEND;TZID=Asia/Seoul:20220314T173000 DTSTAMP:20260506T120258 CREATED:20220314T073000Z LAST-MODIFIED:20240705T174136Z UID:5218-1647275400-1647279000@dimag.ibs.re.kr SUMMARY:Tuan Anh Do\, Rank- and tree-width of supercritical random graphs DESCRIPTION:It is known that the rank- and tree-width of the random graph $G(n\,p)$ undergo a phase transition at $p = 1/n$; whilst for subcritical $p$\, the rank- and tree-width are bounded above by a constant\, for supercritical $p$\, both parameters are linear in $n$. The known proofs of these results use as a black box an important theorem of Benjamini\, Kozma\, and Wormald on the expansion of supercritical random graphs. We give a new\, short\, and direct proof of these results\, leading to more explicit bounds on these parameters\, and also consider the rank- and tree-width of supercritical random graphs closer to the critical point\, showing that this phase transition is smooth. \nThis is joint work with Joshua Erde and Mihyun Kang. URL:https://dimag.ibs.re.kr/event/2022-03-14/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220307T163000 DTEND;TZID=Asia/Seoul:20220307T173000 DTSTAMP:20260506T120258 CREATED:20220307T073000Z LAST-MODIFIED:20240705T174154Z UID:5315-1646670600-1646674200@dimag.ibs.re.kr SUMMARY:Kevin Hendrey\, A unified Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups (revisited) DESCRIPTION:This talk follows on from the recent talk of Pascal Gollin in this seminar series\, but will aim to be accessible for newcomers. \nErdős and Pósa proved in 1965 that there is a duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. By relaxing `packing’ to `half-integral packing’\, Reed obtained an analogous result for odd cycles\, and gave a structural characterisation of when the (integral) packing version fails. \nWe prove some far-reaching generalisations of these theorems. First\, we show that if the edges of a graph are labelled by finitely many abelian groups\, then the cycles whose values avoid a fixed finite set for each abelian group satisfy the half-integral Erdős-Pósa property. Similarly to Reed\, we give a structural characterisation for the failure of the integral Erdős-Pósa property in this setting. This allows us to deduce the full Erdős-Pósa property for many natural classes of cycles. \nWe will look at applications of these results to graphs embedded on surfaces\, and also discuss some possibilities and obstacles for extending these results. \nThis is joint work with Kevin Hendrey\, Ken-ichi Kawarabayashi\, O-joung Kwon\, Sang-il Oum\, and Youngho Yoo. URL:https://dimag.ibs.re.kr/event/2022-03-07/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT END:VCALENDAR