Fakulta matematiky, fyziky
a informatiky
Univerzita Komenského v Bratislave

Seminár z teórie grafov - Tamas Héger (29.4.2021)

vo štvrtok 29.4.2021 o 9:50 hod. online formou


27. 04. 2021 22.20 hod.
Od: Martin Škoviera

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.


Stránka seminára