Inherited correspondence between disjoint cycles and non-zero eigenvalues

About 4 years old · traced to

Let G=([n],E)G=([n],E) be a directed graph, and let 0≤k≤n0 \leq k \leq n be an integer. For a subgraph HH of GG, consider collections of disjoint cycles in HH, and let SG\mathcal{S}_G denote the associated matrix space.

Inherited correspondence conjecture. The maximum number of edges in a subgraph HH of GG in which every collection of disjoint cycles covers at most kk vertices equals the largest dimension of a subspace of SG\mathcal{S}_G in which every matrix has at most kk non-zero eigenvalues.

This conjecture seeks to strengthen the established correspondence between collections of disjoint cycles and the non-zero eigenvalues of matrices in SG\mathcal{S}_G. Its proof or disproof is identified by the authors as an interesting open problem.

References

Primary source

Yinan Li, Youming Qiao, Avi Wigderson, Yuval Wigderson and Chuanqi Zhang, “Connections between graphs and matrix spaces”, arXiv:2206.04815 (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.