On irredundant Ramsey numbers for graphs

The irredundant Ramsey number s(m, n) is the smallest p such that in every two-coloring of the edges of K_p using colors red (R) and blue (B), either the blue graph contains an m-element irredundant set or the red graph contains an n-element irredundant set. We develop techniques to obtain upper bounds for irredundant Ramsey numbers of the form s(3, n) and prove that 18 ≤ s(3,7) ≤ 19.     

ASYMPTOTIC BOUNDS FOR IRREDUNDANT RAMSEY NUMBERS

Abstract

The irredundant Ramsey number s(m,n) is the smallest N such that in every red-blue colouring of the edges of K_N , either the blue graph contains an m-element irredundant set or the red graph contains an n-element irredundant set. We prove an asymptotic lower bound for s(m, n).     

The irredundant ramsey number s(3, 7)

The irredundant Ramsey number s(m, n) is the smallest p such that for every graph G with p vertices, either G contains an n-element irredundant set or its complement G contains an m-element irredundant set. Cockayne, Hattingh, and Mynhardt have given a computer-assisted proof that s(3, 7) = 18. The purpose of this paper is to give a self-contained proof of this result. © 1995 John Wiley & Sons, Inc.     

Irredundant ramsey numbers for graphs

The irredundant Ramsey number s(m, n) is the least value of p such that for any p-vertex graph G, either G has an irredundant set of at least n vertices or its complement G has an irredundant set of at least m vertices. The existence of these numbers is guaranteed by Ramsey's theorem. We prove that s(3, 3) = 6, s(3, 4) = 8, and s(3,5) = 12.     

The mixed irredundant Ramsey numbers t(3, 7) = 18 and t(3, 8) = 22

Abstract

The mixed irredundant Ramsey number t(m, n) is the smallest natural number t such that if the edges of the complete graph K_t on t vertices are arbitrarily bi-coloured using the colours blue and red, then necessarily either the subgraph induced by the blue edges has an irredundant set of cardinality m or the subgraph induced by the red edges has an independent set of cardinality n (or both). Previously it was known that 18 ≤ t(3, 7) ≤ 22 and 18 ≤ t(3, 8) ≤ 28. In this paper we prove that t(3, 7) = 18 and t(3, 8) = 22.     

On cycle—Complete graph ramsey numbers

A new upper bound is given for the cycle-complete graph Ramsey number r(C_m, K_n), the smallest order for a graph which forces it to contain either a cycle of order m or a set of n independent vertices. Then, another cycle-complete graph Ramsey number is studied, namely r(?C_m, K_n) the smallest order for a graph which forces it to contain either a cycle of order / for some / satisfying 3?/?m or a set of n independent vertices. We obtain the exact value of r(?C_m K_n) for all m > n and an upper bound which applies when m is large in comparison with log n.     

All cycle‐complete graph Ramsey numbers r(Cm,K6)

The cycle‐complete graph Ramsey number r(C_m, K_n) is the smallest integer N such that every graph G of order N contains a cycle C_m on m vertices or has independence number α(G) ≥ n. It has been conjectured by Erd?s, Faudree, Rousseau and Schelp that r(C_m, K_n) = (m ? 1) (n ? 1) + 1 for all m ≥ n ≥ 3 (except r(C₃, K₃) = 6). This conjecture holds for 3 ≤ n ≤ 5. In this paper we will present a proof for n = 6 and for all n ≥ 7 with m ≥ n² ? 2n. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 251–260, 2003     

CO‐irredundant Ramsey numbers for graphs

The study of the CO‐irredundant Ramsey numbers t(n₁, ···, n_k) is initiated. It is shown that several values and bounds for these numbers may be obtained from the well‐studied generalized graph Ramsey numbers and the values of t(4, 5), t(4, 6) and t(3, 3, m) are calculated. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 258–268, 2000     

A Note on Uniquely lntersectable Graphs

