Tony Huynh, A tight Erdős-Pósa function for planar minors
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 …
10 events found.
Events
-
-
Room B109 IBS (기초과학연구원)
-
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 …
-
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 …
-
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 …
-
-
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 …
-
-
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 …
-
-
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, …
-
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 …
-
-
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 …