The random-eigenvector probability conjecture for transitive graphs
The random-eigenvector probability conjecture for transitive graphs
Let be a transitive -regular graph, let be an eigenvalue of its adjacency matrix, and let be the independent set obtained from a random unit eigenvector in the -eigenspace by selecting vertices whose value is larger than at each neighbor. Write for the relative volume of the regular spherical simplex associated with pairwise angle .
Random-eigenvector probability conjecture. For any transitive graph ,
for any eigenvalue , or at least for sufficiently small , namely for some . Consequently, if , the independence ratio of is at least .
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.