Decorated Sierpinski graph conjecture for the edge-isoperimetric profile

About 8 years old · traced to

Let Ss,t(n,m)S_{s,t}(n,m) be the decorated Sierpinski graph obtained from S(n,m)S(n,m) by attaching exterior edges to corner vertices indexed by I∪KI\cup K, where I={0,1,…,s−1}I=\{0,1,\ldots,s-1\}, J={s,s+1,…,s+t−1}J=\{s,s+1,\ldots,s+t-1\}, and K={s+t,s+t+1,…,m−1}K=\{s+t,s+t+1,\ldots,m-1\}, with s,t∈Ns,t\in\mathbb N and s+t≤ms+t\leq m. Let Θs,t(S)\Theta_{s,t}(S) denote the corresponding boundary, and let Lex⁡−1(n,m;ℓ)=Lex⁡−1({1,2,…,ℓ})\operatorname{Lex}^{-1}(n,m;\ell)=\operatorname{Lex}^{-1}(\{1,2,\ldots,\ell\}) in Ss,t(n,m)S_{s,t}(n,m). Write ∣Θs,t∣(Ss,t(n,m);ℓ)|\Theta_{s,t}|(S_{s,t}(n,m);\ell) for the minimum boundary size among ℓ\ell-vertex sets.

Decorated Sierpinski graph conjecture. For every ℓ\ell with 0≤ℓ≤mn0\leq\ell\leq m^n,

∣Θs,t∣(Ss,t(n,m);ℓ)=∣Θs,t(Lex⁡−1(n,m;ℓ))∣.|\Theta_{s,t}|(S_{s,t}(n,m);\ell)=|\Theta_{s,t}(\operatorname{Lex}^{-1}(n,m;\ell))|.

This conjecture was stated in the cited earlier work as a decorated analogue of the lexicographic edge-isoperimetric assertion. The supplied text gives no evidence that it has been resolved.

References

Primary source

L. H. Harper, “The Edge-Isoperimetric Problem on Sierpinski Graphs: Final Resolution”, arXiv:1802.08355 (2018).

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.