Almost Tight Upper Bound for Finding Fourier Coefficients of Bounded Pseudo-Boolean Functions (2009)
Sung-soon Choi, Kyomin Jung, Jeong Han Kim
1
Anatomy of a young giant component in the random graph (2009)
Ding, Jian, Kim, Jeong Han, Lubetzky, Eyal, Peres, Yuval
We provide a complete description of the giant component of the Erd\H{o}s-R\'enyi random graph $G(n,p)$ as soon as it emerges from the scaling window, i.e., for $p = (1+\epsilon)/n$ where $\epsilon^3...
Diameters in supercritical random graphs via first passage percolation (2009)
Ding, Jian, Kim, Jeong Han, Lubetzky, Eyal, Peres, Yuval
We study the diameter of $C_1$, the largest component of the Erd\H{o}s-R\'enyi random graph $\cG(n,p)$ emerging from the critical window, i.e., for $p = \frac{1+\epsilon}n$ where $\epsilon^3 n \to...
Finding cores of random 2-SAT formulae via Poisson cloning (2008)
For the random 2-SAT formula $F(n,p)$, let $F_C (n,p)$ be the formula left after the pure literal algorithm applied to $F(n,p)$ stops. Using the recently developed Poisson cloning model together with...
Poisson Cloning Model for Random Graphs (2008)
In the random graph $G(n,p)$ with $pn$ bounded, the degrees of the vertices are almost i.i.d Poisson random variables with mean $\gl:= p(n-1)$. Motivated by this fact, we introduce the Poisson...
Tight Bounds For Random MAX 2-SAT (2008)
Mohammadtaghi Hajiaghayi, Jeong Han Kim
For a conjunctive normal form formula F with n variables and m = cn 2-variable clauses (c is called the density), denote by max F is the maximum number of clauses satisfiable by a single assignment...
For a simple d-regular graph G, let M be chosen uniformly at random from the set of all matchings of G, and for x ∈ V (G) let p(x) be the probability that M does not cover x. We show that for large...
CONFIRMING KLEITMAN–WINSTON CONJECTURE ON THE LARGEST COEFFICIENT IN A q-CATALAN NUMBER. (2008)
Abstract. In 1983 Kleitman and Winston conjectured that the largest coefficient in an n-th q-Catalan number is of order O(4 n /n 3/2). Assuming its truth, they proved that the total number of...
Jeong Han Kim, Redmond Wa, Van H. Vu
�������� � Suppose t1,..., tn are independent random variables which take value either 0 or 1, and Y is a multi-variable polynomial in ti’s with positive coefficients. We give a...
Catherine Greenhill, Jeong Han Kim, Svante Janson, Nicholas C. Wormald
The space of permutation pseudographs is a probabilistic model of 2-regular pseudographs on n vertices, where a pseudograph is produced by choosing a permutation σ of {1, 2,..., n} uniformly at...
On tail distribution of interpost distance (2008)
Abstract. A partial order on Z obtained by taking the transitive closure of a random relation {i < j and there is an edge ij} is studied. Randomness stems from postulating that an edge ij exists...
Finding cores of random 2-SAT formulae via Poisson cloning (2008)
Abstract. For the random 2-SAT formula F (n, p), let FC(n, p) be the formula left after the pure literal algorithm applied to F (n, p) stops. Using the recently developed Poisson cloning model...
Permutation pseudographs and contiguity (2008)
Catherine Greenhill, Jeong Han Kim, Svante Janson, Nicholas C. Wormald
The space of permutation pseudographs is a probabilistic model of 2-regular pseudographs on n vertices, where a pseudograph is produced by choosing a permutation σ of {1, 2,..., n} uniformly at...
Kim, Jeong Han, Montenegro, Ravi, Peres, Yuval, Tetali, Prasad
We show a Birthday Paradox for self-intersections of Markov chains with uniform stationary distribution. As an application, we analyze Pollard's Rho algorithm for finding the discrete logarithm in a...
Christian Borgs, Jennifer T. Chayes, Jeong Han Kim, Prasad Tetali, Eric Vigoda, Van Ha Vu
We study two widely used algorithms, Glauber dynamics and the Swendsen-Wang algorithm, on rectangular subsets of the hypercubic lattice Z d. We prove that under certain circumstances, the mixing time...
Limits on the Efficiency of One-Way Permutation-Based Hash Functions (2007)
Jeong Han Kim, Jeong Han Kim, Daniel R. Simon, Daniel R. Simon, Prasad Tetali, ...
Naor and Yung show that a one-bit-compressing universal oneway hash function (UOWHF) can be constructed based on a one-way permutation. This construction can be iterated to build a UOWHF which...
On tail distribution of interpost distance (2007)
Redmond Wa, Jeong Han Kim, Jeong Han Kim, Boris Pittel, Boris Pittel
Abstract. A partial order on Z obtained by taking the transitive closure of a random relation {i and there is an edge ij} is studied. Randomness stems from postulating that an edge ij exists with...
Dimitris Achlioptas, Jeong Han Kim, Michael Krivelevich, Prasad Tetali
A 2-coloring of a hypergraph is a mapping from its vertex set to a set of two colors such that no edge is monochromatic. Let H = H(k; n; p) be a random k-uniform hypergraph on a vertex set V of...
Permutation Pseudographs and Contiguity (2007)
Catherine Greenhill, Svante Janson, Jeong Han Kim, Nicholas C. Wormald
The space of permutation pseudographs is a probabilistic model of 2-regular pseudographs on n vertices, where a pseudograph is produced by choosing a permutation of f1; 2; : : : ; ng uniformly at...
We show that the hereditary discrepancy of a hypergraph F on n points increases by a factor of at most O(log n) when one adds a new edge to F. Let X be a set of n points. We say that a hypergraph F...
Discrepancy after Adding a Single Set (2007)
Jeong Han Kim, Jiri Matousek, Van H. Vu
We show that the hereditary discrepancy of a hypergraph F on n points increases by a factor of at most O(log n) when one adds a new edge to F .
A Sequential Algorithm for Generating Random Graphs (2007)
Bayati, Mohsen, Kim, Jeong Han, Saberi, Amin
We present the fastest fully polynomial randomized approximation scheme (FPRAS) for counting and randomly generating simple graphs with a given degree sequence in a certain range. For degree sequence...
Near Optimal Bounds for Collision in Pollard Rho for Discrete Log (2007)
We analyze a fairly standard idealization of Pollard’s Rho algorithm for finding the discrete logarithm in a cyclic group G. It is found that, with high probability, a collision occurs in O ( �...
Near Optimal Bounds for Collision in Pollard Rho for Discrete Log (2006)
Kim, Jeong Han, Montenegro, Ravi, Tetali, Prasad
We analyze a fairly standard idealization of Pollard's Rho algorithm for finding the discrete logarithm in a cyclic group G. It is found that, with high probability, a collision occurs in...
A phase transition for avoiding a giant component (2006)
Let c be a constant and (e1, f1), (e2, f2),..., (ecn, fcn) be a sequence of ordered pairs of edges from the complete graph Kn chosen uniformly and independently at random. We prove that there exists...
A phase transition for avoiding a giant component (2006)
\Gamma n1\Gamma ffl \Delta vertices, where ffl is a constant that depends on c2 \Gamma c.
Witnesses for non-satisfiability of dense random 3CNF formulas (2006)
Uriel Feige, Jeong Han Kim, Eran Ofek
We consider random 3CNF formulas with n variables and m clauses. It is well known that when m> cn (for a sufficiently large constant c), most formulas are not satisfiable. However, it is not known...
Phase transition in a random NK landscape model (2005)
Sung-soon Choi, Kyomin Jung, Jeong Han Kim
An analysis for the phase transition in a random NK landscape model, NK(n, k, z), is given. This model is motivated from population genetics and the solubility problem for the model is equivalent to...
Phase transition in a random NK landscape model (2005)
Sung-soon Choi, Kyomin Jung, Jeong Han Kim
An analysis for the phase transition in a random NK landscape model, NK(n, k, z), is given. This model is motivated from population genetics and the solubility problem for the model is equivalent to...
Kim, Kyoung Ju, Huh, Seung Jae, Yang, Jung-Hyun, Park, Won, Nam, Seok Jin, Kim, Jeong Han, ...
Background: The purpose of this study was to analyze the prognostic factors affecting local control and survival rates for patients with early breast cancer who received breast conserving treatment...
How Complex are Random Graphs in First Order Logic? (2004)
Kim, Jeong Han, Pikhurko, Oleg, Spencer, Joel, Verbitsky, Oleg
It is not hard to write a first order formula which is true for a given graph G but is false for any graph not isomorphic to G. The smallest number $(G) of nested quantifiers in a such formula can...
Poisson cloning model for random graphs (2004)
Abstract. In the random graph G(n, p) with pn bounded, the degrees of the vertices are almost i.i.d Poisson random variables with mean λ: = p(n − 1). Motivated by this fact, we introduce the...
Perfect matchings in random uniform hypergraphs (2003)
Abstract. In the random k-uniform hypergraph Hk(n, p) on a vertex set V of size n, each subset of size k of V independently belongs to it with probability p. Motivated by a theorem of Erdős and...
YOON, CHUNG SIK, PAIK, NAM WON, KIM, JEONG HAN
This study was performed to investigate the fume generation rates (FGRs) and the concentrations of total chromium and hexavalent chromium when stainless steel was welded using flux-cored arc welding...
Two-coloring random hypergraphs (2002)
Dimitris Achlioptas, Jeong Han Kim, Michael Krivelevich
A 2-coloring of a hypergraph is a mapping from its vertex set to a set of two colors such that no edge is monochromatic. Let H = H(k;n; p) be a random k-uniform hypergraph on a vertex set V of...
On the asymmetry of random regular graphs and random graphs (2002)
Jeong Han Kim, Benny Sudakov, Van H. Vu
This paper studies the symmetry of random regular graphs and random graphs. Our main result shows that for all 3 d n 4 the random d-regular graph on n vertices almost surely has no non-trivial...
Two-coloring Random Hypergraphs (2002)
Dimitris Achlioptas, Jeong Han Kim, Michael Krivelevich, Prasad Tetali
A 2-coloring of a hypergraph is a mapping from its vertex set to a set of two colors such that no edge is monochromatic. Let H = H(k;n; p) be a random k-uniform hypergraph on a vertex set V of...
Hamiltonian Decompositions of Random Bipartite Regular Graphs (2002)
Catherine Greenhill, Nicholas C. Wormald, Jeong Han Kim
We prove a complete hamiltonian decomposition theorem for random bipartite regular graphs, thereby verifying a conjecture of Robinson and Wormald. The main step is to prove contiguity (a kind of...
On the asymmetry of random regular graphs and random graphs. Random Structures & Algorithms (2002)
Jeong Han Kim, Benny Sudakov, Van H. Vu
ABSTRACT: This paper studies the symmetry of random regular graphs and random graphs. Our main result shows that for all 3�d�n�4the random d-regular graph on nvertices almost...
Two-coloring random hypergraphs (2002)
Dimitris Achlioptas, Jeong Han Kim, Michael Krivelevich, Prasad Tetali
ABSTRACT: A 2-coloring of a hypergraph is a mapping from its vertex set to a set of two colors such that no edge is monochromatic. Let H = H�k � n � p � be a random k-uniform hypergraph on a...
Jeong Han Kim, Nicholas C. Wormald
Select four perfect matchings of 2n vertices, independently at random. We nd the asymptotic probability that each of the rst and second matchings forms a Hamilton cycle with each of the third and...
On the Asymmetry of Random Regular Graphs and Random Graphs (2001)
Jeong Han Kim, Benny Sudakov, Kim Benny, Sudakov Van, Van H. Vu
This paper studies the symmetry of random regular graphs and random graphs. Our main result shows that for all 3 4 the random d-regular graph on n vertices almost surely has no non-trivial...
Jeong Han Kim, Nicholas C. Wormald
Select four perfect matchings of 2n vertices, independently at random. We find the asymptotic probability that each of the first and second matchings forms a Hamilton cycle with each of the third and...
Discrepancy After Adding a Single Set (2001)
We show that the hereditary discrepancy of a hypergraph on n points increases by a factor of at most O(log n) when one adds a new edge to .
The Scaling Window of the 2-SAT Transition (1999)
Bollobás, Béla, Borgs, Christian, Chayes, Jennifer T., Kim, Jeong Han, Wilson, David B.
We consider the random 2-satisfiability problem, in which each instance is a formula that is the conjunction of m clauses of the form (x or y), chosen uniformly at random from among all 2-clauses on...
Confirming Kleitman-Winston Conjecture ON THE LARGEST COEFFICIENT IN A q-CATALAN NUMBER (1999)
Redmond Wa, Jeong Han Kim, Jeong Han Kim, Boris Pittel, Boris Pittel
In 1983 Kleitman and Winston conjectured that the largest coefficient in an n-th q-Catalan number is of order O(4 n /n 3/2 ) . Assuming its truth, they proved that the total number of n-tournament...
The Scaling Window Of The 2-Sat Transition (1999)
Bela Bollobas, Christian Borgs, Jennifer T. Chayes, Jeong Han Kim, David B. Wilson
. We consider the random 2-satisfiability problem, in which each instance is a formula that is the conjunction of m clauses of the form x # y, chosen uniformly at random from among all 2-clauses on n...
Economical Covers With Geometric Applications (1999)
Noga Alon, Bela Bollobas, Jeong Han Kim, Kim Van, Van Ha Vu
A cover of a hypergraph is a collection of edges whose union contains all vertices. Let H = (V, E) be a k-uniform, D-regular hypergraph on n vertices, in which no two vertices are contained in more...
Limits on the Efficiency of One-Way Permutation-Based Hash Functions (1999)
Jeong Han Kim, Daniel R. Simon, Prasad Tetali
Naor and Yung ([NY89]) show that a onebit -compressing universal one-way hash function (UOWHF) can be constructed based on a one-way permutation. This construction can be iterated to build a UOWHF...
The scaling window of the 2-SAT transition (1999)
Béla Bollobás, Christian Borgs, Jennifer T. Chayes, Jeong Han Kim, David B. Wilson
Abstract. We consider the random 2-satisfiability problem, in which each instance is a formula that is the conjunction of m clauses of the form x ∨ y, chosen uniformly at random from among all...
The scaling window of the 2-sat transition (1999)
Béla Bollobás, Christian Borgs, Jennifer T. Chayes, Jeong Han Kim, David B. Wilson
Abstract. We consider the random 2-satisfiability problem, in which each instance is a formula that is the conjunction of m clauses of the form x ∨ y, chosen uniformly at random from among all...
Edge Coloring, Polyhedra and Probability (1998)
Ljubomir Perkovic, Alan Frieze, Avrim Blum, Jeong Han Kim
Submitted inpartial ful llment of the requirements
On increasing subsequences of random permutations (1996)
Let Ln be the length of a longest increasing subsequence in a random permutation of {1,..., n}. It is known that the expected value of Ln is asymptotically equal to 2 √ n as n gets large. This note...
The Ramsey number R(3, t) has order of magnitude t²/log t (1995)
The Ramsey number R(s; t) for positive integers s and t is the minimum integer n for which every red-blue coloring of the edges of a complete n-vertex graph induces either a red complete graph of...
On Brooks' theorem for sparse graphs (1995)
Let G be a graph with maximum degree ∆(G). In this paper we prove that if the girth g(G) of G is greater than 4 then its chromatic number, χ(G), satisfies χ(G) ≤ (1 + o(1)) ∆(G) log ∆(G)...
The Ramsey number R(3, t) has order of magnitude t²/log t (1995)
The Ramsey number R(s, t) for positive integers s and t is the minimum integer n for which every red-blue coloring of the edges of a complete n-vertex graph induces either a red complete graph of...
Kim, Jeong Han., Frost, Robert H.
Typescript (photocopy).
Non-combinatorial approaches to two combinatorial problems / (1993)
"Graduate Program in Mathematics."
Author's name in manuscript on signatory page: Kim Jeong Han.
Tail bound for the minimal spanning tree of a complete graph
Suppose each edge of the complete graph Kn is assigned a random weight chosen independently and uniformly from the unit interval [0,1]. A minimal spanning tree is a spanning tree of Kn with the...
Choi, Jaewon, Hwang, Yu Kyeong, Choi, Young Jin, Yoo, Ki Eun, Kim, Jeong Han, Nam, Seok Jin, ...
Neuronal apoptosis inhibitory protein (NAIP) is a recently identified inhibitor of apoptosis protein. However, the clinical relevance of NAIP expression is not completely understood. In an attempt to...