Seminár z teórie grafov - Tamas Héger (29.4.2021)
vo štvrtok 29.4.2021 o 9:50 hod. online formou
Prednášajúci: Tamas Héger (Lorand Eotvos University, Budapest)
Názov: New results for the bipartite Ramsey number of the four-cycle versus stars
Termín: 29.4.2021, 9:50 hod.
Prístupový kód do MS TEAMS (pre používateľov z UK): gglxxc7
Pripojenie (pre hostí mimo UK)
Abstrakt:
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.