The random-eigenvector probability conjecture for transitive graphs

Let GG be a transitive dd-regular graph, let λ \lambda be an eigenvalue of its adjacency matrix, and let I+I_{+} be the independent set obtained from a random unit eigenvector in the λ \lambda-eigenspace by selecting vertices whose value is larger than at each neighbor. Write qd(λ)q_d(\lambda) for the relative volume of the regular spherical simplex associated with pairwise angle arccos(d2λ2(d1)) \arccos\left(\frac{d-2-\lambda}{2(d-1)}\right).

Random-eigenvector probability conjecture. For any transitive graph GG,

P(vI+)qd(λ)P(v \in I_{+}) \geq q_d(\lambda)

for any eigenvalue λ\lambda, or at least for sufficiently small λ\lambda, namely λλ0\lambda\leq\lambda_0 for some λ0\lambda_0. Consequently, if λminλ0\lambda_{\min}\leq\lambda_0, the independence ratio of GG is at least qd(λmin)q_d(\lambda_{\min}).

For cherry-transitive graphs equality holds by symmetry, so the conjecture asserts that the probability is no smaller in the general transitive case. Its status is not resolved in the supplied source.

Sources & referencesView supporting material

Primary source

Viktor Harangi and Bálint Virág, “Independence ratio and random eigenvectors in transitive graphs”, arXiv:1308.5173 (2015).

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.