The largest-Laplacian-eigenvalue conjecture for Hamming graphs

Let H(d,q,j)H(d,q,j) be the Hamming graph on qdq^d vertices, with two vertices adjacent when their Hamming distance is jj. Write

λ=q(q1)j1(d1j1).\lambda=q(q-1)^{j-1}{d-1 \choose j-1}.

Largest-Laplacian-eigenvalue conjecture. If q2q\geq 2 and jdd1qj\geq d-\frac{d-1}{q}, with jj even if q=2q=2, then λ\lambda is the largest Laplacian eigenvalue of H(d,q,j)H(d,q,j). This conjecture identifies the Laplacian eigenvalue arising from the common Hamming-scheme idempotent as the extremal one in the stated parameter range, extending the known max-cut result for the relevant binary Hamming graphs. Its general status is not established in the supplied source.

Sources & referencesView supporting material

Primary source

Edwin R. van Dam and Renata Sotirov, “New bounds for the max-k-cut and chromatic number of a graph”, arXiv:1503.06595 (2015).

Additional references

2 papers in this index state this conjecture (2013–2015). The statement above is taken from the most recent of them; the others are arXiv:1309.2163.

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.