Source author record

Younjin Kim

Younjin Kim appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Catalog footprint

What is connected

8works
1topics
4close collaborators

Actions

Connect this record

Log in to claim

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

8 published item(s)

preprint2022arXiv

The number of $k$-dimensional corner-free subsets of grids

A subset $A$ of the $k$-dimensional grid $\{1,2, \cdots, N\}^k$ is called $k$-dimensional corner-free if it does not contain a set of points of the form $\{ a \} \cup \{ a + de_i : 1 \leq i \leq k \}$ for some $a \in \{1,2, \cdots, N\}^k$ and $d > 0$, where $e_1,e_2, \cdots, e_k$ is the standard basis of $\mathbb{R}^k$. We define the maximum size of a $k$-dimensional corner-free subset of $\{1,2, \cdots, N\}^k$ by $c_k(N)$. In this paper, we show that the number of $k$-dimensional corner-free subsets of the $k$-dimensional grid $\{1,2, \cdots, N\}^k$ is at most $2^{O(c_k(N))}$ for infinitely many values of $N$. Our main tool for the proof is a supersaturation result for $k$-dimensional corners in sets of size $Θ(c_k(N))$ and the hypergraph container method.

preprint2014arXiv

Identifying codes and searching with balls in graphs

Given a graph $G$ and a positive integer $R$ we address the following combinatorial search theoretic problem: What is the minimum number of queries of the form "does an unknown vertex $v \in V(G)$ belong to the ball of radius $r$ around $u$?" with $u \in V(G)$ and $r\le R$ that is needed to determine $v$. We consider both the adaptive case when the $j$th query might depend on the answers to the previous queries and the non-adaptive case when all queries must be made at once. We obtain bounds on the minimum number of queries for hypercubes, the Erd\H os-Rényi random graphs and graphs of bounded maximum degree .

preprint2014arXiv

On the Erdos-Ko-Rado Theorem and the Bollobas Theorem for t-intersecting families

A family $\mathcal{F}$ is $t$-$\it{intersecting}$ if any two members have at least $t$ common elements. Erd\H os, Ko, and Rado proved that the maximum size of a $t$-intersecting family of subsets of size $k$ is equal to $ {{n-t} \choose {k-t}}$ if $n\geq n_0(k,t)$. Alon, Aydinian, and Huang considered families generalizing intersecting families, and proved the same bound. In this paper, we give a strengthening of their result by considering families generalizing $t$-intersecting families for all $t \geq 1$. In 2004, Talbot generalized Bollobás's Two Families Theorem to $t$-intersecting families. In this paper, we proved a slight generalization of Talbot's result by using the probabilistic method.

preprint2012arXiv

The number of graphs of given diameter

In this paper it is proved that there are constants 0< c_2< c_1 such that an asymptotic formula can be given for the the number of (labeled) n-vertex graphs of diameter d whenever n tends to infinity and 2 < d < n - c_1 (log n). A typical graph of diameter d consists of a combination of an induced path of length d and a highly connected block of size n-d+3. In the case d > n- c_2(log n) another asymptotic formula is calculated and the typical graph has a completely different snakelike structure.

preprint2011arXiv

Cycle-saturated graphs with minimum number of edges

A graph $G$ is called $H$-saturated if it does not contain any copy of $H$, but for any edge $e$ in the complement of $G$ the graph $G+e$ contains some $H$. The minimum size of an $n$-vertex $H$-saturated graph is denoted by $\sat(n,H)$. We prove $$\sat(n,C_k) = n + n/k + O((n/k^2) + k^2)$$ holds for all $n\geq k\geq 3$, where $C_k$ is a cycle with length $k$. We have a similar result for semi-saturated graphs $$\ssat(n,C_k) = n + n/(2k) + O((n/k^2) + k).$$ We conjecture that our three constructions are optimal.

preprint2010arXiv

Large B_d-free and union-free subfamilies

For a property $Γ$ and a family of sets $\cF$, let $f(\cF,Γ)$ be the size of the largest subfamily of $\cF$ having property $Γ$. For a positive integer $m$, let $f(m,Γ)$ be the minimum of $f(\cF,Γ)$ over all families of size $m$. A family $\cF$ is said to be $B_d$-free if it has no subfamily $\cF'=\{F_I: I \subseteq [d]\}$ of $2^d$ distinct sets such that for every $I,J \subseteq [d]$, both $F_I \cup F_J=F_{I \cup J}$ and $F_I \cap F_J = F_{I \cap J}$ hold. A family $\cF$ is $a$-union free if $F_1\cup ... F_a \neq F_{a+1}$ whenever $F_1,..,F_{a+1}$ are distinct sets in $\FF$. We verify a conjecture of Erd\H os and Shelah that $f(m, B_2\text{\rm -free})=Θ(m^{2/3})$. We also obtain lower and upper bounds for $f(m, B_d\text{\rm -free})$ and $f(m,a\text{\rm -union free})$.