The inertia–bicoloring conjecture for full-rank typical graphs
Statement
Let be a full-rank typical graph. A -partial matrix is a partial symmetric matrix whose specified off-diagonal entries correspond to the edges of ; it is minimally completable to full rank if it has a completion of full rank but no proper submatrix obtained by deleting a specified entry has this property. Write for the complement of , and let denote the common inertia of all completions of , with positive and negative eigenvalues. A proper bicoloring of assigns red or blue to every vertex so that adjacent vertices have different colors. Inertia–bicoloring conjecture. There exists a -partial matrix , minimally completable to full rank, with if and only if has a proper bicoloring with red vertices and blue vertices. The conjecture characterizes the possible inertias of minimally full-rank-completable partial matrices in terms of proper two-colorings of the complement. The stated evidence is that the authors found no full-rank typical graph and corresponding partial matrix whose inertia failed to arise from such a coloring; the general characterization remains open.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.