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

Let I={0,1,,s1}I=\left\{0,1,\ldots,s-1\right\}, J={s,s+1,,s+t1}J=\left\{s,s+1,\ldots,s+t-1\right\}, and K={s+t,s+t+1,,m1}K=\left\{s+t,s+t+1,\ldots,m-1\right\}, where s,t0s,t\geq0 and s+tms+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 IKI\cup K. In computing Θs,t(S)\left\lvert\Theta_{s,t}(S)\right\rvert, treat the exterior endpoint corresponding to iIi\in I as belonging to SS, and the one corresponding to iKi\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 0mn0\leq\ell\leq m^n,

Θs,t(Ss,t(n,m);)=Θs,t(Lex1()).\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.

Sources & referencesView supporting material

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.