Let R ( K a , b , K c , d ) be the minimum number n so that any n -vertex 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 n -vertex 3-uniform 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 3-uniform 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 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 ) ≤ 2 b +1. We have also generated examples to show that R ′(1,1,3) ≥ 6 and R ′(1,1,4) ≥ 7.
展开▼
机译：令R（K a，b ，K c，d ）为最小值n，以便任何n个顶点简单无向图G都包含一个K a， b 或其补码G'包含K c，d 。我们证明了构造，它表明R（K 2，b ，K 2，d ）> b + d +1对于d≥b≥2。我们为R建立下界（K a，b ，K a，b ）和R（K a，b ，K c，d ）使用概率方法。我们将R′（a，b，c）定义为最小数n，以使任何n个顶点3均匀超图G（V，E）或其补码G′（V，E c ）包含K a，b，c 。在这里，K a，b，c 定义为顶点集为A∪B∪C的完整三重三均匀超图，其中A，B和C分别具有a，b和c顶点，并且K a，b，c 具有abc 3均匀超边{u，v，w}，u∈A，v∈B和w∈C。我们使用概率方法得出R'（a，b，c）的下界。我们证明R'（1,1，b）≤2 b +1。我们还生成了一些示例来显示R'（1,1,3）≥6和R'（1,1,4）≥7。
展开▼
