Compact graph-induced semiseparable representations for two-dimensional mesh graphs

Let M×MM\times M 2D mesh graphs be graphs with the corresponding vertex sets VG\mathbb{V}_\mathbb{G}, and let a Hamiltonian path be a path P\mathbb{P} visiting every vertex exactly once. A GIRS-cc pair is a pair (A,G)(A,\mathbb{G}) satisfying the paper's GIRS rank bound. Mesh-graph compact representation conjecture. There exists a constant γ1\gamma\geq 1 such that for all M×MM\times M 2D mesh graphs G\mathbb{G} there exists a Hamiltonian path P\mathbb{P} such that, if (A,G)(A,\mathbb{G}) is GIRS-cc, then (A,G)(A,\mathbb{G}) possesses a G\mathbb{G}-SS representation with

rig,rihcγr_i^g,r_i^h\leq c\gamma

for every iVGi\in\mathbb{V}_\mathbb{G}. This is the paper's more specific conjecture for a family of graphs; the source gives no resolution.

Sources & referencesView supporting material

Primary source

Shivkumar Chandrasekaran, Ethan N. Epperly and Nithin Govindarajan, “Graph-Induced Rank Structures and their Representations”, arXiv:1911.05858 (2021).

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.