Essential tightness conjecture for the complete-graph rigidity parameter

About 4 years old · traced to

Let ad(Kn)a_d(K_n) denote the parameter associated with dd-dimensional algebraic connectivity for the complete graph KnK_n. Complete-graph tightness conjecture. If n≥2dn\geq 2d, then

⌊n2d⌋≤ad(Kn)≤n2d.\left\lfloor\frac{n}{2d}\right\rfloor\leq a_d(K_n)\leq \frac{n}{2d}.

The conjecture asserts that the lower bound from the preceding theorem is essentially tight. The upper bound is included in the conjectured estimate, and no resolution is supplied in the source.

References

Primary source

Alan Lew, Eran Nevo, Yuval Peled and Orit E. Raz, “On the d-dimensional algebraic connectivity of graphs”, arXiv:2205.05530 (2022).

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.