In the paper some new upper bounds with parameters were obtained for the classical Ramsey numbers R(m,n,l) and R(m,n,l,s) . By using the upper bounds, it was proved that R (4,4,4)≤236.
Given two graphs G and H,the Ramsey number R(G,H) is the minimum integer N such that any two-coloring of the edges of K_(N) in red or blue yields a red G or a blue H.Let v(G) be the number of vertices of G and χ(G) b...Given two graphs G and H,the Ramsey number R(G,H) is the minimum integer N such that any two-coloring of the edges of K_(N) in red or blue yields a red G or a blue H.Let v(G) be the number of vertices of G and χ(G) be the chromatic number of G.Let s(G) denote the chromatic surplus of G,the number of vertices in a minimum color class among all proper χ(G)-colorings of G.Burr showed that R(G,H)≥(v(G)-1)(χ(H)-1)+s(H) if G is connected and v(G)≥s(H).A connected graph G is H-good if R(G,H)=(v(G)-1)(χ(H)-1)+s(H).Let tH denote the disjoint union of t copies of graph H,and let G∨H denote the join of G and H.Denote a complete graph on n vertices by K_(n),and a tree on n vertices by T_(n).Denote a book with n pages by B_(n),i.e.,the join K_(2) ∨■.Erd?s,Faudree,Rousseau and Schelp proved that T_(n) is B_(m)-good if n≥3m-3.In this paper,we obtain the exact Ramsey number of T_(n) versus 2B_(2).Our result implies that T_(n) is 2B_(2)-good if n≥5.展开更多
For an integer r≥2 and bipartite graphs Hi,where 1≤i≤r,the bipartite Ramsey number br(H1,H2,…,Hr)is the minimum integer N such that any r-edge coloring of the complete bipartite graph KN;N contains a monochromatic...For an integer r≥2 and bipartite graphs Hi,where 1≤i≤r,the bipartite Ramsey number br(H1,H2,…,Hr)is the minimum integer N such that any r-edge coloring of the complete bipartite graph KN;N contains a monochromatic subgraph isomorphic to Hi in color i for some 1≤i≤r.We show that if r≥3;α1,α2>0,αj+2≥[(j+2)!-1]Σi=1^(j+1)α1 for j=1,2…r-2,then br(C2[α1n],C2[α2n],…,C2[αrn]=(Σ=j=1^(r)a j+o(1))n.展开更多
Let K_(1,k)be a star of order k+1 and K_(n)■K_(1,k)the graph obtained from a complete graph K_(n)and an additional vertex v by joining v to k vertices of K_(n).For graphs G and H,the star-critical Ramsey number r_(*)...Let K_(1,k)be a star of order k+1 and K_(n)■K_(1,k)the graph obtained from a complete graph K_(n)and an additional vertex v by joining v to k vertices of K_(n).For graphs G and H,the star-critical Ramsey number r_(*)(G,H)is the minimum integer k such that any red/blue edge-coloring of K_(r-1)■K_(1,k)contains a red copy of G or a blue copy of H,where r is the classical Ramsey number R(G,H).Let C_(m)denote a cycle of order m and W_(n)a wheel of order n+1.Hook(2010)proved that r_(*)(W_(n),C_3)=n+3 for n≥6.In this paper,we show that r_(*)(W_(n),C_(m))=n+3 for m odd,m≥5 and n≥3(m-1)/2+2.展开更多
In this paper, we determine the bounds about Ramsey number R(Wm, Wn), where Wi is a graph obtained from a cycle Ci and an additional vertex by joining it to every vertex of the cycle Ci. We prove that 3m+ 1 ≤ R(W...In this paper, we determine the bounds about Ramsey number R(Wm, Wn), where Wi is a graph obtained from a cycle Ci and an additional vertex by joining it to every vertex of the cycle Ci. We prove that 3m+ 1 ≤ R(Wm, Wn) ≤ 8m-3for odd n, m≥n≥3, m≥5, and2m+1≤R(Wm, Wn) 〈7m-2 for even n and m ≥ n + 502. Especially, if m is sufficiently large and n = 3, we have R(Wm, W3) = 3m + 1.展开更多
The Ramsey number is a foundational result in combinatorics. This article will introduce Ramsey number with the method of graph theory, and the Ramsey pricing theory is applied to the sales price and study of cross su...The Ramsey number is a foundational result in combinatorics. This article will introduce Ramsey number with the method of graph theory, and the Ramsey pricing theory is applied to the sales price and study of cross subsidy. Based on the status of our sales price and cross subsidy, Ramsey pricing methods theoretically guide adjustment thoughts of sales price and solve the practical problems in our life.展开更多
The concept of H-decompositions of graphs was first introduced by Erd?s, Goodman and Pósa in 1966, who were motivated by the problem of representing graphs by set intersections. Given graphs G and H, an H-decompo...The concept of H-decompositions of graphs was first introduced by Erd?s, Goodman and Pósa in 1966, who were motivated by the problem of representing graphs by set intersections. Given graphs G and H, an H-decomposition of G is a partition of the edge set of G such that each part is either a single edge or forms a graph isomorphic to H. Let Ф(n,H) be the smallest number Ф, such that, any graph of order n admits an H-decomposition with at most Ф parts. The exact computation of Ф(n,H) for an arbitrary H is still an open problem. Recently, a few papers have been published about this problem. In this survey we will bring together all the results about H-decompositions. We will also introduce two new related problems, namely Weighted H-Decompositions of graphs and Monochromatic H-Decom- positions of graphs.展开更多
IT is very difficult to establish the Ramsey number, so we often use the way of getting the up-per and lower bound of the Ramsey number to near the exact value. All lower bounds of R (5,l) known so far are shown in ta...IT is very difficult to establish the Ramsey number, so we often use the way of getting the up-per and lower bound of the Ramsey number to near the exact value. All lower bounds of R (5,l) known so far are shown in table 1.展开更多
Let r≥3 be an integer such that r−2 is a prime power and let H be a connected graph on n vertices with average degree at least d andα(H)≤βn,where 0<β<1 is a constant.We prove that the size Ramsey number R^(...Let r≥3 be an integer such that r−2 is a prime power and let H be a connected graph on n vertices with average degree at least d andα(H)≤βn,where 0<β<1 is a constant.We prove that the size Ramsey number R^(H;r)>nd2(r−2)2−Cn−−√for all sufficiently large n,where C is a constant depending only on r,d andβ.In particular,for integers k≥1,and r≥3 such that r−2 is a prime power,we have that there exists a constant C depending only on r and k such that R^(Pkn;r)>kn(r−2)2−Cn−−√−(k2+k)2(r−2)2 for all sufficiently large n,where P k n is the kth power of Pn.展开更多
Let H =(V, E) be a k-uniform hypergraph. For 1 ≤ s ≤ k-1, an s-path P^(k,s)_n of length n in H is a sequence of distinct vertices v_1, v_2, · · ·, v_(s+n(k-s)) such that {v_(1+i(k-s)), · · &...Let H =(V, E) be a k-uniform hypergraph. For 1 ≤ s ≤ k-1, an s-path P^(k,s)_n of length n in H is a sequence of distinct vertices v_1, v_2, · · ·, v_(s+n(k-s)) such that {v_(1+i(k-s)), · · ·, v_(s+(i+1)(k-s))} is an edge of H for each 0 ≤ i ≤ n-1.In this paper, we prove that R(P^(3 s,s)_n, P^(3 s,s)_3) =(2 n + 1)s + 1 for n ≥ 3.展开更多
文摘In the paper some new upper bounds with parameters were obtained for the classical Ramsey numbers R(m,n,l) and R(m,n,l,s) . By using the upper bounds, it was proved that R (4,4,4)≤236.
基金supported in part by National Natural Science Foundation of China (No.11931002)China Postdoctoral Science Foundation (No.2021M701162)。
文摘Given two graphs G and H,the Ramsey number R(G,H) is the minimum integer N such that any two-coloring of the edges of K_(N) in red or blue yields a red G or a blue H.Let v(G) be the number of vertices of G and χ(G) be the chromatic number of G.Let s(G) denote the chromatic surplus of G,the number of vertices in a minimum color class among all proper χ(G)-colorings of G.Burr showed that R(G,H)≥(v(G)-1)(χ(H)-1)+s(H) if G is connected and v(G)≥s(H).A connected graph G is H-good if R(G,H)=(v(G)-1)(χ(H)-1)+s(H).Let tH denote the disjoint union of t copies of graph H,and let G∨H denote the join of G and H.Denote a complete graph on n vertices by K_(n),and a tree on n vertices by T_(n).Denote a book with n pages by B_(n),i.e.,the join K_(2) ∨■.Erd?s,Faudree,Rousseau and Schelp proved that T_(n) is B_(m)-good if n≥3m-3.In this paper,we obtain the exact Ramsey number of T_(n) versus 2B_(2).Our result implies that T_(n) is 2B_(2)-good if n≥5.
基金supported in part by National Natural Science Foundation of China(Grant No.11931002)the Department of Education of Guangdong Province Natural Science Foundation(Grant No.2020KTSCX078)the Project of Hanshan Normal University(Grant No.QN202024).
文摘For an integer r≥2 and bipartite graphs Hi,where 1≤i≤r,the bipartite Ramsey number br(H1,H2,…,Hr)is the minimum integer N such that any r-edge coloring of the complete bipartite graph KN;N contains a monochromatic subgraph isomorphic to Hi in color i for some 1≤i≤r.We show that if r≥3;α1,α2>0,αj+2≥[(j+2)!-1]Σi=1^(j+1)α1 for j=1,2…r-2,then br(C2[α1n],C2[α2n],…,C2[αrn]=(Σ=j=1^(r)a j+o(1))n.
基金supported by the National Natural Science Foundation of China(Nos.11871270,12161141003,11931006)。
文摘Let K_(1,k)be a star of order k+1 and K_(n)■K_(1,k)the graph obtained from a complete graph K_(n)and an additional vertex v by joining v to k vertices of K_(n).For graphs G and H,the star-critical Ramsey number r_(*)(G,H)is the minimum integer k such that any red/blue edge-coloring of K_(r-1)■K_(1,k)contains a red copy of G or a blue copy of H,where r is the classical Ramsey number R(G,H).Let C_(m)denote a cycle of order m and W_(n)a wheel of order n+1.Hook(2010)proved that r_(*)(W_(n),C_3)=n+3 for n≥6.In this paper,we show that r_(*)(W_(n),C_(m))=n+3 for m odd,m≥5 and n≥3(m-1)/2+2.
文摘In this paper, we determine the bounds about Ramsey number R(Wm, Wn), where Wi is a graph obtained from a cycle Ci and an additional vertex by joining it to every vertex of the cycle Ci. We prove that 3m+ 1 ≤ R(Wm, Wn) ≤ 8m-3for odd n, m≥n≥3, m≥5, and2m+1≤R(Wm, Wn) 〈7m-2 for even n and m ≥ n + 502. Especially, if m is sufficiently large and n = 3, we have R(Wm, W3) = 3m + 1.
文摘The Ramsey number is a foundational result in combinatorics. This article will introduce Ramsey number with the method of graph theory, and the Ramsey pricing theory is applied to the sales price and study of cross subsidy. Based on the status of our sales price and cross subsidy, Ramsey pricing methods theoretically guide adjustment thoughts of sales price and solve the practical problems in our life.
文摘The concept of H-decompositions of graphs was first introduced by Erd?s, Goodman and Pósa in 1966, who were motivated by the problem of representing graphs by set intersections. Given graphs G and H, an H-decomposition of G is a partition of the edge set of G such that each part is either a single edge or forms a graph isomorphic to H. Let Ф(n,H) be the smallest number Ф, such that, any graph of order n admits an H-decomposition with at most Ф parts. The exact computation of Ф(n,H) for an arbitrary H is still an open problem. Recently, a few papers have been published about this problem. In this survey we will bring together all the results about H-decompositions. We will also introduce two new related problems, namely Weighted H-Decompositions of graphs and Monochromatic H-Decom- positions of graphs.
文摘IT is very difficult to establish the Ramsey number, so we often use the way of getting the up-per and lower bound of the Ramsey number to near the exact value. All lower bounds of R (5,l) known so far are shown in table 1.
基金This paper is supported by the National Natural Science Foundation of China(No.1217010182).
文摘Let r≥3 be an integer such that r−2 is a prime power and let H be a connected graph on n vertices with average degree at least d andα(H)≤βn,where 0<β<1 is a constant.We prove that the size Ramsey number R^(H;r)>nd2(r−2)2−Cn−−√for all sufficiently large n,where C is a constant depending only on r,d andβ.In particular,for integers k≥1,and r≥3 such that r−2 is a prime power,we have that there exists a constant C depending only on r and k such that R^(Pkn;r)>kn(r−2)2−Cn−−√−(k2+k)2(r−2)2 for all sufficiently large n,where P k n is the kth power of Pn.
文摘Let H =(V, E) be a k-uniform hypergraph. For 1 ≤ s ≤ k-1, an s-path P^(k,s)_n of length n in H is a sequence of distinct vertices v_1, v_2, · · ·, v_(s+n(k-s)) such that {v_(1+i(k-s)), · · ·, v_(s+(i+1)(k-s))} is an edge of H for each 0 ≤ i ≤ n-1.In this paper, we prove that R(P^(3 s,s)_n, P^(3 s,s)_3) =(2 n + 1)s + 1 for n ≥ 3.