Tony Huynh, A tight Erdős-Pósa function for planar minors

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

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

Hong Liu, Polynomial Schur’s Theorem

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

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.

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

2019-1 IBS Workshop on Graph Theory

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

Invited Speakers Jeong Han Kim (김정한), KIAS, Seoul Martin Balko, Charles University, Prague Dániel Gerbner, Alfréd Rényi Institute of Mathematics, Budapest Cory T. Palmer, University of Montana, Missoula Boram Park (박보람), Ajou University Dong Yeap Kang (강동엽), KAIST Schedule Feb. 11, 2019, Monday 1:30pm-2:20pm Jeong Han Kim: Entropy and sorting 2:20pm-3:10pm Cory T. Palmer: Generalized Turán

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

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.