Sang June Lee (이상준), On strong Sidon sets of integers

April 16th, 2019

IBS/KAIST Joint Discrete Math Seminar

On strong Sidon sets of integers
Sang June Lee
Duksung Women’s University, Seoul
2019/05/08 Wed 4:30PM-5:30PM (IBS, Room B232)
Let N be the set of natural numbers. A set A⊂N is called a Sidon set if the sums a1+a2, with a1,a2∈S and a1≤a2, are distinct, or equivalently, if
|(x+w)−(y+z)|≥1
for every x,y,z,w∈S with x<y≤z<w. We define strong Sidon sets as follows:

For a constant α with 0≤α<1, a set S⊂N is called an α-strong Sidon set if
|(x+w)−(y+z)|≥wα
for every x,y,z,w∈S with x<y≤z<w.

The motivation of strong Sidon sets is that a strong Sidon set generates many Sidon sets by altering each element a bit. This infers that a dense strong Sidon set will guarantee a dense Sidon set contained in a sparse random subset of N.

In this talk, we are interested in how dense a strong Sidon set can be. This is joint work with Yoshiharu Kohayakawa, Carlos Gustavo Moreira and Vojtěch Rödl.

Rose McCarty, Circle graphs are polynomially chi-bounded

April 16th, 2019

IBS/KAIST Joint Discrete Math Seminar

Circle graphs are polynomially chi-bounded
Rose McCarty
University of Waterloo, Waterloo, Canada
2019/04/26 Fri 4PM-5PM (IBS, Room B232)
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 4k2. Joint with James Davies.

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.