filter by: Publication Year
(Descending) Articles
Discrete Applied Mathematics (0166218X) 378pp. 87-92
Given two graphs H and G, the size multipartite Ramsey number mj(H,G) is the smallest natural number t such that an arbitrary coloring of the edges of Kj×t, a complete multipartite graph whose vertex set is partitioned into j parts each of size t, using two colors (red and blue), necessarily contains a red copy of H or a blue copy of G as a subgraph. The notion of size multipartite Ramsey number was introduced by Burger and Vuuren in 2004. This notion extends the idea of the original classical Ramsey number, multipartite Ramsey number and the size Ramsey number. In this paper, we focus on mj(H,G) and find a lower bound for mj(H,G) based on the chromatic number of H and the order of G. Also, for every graph G we obtain a tight lower bound for mj(Km,G) based on m and the maximum degree of G. Furthermore, we determine the order of magnitude of mj(Km,K1,n), for j≥m≥3 and n≥2. Then, we specify the exact values of mj(Km,K1,n) for the cases m=3, m=j and j≡0orm−2(modm−1). © 2025 Elsevier B.V.
Discrete Mathematics (0012365X) 347(4)
For an arbitrary graph G, a hypergraph H is called Berge-G if there is an injection i:V(G)⟶V(H) and a bijection ψ:E(G)⟶E(H) such that for each e=uv∈E(G), we have {i(u),i(v)}⊆ψ(e). We denote by BrG, the family of r-uniform Berge-G hypergraphs. For families F1,F2,…,Ft of r-uniform hypergraphs, the Ramsey number R(F1,F2,…,Ft) is the minimum integer n such that in every hyperedge coloring of the complete r-uniform hypergraph on n vertices with t colors, there exists i, 1≤i≤t, such that there is a monochromatic copy of a hypergraph in Fi of color i. Recently, the extremal problems of Berge hypergraphs have received considerable attention. In this paper, we focus on Ramsey numbers involving 3-uniform Berge cycles and prove that for n≥4, R(B3Cn,B3Cn,B3C3)=n+1. Moreover, for m≥11 and m≥n≥5, we show that [Formula presented]. This is the first result of Ramsey number for two different families of Berge hypergraphs. © 2024 Elsevier B.V.
Graphs and Combinatorics (14355914) 38(1)pp. 112-120
Gyárfás et al. determined the asymptotic value of the diagonal Ramsey number of Cnk, R(Cnk,Cnk), generating the same result for k= 3 due to Haxell et al. Recently, the exact values of the Ramsey numbers of 3-uniform loose paths and cycles are completely determined. These results are motivations to conjecture that for every n≥ m≥ 3 and k≥ 3 , R(Cnk,Cmk)=(k-1)n+⌊m-12⌋,as mentioned by Omidi et al. More recently, it has been shown that this conjecture is true for n= m≥ 2 and k≥ 7 and for k= 4 when n> m or n= m is odd. Here we investigate this conjecture for k= 5 and demonstrate that it holds for k= 5 and sufficiently large n. © 2021, The Author(s), under exclusive licence to Springer Japan KK, part of Springer Nature.
Discrete Mathematics (0012365X) 343(8)
For given graphs H1,…,Ht, we say that G is Ramsey for H1,…,Ht and we write G⟶(H1,…,Ht), if no matter how one colors the edges of G with t colors, say 1,…,t, there exists a monochromatic copy of Hi in the ith color for some 1≤i≤t. The multicolor Ramsey number r(H1,…,Ht) is the smallest integer n such that the complete graph Kn is Ramsey for (H1,…,Ht). The multicolor size Ramsey number rˆ(H1,…,Ht) is defined as min{|E(G)|:G⟶(H1,…,Ht)}, while the restricted size Ramsey number rˆ∗(H1,…,Ht) is defined as rˆ∗(H1,…,Ht)=min{|E(G)|:G⟶(H1,…,Ht)and|V(G)|=r(H1,…,Ht)}.In 1978 Erdős et al. initiated the study of the size Ramsey numbers of graphs. Afterwards, size Ramsey numbers have been studied with particular focus on the case of trees, sparse graphs and bounded degree graphs. In this paper, the order of magnitude of multicolor size Ramsey number of stars and cliques is determined in terms of r(K1,q,…,K1,q) and r(Kp,…,Kp). Moreover, in some special cases, restricted size Ramsey number of stars and cliques is determined exactly. Our results have, up to a constant factor, similar order of magnitude and generalize significantly a well known result of Faudree and Sheehan. © 2020 Elsevier B.V.
Journal of Graph Theory (03649024) 92(3)pp. 275-286
The size Ramsey number (Formula presented.) of two graphs (Formula presented.) and (Formula presented.) is the smallest integer (Formula presented.) such that there exists a graph (Formula presented.) on (Formula presented.) edges with the property that every red-blue colouring of the edges of (Formula presented.) yields a red copy of (Formula presented.) or a blue copy of (Formula presented.). In 1981, Erdős observed that (Formula presented.) and he conjectured that this upper bound on (Formula presented.) is sharp. In 1983, Faudree and Sheehan extended this conjecture as follows: (Formula presented.) They proved the case (Formula presented.). In 2001, Pikhurko showed that this conjecture is not true for (Formula presented.) and (Formula presented.), by disproving the mentioned conjecture of Erdős. Here, we prove Faudree and Sheehan's conjecture for a given (Formula presented.) and (Formula presented.). © 2019 Wiley Periodicals, Inc.
Graphs and Combinatorics (14355914) 34(4)pp. 619-632
Given a family F of r-graphs, the Turán number of F for a given positive integer N, denoted by ex(N, F) , is the maximum number of edges of an r-graph on N vertices that does not contain any member of F as a subgraph. For given r≥ 3 , a complete r-uniform Berge-hypergraph, denoted by Kn(r), is an r-uniform hypergraph of order n with the core sequence v1, v2, … , vn as the vertices and distinct edges eij, 1 ≤ i< j≤ n, where every eij contains both vi and vj. Let Fn(r) be the family of complete r-uniform Berge-hypergraphs of order n. We determine precisely ex(N,Fn(3)) for N≥ n≥ 13. We also find the extremal hypergraphs avoiding Fn(3). © 2018, Springer Japan KK, part of Springer Nature.
SIAM Journal on Discrete Mathematics (10957146) 31(3)pp. 1634-1669
A κ-uniform loose cycle Ckn is a hypergraph with vertex set v1, v2, ... , vn(κ-1) and the set of n edges ei = v(i-1)(κ-1)+1; v(i-1)(κ-1)+2; ... ; v(i-1)(κ-1)+kg, 1 ≤ i ≤ n, where we use mod n(κ - 1) arithmetic. The diagonal Ramsey number of Ckn , R(Ckn ; Ckn ), is asymptotically 1/2 (2κ-1)n, as has been proved by Gyárfás, Sárközy, and Szemerédi [Electron. J. Combin., 15 (2008), #R126]. In this paper, we investigate to determine the exact value of R(Ckn , Ckn ) and we show that for n ≥ 2 and k ≥ 8, R(Ckn , Ckn ) = (κ - 1)n + ⌊ n-1/2 ⌋. © 2017 Society for Industrial and Applied Mathematics.
Discrete Mathematics (0012365X) 340(6)pp. 1426-1434
Recently, determining the Ramsey numbers of loose paths and cycles in uniform hypergraphs has received considerable attention. It has been shown that the 2-color Ramsey number of a k-uniform loose cycle Cnk, R(Cnk,Cnk), is asymptotically 1/2(2k−1)n. Here we conjecture that for any n≥m≥3 and k≥3 R(Pnk,Pmk)=R(Pnk,Cmk)=R(Cnk,Cmk)+1=(k−1)n+m+1/2.Recently the case k=3 was proved by the authors. In this paper, first we show that this conjecture is true for k=3 with a much shorter proof. Then, we show that for fixed m≥3 and k≥4 the conjecture is equivalent to (only) the last equality for any 2m≥n≥m≥3. Finally we give a proof for the case m=3. © 2016 Elsevier B.V.
Graphs and Combinatorics (14355914) 31(6)pp. 2299-2308
For given graphs G1,G2,…,Gt, the multicolor Ramsey number R(G1,G2,…,Gt) is the smallest positive integer n, such that if the edges of the complete graph Kn are partitioned into t disjoint color classes giving t graphs H1,H2,…,Ht, then at least one Hi has a subgraph isomorphic to Gi. In this paper, we show that if (n,m)≠(3,3),(3,4) and m≥n, then R(P3,Pn,Pm)=R(Pn,Pm)=m+⌊n2⌋-1. Consequently, R(P3,mK2,nK2)=2m+n-1 for m≥n≥3. © 2015, Springer Japan.
Journal of Combinatorial Theory. Series A (00973165) 121(1)pp. 64-73
The 3-uniform loose cycle, denoted by Cn3, is the hypergraph with vertices v1,v2,.,v2n and n edges v1v2v3,v3v4v5,.,v2n-1v2nv1. Similarly, the 3-uniform loose path Pn3 is the hypergraph with vertices v1,v2,.,v2n+1 and n edges v1v2v3,v3v4v5,.,v2n-1v2nv2n+1. In 2006 Haxell et al. proved that the 2-color Ramsey number of 3-uniform loose cycles on 2. n vertices is asymptotically 5n2. Their proof is based on the method of the Regularity Lemma. Here, without using this method, we generalize their result by determining the exact values of 2-color Ramsey numbers involving loose paths and cycles in 3-uniform hypergraphs. More precisely, we prove that for every n ≥ m ≥ 3,. R(Pn3,Pm3)=R(Pn3,Cm3)=R(Cn3,Cm3)+1=2n+⌊m+12⌋, and for every n > m ≥ 3, R(Pm3,Cn3)=2n+⌊m-12⌋. This gives a positive answer to a recent question of Gyárfás and Raeisi. © 2013 Elsevier Inc.
Electronic Journal of Combinatorics (10778926) 20(1)
Recently, asymptotic values of 2-color Ramsey numbers for loose cycles and also loose paths were determined. Here we determine the 2-color Ramsey number of 3-uniform loose paths when one of the paths is significantly larger than the other: for every we show that.
Journal of Combinatorial Designs (15206610) 20(11)pp. 504-507
In this note, we show that for positive integers s and k, there is a function D(s,k) such that every t-(v,k) packing with at least D(s,k) k-t2 t-2vv-2t-2/k-2t-2 edges, 2circk-1, has choice number greater than s. Consequently, for integers s, k, t, and there is a v0(s,k,t) such that every t-(v,k) design with v>v0(s,k,t) has choice number greater than s. © 2012 Wiley Periodicals, Inc.
Optimal Control Applications and Methods (10991514) 32(6)pp. 647-659
An efficient numerical method for finding the solution of piecewise constant delay systems is presented. The method is based upon hybrid of block-pulse functions and Chebyshev polynomials. The operational matrix of delay is constructed. The properties of hybrid functions together with the operational matrices of integration, delay and product are used to convert the delay differential equation to an algebraic equation, thus greatly simplifying the problem. The method is easy to implement and yields very accurate results. The validity and applicability of the proposed method are demonstrated by considering different types of delay systems. © 2010 John Wiley & Sons, Ltd.
