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.
Loading view.
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 …
Seog-Jin Kim (김석진), Signed colouring and list colouring of k-chromatic graphs
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 …
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 …
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 …