Lower bounds for Ramsey numbers for complete bipartite and 3-uniform tripartite subgraphs

Tapas Kumar Mishra ; Sudebkumar Prasant Pal

Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Seventh International Workshop on Algorithms and Computation, WALCOM 2013 , Tome 17 (2013) no. 6, pp. 671-688.

Résumé

Let R(Ka,b,Kc,d) be the minimum number n so that any n-vertex simple undirected graph G contains a Ka,b or its complement G′ contains a Kc,d. We demonstrate constructions showing that R(K2,b,K2,d) > b+d+1 for d ≥ b ≥ 2. We establish lower bounds for R(Ka,b,Ka,b) and R(Ka,b,Kc,d) using probabilistic methods. We define R′(a,b,c) to be the minimum number n such that any n-vertex 3-uniform hypergraph G(V,E), or its complement G′(V,Ec) contains a Ka,b,c. Here, Ka,b,c is defined as the complete tripartite 3-uniform hypergraph with vertex set A∪B∪C, where the A, B and C have a, b and c vertices respectively, and Ka,b,c has abc 3-uniform 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, r-uniform hypergraph.

Détail

DOI : 10.7155/jgaa.00311

Keywords: Ramsey number, bipartite graph, local lemma, probabilistic method, r-uniform hypergraph