Jon-Lark Kim (김종락), Introduction to Boolean functions with Artificial Neural Network

April 3rd, 2019

IBS/KAIST Joint Discrete Math Seminar

Introduction to Boolean functions with Artificial Neural Network
Jon-Lark Kim (김종락)
Department of Mathematics, Sogang University, Seoul
2019/04/18 Thu 11:00AM-12:00PM (IBS, Room B232)
A Boolean function is a function from the set Q of binary vectors of length n (i.e., the binary n-dimensional hypercube) to F2={0,1}. It has several applications to complexity theory, digital circuits, coding theory, and cryptography.In 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.

Andreas Holmsen, Large cliques in hypergraphs with forbidden substructures

February 26th, 2019

IBS/KAIST Joint Discrete Math Seminar

Large cliques in hypergraphs with forbidden substructures
Andreas Holmsen
Department of Mathematical Sciences, KAIST
2019/03/12 Tue 4:30PM-5:30PM (Room B232, IBS)
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 K2,2 as an induced subgraph yet has at least c n(n-1)/2 edges, then G has a complete subgraph on at least c^2 n /10 vertices. In this paper we suggest a “higher-dimensional” analogue of the notion of an induced K2,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.

Seog-Jin Kim (김석진), Signed coloring and list coloring of k-chromatic graphs

January 2nd, 2019

IBS/KAIST Joint Discrete Math Seminar

Signed colouring and list colouring of k-chromatic graphs
Seog-Jin Kim (김석진)
Department of Mathematics Education, Konkuk University, Seoul
2019/1/28 Mon 4PM-5PM (Room B232, IBS)
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. Let 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.

Joonkyung Lee (이준경), Sidorenko’s conjecture for blow-ups

December 25th, 2018

IBS/KAIST Joint Discrete Math Seminar

Sidorenko’s conjecture for blow-ups
Joonkyung Lee (이준경)
Universität Hamburg, Hamburg, Germany
2019/1/3 Thursday 4PM (Room: DIMAG, IBS)
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.Our 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.

Eun Jung Kim (김은정), New algorithm for multiway cut guided by strong min-max duality

December 17th, 2018

IBS/KAIST Joint Discrete Math Seminar

New algorithm for multiway cut guided by strong min-max duality
Eun Jung Kim (김은정)
CNRS, LAMSADE, Paris, France
2019/01/04 Fri 4PM-5PM (Room: DIMAG, IBS)

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.

In 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.

This talk is based on a joint work with Yoichi Iwata and Yuichi Yoshida from NII.