Lexicographic edge-isoperimetric conjecture for generalized expanded Sierpinski graphs

Let S(n,m)S(n,m) be the generalized and expanded Sierpinski graph, with vertex set VS(n,m)={0,1,,m1}nV_{S(n,m)}=\left\{0,1,\ldots,m-1\right\}^{n}. Let LexLex denote the lexicographic order on this vertex set, let Θ(S)\Theta(S) be the edge-boundary of a vertex set SS, and let Θ(S(n,m);)\left\lvert\Theta\right\rvert(S(n,m);\ell) denote the minimum edge-boundary among subsets of VS(n,m)V_{S(n,m)} of cardinality \ell. Lexicographic edge-isoperimetric conjecture. The graph S(n,m)S(n,m) has nested solutions for the edge-isoperimetric problem: for every \ell with 0mn0\leq\ell\leq m^n, the initial \ell-segment of LexLex minimizes the edge-boundary, so that

Θ(Lex1({0,1,,}))=Θ(S(n,m);).\left\lvert\Theta\left(Lex^{-1}\left(\left\{0,1,\ldots,\ell\right\}\right)\right)\right\rvert=\left\lvert\Theta\right\rvert(S(n,m);\ell).

This would establish that lexicographic initial segments solve the edge-isoperimetric problem for every cardinality, beyond the cardinalities at which the sharp lower bound is already known. The source presents the claim as an unproved extension of the preceding theorem; its status is therefore 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.