Conjecture on the exact value of m(n,r,1,k)

About 19 years old · traced to

Let m(n,r,1,k)m(n,r,1,k) denote the largest integer such that every rr-colouring of the edges of KnK_n contains a monochromatic kk-connected subgraph on at least m(n,r,1,k)m(n,r,1,k) vertices. Let n,k,r∈Nn,k,r\in\mathbb{N} satisfy

r⩾3,n⩾2r(k−1)+1,r\geqslant 3,\qquad n\geqslant 2r(k-1)+1,

with r−1r-1 a prime power and n−r(k−1)n-r(k-1) divisible by (r−1)2(r-1)^2.

Exact-value conjecture. Under these conditions,

m(n,r,1,k)=n−k+1r−1.m(n,r,1,k)=\frac{n-k+1}{r-1}.

The preceding upper and lower bounds motivate this exact formula. The lower bound on nn is sharp in the stated sense, since m(n,r,1,k)=0m(n,r,1,k)=0 when n⩽2r(k−1)n\leqslant 2r(k-1). The conjecture identifies the remaining value in the specified arithmetic range.

References

Primary source

Henry Liu, Robert Morris and Noah Prince, “Highly connected monochromatic subgraphs of multicoloured graphs”, arXiv:math/0702354 (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.