The following conjecture of Alter and Wang is proven. Consider the intersection graph G_n,m,n?2m, determined by the family of all m-element subsets of an n-element set. Then any realization of G_n,m as an intersection graph by a family of sets satisfies |∪_iA_i|?n; and if |∪_iA_i|=n, then F must be the family of all m-element subsets of ∪_iA_i.     

Large Kr‐free subgraphs in Ks‐free graphs and some other Ramsey‐type problems

In this paper we present three Ramsey‐type results, which we derive from a simple and yet powerful lemma, proved using probabilistic arguments. Let 3 ≤ r < s be fixed integers and let G be a graph on n vertices not containing a complete graph K_s on s vertices. More than 40 years ago Erd?s and Rogers posed the problem of estimating the maximum size of a subset of G without a copy of the complete graph K_r. Our first result provides a new lower bound for this problem, which improves previous results of various researchers. It also allows us to solve some special cases of a closely related question posed by Erd?s. For two graphs G and H, the Ramsey number R(G, H) is the minimum integer N such that any red‐blue coloring of the edges of the complete graph K_N, contains either a red copy of G or a blue copy of H. The book with n pages is the graph B_n consisting of n triangles sharing one edge. Here we study the book‐complete graph Ramsey numbers and show that R(B_n, K_n) ≤ O(n³/log^3/2n), improving the bound of Li and Rousseau. Finally, motivated by a question of Erd?s, Hajnal, Simonovits, Sós, and Szemerédi, we obtain for all 0 < δ < 2/3 an estimate on the number of edges in a K₄‐free graph of order n which has no independent set of size n^1‐δ. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

Two remarks on the Burr–Erdős conjecture

The Ramsey number r(H) of a graph H is the minimum positive integer N such that every two-coloring of the edges of the complete graph K_N on N vertices contains a monochromatic copy of H. A graph H is d-degenerate if every subgraph of H has minimum degree at most d. Burr and Erdős in 1975 conjectured that for each positive integer d there is a constant c_d such that r(H)≤c_dn for every d-degenerate graph H on n vertices. We show that for such graphs , improving on an earlier bound of Kostochka and Sudakov. We also study Ramsey numbers of random graphs, showing that for d fixed, almost surely the random graph G(n,d/n) has Ramsey number linear in n. For random bipartite graphs, our proof gives nearly tight bounds.     

On a problem of Erdős and Rado

We give some improved estimates for the digraph Ramsey numbersr(K _n ^* ,L _m ), the smallest numberp such that any digraph of orderp either has an independent set ofn vertices or contains a transitive tournament of orderm. By results of Baumgartner and of Erdős and Rado, this is equivalent to the following infinite partition problem: for an infinite cardinal κ and positive integersn andm, find the smallest numberp such that

The value of the Ramsey number r(3, 8)

The Ramsey number R(3, 8) can be defined as the least number n such that every graph on n vertices contains either a triangle or an independent set of size 8. With the help of a substantial amount of computation, we prove that R(3, 8)=28.     

On Ramsey numbers involving starlike multipartite graphs

The Ramsey number r(G, H) is evaluated exactly in certain cases in which both G and H are complete multipartite graphs K(n,₁, n₂, …. n_k). Specifically, each of the following cases is handled whenever n is sufficiently large: r(K(1, m₁, …. m_k), K(1, n)), r(K(1, m), K(n₁, …. n_k, n)), provided m ≧ 4, and r(K(1, 1, m), K(n_k, …, n_k, n)).     

The minimal eigenvalue of the Lyapunov transform †

An (n m) hypergraph is a coupleH=(N E), where the vertex set N is {1,…n} and the edge set E is an m-element multiset of nonempty subsets of N. In this paper, we count nonisomorphic hypergraphs where isomorphism of hypergraphs is the natural extension of that of graphs. A main result is an explicit formula for the cycle index of the permutation representation of any permutation group P with object set N acting on the k-element subsets of N. By making a simple substitution in these cycle indices for P the symmetric group S_N and k=1,…,n, we obtain generating functions which enumerate various types of hypergraphs. Using the technique developed, we extend Snapper's results on characteristic polynomials of permutation representations and group characters from the case where the group has odd order to the general case.     

