Search

For a graph G and integers a i ≥ 1 , the expression G → (a 1 , ... , a r) v means that for any r-coloring of the vertices of G there exists a monochromatic a i -clique in G for some color i ∈ { 1 , ... , r } . The vertex Folkman numbers are defined as F v (a 1 , ... , a r ; H) = min { | V (G) | : G is H-free and G → (a 1 , ... , a r) v } , where H is a graph. Such vertex Folkman numbers have been extensively studied for H = K s with s > max { a i } 1 ≤ i ≤ r . If a i = a for all i, then we use notation F v (a r ; H) = F v (a 1 , ... , a r ; H) . Let J k be the complete graph K k missing one edge, i.e. J k = K k - e . In this work we focus on vertex Folkman numbers with H = J k , in particular for k = 4 and a i ≤ 3 . A result by Nešetřil and Rödl from 1976 implies that F v (3 r ; J 4) is well defined for any r ≥ 2 . We present a new and more direct proof of this fact. The simplest but already intriguing case is that of F v (3 , 3 ; J 4) , for which we establish the upper bound of 135 by using the J 4 -free process. We obtain the exact values and bounds for a few other small cases of F v (a 1 , ... , a r ; J 4) when a i ≤ 3 for all 1 ≤ i ≤ r , including F v (2 , 3 ; J 4) = 14 , F v (2 4 ; J 4) = 15 , and 22 ≤ F v (2 5 ; J 4) ≤ 25 . Note that F v (2 r ; J 4) is the smallest number of vertices in any J 4 -free graph with chromatic number r + 1 . Most of the results were obtained with the help of computations, but some of the upper bound graphs we found are interesting by themselves. [ABSTRACT FROM AUTHOR]

Let G and H be finite undirected graphs. The Ramsey number R(G, H) is the smallest integer n such that for every graph F of order n, either F contains a subgraph isomorphic to G or its complement F ¯ contains a subgraph isomorphic to H. An (s, t)-graph is a graph that contains neither a clique of order s nor an independent set of order t. In this paper we obtain some inequalities involving Ramsey numbers of the form R (K 4 - e , K t) . In particular, a constructive proof implies that if G is a (k , s + 1) -graph, H is a (k , t + 1) -graph, and both G and H contain a (K k - e) -free graph M as an induced subgraph, then we have R (K k + 1 - e , K s + t + 1) > | V (G) | + | V (H) | + | V (M) |. Furthermore, if s ≤ t , then R (K 4 - e , K s + t + 1) ≥ R (3 , s + 1) + R (3 , t + 1) + s . In the experimental part, we use the (K 4 - e) -free graph generation process to construct graphs witnessing lower bounds for R (K 4 - e , K t) , and compare the results obtained by this approach to the results obtained by analogous triangle-free process. Finally, some open problems involving Ramsey numbers of the form R (K 4 - e , K t) and their asymptotics are posed. [ABSTRACT FROM AUTHOR]

For an undirected simple graph G, we write G→(H1,H2)v if and only if for everyred-blue coloring of its vertices there exists a red H1 or a blue H2. Thegeneralized vertex Folkman number Fv(H1,H2;H) is defined as the smallest integer n for which there exists an H-free graph G of order n such that G→(H1,H2)v. The generalized edge Folkman numbers Fe(H1,H2;H) are defined similarly, when colorings of the edges are considered. We show that Fe(Kk+1,Kk+1;Kk+2-e) and Fv(Kk,Kk;Kk+1-e) are well defined for k≥3. We prove the nonexistence of Fe(K3,K3;H) for some H, in particular for H=B3, where Bk is the book graph of k triangular pages, and for H=K1+P4. We pose three problems ongeneralized Folkman numbers, including the existence question of edge Folkmannumbers Fe(K3,K3;B4), Fe(K3,K3;K1+C4) and Fe(K3,K3;P2∪P3¯). Our results lead to some general inequalities involving two-color and multicolor Folkmannumbers. [ABSTRACT FROM AUTHOR]

