Source author record

Qizhong Lin

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

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

5works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Ramsey non-goodness involving books

In 1983, Burr and Erdős initiated the study of Ramsey goodness problems.Nikiforov and Rousseau (2009) resolved almost all goodness questions raised by Burr and Erdős, in which the bounds on the parameters are of tower type since their proofs rely on the regularity lemma. Let $B_{k,n}$ be the book graph on $n$ vertices which consists of $n-k$ copies of $K_{k+1}$ all sharing a common $K_k$ , and let $H=K_p(a_1,\dots,a_{p})$ be the complete $p$ -partite graph with parts of sizes $a_1,\dots,a_{p}$ . Recently, avoiding use of the regularity lemma, Fox, He and Wigderson (2021) revisit several Ramsey goodness results involving books. They comment that it would be very interesting to see how far one can push these ideas. In particular, they conjecture that for all integers $k, p, t\ge 2$ , there exists some $δ>0$ such that for all $n\ge 1$ , $1\leq a_1\le\cdots\le a_{p-1}\le t$ and $a_p \le δn$ , we have $r(H, B_{k,n})= (p-1)(n-1)+d_k(n,K_{a_1,a_2})+1,$ where $d_k(n,K_{a_1,a_2})$ is the maximum $d$ for which there is an $(n+d-1)$ -vertex $K_{a_1,a_2}$ -free graph in which at most $k-1$ vertices have degree less than $d$ .They verify the conjecture when $a_1=a_2=1$ . Building upon the work of Fox et al. (2021), we make a substantial step by showing that the conjecture "roughly" holds if $a_1=1$ and $a_2|(n-1-k)$ , i.e. $a_2$ divides $n-1-k$ . Moreover, avoiding use of the regularity lemma, we prove that for every $k, a\geq 1$ and $p\ge2$ , there exists $δ>0$ such that for all large $n$ and $b\le δ\ln n$ , $r(K_p(1,a,b,\dots,b), B_{k,n})= (p-1)(n-1)+k(p-1)(a-1)+1$ if $a|(n-1-k)$ , where the case when $a=1$ has been proved by Nikiforov and Rousseau (2009) using the regularity lemma. The bounds on $1/δ$ we obtain are not of tower-type since our proofs do not rely on the regularity lemma.

preprint2022arXiv

Three-color Ramsey number of an odd cycle versus bipartite graphs with small bandwidth

A graph $\mathcal{H}=(W,E_\mathcal{H})$ is said to have {\em bandwidth} at most $b$ if there exists a labeling of $W$ as $w_1,w_2,\dots,w_n$ such that $|i-j|\leq b$ for every edge $w_iw_j\in E_\mathcal{H}$ . We say that $\mathcal{H}$ is a {\em balanced $(β,Δ)$ -graph} if it is a bipartite graph with bandwidth at most $β|W|$ and maximum degree at most $Δ$ , and it also has a proper 2-coloring $χ:W\rightarrow[2]$ such that $||χ^{-1}(1)|-|χ^{-1}(2)||\leqβ|χ^{-1}(2)|$ . In this paper, we prove that for every $γ>0$ and every natural number $Δ$ , there exists a constant $β>0$ such that for every balanced $(β,Δ)$ -graph $\mathcal{H}$ on $n$ vertices we have $R(\mathcal{H}, \mathcal{H}, C_n) \leq (3+γ)n$ for all sufficiently large odd $n$ . The upper bound is sharp for several classes of graphs. Let $θ_{n,t}$ be the graph consisting of $t$ internally disjoint paths of length $n$ all sharing the same endpoints. As a corollary, for each fixed $t\geq 1$ , $R(θ_{n, t},θ_{n, t}, C_{nt+λ})=(3t+o(1))n,$ where $λ=0$ if $nt$ is odd and $λ=1$ if $nt$ is even. In particular, we have $R(C_{2n},C_{2n}, C_{2n+1})=(6+o(1))n$ , which is a special case of a result of Figaj and Łuczak (2018).

