Subadditivity-plus-sigma conjecture for lexicographic edge boundaries

For 0bamn0\leq \ell_b\leq\ell_a\leq m^n, define

σn,m(a,b)={qn,m(b)+qn,m(a+b)qn,m(a),a+b<mn,qn,m(b)qn,m(a+bmn)+mqn,m(a),a+bmn.\sigma_{n,m}(\ell_a,\ell_b)= \begin{cases} q_{n,m}(\ell_b)+q_{n,m}(\ell_a+\ell_b)-q_{n,m}(\ell_a),&\ell_a+\ell_b<m^n,\\ q_{n,m}(\ell_b)-q_{n,m}(\ell_a+\ell_b-m^n)+m-q_{n,m}(\ell_a),&\ell_a+\ell_b\geq m^n. \end{cases}

Here qn,mq_{n,m} is the previously defined auxiliary function, Lex1(n,m;)\operatorname{Lex}^{-1}(n,m;\ell) is the lexicographic initial \ell-segment in S(n,m)S(n,m), and Θ(Lex1(n,m;))|\Theta(\operatorname{Lex}^{-1}(n,m;\ell))| is its edge-boundary size.

Subadditivity-plus-sigma conjecture. For all n,m,a,bNn,m,\ell_a,\ell_b\in\mathbb N with mnab>0m^n\geq\ell_a\geq\ell_b>0, if a+bmn\ell_a+\ell_b\leq m^n, then

Θ(Lex1(n,m;a+b))+σn,m(a,b)Θ(Lex1(n,m;a))+Θ(Lex1(n,m;b)).|\Theta(\operatorname{Lex}^{-1}(n,m;\ell_a+\ell_b))|+\sigma_{n,m}(\ell_a,\ell_b) \leq |\Theta(\operatorname{Lex}^{-1}(n,m;\ell_a))|+|\Theta(\operatorname{Lex}^{-1}(n,m;\ell_b))|.

If a+bmn\ell_a+\ell_b\geq m^n, then

Θ(Lex1(n,m;a+bmn))+σn,m(a,b)Θ(Lex1(n,m;a))+Θ(Lex1(n,m;b)).|\Theta(\operatorname{Lex}^{-1}(n,m;\ell_a+\ell_b-m^n))|+\sigma_{n,m}(\ell_a,\ell_b) \leq |\Theta(\operatorname{Lex}^{-1}(n,m;\ell_a))|+|\Theta(\operatorname{Lex}^{-1}(n,m;\ell_b))|.

For m=3m=3, related strengthened subadditivity inequalities had already been proved, while this statement is presented as their generalization to arbitrary mm. It was introduced as a sufficient ingredient for proving the main lexicographic edge-isoperimetric conjecture.

Sources & referencesView supporting material

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.