BEGIN:VCALENDAR VERSION:2.0 PRODID:-//Discrete Mathematics Group - ECPv6.3.5//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:20220101T000000 END:STANDARD END:VTIMEZONE BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220523T163000 DTEND;TZID=Asia/Seoul:20220523T173000 DTSTAMP:20240328T225101 CREATED:20220523T073000Z LAST-MODIFIED:20220516T214605Z 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:20220525T163000 DTEND;TZID=Asia/Seoul:20220525T173000 DTSTAMP:20240328T225101 CREATED:20220525T073000Z LAST-MODIFIED:20220518T041938Z UID:5509-1653496200-1653499800@dimag.ibs.re.kr SUMMARY:Sebastian Siebertz\, Transducing paths in graph classes with unbounded shrubdepth DESCRIPTION:Transductions are a general formalism for expressing transformations of graphs (and more generally\, of relational structures) in logic. We prove that a graph class C can be FO-transduced from a class of bounded-height trees (that is\, has bounded shrubdepth) if\, and only if\, from C one cannot FO-transduce the class of all paths. This establishes one of the three remaining open questions posed by Blumensath and Courcelle about the MSO-transduction quasi-order\, even in the stronger form that concerns FO-transductions instead of MSO-transductions. \nThe backbone of our proof is a graph-theoretic statement that says the following: If a graph G excludes a path\, the bipartite complement of a path\, and a half-graph as semi-induced subgraphs\, then the vertex set of G can be partitioned into a bounded number of parts so that every part induces a cograph of bounded height\, and every pair of parts semi-induce a bi-cograph of bounded height. This statement may be of independent interest; for instance\, it implies that the graphs in question form a class that is linearly chi-bounded. \nThis is joint work with Patrice Ossona de Mendez and Michał Pilipczuk. URL:https://dimag.ibs.re.kr/event/2022-05-25/ LOCATION:Zoom ID: 869 4632 6610 (ibsdimag) CATEGORIES:Virtual Discrete Math Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20220530T163000 DTEND;TZID=Asia/Seoul:20220530T173000 DTSTAMP:20240328T225101 CREATED:20220530T073000Z LAST-MODIFIED:20220523T020807Z 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:20220602T103000 DTEND;TZID=Asia/Seoul:20220602T113000 DTSTAMP:20240328T225101 CREATED:20220602T013000Z LAST-MODIFIED:20220613T054624Z 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:20240328T225101 CREATED:20220602T071500Z LAST-MODIFIED:20220529T232419Z 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:20240328T225101 CREATED:20220613T073000Z LAST-MODIFIED:20220605T122500Z 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:20240328T225101 CREATED:20220622T073000Z LAST-MODIFIED:20220614T112610Z 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
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:20220831T163000
DTEND;TZID=Asia/Seoul:20220831T173000
DTSTAMP:20240328T225102
CREATED:20220816T233139Z
LAST-MODIFIED:20220817T150245Z
UID:6033-1661963400-1661967000@dimag.ibs.re.kr
SUMMARY:Raphael Steiner\, Congruence-constrained subdivisions in digraphs
DESCRIPTION:I will present the short proof from [1] that for every digraph F and every assignment of pairs of integers $(r_e\,q_e)_{e\in A(F)}$ to its arcs\, there exists an integer $N$ such that every digraph D with dichromatic number at least $N$ contains a subdivision of $F$ in which $e$ is subdivided into a directed path of length congruent to $r_e$ modulo $q_e$ for every $e \in A(F)$. This generalizes to the directed setting the analogous result by Thomassen for undirected graphs and at the same time yields a novel proof of his result. I will also talk about how a hypergraph coloring result from [2] may help to obtain good bounds on $N$ in the special case when $F$ is subcubic. \n[1] https://arxiv.org/abs/2208.06358 \n[2] https://arxiv.org/abs/2206.13635
URL:https://dimag.ibs.re.kr/event/2022-08-31/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220906T163000
DTEND;TZID=Asia/Seoul:20220906T173000
DTSTAMP:20240328T225102
CREATED:20220719T105944Z
LAST-MODIFIED:20220906T113808Z
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:20240328T225102
CREATED:20220614T112030Z
LAST-MODIFIED:20220614T112030Z
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:20240328T225102
CREATED:20220720T105001Z
LAST-MODIFIED:20220720T105001Z
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:20240328T225102
CREATED:20220818T013812Z
LAST-MODIFIED:20220916T065352Z
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:20240328T225102
CREATED:20220825T021718Z
LAST-MODIFIED:20220902T090425Z
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