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

Room B232 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

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

Room B232 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

Andreas Holmsen, Large cliques in hypergraphs with forbidden substructures

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 $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

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

Room B232 IBS (기초과학연구원)

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. In this talk we give a connection between Boolean functions and Artificial Neural Network. We describe how to represent

Rose McCarty, Circle graphs are polynomially chi-bounded

Room B232 IBS (기초과학연구원)

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.

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

Room B232 IBS (기초과학연구원)

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 \ for every $x,y,z,w\in S$ with $x<y\leq z<w$. We define strong Sidon sets as follows: For a constant $\alpha$ with $0\leq

Xin Zhang (张欣), On equitable tree-colorings of graphs

Room B232 IBS (기초과학연구원)

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

Lars Jaffke, A complexity dichotomy for critical values of the b-chromatic number of graphs

Room B232 IBS (기초과학연구원)

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. The $b$-chromatic number of a graph $G$, denoted

Jinyoung Park (박진영), The number of maximal independent sets in the Hamming cube

Room B232 IBS (기초과학연구원)

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

IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.