pipette
ENEnglish

Size Ramsey numbers of star forests with two components on one side

Chunlin You

Preprint

En palabras de los autores

We determine the size Ramsey number of a two-component star forest versus an arbitrary star forest. Let be positive integers with and . We prove that \[ \begin{split} \rhat\left(K_{1,a}\sq K_{1,b}, \bigsqcup_{i=1}^{q}K_{1,n_i}\right) ={}&(a+n_1-1) +\sum_{i=1}^{q-1}\max\{a+n_{i+1}-1,b+n_i-1\}\\ &+(b+n_q-1). \end{split} \] This proves the conjecture of Burr, Erd\H{o}s, Faudree, Rousseau and Schelp (Erd\H{o}s Problem~\#561) in the case where one of the two star forests has exactly two components. The formula holds without any restriction on the parity of the star sizes. The proof combines vertex deletion, iterated matching deletion, and Lov\'asz's factor theorem.

Resultado principalLimitación que admiten los autores

Apareció: martes, 20 de octubre. arXiv. Preprint, todavía sin revisión por pares.