Perfect-power square-maximality conjecture for induced grid subgraphs

Let d2d\ge2 and n1n\ge1. If SZdS\subset\mathbb{Z}^d has S=nd|S|=n^d and the induced graph Ld[S]\mathcal L_d[S] is connected, then

τ(Ld[S])τ(Pnd).\tau(\mathcal L_d[S])\le \tau(P_n^{\square d}).

Perfect-power square-maximality conjecture. Equality should occur only for the dd-dimensional box PndP_n^{\square d}, up to lattice translation and coordinate permutation.

For d=2d=2, 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

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.