The Ramsey Numbers of Large cycles Versus Odd Wheels

For given graphs G and H, the Ramsey number R(G, H) is the smallest positive integer N such that for every graph F of order N the following holds: either F contains G as a subgraph or the complement of F contains H as a subgraph. In this paper, we determine the Ramsey number R(C_n, W_m) = 3n − 2 for odd m ≥ 5 and . Surahmat, Ioan Tomescu: Part of the work was done while the first and the last authors were visiting the School of Mathematical Sciences, Government College University, Lahore, Pakistan. Surahmat: Research partially support under TWAS, Trieste, Italy, RGA No: 06-018 RG/MATHS/AS–UNESCO FR: 3240144875.     

Lower bounds for lower Ramsey numbers

For any graph G, let i(G) and μ;(G) denote the smallest number of vertices in a maximal independent set and maximal clique, respectively. For positive integers m and n, the lower Ramsey number s(m, n) is the largest integer p so that every graph of order p has i(G) ≤ m or μ;(G) ≤ n. In this paper we give several new lower bounds for s (m, n) as well as determine precisely the values s(1, n).     

A conjecture of Erd?s on graph Ramsey numbers

The Ramsey number r(G) of a graph G is the minimum N such that every red–blue coloring of the edges of the complete graph on N vertices contains a monochromatic copy of G. Determining or estimating these numbers is one of the central problems in combinatorics.One of the oldest results in Ramsey Theory, proved by Erd?s and Szekeres in 1935, asserts that the Ramsey number of the complete graph with m edges is at most . Motivated by this estimate Erd?s conjectured, more than a quarter century ago, that there is an absolute constant c such that for any graph G with m edges and no isolated vertices. In this short note we prove this conjecture.     

Ramsey functions involving with large

For fixed integers m,k2, it is shown that the k-color Ramsey number r_k(K_m,n) and the bipartite Ramsey number b_k(m,n) are both asymptotically equal to k^mn as n→∞, and that for any graph H on m vertices, the two-color Ramsey number is at most (1+o(1))n^m+1/(logn)^m-1. Moreover, the order of magnitude of is proved to be n^m+1/(logn)^m if H≠K_m as n→∞.     

Ramsey Numbers of Some Bipartite Graphs Versus Complete Graphs

The Ramsey number r(H, K _n ) is the smallest positive integer N such that every graph of order N contains either a copy of H or an independent set of size n. The Turán number ex(m, H) is the maximum number of edges in a graph of order m not containing a copy of H. We prove the following two results: (1) Let H be a graph obtained from a tree F of order t by adding a new vertex w and joining w to each vertex of F by a path of length k such that any two of these paths share only w. Then r(H,K_n) ￡ c_k,t [(n^1+1/k)/(ln^1/k n)]{r(H,K_n)\leq c_{k,t}\, {n^{1+1/k}\over \ln^{1/k} n}} , where c _k,t is a constant depending only on k and t. This generalizes some results in Li and Rousseau (J Graph Theory 23:413–420, 1996), Li and Zang (J Combin Optim 7:353–359, 2003), and Sudakov (Electron J Combin 9, N1, 4 pp, 2002). (2) Let H be a bipartite graph with ex(m, H) = O(m ^γ ), where 1 < γ < 2. Then r(H,K_n) ￡ c_H ([(n)/(lnn)])^1/(2-g){r(H,K_n)\leq c_H ({n\over \ln n})^{1/(2-\gamma)}}, where c _H is a constant depending only on H. This generalizes a result in Caro et al. (Discrete Math 220:51–56, 2000).