Source author record

Sang June Lee

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.NT

Catalog footprint

Research overview

7works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

The independence number of non-uniform uncrowded hypergraphs and an anti-Ramsey type result

We prove the following: Fix an integer $k\geq 2$ , and let $T$ be a real number with $T\geq 1.5$ . Let $\cH=(V,\cE_2\cup \cE_3\cup\dots\cup\cE_k)$ be a non-uniform hypergraph with the vertex set $V$ and the set $\cE_i$ of edges of size $i=2,\ldots , k$ . Suppose that $\cH$ has no $2$ -cycles (regardless of sizes of edges), and neither contains $3$ -cycles nor $4$ -cycles consisting of $2$ -element edges. If the average degrees $t_i^{i-1} := i |\cE_i|/ |V|$ satisfy that $t_i^{i-1} \leq T^{i-1} (\ln T)^{\frac{k-i}{k-1}}$ for $i= 2, \dots , k$ , then there exists a constant $C_k > 0$ , depending only on $k$ , such that $α(\cH)\geq C_k \frac{|V|}{T} (\ln T)^{\frac{1}{k-1}}$, where $α(\cH)$ denotes the independence number of $\cH$. This extends results of Ajtai, Komlós, Pintz, Spencer and Szemerédi and Duke, Rödl and the second author for uniform hypergraphs. As an application, we consider an anti-Ramsey type problem on non-uniform hypergraphs. Let $\cH=\cH(n;2,\ldots,\ell)$ be the hypergraph on the $n$ -vertex set $V$ in which, for $s=2,\ldots,\ell$ , each $s$ -subset of $V$ is a hyperedge of $\cH$. Let $Δ$ be an edge-coloring of $\cH$ satisfying the following: (a) two hyperedges sharing a vertex have different colors; (b) two hyperedges with distinct size have different colors; (c) a color used for a hyperedge of size $s$ appears at most $u_s$ times. For such a coloring $Δ$ , let $f_Δ(n;u_2,\ldots,u_{\ell})$ be the maximum size of a subset $U$ of $V$ such that each hyperedge of $\cH[U]$ has a distinct color, and let $f(n;u_2,\ldots,u_{\ell}):=\min_Δ f_Δ(n;u_2,\ldots,u_{\ell}).$ We determine $f(n;u_2,\ldots,u_{\ell})$ up to a multiplicative logarithm factor.

preprint2015arXiv

Dynamic coloring of graphs having no $K_5$ minor

We prove that every simple connected graph with no $K_5$ minor admits a proper 4-coloring such that the neighborhood of each vertex $v$ having more than one neighbor is not monochromatic, unless the graph is isomorphic to the cycle of length 5. This generalizes the result by S.-J. Kim, S. J. Lee, and W.-J. Park on planar graphs.

preprint2015arXiv

Towards extending the Ahlswede-Khachatrian theorem to cross t-intersecting families

Ahlswede and Khachatrian's diametric theorem is a weighted version of their complete intersection theorem, itself an extension of the $t$ -intersecting Erdős-Ko-Rado theorem. Their intersection theorem says that the maximum size of a family of subsets of $[n] = \{1, \dots, n\}$ , every pair of which intersects in at least $t$ elements, is the size of certain trivially intersecting families proposed by Frankl. We address a cross intersecting version of their diametric theorem. Two families $\mathcal{A}$ and $\mathcal{B}$ of subsets of $[n]$ are {\em cross $t$ -intersecting} if for every $A \in \mathcal{A}$ and $B \in \mathcal{B}$ , $A$ and $B$ intersect in at least $t$ elements. The $p$ -weight of a $k$ element subset $A$ of $[n]$ is $p^{k}(1-p)^{n-k}$ , and the weight of a family $\mathcal{A}$ is the sum of the weights of its sets. The weight of a pair of families is the product of the weights of the families. The maximum $p$ -weight of a $t$ -intersecting family depends on the value of $p$ . Ahlswede and Khachatrian showed that for $p$ in the range $[\frac{r}{t + 2r - 1}, \frac{r+1}{t + 2r + 1}]$ , the maximum $p$ -weight of a $t$ -intersecting family is that of the family $\mathcal{F}^t_r$ consisting of all subsets of $[n]$ containing at least $t+r$ elements of the set $[t+2r]$ . In a previous paper we showed a cross $t$ -intersecting version of this for large $t$ in the case that $r = 0$ . In this paper, we do the same in the case that $r = 1$ . We show that for $p$ in the range $[\frac{1}{t + 1}, \frac{2}{t + 3}]$ the maximum $p$ -weight of a cross $t$ -intersecting pair of families, for $t \geq 200$ , is achieved when both families are $\mathcal{F}^t_1$ . Further, we show that except at the endpoints of this range, this is, up to isomorphism, the only pair of $t$ -intersecting families achieving this weight.

preprint2014arXiv

An Erd\H os--Ko--Rado theorem for cross $t$ -intersecting families

