Main Menu
side title
Search
profile
Member View
Kim, Jeong Han
/ School of Computational Sciences
Combinatorics
-
-
-
Linear Operators That Preserve the Genus of a Graph Title : Linear Operators That Preserve the Genus of a Graph Journal : MATHEMATICS, 2019
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 k-1. 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.
-
Some advances on Sidorenkos conjecture Title : Some advances on Sidorenkos conjecture Journal : JOURNAL OF THE LONDON MATHEMATICAL SOCIETY-SECOND SERIES, 2018
Publication at kias NUMBER AUTHOR Kim, Jeong Han TITLE Some advances on Sidorenkos conjecture ARCHIVE FILE JOURNAL JOURNAL OF THE LONDON MATHEMATICAL SOCIETY-SECOND 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.
-
On the total variation distance between the binomial random graph and the random intersection graph Title : On the total variation distance between the binomial random graph and the random intersection graph Journal : RANDOM STRUCTURES & ALGORITHMS, 2018
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 Singer-Cohen 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 Singer-Cohen showed that the total variation distance between the random graph G(n, m; p) and the Erdos-Renyi 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).
-
TWO APPROACHES TO SIDORENKOS CONJECTURE Title : TWO APPROACHES TO SIDORENKOS CONJECTURE Journal : TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 2016
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, 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 paper, we present two approaches to the conjecture. First, we introduce the notion of tree-arrangeability, where a bipartite graph H with bipartition A boolean OR B is tree-arrangeable if neighborhoods of vertices in A have a certain tree-like structure. We show that Sidorenkos conjecture holds for all tree-arrangeable 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 d-dimensional grid with arbitrary side lengths satisfies Sidorenkos conjecture.
-
On coupon colorings of graphs Title : On coupon colorings of graphs Journal : DISCRETE APPLIED MATHEMATICS, 2015
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 k-coupon 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 k-coupon coloring exists is called the coupon coloring number of G, and is denoted chi(c)(G). In this paper, we prove that every d-regular graph G has chi(c)(G) >= (1 - 0(1))d/log d as d -> infinity, and the proportion of d-regular 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 k-coloring 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.
-
UNIVERSALITY OF RANDOM GRAPHS FOR GRAPHS OF MAXIMUM DEGREE TWO Title : UNIVERSALITY OF RANDOM GRAPHS FOR GRAPHS OF MAXIMUM DEGREE TWO Journal : SIAM JOURNAL ON DISCRETE MATHEMATICS, 2014
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 F-universal if G contains every graph in F as a subgraph. Let F-n(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 F-n(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 F-n(2)-universal with high probability provided p = C(log n/n)(1/2) for a sufficiently large constant C.
-
- Office:1232 / TEL) 82-2-958-2551 / FAX) 82-2-958-3870
- School of School of Computational Sciences, Korea Institute for Advanced Study
85 Hoegiro, Dongdaemun-gu, Seoul 02455, Korea
