Jaehoon Kim (김재훈), A resilience version of Pósa’s theorem
Pósa's theorem states that any graph G whose degree sequence $d_1\leq \dots \leq d_n$ satisfies $d_i \geq i+1$ for all $i< n/2$ has a Hamilton cycle. This degree condition is …
10 events found.
Discrete Math Seminar
Events
-
-
Room B232 IBS (기초과학연구원)
-
Dennis Wong, Generating Gray codes and universal cycles for weak orders
Room B232 IBS (기초과학연구원)A weak order is a way to rank n objects where ties are allowed. Weak orders have applications in diverse areas such as linguistics, designing combination locks, and even in …
-
-
Seog-Jin Kim (김석진), Online DP-coloring of graphs
Room B232 IBS (기초과학연구원)Online list coloring and DP-coloring are generalizations of list coloring that attracted considerable attention recently. Each of the paint number, $\chi_P(G)$, (the minimum number of colors needed for an online …
-
Casey Tompkins, Inverse Turán Problems
Room B232 IBS (기초과학연구원)For given graphs $G$ and $F$, the Turán number $ex(G,F)$ is defined to be the maximum number of edges in an $F$-free subgraph of $G$. Briggs and Cox introduced a …
-
Ilkyoo Choi (최일규), Flexibility of Planar Graphs
Room B232 IBS (기초과학연구원)Oftentimes in chromatic graph theory, precoloring techniques are utilized in order to obtain the desired coloring result. For example, Thomassen's proof for 5-choosability of planar graphs actually shows that two adjacent …
-
Eun Jung Kim (김은정), Solving hard cut problems via flow-augmentation
Room B232 IBS (기초과학연구원)We present a new technique for designing fixed-parameter algorithms for graph cut problems in undirected graphs, which we call flow augmentation. Our technique is applicable to problems that can be …
-
-
June Huh (허준이), Kazhdan-Lusztig polynomials of graphs and matroids
Room B232 IBS (기초과학연구원)I will introduce Kazhdan-Lusztig polynomials of matroids and survey combinatorial and geometric theories built around them. The focus will be on the conjecture of Gedeon, Proudfoot, and Young that all …
-
Yunbum Kook (국윤범), Vertex Sparsification for Edge Connectivity
Room B232 IBS (기초과학연구원)Graph compression or sparsification is a basic information-theoretic and computational question. A major open problem in this research area is whether $(1+\epsilon)$-approximate cut-preserving vertex sparsifiers with size close to the number …
-
Tuan Tran, Anti-concentration phenomena
Room B232 IBS (기초과학연구원)Let $X$ be a real random variable; a typical anti-concentration inequality asserts that (under certain assumptions) if an interval $I$ has small length, then $\mathbb{P}(X\in I)$ is small, regardless the …
-
Ben Lund, Point-plane incidence bounds
Room B232 IBS (기초과학연구원)In the early 1980s, Beck proved that, if P is a set of n points in the real plane, and no more than g points of P lie on any …