Generalized edge-isoperimetric conjecture for Sierpinski graphs with exterior boundary conditions

About 10 years old · traced to

Let I={0,1,…,s−1}I=\left\{0,1,\ldots,s-1\right\}, J={s,s+1,…,s+t−1}J=\left\{s,s+1,\ldots,s+t-1\right\}, and K={s+t,s+t+1,…,m−1}K=\left\{s+t,s+t+1,\ldots,m-1\right\}, where s,t≥0s,t\geq0 and s+t≤ms+t\leq m. Let Ss,t(n,m)S_{s,t}(n,m) be the graph S(n,m)S(n,m) with exterior edges attached to the corner vertices indexed by I∪KI\cup K. In computing ∣Θs,t(S)∣\left\lvert\Theta_{s,t}(S)\right\rvert, treat the exterior endpoint corresponding to i∈Ii\in I as belonging to SS, and the one corresponding to i∈Ki\in K as belonging to the complement; vertices indexed by JJ remain corner vertices without exterior edges. Let LexLex be the lexicographic order and let ∣Θs,t∣(Ss,t(n,m);ℓ)\left\lvert\Theta_{s,t}\right\rvert(S_{s,t}(n,m);\ell) be the minimum boundary size among subsets of cardinality ℓ\ell. Generalized exterior-boundary conjecture. For every ℓ\ell with 0≤ℓ≤mn0\leq\ell\leq m^n,

∣Θs,t∣(Ss,t(n,m);ℓ)=∣Θs,t(Lex−1(ℓ))∣.\left\lvert\Theta_{s,t}\right\rvert\left(S_{s,t}(n,m);\ell\right)=\left\lvert\Theta_{s,t}\left(Lex^{-1}(\ell)\right)\right\rvert.

This extends the proposed lexicographic optimality from the ordinary generalized expanded Sierpinski graph to graphs with prescribed exterior boundary conditions. The source gives no proof or resolution, so the conjecture remains open.

References

Primary source

L. H. Harper, “The edge-isorperimetric problem on Sierpinski graphs”, arXiv:1610.02089 (2016).

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.