Perfect-power square-maximality conjecture for induced grid subgraphs
Perfect-power square-maximality conjecture for induced grid subgraphs
Let and . If has and the induced graph is connected, then
Perfect-power square-maximality conjecture. Equality should occur only for the -dimensional box , up to lattice translation and coordinate permutation.
For , this specializes to the square-maximality conjecture attributed to Procaccia and Tucker-Foltz. For non-perfect-power vertex counts, the expected maximizing induced grid subgraph may be a compact near-box shape rather than a product, so exact maximality remains open beyond the stated perfect-power case.
Sources & referencesView supporting material
Primary source
Jiechen Zhang, “Extremal Spanning Trees in Product Grid Graphs”, arXiv:2606.24016 (2026).
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.