Subadditivity-plus-sigma conjecture for lexicographic edge boundaries

About 8 years old · traced to

For 0≤ℓb≤ℓa≤mn0\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+ℓb−mn)+m−qn,m(ℓa),ℓa+ℓb≥mn.\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, Lex⁡−1(n,m;ℓ)\operatorname{Lex}^{-1}(n,m;\ell) is the lexicographic initial ℓ\ell-segment in S(n,m)S(n,m), and ∣Θ(Lex⁡−1(n,m;ℓ))∣|\Theta(\operatorname{Lex}^{-1}(n,m;\ell))| is its edge-boundary size.

Subadditivity-plus-sigma conjecture. For all n,m,ℓa,ℓb∈Nn,m,\ell_a,\ell_b\in\mathbb N with mn≥ℓa≥ℓb>0m^n\geq\ell_a\geq\ell_b>0, if ℓa+ℓb≤mn\ell_a+\ell_b\leq m^n, then

∣Θ(Lex⁡−1(n,m;ℓa+ℓb))∣+σn,m(ℓa,ℓb)≤∣Θ(Lex⁡−1(n,m;ℓa))∣+∣Θ(Lex⁡−1(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+ℓb≥mn\ell_a+\ell_b\geq m^n, then

∣Θ(Lex⁡−1(n,m;ℓa+ℓb−mn))∣+σn,m(ℓa,ℓb)≤∣Θ(Lex⁡−1(n,m;ℓa))∣+∣Θ(Lex⁡−1(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.

References

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.