BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Choongbum Lee

Choongbum Lee contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.CODiscrete Mathematicsmath.FAmath.PR

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
24works
0followers
4topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

24 published item(s)

preprint2015arXiv

A transference principle for Ramsey numbers of bounded degree graphs

We investigate Ramsey numbers of bounded degree graphs and provide an interpolation between known results on the Ramsey numbers of general bounded degree graphs and bounded degree graphs of small bandwidth. Our main theorem implies that there exists a constant $c$ such that for every $Δ$, there exists $β$ such that if $G$ is an $n$-vertex graph with maximum degree at most $Δ$ having a homomorphism $f$ into a graph $H$ of maximum degree at most $d$ where $|f^{-1}(v)| \le βn$ for all $v \in V(H)$, then the Ramsey number of $G$ is at most $c^{d \log d} n$. A construction of Graham, Rödl, and Ruciński shows that the statement above holds only if $β\le (c&#39;)^Δ$ for some constant $c&#39; < 1$. We further study the parameter $β$ using a density-type embedding theorem for bipartite graphs of small bandwidth. This theorem may be of independent interest.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Compatible Hamilton cycles in Dirac graphs

A graph is Hamiltonian if it contains a cycle passing through every vertex exactly once. A celebrated theorem of Dirac from 1952 asserts that every graph on $n\ge 3$ vertices with minimum degree at least $n/2$ is Hamiltonian. We refer to such graphs as Dirac graphs. In this paper we obtain the following strengthening of this result. Given a graph $G=(V,E)$, an {\em incompatibility system} $\mathcal{F}$ over $G$ is a family $\mathcal{F}=\{F_v\}_{v\in V}$ such that for every $v\in V$, the set $F_v$ is a set of unordered pairs $F_v \subseteq \{\{e,e&#39;\}: e\ne e&#39;\in E, e\cap e&#39;=\{v\}\}$. An incompatibility system is {\em $Δ$-bounded} if for every vertex $v$ and an edge $e$ incident to $v$, there are at most $Δ$ pairs in $F_v$ containing $e$. We say that a cycle $C$ in $G$ is {\em compatible} with $\mathcal{F}$ if every pair of incident edges $e,e&#39;$ of $C$ satisfies $\{e,e&#39;\} \notin F_v$, where $v=e\cap e&#39;$. This notion is partly motivated by a concept of transition systems defined by Kotzig in 1968, and can be viewed as a quantitative measure of robustness of graph properties. We prove that there is a constant $μ>0$ such that for every $μn$-bounded incompatibility system $\mathcal{F}$ over a Dirac graph $G$, there exists a Hamilton cycle compatible with $\mathcal{F}$. This settles in a very strong form, a conjecture of Häggkvist from 1988.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Judicious partitions of directed graphs

The area of judicious partitioning considers the general family of partitioning problems in which one seeks to optimize several parameters simultaneously, and these problems have been widely studied in various combinatorial contexts. In this paper, we study essentially the most fundamental judicious partitioning problem for directed graphs, which naturally extends the classical Max Cut problem to this setting: we seek bipartitions in which many edges cross in each direction. It is easy to see that a minimum outdegree condition is required in order for the problem to be nontrivial, and we prove that every directed graph with M edges and minimum outdegree at least two admits a bipartition in which at least (1/6 + o(1))M edges cross in each direction. We also prove that if the minimum outdegree is at least three, then the constant can be increased to 1/5. If the minimum outdegree tends to infinity with N, then the constant increases to 1/4. All of these constants are best-possible, and provide asymptotic answers to a question of Alex Scott.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On the grid Ramsey problem and related questions

The Hales--Jewett theorem is one of the pillars of Ramsey theory, from which many other results follow. A celebrated theorem of Shelah says that Hales--Jewett numbers are primitive recursive. A key tool used in his proof, now known as the cube lemma, has become famous in its own right. In its simplest form, this lemma says that if we color the edges of the Cartesian product $K_n \times K_n$ in $r$ colors then, for $n$ sufficiently large, there is a rectangle with both pairs of opposite edges receiving the same color. Shelah&#39;s proof shows that $n = r^{\binom{r+1}{2}} + 1$ suffices. More than twenty years ago, Graham, Rothschild and Spencer asked whether this bound can be improved to a polynomial in $r$. We show that this is not possible by providing a superpolynomial lower bound in $r$. We also discuss a number of related problems.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Two Approaches to Sidorenko&#39;s Conjecture

Sidorenko&#39;s conjecture states that for every bipartite graph $H$ on $\{1,\cdots,k\}$, $\int \prod_{(i,j)\in E(H)} h(x_i, y_j) dμ^{|V(H)|} \ge \left( \int h(x,y) \,dμ^2 \right)^{|E(H)|}$ holds, where $μ$ 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 Erdős-Rényi 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 \cup B$ is tree-arrangeable if neighborhoods of vertices in $A$ have a certain tree-like structure. We show that Sidorenko&#39;s conjecture holds for all tree-arrangeable bipartite graphs. In particular, this implies that Sidorenko&#39;s conjecture holds if there are two vertices $a_1, a_2$ in $A$ such that each vertex $a \in A$ satisfies $N(a) \subseteq N(a_1)$ or $N(a) \subseteq N(a_2)$, and also implies a recent result of Conlon, Fox, and Sudakov \cite{CoFoSu}. Second, if $T$ is a tree and $H$ is a bipartite graph satisfying Sidorenko&#39;s conjecture, then it is shown that the Cartesian product $T \Box H$ of $T$ and $H$ also satisfies Sidorenko&#39;s conjecture. This result implies that, for all $d \ge 2$, the $d$-dimensional grid with arbitrary side lengths satisfies Sidorenko&#39;s conjecture.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Bisections of graphs

A bisection of a graph is a bipartition of its vertex set in which the number of vertices in the two parts differ by at most 1, and its size is the number of edges which go across the two parts. In this paper, motivated by several questions and conjectures of Bollobás and Scott, we study maximum bisections of graphs. First, we extend the classical Edwards bound on maximum cuts to bisections. A simple corollary of our result implies that every graph on $n$ vertices and $m$ edges with no isolated vertices, and maximum degree at most $n/3 + 1$, admits a bisection of size at least $m/2 + n/6$. Then using the tools that we developed to extend Edwards&#39;s bound, we prove a judicious bisection result which states that graphs with large minimum degree have a bisection in which both parts span relatively few edges. A special case of this general theorem answers a conjecture of Bollobás and Scott, and shows that every graph on $n$ vertices and $m$ edges of minimum degree at least 2 admits a bisection in which the number of edges in each part is at most $(1/3+o(1))m$. We also present several other results on bisections of graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Long paths and cycles in random subgraphs of graphs with large minimum degree

For a given finite graph $G$ of minimum degree at least $k$, let $G_{p}$ be a random subgraph of $G$ obtained by taking each edge independently with probability $p$. We prove that (i) if $p \ge ω/k$ for a function $ω=ω(k)$ that tends to infinity as $k$ does, then $G_p$ asymptotically almost surely contains a cycle (and thus a path) of length at least $(1-o(1))k$, and (ii) if $p \ge (1+o(1))\ln k/k$, then $G_p$ asymptotically almost surely contains a path of length at least $k$. Our theorems extend classical results on paths and cycles in the binomial random graph, obtained by taking $G$ to be the complete graph on $k+1$ vertices.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Ramsey numbers of cubes versus cliques

The cube graph Q_n is the skeleton of the n-dimensional cube. It is an n-regular graph on 2^n vertices. The Ramsey number r(Q_n, K_s) is the minimum N such that every graph of order N contains the cube graph Q_n or an independent set of order s. Burr and Erdos in 1983 asked whether the simple lower bound r(Q_n, K_s) >= (s-1)(2^n - 1)+1 is tight for s fixed and n sufficiently large. We make progress on this problem, obtaining the first upper bound which is within a constant factor of the lower bound.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Towards a weighted version of the Hajnal-Szemerédi Theorem

For a positive integer r>=2, a K_r-factor of a graph is a collection vertex-disjoint copies of K_r which covers all the vertices of the given graph. The celebrated theorem of Hajnal and Szemerédi asserts that every graph on n vertices with minimum degree at least (1-1/r)n contains a K_r-factor. In this note, we propose investigating the relation between minimum degree and existence of perfect K_r-packing for edge-weighted graphs. The main question we study is the following. Suppose that a positive integer r>=2 and a real t in [0,1] is given. What is the minimum weighted degree of K_n that guarantees the existence of a K_r-factor such that every factor has total edge weight at least tr(r-1)/2? We provide some lower and upper bounds and make a conjecture on the asymptotics of the threshold as n goes to infinity.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Chromatic number, clique subdivisions, and the conjectures of Hajós and Erdős-Fajtlowicz

For a graph $G$, let $χ(G)$ denote its chromatic number and $σ(G)$ denote the order of the largest clique subdivision in $G$. Let H(n) be the maximum of $χ(G)/σ(G)$ over all $n$-vertex graphs $G$. A famous conjecture of Hajós from 1961 states that $σ(G) \geq χ(G)$ for every graph $G$. That is, $H(n) \leq 1$ for all positive integers $n$. This conjecture was disproved by Catlin in 1979. Erdős and Fajtlowicz further showed by considering a random graph that $H(n) \geq cn^{1/2}/\log n$ for some absolute constant $c>0$. In 1981 they conjectured that this bound is tight up to a constant factor in that there is some absolute constant $C$ such that $χ(G)/σ(G) \leq Cn^{1/2}/\log n$ for all $n$-vertex graphs $G$. In this paper we prove the Erdős-Fajtlowicz conjecture. The main ingredient in our proof, which might be of independent interest, is an estimate on the order of the largest clique subdivision which one can find in every graph on $n$ vertices with independence number $α$.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Dirac&#39;s theorem for random graphs

A classical theorem of Dirac from 1952 asserts that every graph on $n$ vertices with minimum degree at least $\lceil n/2 \rceil$ is Hamiltonian. In this paper we extend this result to random graphs. Motivated by the study of resilience of random graph properties we prove that if $p \gg \log n /n$, then a.a.s. every subgraph of $G(n,p)$ with minimum degree at least $(1/2+o(1))np$ is Hamiltonian. Our result improves on previously known bounds, and answers an open problem of Sudakov and Vu. Both, the range of edge probability $p$ and the value of the constant 1/2 are asymptotically best possible.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Getting directed Hamilton cycle twice faster

Consider the random graph process where we start with an empty graph on n vertices, and at time t, are given an edge e_t chosen uniformly at random among the edges which have not appeared so far. A classical result in random graph theory asserts that w.h.p. the graph becomes Hamiltonian at time (1/2+o(1))n log n. On the contrary, if all the edges were directed randomly, then the graph has a directed Hamilton cycle w.h.p. only at time (1+o(1))n log n. In this paper we further study the directed case, and ask whether it is essential to have twice as many edges compared to the undirected case. More precisely, we ask if at time t, instead of a random direction one is allowed to choose the orientation of e_t, then whether it is possible or not to make the resulting directed graph Hamiltonian at time earlier than n log n. The main result of our paper answers this question in the strongest possible way, by asserting that one can orient the edges on-line so that w.h.p., the resulting graph has a directed Hamilton cycle exactly at the time at which the underlying graph is Hamiltonian.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Rainbow Turán Problem for Even Cycles

An edge-colored graph is rainbow if all its edges are colored with distinct colors. For a fixed graph $H$, the rainbow Turán number $\mathrm{ex}^{\ast}(n,H)$ is defined as the maximum number of edges in a properly edge-colored graph on $n$ vertices with no rainbow copy of $H$. We study the rainbow Turán number of even cycles, and prove that for every fixed $\varepsilon > 0$, there is a constant $C(\varepsilon)$ such that every properly edge-colored graph on $n$ vertices with at least $C(\varepsilon) n^{1 + \varepsilon}$ edges contains a rainbow cycle of even length at most $2 \lceil \frac{\ln 4 - \ln \varepsilon}{\ln (1 + \varepsilon)} \rceil$. This partially answers a question of Keevash, Mubayi, Sudakov, and Verstraëte, who asked how dense a graph can be without having a rainbow cycle of any length.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Robust Hamiltonicity of Dirac graphs

A graph is Hamiltonian if it contains a cycle which passes through every vertex of the graph exactly once. A classical theorem of Dirac from 1952 asserts that every graph on $n$ vertices with minimum degree at least $n/2$ is Hamiltonian. We refer to such graphs as Dirac graphs. In this paper we extend Dirac&#39;s theorem in two directions and show that Dirac graphs are robustly Hamiltonian in a very strong sense. First, we consider a random subgraph of a Dirac graph obtained by taking each edge independently with probability $p$, and prove that there exists a constant $C$ such that if $p \ge C \log n / n$, then a.a.s. the resulting random subgraph is still Hamiltonian. Second, we prove that if a $(1:b)$ Maker-Breaker game is played on a Dirac graph, then Maker can construct a Hamiltonian subgraph as long as the bias $b$ is at most $cn /\log n$ for some absolute constant $c > 0$. Both of these results are tight up to a constant factor, and are proved under one general framework.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Self-similarity of graphs

An old problem raised independently by Jacobson and Schönheim asks to determine the maximum $s$ for which every graph with $m$ edges contains a pair of edge-disjoint isomorphic subgraphs with $s$ edges. In this paper we determine this maximum up to a constant factor. We show that every $m$-edge graph contains a pair of edge-disjoint isomorphic subgraphs with at least $c (m\log m)^{2/3}$ edges for some absolute constant $c$, and find graphs where this estimate is off only by a multiplicative constant. Our results improve bounds of Erdős, Pach, and Pyber from 1987.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Bandwidth theorem for random graphs

A graph $G$ is said to have \textit{bandwidth} at most $b$, if there exists a labeling of the vertices by $1,2,..., n$, so that $|i - j| \leq b$ whenever $\{i,j\}$ is an edge of $G$. Recently, Böttcher, Schacht, and Taraz verified a conjecture of Bollobás and Komlós which says that for every positive $r,Δ,γ$, there exists $β$ such that if $H$ is an $n$-vertex $r$-chromatic graph with maximum degree at most $Δ$ which has bandwidth at most $βn$, then any graph $G$ on $n$ vertices with minimum degree at least $(1 - 1/r + γ)n$ contains a copy of $H$ for large enough $n$. In this paper, we extend this theorem to dense random graphs. For bipartite $H$, this answers an open question of Böttcher, Kohayakawa, and Taraz. It appears that for non-bipartite $H$ the direct extension is not possible, and one needs in addition that some vertices of $H$ have independent neighborhoods. We also obtain an asymptotically tight bound for the maximum number of vertex disjoint copies of a fixed $r$-chromatic graph $H_0$ which one can find in a spanning subgraph of $G(n,p)$ with minimum degree $(1-1/r + γ)np$.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Corrádi and Hajnal&#39;s theorem for sparse random graphs

In this paper we extend a classical theorem of Corrádi and Hajnal into the setting of sparse random graphs. We show that if $p(n) \gg (\log n / n)^{1/2}$, then asymptotically almost surely every subgraph of $G(n,p)$ with minimum degree at least $(2/3 + o(1))np$ contains a triangle packing that covers all but at most $O(p^{-2})$ vertices. Moreover, the assumption on $p$ is optimal up to the $(\log n)^{1/2}$ factor and the presence of the set of $O(p^{-2})$ uncovered vertices is indispensable. The main ingredient in the proof, which might be of independent interest, is an embedding theorem which says that if one imposes certain natural regularity conditions on all three pairs in a balanced 3-partite graph, then this graph contains a perfect triangle packing.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Hamiltonicity, independence number, and pancyclicity

A graph on n vertices is called pancyclic if it contains a cycle of length l for all 3 \le l \le n. In 1972, Erdos proved that if G is a Hamiltonian graph on n > 4k^4 vertices with independence number k, then G is pancyclic. He then suggested that n = Ω(k^2) should already be enough to guarantee pancyclicity. Improving on his and some other later results, we prove that there exists a constant c such that n > ck^{7/3} suffices.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Maximum union-free subfamilies

An old problem of Moser asks: how large of a union-free subfamily does every family of m sets have? A family of sets is called union-free if there are no three distinct sets in the family such that the union of two of the sets is equal to the third set. We show that every family of m sets contains a union-free subfamily of size at least \lfloor \sqrt{4m+1}\rfloor - 1 and that this bound is tight. This solves Moser&#39;s problem and proves a conjecture of Erdős and Shelah from 1972. More generally, a family of sets is a-union-free if there are no a+1 distinct sets in the family such that one of them is equal to the union of a others. We determine up to an absolute multiplicative constant factor the size of the largest guaranteed a-union-free subfamily of a family of m sets. Our result verifies in a strong form a conjecture of Barat, Füredi, Kantor, Kim and Patkos.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Pancyclic subgraphs of random graphs

An $n$-vertex graph is called pancyclic if it contains a cycle of length $t$ for all $3 \leq t \leq n$. In this paper, we study pancyclicity of random graphs in the context of resilience, and prove that if $p \gg n^{-1/2}$, then the random graph $G(n,p)$ a.a.s. satisfies the following property: Every Hamiltonian subgraph of $G(n,p)$ with more than $(1/2 + o(1)){n \choose 2}p$ edges is pancyclic. This result is best possible in two ways. First, the range of $p$ is asymptotically tight; second, the proportion 1/2 of edges cannot be reduced. Our theorem extends a classical theorem of Bondy, and is closely related to a recent work of Krivelevich, Lee, and Sudakov. The proof uses a recent result of Schacht (also independently obtained by Conlon and Gowers).

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Quasi-randomness of graph balanced cut properties

Quasi-random graphs can be informally described as graphs whose edge distribution closely resembles that of a truly random graph of the same edge density. Recently, Shapira and Yuster proved the following result on quasi-randomness of graphs. Let $k \ge 2$ be a fixed integer, $α_1,...,α_k$ be positive reals satisfying $\sum_{i} α_i = 1$ and $(α_1,..., α_k) \neq (1/k,...,1/k)$, and $G$ be a graph on $n$ vertices. If for every partition of the vertices of $G$ into sets $V_1,..., V_k$ of size $α_1 n,..., α_k n$, the number of complete graphs on $k$ vertices which have exactly one vertex in each of these sets is similar to what we would expect in a random graph, then the graph is quasi-random. However, the method of quasi-random hypergraphs they used did not provide enough information to resolve the case $(1/k,..., 1/k)$ for graphs. In their work, Shapira and Yuster asked whether this case also forces the graph to be quasi-random. Janson also posed the same question in his study of quasi-randomness under the framework of graph limits. In this paper, we positively answer their question.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Rank-width of Random Graphs

Rank-width of a graph G, denoted by rw(G), is a width parameter of graphs introduced by Oum and Seymour (2006). We investigate the asymptotic behavior of rank-width of a random graph G(n,p). We show that, asymptotically almost surely, (i) if 0<p<1 is a constant, then rw(G(n,p)) = \lceil n/3 \rceil-O(1), (ii) if 1/n<< p <1/2, then rw(G(n,p))= \lceil n/3\rceil-o(n), (iii) if p = c/n and c > 1, then rw(G(n,p)) > r n for some r = r(c), and (iv) if p <= c/n and c<1, then rw(G(n,p)) <=2. As a corollary, we deduce that G(n,p) has linear tree-width whenever p=c/n for each c>1, answering a question of Gao (2006).

0 citations0 reviewsNo code linkedOpen access