김재훈

Archive of posts with tag '김재훈'

  • Jaehoon Kim, Rainbow subgraphs in graphs
    Rainbow subgraphs in graphs
    Jaehoon Kim (김재훈)
    Mathematics Institute, University of Warwick, UK
    2018/10/15 2:30PM
    We say a subgraph H of an edge-colored graph is rainbow if all edges in H has distinct colors. The concept of rainbow subgraphs generalizes the concept of transversals in latin squares.
    In this talk, we discuss how these concepts are related and we introduce a result regarding approximate decompositions of graphs into rainbow subgraphs. This has implications on transversals in latin square. It is based on a joint work with Kühn, Kupavskii and Osthus.
    Tags:

  • Jaehoon Kim, Introduction to Graph Decomposition
    Introduction to Graph Decomposition
    Jaehoon Kim (김재훈)
    Mathematics Institute, University of Warwick, UK
    2018/10/15 5PM
    Graphs are mathematical structures used to model pairwise relations between objects.
    Graph decomposition problems ask to partition the edges of large/dense graphs into small/sparse graphs.
    In this talk, we introduce several famous graph decomposition problems, related puzzles and known results on the problems.
    Tags:

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

    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

    Tags:

  • Jaehoon Kim (김재훈), Spanning trees in a randomly perturbed graphs
    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.
    Tags:

  • Jaehoon Kim (김재훈), Property testing for hypergraphs
    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.
    Tags:

  • Jaehoon Kim (김재훈), Tree packing conjecture for bounded degree trees
    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.
    Tags:

  • 1st Korean Workshop on Graph Theory
    1st Korean Workshop on Graph Theory
    August 26-28, 2015
    KAIST  (E6-1 1501 & 3435)
    • 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:
    Tags:

  • 2014 KAIST CMC Discrete Math Workshop
    2014 KAIST CMC Discrete Math Workshop
    December 10–12, 2014
    자연과학동(E6-1), KAIST

    Preregistration in kcw2014.eventbrite.com deadline: Dec. 5 (Friday)

    ABSTRACTS
    Program (Dec.10 Wed-Room 1409)
    • 1:30-2:00 Registration
    • 2:00-2:30 Young Soo Kwon (권영수), Yeungnam University: A variation of list coloring and its properties
    • 2:40-3:10 Mitsugu Hirasaka, Pusan National University: Small topics on association schemes
    • 3:10-3:40 Coffee Break
    • 3:40-4:10 Younjin Kim (김연진),  KAIST: On Extremal Combinatorial Problems of Noga Alon
    • 4:20-4:50 Jang Soo Kim (김장수),  Sungkyunkwan University: A new q-Selberg integral, Schur functions, and Young books
    • 5:00-6:00 Discussion
    • 6:00- Dinner
    Program (Dec.11 Thurs-Room 1501 & 3435)
    Program (Dec.12 Fri-Room 1501)
    Tags:

  • Jaehoon Kim, On r-dynamic coloring of graphs
    On r-dynamic coloring of graphs
    Jaehoon Kim
    KAIST/Univ. of Birmingham, UK
    2014/06/09 Monday 4PM-5PM
    Room 1409
    An r-dynamic proper k-coloring of a graph G is a proper k-coloring of G such that every vertex in V(G) has neighbors in at least \min\{d(v),r\} different color classes. The r-dynamic chromatic number of a graph G, written \chi_r(G), is the least k such that G has such a coloring. By a greedy coloring algorithm, \chi_r(G)\le r\Delta(G)+1 and the equality holds if and only if G is r-regular with diameter 2 and girth 5. We improve the bound to \chi_r(G)\le \Delta(G)+2r when \delta(G)\ge 2r\ln n. In terms of the chromatic number, we prove \chi_r(G)\le r\chi(G) when G is k-regular with k \ge (3+o(1))r\ln r and show that \chi_r(G) may exceed r^{1.377}\chi(G) when k=r. We prove \chi_2(G)\leq \chi(G)+2 when G has diameter 2, with equality only for complete bipartite graphs and the 5-cycle. Also, \chi_2(G)\le 3\chi(G) when G has diameter 3, which is sharp. This is joint work with Sogol Jahanbekam, Suil O, and Douglas B. West.
    Tags:

  • Jaehoon Kim, (0,1)-improper coloring of sparse triangle-free graph
    (0,1)-improper coloring of sparse triangle-free graph
    Jaehoon Kim
    Department of Mathematics
    University of Illinois at Urbana Champagne
    2013/06/04 Tuesday 4PM-5PM
    ROOM 3433
    A graph G is (0,1)-colorable if V(G) can be partitioned into two sets V and V1 so that G[V] is an independent set and G[V1] has maximum degree at most 1. The problem of verifying whether a graph is (0,1)-colorable is NP-complete even in the class of planar graphs of girth 9.</p>

    Maximum average degree, Mad(G), is a graph parameter measuring how sparse the graph G is. Borodin and Kostochka showed that every graph G with Mad(G) ≤ 12/5 is (0,1)-colorable, thus every planar graph with girth at least 12 also is (0,1)-colorable.

    The aim of this talk is to prove that every triangle-free graph G with Mad(G) ≤ 22/9 is (0,1)-colorable. We prove the slightly stronger statement that every triangle-free graph G with |E(H)| < (11|V(H)|+5)/9 for every subgraph H is (0,1)-colorable and show that there are infinitely many non (0,1)-colorable graphs G with |E(G)|= (11|V(G)|+5)/9.

    This is joint work with A. V. Kostochka and Xuding Zhu.

    Tags:

  • Jaehoon Kim (김재훈), Maximum hypergraphs without regular subgraphs
    Maximum hypergraphs without regular subgraphs
    Jaehoon Kim (김재훈)</a>
    Department of Mathematics, University of Illinois at Urbana-Champaign, Urbana, Illinois, USA
    2011/06/03 Fri 4PM-5PM (Room 3433, Bldg. E6-1)
    We show that an n-vertex hypergraph with no r-regular subgraph has at most 2n-1+r-2 edges. We conjecture that if n>r, then every n-vertex hypergraph with no r-regular subgraph having the maximum number of edges contains a full star, meaning 2n-1 distinct edges containing a single vertex. We prove this conjecture for n≥425. This is joint work with Alexandr V. Kostochka.
    Tags:

Monthly Archives