기초과학연구원 이산수학그룹
On March 21, 2022, Jaehoon Kim (김재훈) from KAIST gave a talk at the Discrete Math Seminar on the Ramsey number with respect to a cycle graph and an arbitrary graph. The title of his talk was “Ramsey numbers of cycles versus general graphs“.
The Ramsey number
We improve this 40-year-old result of Burr by giving quantitative bounds of the form
This is joint work with John Haslegrave, Joseph Hyde and Hong Liu
On November 9, 2021, Jaehoon Kim (김재훈) from KAIST gave a talk at the Discrete Math Seminar on a 3-dimensional analog of Whitney’s theorem on the uniqueness of planar embeddings of a 3-connected graph. The title of his talk was “2-complexes with unique embeddings in 3-space“.
A well-known theorem of Whitney states that a 3-connected planar graph admits an essentially unique embedding into the 2-sphere. We prove a 3-dimensional analogue: a simply-connected 2-complex every link graph of which is 3-connected admits an essentially unique locally flat embedding into the 3-sphere, if it admits one at all. This can be thought of as a generalisation of the 3-dimensional Schoenflies theorem. This is joint work with Agelos Georgakopoulos.
On July 13, 2021, Jaehoon Kim (김재훈) from KAIST gave a talk at the Discrete Math Seminar on a lower bound on the spectral radius of a
For a graph
A special session “Extremal and Probabilistic Combinatorics” at the 2021 KMS Spring Meeting is organized by Tuan Tran.
URL: https://www.kms.or.kr/meetings/spring2021/
All talks are on April 30.
Graph saturation is one of the oldest areas of investigation in extremal combinatorics. A graph G is called F-saturated if G does not contain a subgraph isomorphic to F, but the addition of any edge creates a copy of F. We resolve one of the most fundamental questions of minimizing the number of cliques of size r in a
The Oberwolfach problem, posed by Ringel in 1967, asks for a decomposition of
A hypergraph is linear if every pair of two distinct edges shares at most one vertex. A longstanding conjecture by Erdős, Faber, and Lovász in 1972, states that the chromatic index of any linear hypergraph on n vertices is at most n.
In this talk, I will present the ideas to prove the conjecture for all large n. This is joint work with Tom Kelly, Daniela Kühn, Abhishek Methuku, and Deryk Osthus.
Majority dynamics on a graph G is a deterministic process such that every vertex updates its {-1,1}-assignment according to the majority assignment on its neighbor simultaneously at each step. Benjamini, Chan, O’Donnell, Tamuz and Tan conjectured that, in the Erdős-Rényi random graph G(n,p), the random initial {-1,1}-assignment converges to the unanimity with high probability whenever p>> 1/n.
This conjecture was firstly confirmed for
Joint work with Debsoumya Chakraborti, Jeong Han Kim and Tuan Tran.
I will review the history of sublinear expander and present some recent applications, which lead to resolutions of several long-standing problems in sparse graphs embeddings.
We will talk about a recent result of Jeff Kahn, Bhargav Narayanan, and myself stating that the threshold for the random graph G(n,p) to contain the square of a Hamilton cycle is
On June 23, 2020, Jaehoon Kim (김재훈) from KAIST presented his work with Padraig Condon, Alberto Espuny Diaz, Daniela Kühn and Deryk Osthus on a resilience version of Pósa’s theorem regarding a sufficient condition on the degree sequence for a graph to have a Hamiltonian cycle at the Discrete Math Seminar. The title of his talk is “A resilience version of Pósa’s theorem“.
Pósa’s theorem states that any graph G whose degree sequence
The 2019 Combinatorics Workshop (2019 조합론 학술대회) was held from August 13, 2019 to August 15, 2019 at the SKYPARK Hotel, Songdo, Incheon. There were 16 talks.