Lexicographic edge-isoperimetric conjecture for generalized expanded Sierpinski graphs

About 10 years old · traced to

Let S(n,m)S(n,m) be the generalized and expanded Sierpinski graph, with vertex set VS(n,m)={0,1,…,m−1}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 0≤ℓ≤mn0\leq\ell\leq m^n, the initial ℓ\ell-segment of LexLex minimizes the edge-boundary, so that

∣Θ(Lex−1({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.

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.