Odd-colour phase-transition conjecture for multicoloured connectivity

Let m(n,r,s,k)m(n,r,s,k) denote the largest order guaranteed for a kk-connected subgraph using at most ss colours in every rr-colouring of KnK_n. Let s3s\geq 3, and let nn and kk be sufficiently large. Set r=2s1r=2s-1.

Odd-colour phase-transition conjecture. One has

m(n,2s1,s,k)n(2s(r2)r22r+2)k=n(1+2s54(s1)2+1)k,m(n,2s-1,s,k)\leq n-\left(\frac{2s(r-2)}{r^2-2r+2}\right)k =n-\left(1+\frac{2s-5}{4(s-1)^2+1}\right)k,

where r=2s1r=2s-1.

This conjecture concerns the value to which the function jumps when the number of colours is odd, just below the threshold r=2sr=2s. The case s=2s=2 is known, but the authors conjecture that the analogous general formula gives an upper bound for all s3s\geq 3.

Sources & referencesView supporting material

Primary source

Henry Liu, Robert Morris and Noah Prince, “Highly connected multicoloured subgraphs of multicoloured graphs”, arXiv:math/0702369 (2007).

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.