RUS  ENG
Полная версия
СЕМИНАРЫ

Большой семинар лаборатории комбинаторных и геометрических структур
22 апреля 2021 г. 19:00, Москва, Онлайн! https://zoom.us/j/279059822 пароль: первые шесть цифр числа \pi после запятой


Size-Ramsey numbers of powers of hypergraph trees and long subdivisions

L. Yepremyan


https://youtu.be/x_ckya1Plxo

Аннотация: The $s$-colour size-Ramsey number of a hypergraph $H$ is the minimum number of edges in a hypergraph $G$ whose every $s$-edge-colouring contains a monochromatic copy of $H$. We show that the $s$-colour size-Ramsey number of the $t$-power of the $r$-uniform tight path on $n$ vertices is linear in $n$, for every fixed $r, s, t$, thus answering a question of Dudek, La Fleur, Mubayi, and Rödl (2017). In fact, we prove a stronger result that allows us to deduce that powers of bounded degree hypergraph trees and of ‘long subdivisions’ of bounded degree hypergraphs have size-Ramsey numbers that are linear in the number of vertices. This extends recent results about the linearity of size-Ramsey numbers of powers of bounded degree trees and of long subdivisions of bounded degree graphs.
This is joint work with Shoham Letzter and Alexey Pokrovskiy.


© МИАН, 2024