Query：
学者姓名：林启忠
Refining：
Year
Type
Indexed by
Source
Complex
Co-
Language
Clean All
Abstract ：
A book B-n is a graph which consists of n triangles sharing a common edge. Rousseau and Sheehan (1978) conjectured that r(B-m, B-n) <= 2(m+ n+ 1)+ c some constant c > 0. Let m = left Perpendicular alpha n right Perpendicular where 0 < alpha = 1 is a real number. A result of Nikiforov and Rousseau [Random Structures Algorithms 27 (2005), 379-400] implies that this conjecture holds in a stronger form for 0 < alpha <= 1/6 and large n. We prove that r(B-m, B-n) <= (3/2 + 3 alpha + o(1))n, where 1/4 < alpha < 1/2. This confirms the conjecture in a stronger form for 1/6 <= alpha < 1/2 and large n. As a corollary, r(B (inverted left Perpendicular n4 inverted right Perpendicular), B-n) = (9/4 + o(1))n. (c) 2023 Elsevier Ltd. All rights reserved.
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Chen, Xun , Lin, Qizhong . New upper bounds for Ramsey numbers of books [J]. | EUROPEAN JOURNAL OF COMBINATORICS , 2024 , 115 . |
| MLA | Chen, Xun 等. "New upper bounds for Ramsey numbers of books" . | EUROPEAN JOURNAL OF COMBINATORICS 115 (2024) . |
| APA | Chen, Xun , Lin, Qizhong . New upper bounds for Ramsey numbers of books . | EUROPEAN JOURNAL OF COMBINATORICS , 2024 , 115 . |
| Export to | NoteExpress RIS BibTex |
Version ：
Abstract ：
For graphs $G$ and $H$ , the Ramsey number $r(G,H)$ is the smallest positive integer $N$ such that any red/blue edge colouring of the complete graph $K_N$ contains either a red $G$ or a blue $H$ . A book $B_n$ is a graph consisting of $n$ triangles all sharing a common edge.Recently, Conlon, Fox, and Wigderson conjectured that for any $0\lt \alpha \lt 1$ , the random lower bound $r(B_{\lceil \alpha n\rceil },B_n)\ge (\sqrt{\alpha }+1)<^>2n+o(n)$ is not tight. In other words, there exists some constant $\beta \gt (\sqrt{\alpha }+1)<^>2$ such that $r(B_{\lceil \alpha n\rceil },B_n)\ge \beta n$ for all sufficiently large $n$ . This conjecture holds for every $\alpha \lt 1/6$ by a result of Nikiforov and Rousseau from 2005, which says that in this range $r(B_{\lceil \alpha n\rceil },B_n)=2n+3$ for all sufficiently large $n$ .We disprove the conjecture of Conlon, Fox, and Wigderson. Indeed, we show that the random lower bound is asymptotically tight for every $1/4\leq \alpha \leq 1$ . Moreover, we show that for any $1/6\leq \alpha \le 1/4$ and large $n$ , $r(B_{\lceil \alpha n\rceil }, B_n)\le \left (\frac 32+3\alpha \right ) n+o(n)$ , where the inequality is asymptotically tight when $\alpha =1/6$ or $1/4$ . We also give a lower bound of $r(B_{\lceil \alpha n\rceil }, B_n)$ for $1/6\le \alpha \lt \frac{52-16\sqrt{3}}{121}\approx 0.2007$ , showing that the random lower bound is not tight, i.e., the conjecture of Conlon, Fox, and Wigderson holds in this interval.
Keyword ：
Book Book Ramsey number Ramsey number refined regularity lemma refined regularity lemma
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Fan, Chunchao , Lin, Qizhong , Yan, Yuanhui . On a conjecture of Conlon, Fox, and Wigderson [J]. | COMBINATORICS PROBABILITY & COMPUTING , 2024 . |
| MLA | Fan, Chunchao 等. "On a conjecture of Conlon, Fox, and Wigderson" . | COMBINATORICS PROBABILITY & COMPUTING (2024) . |
| APA | Fan, Chunchao , Lin, Qizhong , Yan, Yuanhui . On a conjecture of Conlon, Fox, and Wigderson . | COMBINATORICS PROBABILITY & COMPUTING , 2024 . |
| Export to | NoteExpress RIS BibTex |
Version ：
Abstract ：
Given integers p,q ≥ 2, we say that a graph G is (Kp,Kq)-free if there exists a red/blue edge coloring of G such that it contains neither a red Kp nor a blue Kq. Given a function f(n), the Ramsey-Turán number RT(n,p,q,f(n)) is the maximum number of edges in an n-vertex (Kp,Kq)-free graph with independence number at most f(n). For any δ > 0, let ρ(p,q,δ)= limn→∞ RT(n,p,q,δn)/n2. We always call ρ(p,q) := limδ→0 ρ(p,q,δ) the Ramsey-Turán density of Kp and Kq. In 1993, Erdós, Hajnal, Simonovits, Sós, and Szemerédi proposed to determine the value of ρ(3,q) for q ≥ 3, and they conjectured that for q ≥ 2, ρ(3,2q - 1) = 1/2(1- 1/r(3,q)-1). More recently, in 2019, Kim, Kim, and Liu conjectured that for q ≥ 2, ρ(3,2q) = 1/2(1- 1/r(3,q)). Erdós et al. (1993) determined ρ(3,q) for q = 3,4,5 and ρ(4,4). There has been no progress on the Ramsey-Turán density ρ(p,q) in the past 30 years. In this paper, we obtain ρ(3,6) = 5/12 and ρ(3,7) =7/16. Moreover, we show that the corresponding asymptotically extremal structures are weakly stable, which answers a problem of Erd\os et al. (1993) for the two cases. © 2024 Society for Industrial and Applied Mathematics.
Keyword ：
Ramsey graph Ramsey graph Ramsey-Turán number Ramsey-Turán number Szemerédi's regularity lemma Szemerédi's regularity lemma
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Hu, X. , Lin, Q. . TWO-COLORED RAMSEY-TURAN DENSITIES INVOLVING TRIANGLES [J]. | SIAM Journal on Discrete Mathematics , 2024 , 38 (3) : 2132-2162 . |
| MLA | Hu, X. 等. "TWO-COLORED RAMSEY-TURAN DENSITIES INVOLVING TRIANGLES" . | SIAM Journal on Discrete Mathematics 38 . 3 (2024) : 2132-2162 . |
| APA | Hu, X. , Lin, Q. . TWO-COLORED RAMSEY-TURAN DENSITIES INVOLVING TRIANGLES . | SIAM Journal on Discrete Mathematics , 2024 , 38 (3) , 2132-2162 . |
| Export to | NoteExpress RIS BibTex |
Version ：
Abstract ：
Given a graph F, let L(F) be a fixed finite family of graphs consisting of a C4 and some bipartite graphs relying on an s-partite subgraph partitioning of edges of F. Define (m,n,a,b)-graph by an m×n bipartite graph with n≥m such that all vertices in the part of size n have degree a and all vertices in the part of size m have degree b≥a. In this paper, building upon the work of Janzer and Sudakov (2023+) and combining with the idea of Conlon, Mattheus, Mubayi and Verstraëte (2023+) we obtain that for each s≥2, if there exists an L(F)-free (m,n,a,b)-graph, then there exists an F-free graph H⁎ with at least [Formula presented] contains a copy of Ks. As applications, we obtain some upper bounds of general Erdős-Rogers functions for some special graphs of F. Moreover, we obtain the multicolor Ramsey numbers [Formula presented], which improve that by Xu and Ge (2022) [24]. © 2024 Elsevier B.V.
Keyword ：
Erdős-Rogers problem Erdős-Rogers problem Hypergraph container method Hypergraph container method Ramsey number Ramsey number Random block construction Random block construction
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Hu, X. , Lin, Q. . Ramsey numbers and a general Erdős-Rogers function [J]. | Discrete Mathematics , 2024 , 347 (12) . |
| MLA | Hu, X. 等. "Ramsey numbers and a general Erdős-Rogers function" . | Discrete Mathematics 347 . 12 (2024) . |
| APA | Hu, X. , Lin, Q. . Ramsey numbers and a general Erdős-Rogers function . | Discrete Mathematics , 2024 , 347 (12) . |
| Export to | NoteExpress RIS BibTex |
Version ：
Abstract ：
For graphs F and H, the Ramsey number R(F, H) is the smallest positive integer N such that any red/blue edge coloring of KN contains either a red F or a blue H. Let Cn be a cycle of length n and Fn be a fan consisting of n triangles all sharing a common vertex. In this paper, we prove that for all sufficiently large n, � (2 + 2a + o(1))n if 1/2 < a < 1, R(C2 �an �, Fn) = (4a + o(1))n if a > 1.
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | You, Chunlin , Lin, Qizhong . Ramsey Numbers of Large Even Cycles and Fans [J]. | ELECTRONIC JOURNAL OF COMBINATORICS , 2023 , 30 (3) . |
| MLA | You, Chunlin 等. "Ramsey Numbers of Large Even Cycles and Fans" . | ELECTRONIC JOURNAL OF COMBINATORICS 30 . 3 (2023) . |
| APA | You, Chunlin , Lin, Qizhong . Ramsey Numbers of Large Even Cycles and Fans . | ELECTRONIC JOURNAL OF COMBINATORICS , 2023 , 30 (3) . |
| Export to | NoteExpress RIS BibTex |
Version ：
Abstract ：
In 1983, Burr and Erd6s initiated the study of Ramsey goodness problems. Nikiforov and Rousseau (2009) resolved almost all goodness questions raised by Burr and Erd6s, in which the bounds on the parameters are of tower type since their proofs rely on the regularity lemma. Let Bk,n be the book graph on n vertices which consists of n - k copies of Kk +1 all sharing a common Kk, and let H = Kp(a1, . . . , ap) be the complete p-partite graph with parts of sizes a1, . . . , ap. Recently, avoiding use of the regularity lemma, Fox, He and Wigderson (2023) 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 & delta; > 0 such that for all n & GE; 1, 1 < a1 < & BULL; & BULL; & BULL; < ap-1 < t and ap < & delta; n, we have r(H, Bk,n) = (p - 1)(n - 1) + dk(n, Ka1,a2 ) + 1, where dk(n, Ka1,a2 ) is the maximum d for which there is an (n +d -1)-vertex Ka1,a2-free graph in which at most k - 1 vertices have degree less than d. They verify the conjecture when a1 = a2 = 1. We disprove the conjecture of Fox et al. (2023). Building upon the work of Fox et al., we make a substantial step by showing that for every k, p, t & GE; 2, there exists & delta; > 0 such that the following holds for all large n. Let 1 < a1 < & BULL; & BULL; & BULL; < ap-1 < t and ap < & delta;n be positive integers. If a1 = 1, then r(H, Bk,n) < (p - 1)(n - 1) + k(p - 1)(a2 - 1) + 1. The inequality is tight if a2 (n - 1 - k). Moreover, we prove that for every k, a & GE; 1 and p & GE; 2, there exists & delta; > 0 such that for all large n and b < & delta; ln n, r(Kp(1, a, b, ..., b), Bk,n) = (p -1)(n -1) + k(p -1)(a -1) +1
Keyword ：
Book Book Ramsey goodness Ramsey goodness Stability-supersaturation lemma Stability-supersaturation lemma
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Fan, Chunchao , Lin, Qizhong . Ramsey non-goodness involving books [J]. | JOURNAL OF COMBINATORIAL THEORY SERIES A , 2023 , 199 . |
| MLA | Fan, Chunchao 等. "Ramsey non-goodness involving books" . | JOURNAL OF COMBINATORIAL THEORY SERIES A 199 (2023) . |
| APA | Fan, Chunchao , Lin, Qizhong . Ramsey non-goodness involving books . | JOURNAL OF COMBINATORIAL THEORY SERIES A , 2023 , 199 . |
| Export to | NoteExpress RIS BibTex |
Version ：
Abstract ：
A graph H = (W, E-H) is said to have bandwidth at most b if there exists a labeling of W as w(1), w(2),..., w(n) such that vertical bar i - j vertical bar <= b for every edge w(i)w(j) is an element of E-H. We say that H is a balanced (beta, Delta)-graph if it is a bipartite graph with bandwidth at most beta vertical bar W vertical bar and maximum degree at most Delta, and it also has a proper 2-coloring chi : W -> [2] such that parallel to chi(-1)(1)vertical bar - vertical bar chi(-1)(2)parallel to <= beta vertical bar chi(-1)(2)|. In this paper, we prove that for every gamma > 0 and every natural number Delta, there exists a constant beta > 0 such that for every balanced (beta, Delta)-graph H on n vertices we have R(H, H, C-n) <= (3 + gamma)n for all sufficiently large odd n. The upper bound is sharp for several classes of graphs. Let theta(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 >= 1, R(theta(n,t), theta(n,t), Cnt+lambda) = (3t + o(1))n, where lambda = 0 if nt is odd and lambda = 1 if nt is even. In particular, we have R(C-2n, C-2n, C2n+1) = (6 + o(1))n, which is a special case of a result of Figaj and Luczak (2018).
Keyword ：
Cycle Cycle Ramsey number Ramsey number Regularity Lemma Regularity Lemma Small bandwidth Small bandwidth
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | You, Chunlin , Lin, Qizhong . Three-Color Ramsey Number of an Odd Cycle Versus Bipartite Graphs with Small Bandwidth [J]. | GRAPHS AND COMBINATORICS , 2023 , 39 (3) . |
| MLA | You, Chunlin 等. "Three-Color Ramsey Number of an Odd Cycle Versus Bipartite Graphs with Small Bandwidth" . | GRAPHS AND COMBINATORICS 39 . 3 (2023) . |
| APA | You, Chunlin , Lin, Qizhong . Three-Color Ramsey Number of an Odd Cycle Versus Bipartite Graphs with Small Bandwidth . | GRAPHS AND COMBINATORICS , 2023 , 39 (3) . |
| Export to | NoteExpress RIS BibTex |
Version ：
Abstract ：
A book Bn ${B}_{n}$ is a graph which consists of n $n$ triangles sharing a common edge. In 1978, Rousseau and Sheehan conjectured that the Ramsey number satisfies r(Bm,Bn)<= 2(m+n)+c $r({B}_{m},{B}_{n})\le \,2(m+n)+c$ for some constant c>0 $c\gt 0$. In this article, we obtain that r(Bm,Bn)<= 2(m+n)+o(n) $r({B}_{m},{B}_{n})\le 2(m+n)+o(n)$ for all m <= n $m\le n$ and n $n$ large, which confirms the conjecture of Rousseau and Sheehan asymptotically. As a corollary, our result implies that a related conjecture of Faudree, Rousseau and Sheehan on strongly regular graph holds asymptotically.
Keyword ：
book book probabilistic method probabilistic method Ramsey number Ramsey number refined regularity lemma refined regularity lemma
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Chen, Xun , Lin, Qizhong , You, Chunlin . Ramsey numbers of large books [J]. | JOURNAL OF GRAPH THEORY , 2022 , 101 (1) : 124-133 . |
| MLA | Chen, Xun 等. "Ramsey numbers of large books" . | JOURNAL OF GRAPH THEORY 101 . 1 (2022) : 124-133 . |
| APA | Chen, Xun , Lin, Qizhong , You, Chunlin . Ramsey numbers of large books . | JOURNAL OF GRAPH THEORY , 2022 , 101 (1) , 124-133 . |
| Export to | NoteExpress RIS BibTex |
Version ：
Abstract ：
A book B-n is a graph which consists of n triangles sharing a common edge. In this paper, we study Ramsey numbers of quadrilateral versus books. Previous results give the exact value of r (C-4, B-n) for 1 <= n <= 14. We aim to determine the exact value of r (C-4, B-n) for infinitely many n. To achieve this, we first prove that r (C-4, B-(m -1)(2) +(t-2)) <= m(2) + t 2 for m >= 4 and 0 <= t <= m - 1. This improves upon a result by Faudree, Rousseau, and Sheehan which states that r (C-4, B-n) <= g (g (n)), where g (n) = n + left floor root n - 1 right floor + 2. Combining the new upper bound and constructions of C4-free graphs, we are able to determine the exact value of r (C4, Bn) for infinitely many n. As a special case, we show r (C-4, B-q(2) -q-2) = q(2) + q - 1 for all prime powers q >= 4.
Keyword ：
book book four-cycle four-cycle Ramsey number Ramsey number
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Li, Tianyu , Lin, Qizhong , Peng, Xing . Ramsey numbers of the quadrilateral versus books [J]. | JOURNAL OF GRAPH THEORY , 2022 , 103 (2) : 309-322 . |
| MLA | Li, Tianyu 等. "Ramsey numbers of the quadrilateral versus books" . | JOURNAL OF GRAPH THEORY 103 . 2 (2022) : 309-322 . |
| APA | Li, Tianyu , Lin, Qizhong , Peng, Xing . Ramsey numbers of the quadrilateral versus books . | JOURNAL OF GRAPH THEORY , 2022 , 103 (2) , 309-322 . |
| Export to | NoteExpress RIS BibTex |
Version ：
Abstract ：
A cornerstone contribution due to Chung, Graham and Wilson (1989) implies that many graph properties of different na-ture are equivalent. Graphs that satisfy any (and thus all) of the properties are called quasi-random graphs. In this paper, we con-struct families of quasi-random graphs for any given edge density, which are regular but not strongly regular. Moreover, we obtain a lower bound for Ramsey number r(K1 + G) in which the graph G contains no isolated vertex, which extends a classical result by Shearer and Mathon
Keyword ：
quasi-randomness quasi-randomness Ramsey number Ramsey number Weil bound Weil bound
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Lin, Qizhong , Li, Yusheng . Quasi-random graphs of given density and Ramsey numbers? [J]. | PURE AND APPLIED MATHEMATICS QUARTERLY , 2022 , 18 (6) : 2537-2549 . |
| MLA | Lin, Qizhong 等. "Quasi-random graphs of given density and Ramsey numbers?" . | PURE AND APPLIED MATHEMATICS QUARTERLY 18 . 6 (2022) : 2537-2549 . |
| APA | Lin, Qizhong , Li, Yusheng . Quasi-random graphs of given density and Ramsey numbers? . | PURE AND APPLIED MATHEMATICS QUARTERLY , 2022 , 18 (6) , 2537-2549 . |
| Export to | NoteExpress RIS BibTex |
Version ：
Export
| Results： |
Selected to |
| Format： |