preprint2021arXiv

Large book--cycle Ramsey numbers

Let $B_n^{(k)}$ be the book graph which consists of $n$ copies of $K_{k+1}$ all sharing a common $K_k$ , and let $C_m$ be a cycle of length $m$ . In this paper, we first determine the exact value of $r(B_n^{(2)}, C_m)$ for $\frac{8}{9}n+112\le m\le \lceil\frac{3n}{2}\rceil+1$ and $n \geq 1000$ . This answers a question of Faudree, Rousseau and Sheehan (Cycle--book Ramsey numbers, {\it Ars Combin.,} {\bf 31} (1991), 239--248) in a stronger form when $m$ and $n$ are large. Building upon this exact result, we are able to determine the asymptotic value of $r(B_n^{(k)}, C_n)$ for each $k \geq 3$ . Namely, we prove that for each $k \geq 3$ , $r(B_n^{(k)}, C_n)= (k+1+o_k(1))n.$ This extends a result due to Rousseau and Sheehan (A class of Ramsey problems involving trees, {\it J.~London Math.~Soc.,} {\bf 18} (1978), 392--396).

preprint2015arXiv

Sparse Multipartite Graphs as Partition Universal for Graphs of Bounded-Degrees

For graphs $G$ and $H$ , let $G\to (H,H)$ signify that any red/blue edge coloring of $G$ contains a monochromatic $H$ as a subgraph, and $\mathcal{H}(Δ,n)=\{H:|V(H)|=n,Δ(H)\le Δ\}$ . For fixed $Δ$ and $n$ , we say that $G$ is a partition universal graph for $\mathcal{H}(Δ,n)$ if $G\to (H,H)$ for every $H\in\mathcal{H}(Δ,n)$ . In 1983, Chvátal, Rödl, Szemerédi and Trotter proved that for any $Δ\ge2$ there exists a constant $B$ such that, for any $n$ , if $N\ge Bn$ then $K_N$ is partition universal for $\mathcal{H}(Δ,n)$ . Recently, Kohayakawa, Rödl, Schacht and Szemerédi proved that the complete graph $K_N$ in above result can be replaced by sparse graphs. They obtained that for fixed $Δ\ge2$ , there exist constants $B$ and $C$ such that if $N\ge Bn$ and $p=C(\log N/N)^{1/Δ}$ , then {\bf a.a.s.} $G(N,p)$ is partition universal graph for $\mathcal{H}(Δ,n)$ , where $G(N,p)$ is the standard random graph on $N$ vertices with $\mathbb{P}(e)=p$ for each edge $e$ . From some results of Bollobás and Łuczak, we know that {\bf a.a.s.} $χ(G(N,p)) = Θ((N/\log N)^{1-1/Δ})$ . In this paper, we shall show that the $G(N,p)$ in above result can be replaced by random multipartite graph. Let $K_{r}(N)$ be the complete $r$ -partite graph with $N$ vertices in each part, and $G_r(N,p)$ the random spanning subgraph of $K_r(N)$ , in which each edge appears with probability $p$ . It is shown that for fixed $Δ\ge2$ there exist constants $r, B$ and $C$ depending only on $Δ$ such that if $N\ge Bn$ and $p=C(\log N/N)^{1/Δ}$ , then {\bf a.a.s.} $G_r(N,p)$ is partition universal graph for $\mathcal{H}(Δ,n)$ . The proof mainly uses the sparse multipartite regularity lemma.

preprint2014arXiv

A Folkman Linear Family

For graphs $F$ and $G$ , let $F\to (G,G)$ signify that any red/blue edge coloring of $F$ contains a monochromatic $G$ . Define Folkman number $f(G;p)$ to be the smallest order of a graph $F$ such that $F\to (G,G)$ and $ω(F) \le p$ . It is shown that $f(G;p)\le cn$ for graphs $G$ of order $n$ with $Δ(G)\le Δ$ , where $Δ\ge 3$ , $c=c(Δ)$ and $p=p(Δ)$ are positive constants.

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.