The largest-Laplacian-eigenvalue conjecture for Hamming graphs

About 13 years old · traced to

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(q−1)j−1(d−1j−1).\lambda=q(q-1)^{j-1}{d-1 \choose j-1}.

Largest-Laplacian-eigenvalue conjecture. If q≥2q\geq 2 and j≥d−d−1qj\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.

References

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.