BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv5.15.0//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:20220522T103946
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:20220522T103946
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;VALUE=DATE:20220527
DTEND;VALUE=DATE:20220530
DTSTAMP:20220522T103946
CREATED:20220526T150000Z
LAST-MODIFIED:20220515T061308Z
UID:5555-1653609600-1653868799@dimag.ibs.re.kr
SUMMARY:KSIAM 2022 Spring Meeting
DESCRIPTION:KSIAM (Korean Society for Industrial and Applied Mathematics) will have the KSIAM 2022 Spring Conference at the Institute for Basic Science (IBS). Its academic session for Combinatorics decided to have an invited talk by Joonkyung Lee at the Hanyang University\, a special session “Graph Theory” organized by Sang-il Oum and the IBS DIMAG\, a special session “Enumerative Combinatorics” organized by Dongsu Kim at KAIST\, and a poster session\, all on May 27 afternoon. The deadline for the abstract submission is May 2 and the deadline for the early registration is May 9. \nInvited talk (May 27 Friday\, 16:40-17:40)\n\nJoonkyung Lee이준경 (Hanyang University)\, Graph homomorphism inequalities and their applications\nCounting (weighted) homomorphisms between graphs relates to a wide variety of areas\, in- cluding graph theory\, probability\, statistical physics and theoretical computer science. In recent years\, various new applications of inequalities between graph homomorphism counts have been found.\nWe will discuss some of the examples\, including a simple proof of the Bondy–Simonovits theorem and a new estimate for the rainbow Turán numbers of even cycles. If time permits\, we will also touch upon some recent progress on Sidorenko’s conjecture and related questions\, in particular their applications on the bipartite Turán problems.\nBased on joint work with David Conlon\, Jaehoon Kim\, Hong Liu\, and Tuan Tran. \n\nSpecial session “Graph Theory” (May 27\, 13:20-14:40)\nOrganized by Sang-il Oum엄상일 (IBS Discrete Mathematics Group & KAIST). \nSpeakers\n\nBoram Park박보람 (Ajou University)\, Odd Coloring of Graphs\nAn odd $c$-coloring of a graph is a proper $c$-coloring such that each non-isolated vertex has a color appearing an odd number of times on its neighborhood. Recently\, Cranston investigated odd colorings of graphs with bounded maximum average degree\, and conjectured that every graph $G$ with $\operatorname{mad}(G)\leq \frac{4c-4}{c+1}$ has an odd $c$-coloring for $c\geq 4$\, and proved the conjecture for $c\in\{5\, 6\}$. In particular\, planar graphs with girth at least $7$ and $6$ have an odd $5$-coloring and an odd $6$-coloring\, respectively.\nWe completely resolve Cranston’s conjecture. For $c\geq 7$\, we show that the conjecture is true\, in a stronger form that was implicitly suggested by Cranston\, but for $c=4$\, we construct counterexamples\, which all contain $5$-cycles. On the other hand\, we show that a graph $G$ with $\operatorname{mad}(G)<\frac{22}{9}$ and no induced $5$-cycles has an odd $4$-coloring. This implies that a planar graph with girth at least 11 has an odd $4$-coloring. We also prove that a planar graph with girth at least 5 has an odd $6$-coloring.\nJoint work with Eun-Kyung Cho\, Ilkyoo Choi\, and Hyemin Kown. \n\n\nJongyook Park박종육 (Kyungpook National University)\, On the Delsarte bound\nWe study the order of a maximal clique in an amply regular graph with a fixed smallest eigenvalue by considering a vertex that is adjacent to some (but not all) vertices of the maximal clique. As a consequence\, we show that if a strongly regular graph contains a Delsarte clique\, then the parameter μ is either small or large. Furthermore\, we obtain a cubic polynomial that assures that a maximal clique in an amply regular graph is either small or large (under certain assumptions). Combining this cubic polynomial with the claw-bound\, we rule out an infinite family of feasible parameters (v\, k\, λ\, μ) for strongly regular graphs. Lastly\, we provide tables of parameters (v\, k\, λ\, μ) for nonexistent strongly regular graphs with smallest eigenvalue −4\,−5\,−6 or −7. This is joint work with Gary Greaves and Jack Koolen. \n\n\nO-joung Kwon권오정 (Hanyang University and IBS Discrete Mathematics Group)\, Well-partitioned chordal graphs\nWe introduce a new subclass of chordal graphs that generalizes the class of split graphs\, which we call well-partitioned chordal graphs. A connected graph $G$ is a well-partitioned chordal graph if there exist a partition $\mathcal{P}$ of the vertex set of $G$ into cliques and a tree $\mathcal{T}$ having $\mathcal{P}$ as a vertex set such that for distinct $X\,Y\in \mathcal{P}$\, (1) the edges between $X$ and $Y$ in $G$ form a complete bipartite subgraph whose parts are some subsets of $X$ and $Y$\, if $X$ and $Y$ are adjacent in $\mathcal{T}$\, and (2) there are no edges between $X$ and $Y$ in $G$ otherwise. A split graph with vertex partition $(C\, I)$ where $C$ is a clique and $I$ is an independent set is a well-partitioned chordal graph as witnessed by a star $\mathcal{T}$ having $C$ as the center and each vertex in $I$ as a leaf\, viewed as a clique of size $1$. We characterize well-partitioned chordal graphs by forbidden induced subgraphs\, and give a polynomial-time algorithm that given a graph\, either finds an obstruction\, or outputs a partition of its vertex set that asserts that the graph is well-partitioned chordal.\nWe observe that there are problems\, for instance Densest $k$-Subgraph and $b$-Coloring\, that are polynomial-time solvable on split graphs but become NP-hard on well-partitioned chordal graphs. On the other hand\, we show that the Geodetic Set problem\, known to be NP-hard on chordal graphs\, can be solved in polynomial time on well-partitioned chordal graphs. We also answer two combinatorial questions on well-partitioned chordal graphs that are open on chordal graphs\, namely that each well-partitioned chordal graph admits a polynomial-time constructible tree $3$-spanner\, and that each ($2$-connected) well-partitioned chordal graph has a vertex that intersects all its longest paths (cycles). Joint work with Jungho Ahn\, Lars Jaffke\, and Paloma T. Lima. \n\n\nStijn Cambie (IBS Extremal Combinatorics and Probability Group)\, Regular Cereceda’s Conjecture\nThe reconfiguration graph $\mathcal C_k(G)$ for the $k$-colourings of a graph $G$ has a vertex for each proper $k$-colouring of $G$\, and two vertices of $\mathcal C_k(G)$ are adjacent precisely when those $k$-colourings differ on a single vertex of $G$. Much work has focused on bounding the maximum value of $\operatorname{diam} \mathcal C_k(G)$ over all $n$-vertex graphs $G$. One of the most famous conjectures related related to $\mathcal C_k(G)$ is Cereceda’s conjecture\, which says that if $k \ge \operatorname{degen}(G) + 2$\, the diameter of $\mathcal C_k(G)$ is $O(n^2)$. In this talk\, we give some ideas towards a precise form for Cereceda’s conjecture\, when restricting to regular graphs. \nThis is based on joint work with Wouter Cames van Batenburg (TU Delft\, the Netherlands) and Daniel Cranston (Virginia Commonwealth University\, USA)\, which originates from the online workshop Graph Reconfiguration of the Sparse Graphs Coalition. \n\nSpecial session “Enumerative Combinatorics” (May 27\, 15:00-16:20)\nOrganized by Dongsu Kim김동수 (KAIST). \nSpeakers\n\nMeesue Yoo류미수 (Chungbuk National University)\, Combinatorial description for the Hall-Littlewood expansion of unicellular LLT and chromatic quasisymmetric polynomials\nIn this work\, we obtain a Hall–Littlewood expansion of the chromatic quasisymmetric functions by using a Dyck path model and linked rook placements. By using the Carlsson–Mellit relation between the chromatic quasisymmetric functions and the unicellular LLT polynomials\, this combinatorial description for the Hall–Littlewood coefficients of the chromatic quasisymmetric functions also gives the coefficients of the unicellular LLT polynomials expanded in terms of the modified transformed Hall–Littlewood polynomials. Joint work with Seung Jin Lee. \n\n\nDonghyun Kim김동현 (Sungkyunkwan University)\, Combinatorial formulas for the coefficients of the Al-Salam-Chihara polynomials\nThe Al-Salam-Chihara polynomials are an important family of orthogonal polynomials in one variable $x$ depending on 3 parameters $\alpha$\, $\beta$ and $q$. They are closely connected to a model from statistical mechanics called the partially asymmetric simple exclusion process (PASEP) and they can be obtained as a specialization of the Askey-Wilson polynomials. We give two different combinatorial formulas for the coefficients of the (transformed) Al-Salam-Chihara polynomials. Our formulas make manifest the fact that the coefficients are polynomials in $\alpha$\, $\beta$ and $q$ with positive coefficients. \n\n\nJisun Huh허지선 (Ajou University)\, Combinatorics on bounded Motzkin paths and its applications\nA free Motzkin path of length \(n\) is a lattice path which starts at \((0\,0)\) or \((0\,1)\)\, ends at \((n\,0)\)\, and has only up steps \(u=(1\,1)\)\, down steps \(d=(1\,-1)\)\, and flat steps \(f=(1\,0)\). In addition\, if a free Motzkin path starts at \((0\,0)\) and stays weakly above the \(x\)-axis\, then it is called a Motzkin path. In this talk\, we construct a bijection between \(F(m\,r\,k)\) and \(M(m\,r\,k)\)\, where \(F(m\,r\,k)\) is the set of free Motzkin paths of length \(m+r\) with \(r\) flat steps that are contained in the strip \(-\lfloor k/2 \rfloor \leq y \leq \lfloor (k+1)/2 \rfloor\) and \(M(m\,r\,k)\) is the set of Motzkin prefixed of length \(m+r\) with \(r\) flat steps that are contained in the strip \(0 \leq y \leq k\). Furthermore\, we provide path interpretations of ordinary/self-conjugate \(t\)-core partitions with \(m\)-corners as an application.\nThis is joint work with Hyunsoo Cho\, Hayan Nam\, and Jaebum Sohn. \n\n\nJihyeug Jang장지혁 (Sungkyunkwan University)\, A combinatorial model for the transition matrix between the Specht and web bases\nWe introduce a new class of permutations\, called web permutations. Using these permutations\, we provide a combinatorial interpretation for entries of the transition between the Specht and web bases\, which answers Rhoades’s question. Furthermore\, we study enumerative properties of these permutations. Joint work with Byung-Hak Hwang and Jaeseong Oh.
URL:https://dimag.ibs.re.kr/event/ksiam-2022-spring-meeting/
LOCATION:IBS Science Culture Center
CATEGORIES:Workshops and Conferences
ATTACH;FMTTYPE=image/png:https://dimag.ibs.re.kr/cms/wp-content/uploads/2022/05/main_ss20220329.png
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220530T163000
DTEND;TZID=Asia/Seoul:20220530T173000
DTSTAMP:20220522T103946
CREATED:20220530T073000Z
LAST-MODIFIED:20220426T130212Z
UID:5495-1653928200-1653931800@dimag.ibs.re.kr
SUMMARY:Hongseok Yang (양홍석)\, TBA
DESCRIPTION:
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:20220522T103946
CREATED:20220602T013000Z
LAST-MODIFIED:20220506T045858Z
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)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220613T163000
DTEND;TZID=Asia/Seoul:20220613T173000
DTSTAMP:20220522T103946
CREATED:20220502T144707Z
LAST-MODIFIED:20220502T144707Z
UID:5578-1655137800-1655141400@dimag.ibs.re.kr
SUMMARY:Amadeus Reinald\, TBA
DESCRIPTION:
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:20220720T163000
DTEND;TZID=Asia/Seoul:20220720T173000
DTSTAMP:20220522T103946
CREATED:20220512T003143Z
LAST-MODIFIED:20220512T003143Z
UID:5637-1658334600-1658338200@dimag.ibs.re.kr
SUMMARY:Lars Jaffke\, Taming graphs with no large creatures and skinny ladders
DESCRIPTION:We confirm a conjecture of Gartland and Lokshtanov [arXiv:2007.08761]: if for a hereditary graph class $\mathcal{G}$ there exists a constant $k$ such that no member of $\mathcal{G}$ contains a $k$-creature as an induced subgraph or a $k$-skinny-ladder as an induced minor\, then there exists a polynomial $p$ such that every $G \in \mathcal{G}$ contains at most $p(|V(G)|)$ minimal separators. By a result of Fomin\, Todinca\, and Villanger [SIAM J. Comput. 2015] the latter entails the existence of polynomial-time algorithms for Maximum Weight Independent Set\, Feedback Vertex Set and many other problems\, when restricted to an input graph from $\mathcal{G}$. Furthermore\, as shown by Gartland and Lokshtanov\, our result implies a full dichotomy of hereditary graph classes defined by a finite set of forbidden induced subgraphs into tame (admitting a polynomial bound of the number of minimal separators) and feral (containing infinitely many graphs with exponential number of minimal separators). \nJoint work with Jakub Gajarský\, Paloma T. Lima\, Jana Novotná\, Marcin Pilipczuk\, Paweł Rzążewski\, and Uéverton S. Souza.
URL:https://dimag.ibs.re.kr/event/2022-07-20/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
END:VCALENDAR