Perfect-power square-maximality conjecture for induced grid subgraphs

Less than 1 year old · traced to

Let d≥2d\ge2 and n≥1n\ge1. If S⊂ZdS\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])≤τ(Pn□d).\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 Pn□dP_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.

References

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.