The conjectured threshold for graphs with two distinct eigenvalues

For each integer n2n\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)(n3)m(n)={n\choose 2}-(n-3)

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

Sources & referencesView supporting material

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.