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

From papers

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,rNn,k,r\in\mathbb{N} satisfy

r3,n2r(k1)+1,r\geqslant 3,\qquad n\geqslant 2r(k-1)+1,

with r1r-1 a prime power and nr(k1)n-r(k-1) divisible by (r1)2(r-1)^2.

Exact-value conjecture. Under these conditions,

m(n,r,1,k)=nk+1r1.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 n2r(k1)n\leqslant 2r(k-1). The conjecture identifies the remaining value in the specified arithmetic range.

Progress summary

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

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.