Variance-optimal functions determine isoperimetric extremizers

At least 8 years old · documented by

Let GG be a graph, let XX be a variance-optimal function over GG, and for suitable rr define Sr={a=(a1,…,an)∈V(Gn):∑i=1nX(ai)≤r}S_r=\{a=(a_1,\ldots,a_n)\in V(G^n):\sum_{i=1}^n X(a_i)\leq r\}. For a vertex set S⊆V(Gn)S\subseteq V(G^n), let Bd(S)={u:dGn(u,S)≤d}B_d(S)=\{u:d_{G^n}(u,S)\leq d\}.

Isoperimetric extremizer conjecture. For nn sufficiently large and d,rd,r in appropriate ranges,

∣Bd(Sr)∣≤∣Bd(S′)∣|B_d(S_r)|\leq |B_d(S')|

for every S′⊂V(Gn)S'\subset V(G^n) with ∣Sr∣≤∣S′∣|S_r|\leq |S'|.

This conjecture proposes that sets formed from variance-optimal functions determine the extremal isoperimetric behavior of Cartesian powers of graphs. The supplied text gives no resolution or precise ranges for dd and rr.

References

Primary source

Matthew Yancey, “Probabilistic and Geometrical Applications to Graph Theory”, arXiv:1705.09725 (2017).

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.