Search
Member View
/ School of Computational Sciences



Publication at kias
NUMBER  
AUTHOR  Kim, Jeong Han 
TITLE  Linear Operators That Preserve the Genus of a Graph 
ARCHIVE  
FILE  
JOURNAL  MATHEMATICS, 2019 
ABSTRACT  A graph has genus k if it can be embedded without edge crossings on a smooth orientable surface of genus k and not on one of genus k1. A mapping of the set of graphs on n vertices to itself is called a linear operator if the image of a union of graphs is the union of their images and if it maps the edgeless graph to the edgeless graph. We investigate linear operators on the set of graphs on n vertices that map graphs of genus k to graphs of genus k and graphs of genus k+1 to graphs of genus k+1. We show that such linear operators are necessarily vertex permutations. Similar results with different restrictions on the genus k preserving operators give the same conclusion. 

Publication at kias
NUMBER  
AUTHOR  Kim, Jeong Han 
TITLE  Some advances on Sidorenkos conjecture 
ARCHIVE  
FILE  
JOURNAL  JOURNAL OF THE LONDON MATHEMATICAL SOCIETYSECOND SERIES, 2018 
ABSTRACT  A bipartite graph H is said to have Sidorenkos property if the probability that the uniform random mapping from V(H) to the vertex set of any graph G is a homomorphism is at least the product over all edges in H of the probability that the edge is mapped to an edge of G. In this paper, we provide three distinct families of bipartite graphs that have Sidorenkos property. First, using branching random walks, we develop an embedding algorithm which allows us to prove that bipartite graphs admitting a certain type of tree decomposition have Sidorenkos property. Second, we use the concept of locally dense graphs to prove that subdivisions of certain graphs, including cliques, have Sidorenkos property. Third, we prove that if H has Sidorenkos property, then the Cartesian product of H with an even cycle also has Sidorenkos property. 

Publication at kias
NUMBER  
AUTHOR  Kim, Jeong Han 
TITLE  On the total variation distance between the binomial random graph and the random intersection graph 
ARCHIVE  
FILE  
JOURNAL  RANDOM STRUCTURES & ALGORITHMS, 2018 
ABSTRACT  When each vertex is assigned a set, the intersection graph generated by the sets is the graph in which two distinct vertices are joined by an edge if and only if their assigned sets have a nonempty intersection. An interval graph is an intersection graph generated by intervals in the real line. A chordal graph can be considered as an intersection graph generated by subtrees of a tree. In 1999, Karonski, Scheinerman, and SingerCohen introduced a random intersection graph by taking randomly assigned sets. The random intersection graph G(n, m; p) has n vertices and sets assigned to the vertices are chosen to be i.i.d. random subsets of a fixed set M of size m where each element of M belongs to each random subset with probability p, independently of all other elements in M. In 2000, Fill, Scheinerman, and SingerCohen showed that the total variation distance between the random graph G(n, m; p) and the ErdosRenyi graph G(n, <(p))over cap> tends to 0 for any 0 <= p = p(n) <= 1 if m = n(alpha), alpha > 6, where fr is chosen so that the expected numbers of edges in the two graphs are the same. In this paper, it is proved that the total variation distance still tends to 0 for any 0 <= p = p(n) <= 1 whenever m >> n(4). 

Publication at kias
NUMBER  
AUTHOR  Kim, Jeong Han 
TITLE  TWO APPROACHES TO SIDORENKOS CONJECTURE 
ARCHIVE  
FILE  
JOURNAL  TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 2016 
ABSTRACT  Sidorenkos conjecture states that for every bipartite graph H on {1,..., k} integral Pi((i, j)is an element of E(H)) h(x(i), y(j))d mu(vertical bar) (V(H)vertical bar) >= (integral h(x, y) d mu(2))(vertical bar) (E(H)vertical bar) holds, where mu is the Lebesgue measure on [0, 1] and h is a bounded, nonnegative, 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 ErdosRenyi random graph with the same expected edge density as G. In this paper, we present two approaches to the conjecture. First, we introduce the notion of treearrangeability, where a bipartite graph H with bipartition A boolean OR B is treearrangeable if neighborhoods of vertices in A have a certain treelike structure. We show that Sidorenkos conjecture holds for all treearrangeable bipartite graphs. In particular, this implies that Sidorenkos conjecture holds if there are two vertices a(1), a(2) in A such that each vertex a is an element of A satisfies N(a) subset of N(a(1)) or N(a) subset of N(a(2)), and also implies a recent result of Conlon, Fox, and Sudakov (2010). Second, if T is a tree and H is a bipartite graph satisfying Sidorenkos conjecture, then it is shown that the Cartesian product T square H of T and H also satisfies Sidorenkos conjecture. This result implies that, for all d >= 2, the ddimensional grid with arbitrary side lengths satisfies Sidorenkos conjecture. 

Publication at kias
NUMBER  
AUTHOR  Kim, Jeong Han 
TITLE  On coupon colorings of graphs 
ARCHIVE  
FILE  
JOURNAL  DISCRETE APPLIED MATHEMATICS, 2015 
ABSTRACT  Let G be a graph with no isolated vertices. A kcoupon coloring of G is an assignment of colors from [k] := {1, 2,..., k} to the vertices of G such that the neighborhood of every vertex of G contains vertices of all colors from [k]. The maximum k for which a kcoupon coloring exists is called the coupon coloring number of G, and is denoted chi(c)(G). In this paper, we prove that every dregular graph G has chi(c)(G) >= (1  0(1))d/log d as d > infinity, and the proportion of dregular graphs G for which chi(c)(G) <= (1 + 0(1))d/log d tends to 1 as vertical bar V(G)vertical bar > infinity. An infective kcoloring of a graph G is an assignment of colors from [k] to the vertices of G such that no two vertices joined by a path of length two in G have the same color. The minimum k for which such a coloring exists is called the infective coloring number of G, denoted chi(i)(G). In this paper, we also discuss injective colorings of Hamming graphs. (C) 2015 Elsevier B.V. All rights reserved. 

Publication at kias
NUMBER  
AUTHOR  Kim, Jeong Han 
TITLE  UNIVERSALITY OF RANDOM GRAPHS FOR GRAPHS OF MAXIMUM DEGREE TWO 
ARCHIVE  
FILE  
JOURNAL  SIAM JOURNAL ON DISCRETE MATHEMATICS, 2014 
ABSTRACT  For a family F of graphs, a graph G is called Funiversal if G contains every graph in F as a subgraph. Let Fn(d) be the family of all graphs on n vertices with maximum degree at most d. Dellamonica, Kohayakawa, Rodl, and Rucinski [An improved upper bound on the density of universal random graphs, Random Structures & Algorithms, doi:10.1002/rsa.20545] showed that, for d = 3, the random graph G(n,p) is Fn(d)universal with high probability provided p >= C(logn/n)(1/d) for a sufficiently large constant C = C(d). In this paper we prove the missing part of the result, that is, the random graph G(n, p) is Fn(2)universal with high probability provided p = C(log n/n)(1/2) for a sufficiently large constant C. 
 Office:1232 / TEL) 8229582551 / FAX) 8229583870
 School of School of Computational Sciences, Korea Institute for Advanced Study
85 Hoegiro, Dongdaemungu, Seoul 02455, Korea