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:20190426T160000
DTEND;TZID=Asia/Seoul:20190426T170000
DTSTAMP:20260422T194101
CREATED:20190309T122202Z
LAST-MODIFIED:20240705T211023Z
UID:666-1556294400-1556298000@dimag.ibs.re.kr
SUMMARY:Rose McCarty\, Circle graphs are polynomially chi-bounded
DESCRIPTION:Circle graphs are the intersection graphs of chords on a circle; vertices correspond to chords\, and two vertices are adjacent if their chords intersect. We prove that every circle graph with clique number k has chromatic number at most $4k^2$. Joint with James Davies.
URL:https://dimag.ibs.re.kr/event/2019-04-26/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20190418T110000
DTEND;TZID=Asia/Seoul:20190418T120000
DTSTAMP:20260422T194101
CREATED:20190403T013055Z
LAST-MODIFIED:20240707T090539Z
UID:733-1555585200-1555588800@dimag.ibs.re.kr
SUMMARY:Jon-Lark Kim (김종락)\, Introduction to Boolean functions with Artificial Neural Network
DESCRIPTION:A Boolean function is a function from the set Q of binary vectors of length n (i.e.\, the binary n-dimensional hypercube) to $F_2=\{0\,1\}$. It has several applications to complexity theory\, digital circuits\, coding theory\, and cryptography.\nIn this talk we give a connection between Boolean functions and Artificial Neural Network. We describe how to represent Boolean functions by Artificial Neural Network including linear and polynomial threshold units and sigmoid units. For example\, even though a linear threshold function cannot realize XOR\, a polynomial threshold function can do it. We also give currently open problems related to the number of (Boolean) linear threshold functions and polynomial threshold functions.
URL:https://dimag.ibs.re.kr/event/2019-04-18/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20190312T163000
DTEND;TZID=Asia/Seoul:20190312T173000
DTSTAMP:20260422T194101
CREATED:20190226T113020Z
LAST-MODIFIED:20240707T090549Z
UID:635-1552408200-1552411800@dimag.ibs.re.kr
SUMMARY:Andreas Holmsen\, Large cliques in hypergraphs with forbidden substructures
DESCRIPTION:A result due to Gyárfás\, Hubenko\, and Solymosi\, answering a question of Erdős\, asserts that if a graph $G$ does not contain $K_{2\,2}$ as an induced subgraph yet has at least $c\binom{n}{2}$ edges\, then $G$ has a complete subgraph on at least $\frac{c^2}{10}n$ vertices. In this paper we suggest a “higher-dimensional” analogue of the notion of an induced $K_{2\,2}$\, which allows us to extend their result to $k$-uniform hypergraphs. Our result also has interesting consequences in topological combinatorics and abstract convexity\, where it can be used to answer questions by Bukh\, Kalai\, and several others.
URL:https://dimag.ibs.re.kr/event/2019-03-12/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20190128T160000
DTEND;TZID=Asia/Seoul:20190128T170000
DTSTAMP:20260422T194101
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:20260422T194101
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:20260422T194101
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:20260422T194101
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:20260422T194101
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