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:20170101T000000 END:STANDARD END:VTIMEZONE BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20190603T163000 DTEND;TZID=Asia/Seoul:20190603T173000 DTSTAMP:20260419T183632 CREATED:20190411T160640Z LAST-MODIFIED:20240707T090357Z UID:770-1559579400-1559583000@dimag.ibs.re.kr SUMMARY:Jinyoung Park (박진영)\, The number of maximal independent sets in the Hamming cube DESCRIPTION:Let $Q_n$ be the $n$-dimensional Hamming cube (hypercube) and $N=2^n$. We prove that the number of maximal independent sets in $Q_n$ is asymptotically $2n2^{N/4}$\, as was conjectured by Ilinca and Kahn in connection with a question of Duffus\, Frankl and Rödl. The value is a natural lower bound derived from a connection between maximal independent sets and induced matchings. The proof of the upper bound draws on various tools\, among them “stability” results for maximal independent set counts and old and new results on isoperimetric behavior in $Q_n$. This is joint work with Jeff Kahn. URL:https://dimag.ibs.re.kr/event/2019-06-03/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20190520T163000 DTEND;TZID=Asia/Seoul:20190520T173000 DTSTAMP:20260419T183632 CREATED:20190304T123855Z LAST-MODIFIED:20240707T090406Z UID:642-1558369800-1558373400@dimag.ibs.re.kr SUMMARY:Lars Jaffke\, A complexity dichotomy for critical values of the b-chromatic number of graphs DESCRIPTION:A $b$-coloring of a graph $G$ is a proper coloring of its vertices such that each color class contains a vertex that has at least one neighbor in all the other color classes. The $b$-Coloring problem asks whether a graph $G$ has a $b$-coloring with $k$ colors.\nThe $b$-chromatic number of a graph $G$\, denoted by $\chi_b(G)$\, is the maximum number $k$ such that $G$ admits a $b$-coloring with $k$ colors. We consider the complexity of the $b$-Coloring problem\, whenever the value of $k$ is close to one of two upper bounds on $\chi_b(G)$: The maximum degree $\Delta(G)$ plus one\, and the $m$-degree\, denoted by $m(G)$\, which is defined as the maximum number $i$ such that $G$ has $i$ vertices of degree at least $i-1$. We obtain a dichotomy result stating that for fixed $k \in\{\Delta(G) + 1 − p\, m(G) − p\}$\, the problem is polynomial-time solvable whenever $p\in\{0\, 1\}$ and\, even when $k = 3$\, it is NP-complete whenever $p \ge 2$.\nWe furthermore consider parameterizations of the $b$-Coloring problem that involve the maximum degree $\Delta(G)$ of the input graph $G$ and give two FPT-algorithms. First\, we show that deciding whether a graph G has a $b$-coloring with $m(G)$ colors is FPT parameterized by $\Delta(G)$. Second\, we show that $b$-Coloring is FPT parameterized by $\Delta(G) + \ell_k(G)$\, where $\ell_k(G)$ denotes the number of vertices of degree at least $k$.\nThis is joint work with Paloma T. Lima. URL:https://dimag.ibs.re.kr/event/2019-05-20/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20190516T163000 DTEND;TZID=Asia/Seoul:20190516T173000 DTSTAMP:20260419T183632 CREATED:20190118T041528Z LAST-MODIFIED:20240707T090507Z UID:423-1558024200-1558027800@dimag.ibs.re.kr SUMMARY:Xin Zhang (张欣)\, On equitable tree-colorings of graphs DESCRIPTION:An equitable tree-$k$-coloring of a graph is a vertex coloring using $k$ distinct colors such that every color class (i.e\, the set of vertices in a common color) induces a forest and the sizes of any two color classes differ by at most one. The minimum integer $k$ such that a graph $G$ is equitably tree-$k$-colorable is the equitable vertex arboricity of $G$\, denoted by $va_{eq}(G)$. A graph that is equitably tree-$k$-colorable may admits no equitable tree-$k’$-coloring for some $k’>k$. For example\, the complete bipartite graph $K_{9\,9}$ has an equitable tree-$2$-coloring but is not equitably tree-3-colorable. In view of this a new chromatic parameter so-called the equitable vertex arborable threshold is introduced. Precisely\, it is the minimum integer $k$ such that $G$ has an equitable tree-$k’$-coloring for any integer $k’\geq k$\, and is denoted by $va_{eq}^*(G)$. The concepts of the equitable vertex arboricity and the equitable vertex arborable threshold were introduced by J.-L. Wu\, X. Zhang and H. Li in 2013. In 2016\, X. Zhang also introduced the list analogue of the equitable tree-$k$-coloring. There are many interesting conjectures on the equitable (list) tree-colorings\, one of which\, for example\, conjectures that every graph with maximum degree at most $\Delta$ is equitably tree-$k$-colorable for any integer $k\geq (\Delta+1)/2$\, i.e\, $va_{eq}^*(G)\leq \lceil(\Delta+1)/2\rceil$. In this talk\, I review the recent progresses on the studies of the equitable tree-colorings from theoretical results to practical algorithms\, and also share some interesting problems for further research. URL:https://dimag.ibs.re.kr/event/2019-05-16/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20190508T163000 DTEND;TZID=Asia/Seoul:20190508T173000 DTSTAMP:20260419T183632 CREATED:20190310T074230Z LAST-MODIFIED:20240707T090513Z UID:673-1557333000-1557336600@dimag.ibs.re.kr SUMMARY:Sang June Lee (이상준)\, On strong Sidon sets of integers DESCRIPTION:Let $\mathbb N$ be the set of natural numbers. A set $A\subset \mathbb N$ is called a Sidon set if the sums $a_1+a_2$\, with $a_1\,a_2\in S$ and $a_1\leq a_2$\, are distinct\, or equivalently\, if \[|(x+w)-(y+z)|\geq 1\] for every $x\,y\,z\,w\in S$ with $xa$ and $b \equiv \pm 1 ~({\rm mod}\:a)$. This includes all previously known ones\, and gives infinitely many limit points $2-\frac{1}{m}$ in the set of all realisable numbers as a consequence. \nSecondly\, we propose a conjecture on subdivisions of bipartite graphs. Apart from being interesting on its own\, we show that\, somewhat surprisingly\, this subdivision conjecture in fact implies that every rational number between 1 and 2 is realisable. \nThis is joint work with Jaehoon Kim and Hong Liu. \nBoram Park (박보람)\, Sum-free set problem on integers\nFor an abelian  group $G$\, a set $A \subset G$ is sum-free if there are no $x\, y\, z \in A$ such that $x + y = z$. Sum-free sets was initiated by Schur (1916) by an attempt to prove the famous Fermat’s Last Theorem. Since then\, there have been intensive and fruitful research in the field of additive combinatorics. One of great interest in the study of sum-free sets is to consider sum-free subsets of a set of integers\, which has attracted a significant attention in the literature over the years. \nIn this talk\, some recent results on sum-free sets of integers are discussed. Then we present a result on $k$-sum $\bf{n}$-free set\, where $\bf{n}$ is an $n$-dimensional integer vector. The work is based on joint work with Ilkyoo Choi and Ringi Kim. \nDániel Gerbner\, Generalized Turán problems – counting subgraphs\nGiven two graphs $H$ and $F$\, our goal is to determine the maximum number of copies of $H$ in an $F$-free graph on $n$ vertices. The systematic research of these problems was initiated (after several sporadic results) by Alon and Shikhelman. I describe several results of mine in this area\, with different sets of co-authors. \nJoint work with Ervin Győri\, Abhishek Methuku\, Cory Palmer and Mate Vizer. URL:https://dimag.ibs.re.kr/event/2019-1-graph-theory/ LOCATION:Room B234\, IBS (기초과학연구원) CATEGORIES:Workshops and Conferences END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20190128T160000 DTEND;TZID=Asia/Seoul:20190128T170000 DTSTAMP:20260419T183632 CREATED:20190102T015548Z LAST-MODIFIED:20240705T211438Z UID:348-1548691200-1548694800@dimag.ibs.re.kr SUMMARY:Seog-Jin Kim (김석진)\, Signed colouring and list colouring of k-chromatic graphs DESCRIPTION:A signed graph is a pair (G\, σ)\, where G is a graph and σ: E(G) → {1\,-1} is a signature of G. A set S of integers is symmetric if I∈S implies that -i∈S. A k-colouring of (G\,σ) is a mapping f:V(G) → Nk such that for each edge e=uv\, f(x)≠σ(e) f(y)\, where Nk is a symmetric integer set of size k. We define the signed chromatic number of a graph G to be the minimum integer k such that for any signature σ of G\, (G\, σ) has a k-colouring. \nLet f(n\,k) be the maximum signed chromatic number of an n-vertex k-chromatic graph. This paper determines the value of f(n\,k) for all positive integers n ≥ k. Then we study list colouring of signed graphs. A list assignment L of G is called symmetric if L(v) is a symmetric integer set for each vertex v. The weak signed choice number ch±w(G) of a graph G is defined to be the minimum integer k such that for any symmetric k-list assignment L of G\, for any signature σ on G\, there is a proper L-colouring of (G\, σ). We prove that the difference ch±w(G)-χ±(G) can be arbitrarily large. On the other hand\, ch±w(G) is bounded from above by twice the list vertex arboricity of G. Using this result\, we prove that ch±w(K2⋆n)= χ±(K2⋆n) = ⌈2n/3⌉ + ⌊2n/3⌋. This is joint work with Ringi Kim and Xuding Zhu. URL:https://dimag.ibs.re.kr/event/2019-01-28/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20190104T160000 DTEND;TZID=Asia/Seoul:20190104T170000 DTSTAMP:20260419T183632 CREATED:20181217T143613Z LAST-MODIFIED:20240705T211439Z UID:279-1546617600-1546621200@dimag.ibs.re.kr SUMMARY:Eun Jung Kim (김은정)\, New algorithm for multiway cut guided by strong min-max duality DESCRIPTION:Problems such as Vertex Cover and Multiway Cut have been well-studied in parameterized complexity. Cygan et al. 2011 drastically improved the running time of several problems including Multiway Cut and Almost 2SAT by employing LP-guided branching and aiming for FPT algorithms parameterized above LP lower bounds. Since then\, LP-guided branching has been studied in depth and established as a powerful technique for parameterized algorithms design. \nIn this talk\, we make a brief overview of LP-guided branching technique and introduce the latest results whose parameterization is above even stronger lower bounds\, namely μ(I)=2LP(I)-IP(dual-I). Here\, LP(I) is the value of an optimal fractional solution and IP(dual-I) is the value of an optimal integral dual solution. Tutte-Berge formula for Maximum Matching (or equivalently Edmonds-Gallai decomposition) and its generalization Mader’s min-max formula are exploited to this end. As a result\, we obtain an algorithm running in time 4k-μ(I) for multiway cut and its generalizations\, where k is the budget for a solution. \nThis talk is based on a joint work with Yoichi Iwata and Yuichi Yoshida from NII. URL:https://dimag.ibs.re.kr/event/2019-01-04/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20190103T160000 DTEND;TZID=Asia/Seoul:20190103T170000 DTSTAMP:20260419T183632 CREATED:20181224T085518Z LAST-MODIFIED:20240707T090650Z UID:305-1546531200-1546534800@dimag.ibs.re.kr SUMMARY:Joonkyung Lee (이준경)\, Sidorenko’s conjecture for blow-ups DESCRIPTION:A celebrated conjecture of Sidorenko and Erdős–Simonovits states that\, for all bipartite graphs H\, quasirandom graphs contain asymptotically the minimum number of copies of H taken over all graphs with the same order and edge density. This conjecture has attracted considerable interest over the last decade and is now known to hold for a broad range of bipartite graphs\, with the overall trend saying that a graph satisfies the conjecture if it can be built from simple building blocks such as trees in a certain recursive fashion. \nOur contribution here\, which goes beyond this paradigm\, is to show that the conjecture holds for any bipartite graph H with bipartition A∪B where the number of vertices in B of degree k satisfies a certain divisibility condition for each k. As a corollary\, we have that for every bipartite graph H with bipartition A∪B\, there is a positive integer p such that the blow-up HAp formed by taking p vertex-disjoint copies of H and gluing all copies of A along corresponding vertices satisfies the conjecture. Joint work with David Conlon. URL:https://dimag.ibs.re.kr/event/2019-01-03/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20181213T170000 DTEND;TZID=Asia/Seoul:20181213T180000 DTSTAMP:20260419T183632 CREATED:20181120T125609Z LAST-MODIFIED:20240707T090704Z UID:250-1544720400-1544724000@dimag.ibs.re.kr SUMMARY:Hong Liu\, Polynomial Schur’s Theorem DESCRIPTION:I will discuss the Ramsey problem for {x\,y\,z:x+y=p(z)} for polynomials p over ℤ. This is joint work with Peter Pach and Csaba Sandor. URL:https://dimag.ibs.re.kr/event/2018-12-13/ LOCATION:Room B109\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20181210T170000 DTEND;TZID=Asia/Seoul:20181210T180000 DTSTAMP:20260419T183632 CREATED:20181031T151146Z LAST-MODIFIED:20240707T090718Z UID:180-1544461200-1544464800@dimag.ibs.re.kr SUMMARY:Tony Huynh\, A tight Erdős-Pósa function for planar minors DESCRIPTION:Let H be a planar graph. By a classical result of Robertson and Seymour\, there is a function f(k) such that for all k and all graphs G\, either G contains k vertex-disjoint subgraphs each containing H as a minor\, or there is a subset X of at most f(k) vertices such that G−X has no H-minor. We prove that this remains true with f(k)=ck log k for some constant c depending on H. This bound is best possible\, up to the value of c\, and improves upon a recent bound of Chekuri and Chuzhoy. The proof is constructive and yields the first polynomial-time O(log 𝖮𝖯𝖳)-approximation algorithm for packing subgraphs containing an H-minor. \nThis is joint work with Wouter Cames van Batenburg\, Gwenaël Joret\, and Jean-Florent Raymond. URL:https://dimag.ibs.re.kr/event/2018-12-10/ LOCATION:Room B109\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT END:VCALENDAR