Largest-diameter conjecture for perfect matching association scheme graphs

Let XμX_\mu denote the graph in the perfect matching association scheme associated with the relation indexed by a partition μ\mu of nn. In particular, consider the graph X[2,1n2]X_{[2,1^{n-2}]}.

Largest-diameter conjecture. The diameter of X[2,1n2]X_{[2,1^{n-2}]} is the largest diameter among all graphs in the perfect matching association scheme.

The graph X[2,1n2]X_{[2,1^{n-2}]} is known to have diameter n1n-1, and the conjecture is motivated by the relationship between spectral gap and diameter. The source explicitly presents the claim as a conjecture and does not state that it has been resolved.

Sources & referencesView supporting material

Primary source

Himanshu Gupta, Allen Herman, Alice Lacaze-Masmonteil, Roghayeh Maleki and Karen Meagher, “On the second largest eigenvalue of certain graphs in the perfect matching association scheme”, arXiv:2510.17135 (2025).

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.