Description
Abstract:
For (finite, simple) bipartite graphs G and H, let R_B(G,H) denote the smallest number b such that each red-blue edge coloring of the complete balanced bipartite graph on b+b vertices contains a red copy of G or a blue copy of H. This variation of the Ramsey problem has been studied for different pairs of G and H. In particular, the function b(n) = R_B(C_4, K_{1,n}) (that is, the bipartite Ramsey number for the 4-cycle and the star with n+1 vertices) has been studied by Carnielli, Goncalves and Monte Carmelo (2000, 2008), where they obtained the upper bound b(n) <= n + [sqrt(n)], and provided constructions that prove this bound sharp in infinitely many cases. Not surprisingly, these constructions are related to the incidence graphs of projective planes. They posed two conjectures, a stronger one claiming that the upper bound is always sharp, and a weaker one saying that b(n) is strictly increasing in n. Studying appropriate subgraphs of the incidence graphs of projective planes, we provide further exact values for b(n), and also show that both conjectures fail for infinitely many values of n. Refuting the first conejcture is rather easy, while the second one is related to some Zarankiewicz numbers and the non-existence of certain nearly generalized polygons. Joint work with Imre Hatala and Sam Mattheus.