Let Δ s = R ( K 3 , K s ) − R ( K 3 , K s − 1 ) , where R ( G , H ) is the Ramsey number of graphs G and H defined as the smallest n such that any edge coloring of K n with two colors contains G in the first color or H in the second color. In 1980, Erdős and Sós posed some questions about the growth of Δ s . The best known concrete bounds on Δ s are 3 ≤ Δ s ≤ s , and they have not been improved since the stating of the problem. In this paper we present some constructions, which imply in particular that R ( K 3 , K s ) ≥ R ( K 3 , K s − 1 − e ) + 4 , and R ( 3 , K s + t − 1 ) ≥ R ( 3 , K s + 1 − e ) + R ( 3 , K t + 1 − e ) − 5 for s , t ≥ 3 . This does not improve the lower bound of 3 on Δ s , but we still consider it a step towards to understanding its growth. We discuss some related questions and state two conjectures involving Δ s , including the following: for some constant d and all s it holds that Δ s − Δ s + 1 ≤ d . We also prove that if the latter is true, then lim s → ∞ Δ s / s = 0 . [ABSTRACT FROM AUTHOR]

In this paper, we study Shannon capacity of channels in the context of classical Ramsey numbers. We overview some of the results on capacity of noisy channels modeled by graphs, and how some constructions may contribute to our knowledge of this capacity. We present an improvement to the constructions by Abbott and Song and thus establish new lower bounds for a special type of multicolor Ramsey numbers. We prove that our construction implies that the supremum of the Shannon capacity over all graphs with independence number 2 cannot be achieved by any finite graph power. This can be generalized to graphs with bounded independence number. [ABSTRACT FROM AUTHOR]

Abstract: For given graphs , the three-color Ramsey number is defined to be the least positive integer such that every 3-coloring of the edges of complete graph contains a monochromatic copy of colored with , for some . In this paper, we prove that , , , , for ; , , for . [Copyright &y& Elsevier]

For positive integers s and t, the Ramsey number R (s , t) is the smallest positive integer n such that every graph of order n contains either a clique of order s or an independent set of order t. The triangle-free process begins with an empty graph of order n, and iteratively adds edges chosen uniformly at random subject to the constraint that no triangle is formed. It has been an important tool in studying the asymptotic lower bound for R (3 , t) . Cyclic graphs are vertex-transitive. The symmetry of cyclic graphs makes it easier to compute their independent numbers than related general graphs. In this paper, the cyclic triangle-free process is studied. The sizes of the parameter sets and the independence numbers of the graphs obtained by the cyclic triangle-free process are studied. Lower bounds on R (3 , t) for small t's are computed, and R (3 , 35) ≥ 237 , R (3 , 36) ≥ 244 , R (3 , 37) ≥ 255 , R (3 , 38) ≥ 267 , etc. are obtained based on the graphs obtained by the cyclic triangle-free process. Finally, some problems on the cyclic triangle-free process and R (3 , t) are proposed. [ABSTRACT FROM AUTHOR]

Let R (k 1 , ... , k r) denote the classical r -color Ramsey number for integers k i ≥ 2. The Diagonal Conjecture (DC) for classical Ramsey numbers poses that if k 1 , ... , k r are integers no smaller than 3 and k r − 1 ≤ k r , then R (k 1 , ... , k r − 2 , k r − 1 − 1 , k r + 1) ≤ R (k 1 , ... , k r). We obtain some implications of this conjecture, present evidence for its validity, and discuss related problems. Let R r (k) stand for the r -color Ramsey number R (k , ... , k). It is known that lim r → ∞ R r (3) 1 ∕ r exists, either finite or infinite, the latter conjectured by Erdős. This limit is related to the Shannon capacity of complements of K 3 -free graphs. We prove that if DC holds, and lim r → ∞ R r (3) 1 ∕ r is finite, then lim r → ∞ R r (k) 1 ∕ r is finite for every integer k ≥ 3. [ABSTRACT FROM AUTHOR]

Abstract: New lower bounds for seven classical Ramsey numbers are obtained by considering some circulant graphs with whose orders might be either prime or not. The results are ,. [Copyright &y& Elsevier]