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:20220719T140000
DTEND;TZID=Asia/Seoul:20220719T160000
DTSTAMP:20260417T064551
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:20260417T064551
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:20260417T064551
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:20220707T100000
DTEND;TZID=Asia/Seoul:20220707T110000
DTSTAMP:20260417T064551
CREATED:20220707T010000Z
LAST-MODIFIED:20240707T075642Z
UID:5783-1657188000-1657191600@dimag.ibs.re.kr
SUMMARY:Sepehr Hajebi\, Holes\, hubs and bounded treewidth
DESCRIPTION:A hole in a graph $G$ is an induced cycle of length at least four\, and for every hole $H$ in $G$\, a vertex $h\in G\setminus H$ is called a $t$-hub for $H$ if $h$ has at least $t$ neighbor in $H$. Sintiari and Trotignon were the first to construct graphs with arbitrarily large treewidth and no induced subgraph isomorphic to the “basic obstructions\,” that is\, a fixed complete graph\, a fixed complete bipartite graph (with parts of equal size)\, all subdivisions of a fixed wall and line graphs of all subdivisions of a fixed wall. They named their counterexamples “layered wheels” for a good reason: layered wheels contain wheels in abundance\, where a wheel means a hole with a $3$-hub. In accordance\, one may ask whether graphs with no wheel and no induced subgraph isomorphic to the basic obstructions have bounded treewidth. This was also disproved by a recent construction due to Davies. But holes with a $2$-hub cannot be avoided in graphs with large treewidth: graphs containing no hole with a $2$-hub and no induced subgraph isomorphic to the basic obstructions have bounded treewidth. I will present a proof of this result\, and will also give an overview of related works.\nBased on joint work with Tara Abrishami\, Bogdan Alecu\, Maria Chudnovsky\, Sophie Spirkl and Kristina Vušković.
URL:https://dimag.ibs.re.kr/event/2022-07-07/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220704T163000
DTEND;TZID=Asia/Seoul:20220704T173000
DTSTAMP:20260417T064551
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:20220629T163000
DTEND;TZID=Asia/Seoul:20220629T173000
DTSTAMP:20260417T064551
CREATED:20220611T121204Z
LAST-MODIFIED:20240705T171148Z
UID:5827-1656520200-1656523800@dimag.ibs.re.kr
SUMMARY:Xizhi Liu\, Hypergraph Turán problem: from 1 to ∞
DESCRIPTION:One interesting difference between (nondegenerate) Graph Turán problem and Hypergraph Turán problem is that the hypergraph families can have at least two very different extremal constructions. In this talk\, we will look at some recent progress and approaches to constructing hypergraph families with at least two different extremal constructions.\nBased on some joint work with Dhruv Mubayi\, Christian Reiher\, Jianfeng Hou\, Heng Li\, and Yixiao Zhang.
URL:https://dimag.ibs.re.kr/event/2022-06-29/
LOCATION:Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED]
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220627T163000
DTEND;TZID=Asia/Seoul:20220627T173000
DTSTAMP:20260417T064551
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:20220622T163000
DTEND;TZID=Asia/Seoul:20220622T173000
DTSTAMP:20260417T064551
CREATED:20220622T073000Z
LAST-MODIFIED:20240707T075717Z
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<p<2 $\, the translative packing density of superballs (a generalization of $\ell^p$ balls) in $\mathbb{R}^n$ is $\Omega(n/2^n)$.\nThis is joint work with Gennian Ge.
URL:https://dimag.ibs.re.kr/event/2022-06-22/
LOCATION:Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED]
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220613T163000
DTEND;TZID=Asia/Seoul:20220613T173000
DTSTAMP:20260417T064551
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:20220602T161500
DTEND;TZID=Asia/Seoul:20220602T171500
DTSTAMP:20260417T064551
CREATED:20220602T071500Z
LAST-MODIFIED:20240705T172222Z
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:20220602T103000
DTEND;TZID=Asia/Seoul:20220602T113000
DTSTAMP:20260417T064551
CREATED:20220602T013000Z
LAST-MODIFIED:20240707T075917Z
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:20220530T163000
DTEND;TZID=Asia/Seoul:20220530T173000
DTSTAMP:20260417T064551
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:20220527T132000
DTEND;TZID=Asia/Seoul:20220527T174000
DTSTAMP:20260417T064551
CREATED:20220527T042000Z
LAST-MODIFIED:20240707T075940Z
UID:5555-1653657600-1653673200@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:20220525T163000
DTEND;TZID=Asia/Seoul:20220525T173000
DTSTAMP:20260417T064551
CREATED:20220525T073000Z
LAST-MODIFIED:20240705T172235Z
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:20220523T163000
DTEND;TZID=Asia/Seoul:20220523T173000
DTSTAMP:20260417T064551
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:20220519T161500
DTEND;TZID=Asia/Seoul:20220519T171500
DTSTAMP:20260417T064551
CREATED:20220519T071500Z
LAST-MODIFIED:20240707T080000Z
UID:5661-1652976900-1652980500@dimag.ibs.re.kr
SUMMARY:Gil Kalai\, The Cascade Conjecture and other Helly-type Problems
DESCRIPTION:[Colloquium\, Department of Mathematical Sciences\, KAIST] \nFor a set $X$ of points $x(1)$\, $x(2)$\, $\ldots$\, $x(n)$ in some real vector space $V$ we denote by $T(X\,r)$ the set of points in $X$ that belong to the convex hulls of r pairwise disjoint subsets of $X$.\nWe let $t(X\,r)=1+\dim(T(X\,r))$. \nRadon’s theorem asserts that\nIf $t(X\,1)< |X|$\, then $t(X\, 2) >0$. \nThe first open case of the cascade conjecture asserts that\nIf $t(X\,1)+t(X\,2) < |X|$\, then $t(X\,3) >0$. \nIn the lecture\, I will discuss connections with topology and with various problems in graph theory. I will also mention questions regarding dimensions of intersection of convex sets. \nSome related material:\n1) A lecture (from 1999): An invitation to Tverberg Theorem: https://youtu.be/Wjg1_QwjUos\n2) A paper on Helly type problems by Barany and me https://arxiv.org/abs/2108.08804\n3) A link to Barany’s book: Combinatorial convexity https://www.amazon.com/Combinatorial-Convexity-University-Lecture-77/dp/1470467097
URL:https://dimag.ibs.re.kr/event/2022-05-19/
LOCATION:Zoom ID: 868 7549 9085
CATEGORIES:Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220518T163000
DTEND;TZID=Asia/Seoul:20220518T173000
DTSTAMP:20260417T064551
CREATED:20220518T073000Z
LAST-MODIFIED:20240705T173008Z
UID:5506-1652891400-1652895000@dimag.ibs.re.kr
SUMMARY:Jan Kurkofka\, Canonical Graph Decompositions via Coverings
DESCRIPTION:We present a canonical way to decompose finite graphs into highly connected local parts. The decomposition depends only on an integer parameter whose choice sets the intended degree of locality. The global structure of the graph\, as determined by the relative position of these parts\, is described by a coarser model. This is a simpler graph determined entirely by the decomposition\, not imposed. \nThe model and decomposition are obtained as projections of the tangle-tree structure of a covering of the given graph that reflects its local structure at the intended level of locality while unfolding its global structure. \nOur theorem extends to locally finite quasi-transitive graphs and in particular to locally finite Cayley graphs. It thereby offers a canonical decomposition theorem for finitely generated groups into local parts\, whose relative structure is displayed by a graph. \nJoint work with Reinhard Diestel\, Raphael W. Jacobs and Paul Knappe.
URL:https://dimag.ibs.re.kr/event/2022-05-18/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220516T163000
DTEND;TZID=Asia/Seoul:20220516T173000
DTSTAMP:20260417T064551
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:20260417T064551
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:20260417T064551
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:20220427T163000
DTEND;TZID=Asia/Seoul:20220427T173000
DTSTAMP:20260417T064551
CREATED:20220427T073000Z
LAST-MODIFIED:20240705T173041Z
UID:5399-1651077000-1651080600@dimag.ibs.re.kr
SUMMARY:Michael Savery\, Induced subgraphs of induced subgraphs of large chromatic number
DESCRIPTION:We prove that for every graph F with at least one edge there are graphs H of arbitrarily large chromatic number and the same clique number as F such that every F-free induced subgraph of H has chromatic number at most c=c(F). (Here a graph is F-free if it does not contain an induced copy of F.) This generalises recent theorems of Briański\, Davies and Walczak\, and of Carbonero\, Hompe\, Moore and Spirkl. We further show an analogous statement where clique number is replaced by odd girth. This is joint work with Antonio Girão\, Freddie Illingworth\, Emil Powierski\, Alex Scott\, Youri Tamitegama and Jane Tan.
URL:https://dimag.ibs.re.kr/event/2022-04-27/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220425T163000
DTEND;TZID=Asia/Seoul:20220425T173000
DTSTAMP:20260417T064551
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:20220413T163000
DTEND;TZID=Asia/Seoul:20220413T173000
DTSTAMP:20260417T064551
CREATED:20220413T073000Z
LAST-MODIFIED:20240707T080102Z
UID:5378-1649867400-1649871000@dimag.ibs.re.kr
SUMMARY:Jakub Gajarský\, Model Checking on Interpretations of Classes of Bounded Local Clique-Width
DESCRIPTION:The first-order model checking problem for finite graphs asks\, given a graph G and a first-order sentence $\phi$ as input\, to decide whether $\phi$ holds on G. Showing the existence of an efficient algorithm for this problem implies the existence of efficient parameterized algorithms for various commonly studied problems\, such as independent set\, distance-r dominating set\, and many others. \nWhile the first-order model-checking problem is likely not efficiently solvable in general\, efficient algorithms exist for various restricted graph classes\, such as graphs of bounded degree\, planar graphs etc. After the existence of an efficient model checking algorithm was shown for nowhere dense classes of graphs (which include most of commonly studied classes of sparse graphs)\, the attention turned to the more general setting of graph classes which can be obtained from sparse graphs using graph transformations called interpretations/transductions. However\, despite efforts of several groups of researchers\, no positive algorithmic result has been achieved since 2016\, when the existence of an efficient algorithm was shown for graph classes interpretable in graphs of bounded degree. \nWe present a fixed-parameter tractable algorithm for first-order model checking on interpretations of graph classes with bounded local clique-width. Notably\, this includes interpretations of planar graphs (and more generally\, of locally bounded treewidth) and vastly generalizes the result for interpretations of graphs of bounded degree. To obtain this result we developed a new tool which works in a very general setting of dependent classes and which we believe can be an important ingredient in achieving similar results in the future. \nThis is joint work with Édouard Bonnet\, Jan Dreier\, Stephan Kreutzer\, Nikolas Mählmann\, Pierre Simon\, Szymon Toruńczyk.
URL:https://dimag.ibs.re.kr/event/2022-04-13/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220411T163000
DTEND;TZID=Asia/Seoul:20220411T173000
DTSTAMP:20260417T064551
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;VALUE=DATE:20220404
DTEND;VALUE=DATE:20220407
DTSTAMP:20260417T064551
CREATED:20220311T230000Z
LAST-MODIFIED:20240707T080124Z
UID:5370-1649030400-1649289599@dimag.ibs.re.kr
SUMMARY:IBS ECOPRO Opening conference
DESCRIPTION:To celebrate the opening of the IBS ECOPRO (Extremal Combinatorics and Probability) Group\, we will organize a 3-day online conference from April 4 to April 6. \nOfficial Website: https://www.ibs.re.kr/ecopro/event/opening/ \nInvited Speakers\n\n\n\n\n\nNoga Alon\nPrinceton University \n\n\n\n\n\nJózsef Balogh\nUniversity of Illinois at Urbana-Champaign \n\n\n\n\n\nJeff Kahn\nRutgers University \n\n\n\n\n\n\n\nMihyun Kang\nGraz University of Technology \n\n\n\n\n\nJeong Han Kim\nKIAS \n\n\n\n\n\nNati Linial\nHebrew University of Jerusalem \n\n\n\n\n\n\n\nOleg Pikhurko\nUniversity of Warwick \n\n\n\n\n\nBenny Sudakov\nETH Zürich \n\n\n\n\n\nTibor Szabó\nFreie Universität Berlin \n\n\n\n\n\n\n\nVan Vu\nYale \n\n\n\n\n\n\n\n\nProgram\n\n\n\n\nTime in Korea\nMonday\nTuesday\nWednesday\n\n\n\n\n7:15 PM\nKim\n\n\n\n\n8:00 PM\nPikhurko\nKang\nVu\n\n\n8:45 PM\nKahn\nBalogh\nSzabó\n\n\n9:30 PM\nAlon\nSudakov\nLinial\n\n\n\n\n\nOrganizers\n\nJaehoon Kim\, KAIST\nHong Liu\, IBS Extremal Combinatorics and Probability Group\nSang-il Oum\, IBS Discrete Mathematics Group / KAIST\nTuan Tran\, IBS Discrete Mathematics Group
URL:https://dimag.ibs.re.kr/event/ibs-ecopro-opening-conference/
LOCATION:Zoom ID: 878 0445 3986 (ibsecopro) [CLOSED]
CATEGORIES:Workshops and Conferences
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220330T163000
DTEND;TZID=Asia/Seoul:20220330T173000
DTSTAMP:20260417T064551
CREATED:20220330T073000Z
LAST-MODIFIED:20240707T080136Z
UID:5270-1648657800-1648661400@dimag.ibs.re.kr
SUMMARY:Jean-Florent Raymond\, Long induced paths in minor-closed graph classes and beyond
DESCRIPTION:In 1982 Galvin\, Rival\, and Sands proved that in $K_{t\,t}$-subgraph free graphs (t being fixed)\, the existence of a path of order n guarantees the existence of an induced path of order f(n)\, for some (slowly) increasing function f. The problem of obtaining good lower-bounds for f for specific graph classes was investigated decades later and logarithmic bounds have been obtained for planar graphs (more generally for graphs of bounded genus) and for interval graphs. \nIn this talk I will show that every graph of pathwidth less than k that has a path of order n also has an induced path of order $Ω(n^{1/k})$. I will then explain how this result can be used to prove the two following generalizations: \n\nevery graph of treewidth less than k that has a path of order n contains an induced path of order $Ω((\log n)^{1/k})$;\nfor every non-trivial graph class that is closed under topological minors there is a constant d∈(0\,1) such that every graph from this class that has a path of order n contains an induced path of order $Ω((\log n)^d)$.\n\nJoint work with Claire Hilaire.
URL:https://dimag.ibs.re.kr/event/2022-03-30/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220328T163000
DTEND;TZID=Asia/Seoul:20220328T173000
DTSTAMP:20260417T064551
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:20260417T064551
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;VALUE=DATE:20220320
DTEND;VALUE=DATE:20220328
DTSTAMP:20260417T064551
CREATED:20220131T150000Z
LAST-MODIFIED:20240705T175059Z
UID:3527-1647734400-1648425599@dimag.ibs.re.kr
SUMMARY:MATRIX-IBS Workshop: Structural Graph Theory Downunder II
DESCRIPTION:This program consists of a short intensive workshop\, where mathematicians from across the globe will come together to work on open problems in structural graph theory. We will consider the following research themes: graph minors\, graph colouring\, Hadwiger’s Conjecture\, bounded expansion classes\, graph product structure theory\, generalised colouring numbers\, VC dimension\, induced subgraphs\, Erdős-Hajnal conjecture\, Gyárfás-Sumner conjecture\, twin-width\, asymptotic dimension. The majority of the time will be allocated to collaborative research (with only a few talks). The goal is to create an environment where mathematicians at all career stages work side-by-side. We anticipate that open problems will be solved\, and lasting collaborations will be initiated. \nURL: https://www.matrix-inst.org.au/events/structural-graph-theory-downunder-ll/ \nRegistration is by invitation only. If you are interested to participate in this research program\, please contact one of the organisers with your CV and research background. \n 
URL:https://dimag.ibs.re.kr/event/2022-03-20/
LOCATION:MATRIX\, Australia
CATEGORIES:Workshops and Conferences
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220314T163000
DTEND;TZID=Asia/Seoul:20220314T173000
DTSTAMP:20260417T064551
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
END:VCALENDAR