Let $C_k$ be the cycle on $k$ vertices and $H$ be an arbitrary graph on $m$ edges and no isolated vertices. Erd{\H o}s, Faudree, Rousseau and Schelp conjectured that if $m$ is sufficiently large compared to $k$ then the Ramsey number $R(C_k,H)$ is at most $2m+\left\lfloor\frac{k-1}{2}\right\rfloor$. This was verified for $k$ even and for $k\in\{3,5\}$.
In this talk, we present a resolution of all remaining cases, thus confirming the conjecture. This is joint work with Stijn Cambie, Patryk Morawski, Kalina Petrova and Alexey Pokrovskiy
Legyen $G_1, G_2$ két gráf. $G_1$ parkettázható $G_2$ példányokkal, ha le tudunk úgy rakni csúcsdiszjunkt $G_2$-ket $G_1$-be, hogy ne maradjon ki csúcsa $G_1$-nek. Majdnem parkettázható, ha egy "kevés", általában konstans sok, néha kis lineáris számú csúcs kimaradhat.
Verstraete 2002-es sejtése úgy szól, hogy ha G egy $n$ csúcsú $r$-reguláris (minden csúcs foka $r$) gráf, $H$ egy rögzített gráf, akkor van $H$-nak olyan $TH$ felosztása (minden élt helyettesítünk egy $s\ge 2$ hosszú úttal, és $TH$ páros legyen), hogy $G$ majdnem parkettázható $TH$ példányokkal, legfeljebb konstans sok maradhat ki. Pár évvel később Kühn és Osthus belátták a sejtést arra az esetre, ha $r=cn$ valamely $c>0$ konstansra, illetve approximációt adtak arra az esetre, ha $TH$ helyett $H$-val parkettázunk, ahol $H$ páros.
Az utóbbi időben (2025-ben és 2026-ban) megjelent pár cikk, amik igen közel kerültek a sejtésnek, vagy valamely változatának a megoldásához. Montgomery, Petrova, Ranganathan és Tan belátták a sejtés egy approximációs változatát, ha $r$ egy elég nagy konstans. Letzter, Methuku és Sudakov bebizonyították, hogy $H$ példányokkal majdnem parkettázható $G$, csak konstans sok csúcs marad ki, ha $r=cn$ valamely $c>0$ számra. Azt is belátták, hogy ha $r=polylog(n)$, $H$ rőgzített, akkor $TH$ példányokkal majdnem parkettázható $G$, csak $o(n)$ csúcs marad fedetlen $G$-ben.
Ezekről a tételekről és egy ezeket kiegészítő friss eredményemről szeretnék beszélni.
Raimi's theorem guarantees the existence of a partition of $\mathbb{N}$ into two parts with an unavoidable intersection property: for any finite coloring of $\mathbb{N}$, some color class intersects both parts infinitely many times, after an appropriate shift (translation). We extend this result to higher dimension, in fact a stronger form that the traslation will be "polynomial" shifts.
We also prove some finite analogues of the above results for abelian groups and $SL_2(\mathbb{F}_q)$.
This is a joint work with János Pach and Thang Pham.
Az előadás a következő probléma általánosításairól szól: Maximum hány háromszög lehet egy $n$-csúcsú gráfban, amely nem tartalmaz $K_{2,2,1}$-t mint részgráf?