Posts Tagged ‘김재훈’

(Intensive Lecture Series) Jaehoon Kim, A course in graph embedding

Saturday, May 19th, 2018

Intensive Lecture Series

A course in graph embedding
Jaehoon Kim (김재훈)
School of Mathematics, Birmingham University, Birmingham, UK
2018/6/25-29 10:30AM-12PM, 2:30PM-4PM (Room 3434, Bldg. E6-1)

In this lecture, we aim to learn several techniques to find sufficient conditions on a dense graph G to contain a sparse graph H as a subgraph.

Lecture note (PDF file)

Tentative plan for the course (June 25, 26, 27, 28, 29)
Lecture 1 : Basic probabilistic methods
Lecture 2 : Extremal number of graphs
Lecture 3 : Extremal number of even cycles
Lecture 4 : Dependent random choice
Lecture 5 : The regularity lemma and its applications
Lecture 6 : Embedding large graphs
Lecture 7 : The blow-up lemma and its applications I
Lecture 8 : The blow-up lemma and its applications II
Lecture 9 : The absorbing method I
Lecture 10 : The absorbing method II

Jaehoon Kim (김재훈), Spanning trees in a randomly perturbed graphs

Thursday, December 21st, 2017
Spanning trees in a randomly perturbed graphs
Jaehoon Kim (김재훈)
School of Mathematics, Birmingham University, UK
2017/12/28 Thursday 2PM-3PM (Room 3433)
A classical result of Komlós, Sárközy and Szemerédi states that every n-vertex graph with minimum degree at least (1/2 +o(1))n contains every n-vertex tree with maximum degree at most O(n/log n) as a subgraph, and the bounds on the degree conditions are sharp.
On the other hand, Krivelevich, Kwan and Sudakov recently proved that for every n-vertex graph G with minimum degree at least αn for any fixed α>0 and every n-vertex tree T with bounded maximum degree, one can still find a copy of T in G with high probability after adding O(n) randomly-chosen edges to G.
We extend this result to trees with unbounded maximum degree. More precisely, for a given nε ≤ Δ≤ cn/log n and α>0, we determined the precise number (up to a constant factor) of random edges that we need to add to an arbitrary n-vertex graph G with minimum degree αn in order to guarantee with high probability a copy of any fixed T with maximum degree at most Δ. This is joint work with Felix Joos.

Jaehoon Kim (김재훈), Property testing for hypergraphs

Saturday, July 15th, 2017
Property testing for hypergraphs
Jaehoon Kim (김재훈)
School of Mathematics, Birmingham University, UK
2017/7/27 Thu 4PM-5PM
We provide a combinatorial characterization of all testable properties of k-graphs (i.e. k-uniform hypergraphs).
Here, a k-graph property ? is testable if there is a randomized algorithm which quickly distinguishes with high probability between k-graphs that satisfy ? and those that are far from satisfying ?. For the 2-graph case, such a combinatorial characterization was obtained by Alon, Fischer, Newman and Shapira. This is joint work with Felix Joos, Deryk Osthus and Daniela Kühn.

Jaehoon Kim (김재훈), Tree packing conjecture for bounded degree trees

Thursday, December 15th, 2016
Tree packing conjecture for bounded degree trees
Jaehoon Kim (김재훈)
School of Mathematics, Birmingham University, UK
2016/12/28 Wed 4PM-5PM
We prove that if T1,…, Tn is a sequence of bounded degree trees so that Ti has i vertices, then Kn has a decomposition into T1,…, Tn. This shows that the tree packing conjecture of Gyárfás and Lehel from 1976 holds for all bounded degree trees.
We deduce this result from a more general theorem, which yields decompositions of dense quasi-random graphs into suitable families of bounded degree graphs.
In this talk, we discuss the ideas used in the proof.
This is joint work with Felix Joos, Daniela Kühn and Deryk Osthus.

1st Korean Workshop on Graph Theory

Tuesday, July 28th, 2015
1st Korean Workshop on Graph Theory
August 26-28, 2015
KAIST  (E6-1 1501 & 3435)
http://home.kias.re.kr/MKG/h/KWGT2015/
  • Program Book
  • Currently, we are planning to have talks in KOREAN.
  • Students/postdocs may get the support for the accommodation. (Hotel Interciti)
  • Others may contact us if you wish to book a hotel at a pre-negotiated price. Please see the website.
  • We may or may not have contributed talks. If you want, please contact us.
  • PLEASE REGISTER UNTIL AUGUST 16.
Location: KAIST
  • Room 1501 of E6-1 (August 26, 27)
  • Room 3435 of E6-1 (August 28)
Invited Speakers:
Organizers: