The conjectured threshold for graphs with two distinct eigenvalues

At least 2 years old · documented by

For each integer n≥2n\geq 2, let m(n)m(n) denote the least number of edges such that every graph on nn vertices with at least m(n)m(n) edges has a matrix realization with two distinct eigenvalues. Threshold conjecture.

m(2)=1,m(2)=1,

and

m(n)=(n2)−(n−3)m(n)={n\choose 2}-(n-3)

for all n≥3n\geq 3. The values through n=7n=7 support this formula, while the preceding lower bound establishes only that m(n)≥(n2)−(n−3)m(n)\geq {n\choose 2}-(n-3) in the stated range.

References

Primary source

Shaun Fallat and Seyed Ahmad Mojallal, “Spectral Applications of Vertex-Clique Incidence Matrices Associated with a Graph”, arXiv:2307.09663 (2023).

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.