Multicolor Burr–Erdős–Faudree–Rousseau–Schelp conjecture for star forests

At least 4 years old · documented by

Let p1,p2,…,pqp_1,p_2,\ldots,p_q be positive integers, and for each i∈{1,…,q}i\in\{1,\ldots,q\} let

ni1≥ni2≥⋯≥nipin_{i_1}\geq n_{i_2}\geq \cdots\geq n_{i_{p_i}}

be positive integers. Set p=∑i=1qpip=\sum_{i=1}^{q}p_i, and let F1,F2,…,FqF_1,F_2,\ldots,F_q be star forests with

Fi=⨆j=1piK1,nij.F_i=\bigsqcup_{j=1}^{p_i}K_{1,n_{i_j}}.

For k=q,…,pk=q,\ldots,p, define

lk=max⁡{(n1j1−1)+(n2j2−1)+⋯+(nqjq−1)+1:j1+j2+⋯+jq=k}.l_k=\max\{(n_{1_{j_1}}-1)+(n_{2_{j_2}}-1)+\cdots+(n_{q_{j_q}}-1)+1:j_1+j_2+\cdots+j_q=k\}.

Multicolor star-forest conjecture. The multicolor size Ramsey number satisfies

r^(F1,F2,…,Fq)=∑k=qplk.\hat{r}(F_1,F_2,\ldots,F_q)=\sum_{k=q}^{p}l_k.

The equality is proposed as an extension of the two-color conjecture. The preceding construction establishes the corresponding upper bound, but the source gives no resolution of equality in general, so the conjecture is recorded as open.

References

Primary source

Akbar Davoodi, Ramin Javadi, Azam Kamranian and Ghaffar Raeisi, “On a Conjecture of Erdős on Size Ramsey Number of Star Forests”, arXiv:2111.02065 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.