Babai spectrum conjecture for paths

From papers

Let nn and kk be fixed positive integers with

n2<kn1,\left\lfloor \frac{n}{2} \right\rfloor < k \leq n-1,

and let m{2,3,,n1}m\in\{2,3,\ldots,n-1\} be the unique integer satisfying

nnm<knnm+1.n-\left\lceil \frac{n}{m} \right\rceil < k \leq n-\left\lceil \frac{n}{m+1} \right\rceil.

For the path PnP_n and its kk-Babai spectrum Spec(Pn,k)\operatorname{Spec}(P_n,k), the preceding theorem gives

{m+1,m+2,,k+1}Spec(Pn,k).\{m+1,m+2,\ldots,k+1\}\subseteq \operatorname{Spec}(P_n,k).

Babai spectrum conjecture for paths. Under these hypotheses,

Spec(Pn,k)={m+1,m+2,,k+1}.\operatorname{Spec}(P_n,k)=\{m+1,m+2,\ldots,k+1\}.

The conjecture strengthens the preceding theorem's inclusion to an exact description of the Babai spectrum. The authors say that numerical examples motivate it, but no resolution is supplied in the source.

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

Peter Johnson, Celalettin Kaya and Ryan W. Matzke, “Babai Numbers and Babai Spectra of Paths and Cycles”, arXiv:2409.04869 (2024).

Additional references

3 papers in this index state this conjecture (2014–2024). The statement above is taken from the most recent of them; the others are arXiv:2005.02797, arXiv:1412.1438.

Solutions 0

No solutions have been posted yet.