Faculty of Mathematics, Physics
and Informatics
Comenius University Bratislava

Seminar of Graph Theory - Tamas Héger (29.4.2021)

Thursday 29.4.2021 at 9:50

27. 04. 2021 22.25 hod.
By: Martin Škoviera

Tamas Héger (Lorand Eotvos University, Budapest):
New results for the bipartite Ramsey number of the four-cycle versus stars

MS TEAMS code (users from Comenius University in Bratislava): gglxxc7
Link (guests outside Comenius University in Bratislava)

Let $b(n)$ denote the smallest integer $b$ such that each red-blue edge coloring of the complete bipartite graph $K_{b,b}$ contains a red $C_4$ or blue $K_{1,n}$. This variation of the Ramsey problem was studied by Carnielli, Goncalves and Monte Carmelo (2000, 2008). They obtained the upper bound b(n) <= n + [sqrt(n)], and provided constructions that prove this bound sharp in infinitely many cases. They also posed two conjectures about $b(n)$. We give further constructions that give equality in this bound, and refute both conjectures. The results rely on projective planes, some Zarankiewicz numbers and the non-existence of certain nearly generalized polygons.

This work is joint with Imre Hatala and Sam Mattheus.

More information