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 …
10 events found.
Discrete Math Seminar
-
-
-
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 …
-
-
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 …
-
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 …