Inherited correspondence between disjoint cycles and non-zero eigenvalues

Let G=([n],E)G=([n],E) be a directed graph, and let 0kn0 \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.

Sources & referencesView supporting material

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.