The cycle rainbow matching conjecture

Let CtC_t be the cycle on tt vertices, and let fCt(s,s)f_{C_t}(s,s) denote the least number of independent sets of size ss in CtC_t that guarantees a rainbow independent set of size ss. Cycle rainbow matching conjecture. If

s<t2,s<\frac{t}{2},

then

fCt(s,s)=s.f_{C_t}(s,s)=s.

The source presents this as a possible explanation for the jump between the almost-full and full rainbow matching problems.

Sources & referencesView supporting material

Primary source

Ron Aharoni, Joseph Briggs, Jinha Kim and Minki Kim, “Rainbow independent sets in certain classes of graphs”, arXiv:1909.13143 (2019).

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.