이준경

Archive of posts with tag '이준경'

  • Joonkyung Lee (이준경), On some properties of graph norms

    IBS/KAIST Joint Discrete Math Seminar

    On some properties of graph norms
    Joonkyung Lee (이준경)
    Department of Mathematics, University of Hamburg, Germany
    2019/10/22 Tue 4:30PM-5:30PM (Room B232, IBS)
    For a graph $H$, its homomorphism density in graphs naturally extends to the space of two-variable symmetric functions $W$ in $L^p$, $p\geq e(H)$, denoted by $t_H(W)$. One may then define corresponding functionals $\|W\|_{H}:=|t_H(W)|^{1/e(H)}$ and $\|W\|_{r(H)}:=t_H(|W|)^{1/e(H)}$ and say that $H$ is (semi-)norming if $\|.\|_{H}$ is a (semi-)norm and that $H$ is weakly norming if $\|.\|_{r(H)}$ is a norm. We obtain some results that contribute to the theory of (weakly) norming graphs. Firstly, we show that ‘twisted’ blow-ups of cycles, which include $K_{5,5}\setminus C_{10}$ and $C_6\square K_2$, are not weakly norming. This answers two questions of Hatami, who asked whether the two graphs are weakly norming. Secondly, we prove that $\|.\|_{r(H)}$ is not uniformly convex nor uniformly smooth, provided that $H$ is weakly norming. This answers another question of Hatami, who estimated the modulus of convexity and smoothness of $\|.\|_{H}$. We also prove that every graph $H$ without isolated vertices is (weakly) norming if and only if each component is an isomorphic copy of a (weakly) norming graph. This strong factorisation result allows us to assume connectivity of $H$ when studying graph norms. Based on joint work with Frederik Garbe, Jan Hladký, and Bjarne Schülke.
    Tags:

  • Joonkyung Lee (이준경), Sidorenko’s conjecture for blow-ups

    IBS/KAIST Joint Discrete Math Seminar

    Sidorenko’s conjecture for blow-ups
    Joonkyung Lee (이준경)
    Universität Hamburg, Hamburg, Germany
    2019/1/3 Thursday 4PM (Room: DIMAG, 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 the same order and edge density. This conjecture has attracted considerable interest over the last decade and is now known to hold for a broad range of bipartite graphs, with the overall trend saying that a graph satisfies the conjecture if it can be built from simple building blocks such as trees in a certain recursive fashion.Our contribution here, which goes beyond this paradigm, is to show that the conjecture holds for any bipartite graph H with bipartition A∪B where the number of vertices in B of degree k satisfies a certain divisibility condition for each k. As a corollary, we have that for every bipartite graph H with bipartition A∪B, there is a positive integer p such that the blow-up HAp formed by taking p vertex-disjoint copies of H and gluing all copies of A along corresponding vertices satisfies the conjecture. Joint work with David Conlon.</p>
    Tags:

  • Joonkyung Lee (이준경), The extremal number of subdivisions
    The extremal number of subdivisions
    Joonkyung Lee (이준경)
    Universität Hamburg, Hamburg, Germany
    2018/9/17 Monday 5PM
    One of the cornerstones of extremal graph theory is a result of Füredi, later reproved and given due prominence by Alon, Krivelevich and Sudakov, saying that if H is a bipartite graph with maximum degree r on one side, then there is a constant C such that every graph with n vertices and C n2 – 1/r edges contains a copy of H. This result is tight up to the constant when H contains a copy of Kr,s with s sufficiently large in terms of r. We conjecture that this is essentially the only situation in which Füredi’s result can be tight and prove this conjecture for r = 2. More precisely, we show that if H is a C4-free bipartite graph with maximum degree 2 on one side, then there are positive constants C and δ such that every graph with n vertices and C n3/2 – δ edges contains a copy of H. This answers a question by Erdős from 1988. The proof relies on a novel variant of the dependent random choice technique which may be of independent interest. This is joint work with David Conlon.
    Tags:

  • Joonkyung Lee (이준경), Counting tree-like graphs in locally dense graphs
    Counting tree-like graphs in locally dense graphs
    Joonkyung Lee (이준경)
    Mathematical Institute, University of Oxford, Oxford, UK
    2018/1/8 Mon 4PM-5PM
    We prove that a class of graphs obtained by gluing complete multipartite graphs in a tree-like way satisfies a conjecture of Kohayakawa, Nagle, Rödl, and Schacht on random-like counts for small graphs in locally dense graphs. This implies an approximate version of the conjecture for graphs with bounded tree-width. We also prove an analogous result for odd cycles instead of complete multipartite graphs.
    The proof uses a general information theoretic method to prove graph homomorphism inequalities for tree-like structured graphs, which may be of independent interest.
    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:

  • Joonkyung Lee, Some Advances in Sidorenko’s Conjecture
    Some Advances in Sidorenko’s Conjecture
    Joonkyung Lee
    University of Oxford, UK
    2014/09/04 *Thursday* 4PM-5PM
    Room 1409
    Sidorenko’s conjecture states that for every bipartite graph H on \{1,\cdots,k\}
    \begin{eqnarray*}
    \int \prod_{(i,j)\in E(H)} h(x_i, y_j) d\mu^{|V(H)|}
    \ge \left( \int h(x,y) \,d\mu^2 \right)^{|E(H)|}
    \end{eqnarray*}
    holds, where \mu is the Lebesgue measure on [0,1] and h is a bounded, non-negative, symmetric, measurable function on [0,1]^2. An equivalent discrete form of the conjecture is that the number of homomorphisms from a bipartite graph H to a graph G is asymptotically at least the expected number of homomorphisms from H to the Erdos-Renyi random graph with the same expected edge density as G. In this talk, we will give an overview on known results and new approaches to attack Sidorenko’s conjecture.
    This is a joint work with Jeong Han Kim and Choongbum Lee.
    Tags:

Monthly Archives