Two families $\mathcal{A}$ and $\mathcal{B}$ , of $k$ -subsets of an $n$ -set, are {\em cross $t$ -intersecting} if for every choice of subsets $A \in \mathcal{A}$ and $B \in \mathcal{B}$ we have $|A \cap B| \geq t$ . We address the following conjectured cross $t$ -intersecting version of the Erd\H os--Ko--Rado Theorem: For all $n \geq (t+1)(k-t+1)$ the maximum value of $|\mathcal{A}||\mathcal{B}|$ for two cross $t$ -intersecting families $\mathcal{A}, \mathcal{B} \subset\binom{[n]}{k}$ is $\binom{n-t}{k-t}^2$ . We verify this for all $t \geq 14$ except finitely many $n$ and $k$ for each fixed $t$ . Further, we prove uniqueness and stability results in these cases, showing, for instance, that the families reaching this bound are unique up to isomorphism. We also consider a {\em $p$ -weight} version of the problem, which comes from the product measure on the power set of an $n$ -set.

preprint2014arXiv

On Sidon sets in a random set of vectors

For positive integers $d$ and $n$ , let $[n]^d$ be the set of all vectors $(a_1,a_2,\dots, a_d)$ , where $a_i$ is an integer with $0\leq a_i\leq n-1$ . A subset $S$ of $[n]^d$ is called a \emph{Sidon set} if all sums of two (not necessarily distinct) vectors in $S$ are distinct. In this paper, we estimate two numbers related to the maximum size of Sidon sets in $[n]^d$ . First, let $\mathcal{Z}_{n,d}$ be the number of all Sidon sets in $[n]^d$ . We show that $\log (\mathcal{Z}_{n,d})=Θ(n^{d/2})$ , where the constants of $Θ$ depend only on $d$ . Next, we estimate the maximum size of Sidon sets contained in a random set $[n]^d_p$ , where $[n]^d_p$ denotes a random set obtained from $[n]^d$ by choosing each element independently with probability $p$ .

preprint2013arXiv

Universality of random graphs for graphs of maximum degree two

For a family $\mathcal{F}$ of graphs, a graph $G$ is called \emph{ $\mathcal{F}$ -universal} if $G$ contains every graph in $\mathcal{F}$ as a subgraph. Let $\mathcal{F}_n(d)$ be the family of all graphs on $n$ vertices with maximum degree at most $d$ . Dellamonica, Kohayakawa, Rödl and Ruciński showed that, for $d\geq 3$ , the random graph $G(n,p)$ is $\mathcal{F}_n(d)$ -universal with high probability provided $p\geq C\big(\frac{\log n}{n}\big)^{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 $\mathcal{F}_n(2)$ -universal with high probability provided $p\geq C\big(\frac{\log n}{n}\big)^{1/2}$ for a sufficiently large constant $C$ .

preprint2012arXiv

On constant-multiple-free sets contained in a random set of integers

For a rational number $r>1$ , a set $A$ of positive integers is called an $r$ -multiple-free set if $A$ does not contain any solution of the equation $rx = y$ . The extremal problem on estimating the maximum possible size of $r$ -multiple-free sets contained in $[n]:={1,2,...,n}$ has been studied for its own interest in combinatorial number theory and application to coding theory. Let $a$ , $b$ be positive integers such that $a<b$ and the greatest common divisor of $a$ and $b$ is 1. Wakeham and Wood showed that the maximum size of $(b/a)$ -multiple-free sets contained in $[n]$ is $\frac{b}{b+1}n+O(\log n)$ . In this paper we generalize this result as follows. For a real number $p\in (0,1)$ , let $[n]_p$ be a set of integers obtained by choosing each element $i\in [n]$ randomly and independently with probability $p$ . We show that the maximum possible size of $(b/a)$ -multiple-free sets contained in $[n]_p$ is $\frac{b}{b+p}pn+O(\sqrt{pn}\log n \log \log n)$ with probability that goes to 1 as $n\to \infty$ .

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.

Sang June Lee

Research overview

Is this your work?

7 publications

The independence number of non-uniform uncrowded hypergraphs and an anti-Ramsey type result

Dynamic coloring of graphs having no $K_5$ minor

Towards extending the Ahlswede-Khachatrian theorem to cross t-intersecting families

An Erd\H os--Ko--Rado theorem for cross $t$ -intersecting families

On Sidon sets in a random set of vectors

Universality of random graphs for graphs of maximum degree two

On constant-multiple-free sets contained in a random set of integers

See the researcher in context

Building this map preview

Sang June Lee

Research overview

Is this your work?

7 publications

The independence number of non-uniform uncrowded hypergraphs and an anti-Ramsey type result

Dynamic coloring of graphs having no K5K_5K5​ minor

Towards extending the Ahlswede-Khachatrian theorem to cross t-intersecting families

An Erd\H os--Ko--Rado theorem for cross ttt-intersecting families

On Sidon sets in a random set of vectors

Universality of random graphs for graphs of maximum degree two

On constant-multiple-free sets contained in a random set of integers

See the researcher in context

Building this map preview

Dynamic coloring of graphs having no $K_5$ minor

An Erd\H os--Ko--Rado theorem for cross $t$ -intersecting families