Home  Issues  Aims and Scope  Instructions for Authors 
Special Issue on Selected Papers from the Seventh International Workshop on Algorithms and Computation, WALCOM 2013
DOI: 10.7155/jgaa.00311
Lower bounds for Ramsey numbers for complete bipartite and 3uniform tripartite subgraphs
Vol. 17, no. 6, pp. 671688, 2013. Regular paper.
Abstract Let R(K_{a,b},K_{c,d}) be the minimum number n so that any nvertex simple undirected graph G contains a K_{a,b} or its complement G′ contains a K_{c,d}. We demonstrate constructions showing that R(K_{2,b},K_{2,d}) > b+d+1 for d ≥ b ≥ 2. We establish lower bounds for R(K_{a,b},K_{a,b}) and R(K_{a,b},K_{c,d}) using probabilistic methods. We define R′(a,b,c) to be the minimum number n such that any nvertex 3uniform hypergraph G(V,E), or its complement G′(V,E^{c}) contains a K_{a,b,c}. Here, K_{a,b,c} is defined as the complete tripartite 3uniform hypergraph with vertex set A∪B∪C, where the A, B and C have a, b and c vertices respectively, and K_{a,b,c} has abc 3uniform hyperedges {u,v,w}, u ∈ A, v ∈ B and w ∈ C. We derive lower bounds for R′(a,b,c) using probabilistic methods. We show that R′(1,1,b) ≤ 2b+1. We have also generated examples to show that R′(1,1,3) ≥ 6 and R′(1,1,4) ≥ 7.
Keywords: Ramsey number, bipartite graph, local lemma, probabilistic method, runiform hypergraph. 
Submitted: April 2013.
Reviewed: September 2013.
Revised: October 2013.
Accepted: October 2013.
Final: October 2013.
Published: November 2013.
Communicated by
Subir Kumar Ghosh
