The edge-isoperimetric problem for discrete tori (Q1613525)

In a graph \(G=(V_G,E_G)\), with \(A\subseteq V_G\), \(I_G(A)=\{(u,v)\in E_G:u,v\in A\}\) and \(I_G(t)=\max_{|A|=t}|I_G(A)|\). The edge-isoperimetric problem is to find optimal sets \(A\), where the maximum \(I_G(t)\) is realized. \(G\) is said to have nested optimal subsets if there is a total order on \(V_G\), called an optimal order, relative to which, for \(t=1,2,\dots, |V_G|\), the initial segment of \(V_G\) of size \(t\) is optimal. In the context of edge-isoperimetric problems for Cartesian powers of graphs [cf. \textit{S. L. Bezrukov}, Bolyai Soc. Math. Stud. 7, 157-197 (1999; Zbl 0927.05080)], the author is specifically interested in discrete tori -- Cartesian products of cycles. From the author's introduction: ``\(C_k^n\) has nested optimal subsets for \(k=3,4\), the optimal order being lexicographic [\textit{L. H. Harper}, J. Appl. Probab. 4, 397-401 (1967; Zbl 0173.21203), \textit{J. H. Lindsay II}, Am. Math. Mon. 71, 508-516 (1964; Zbl 0279.05019)]. For \(k>5\), \(C_k^n\) does not have nested optimal subsets.'' On the vertices of a pentagon \(C_5\) the order \({\mathcal C}_5\) is defined by labelling adjacent vertices 0, 1, 2, 3, 4, (followed by 0). An order \({\mathcal C}_5^k\) is defined recursively for \(k\geq 1\). Theorem 1. Let \(F^n(t)\) be the initial segment of \(V_{ C^n_5}\) under order \({\mathcal C}^n_5\) with length \(t\). Then, for any \(n\geq 1\) and \(t=1,\dots,5^n\), the set \(F^n(t)\) is optimal. ``The structure of (the) proof is roughly analogous to, and inspired by, the corresponding proof in [\textit{S. L. Bezrukov, S. K. Das} and \textit{R. Elsässer}, Ann. Comb. 4, 153-169 (2000; Zbl 0951.05053)] for the Petersen graph.'' \(T(0,i,j,k)\) and \(T(n,i,j,k)\) are defined to be, respectively, \(C_5^i\times C_4^j\times C_5^k\) and \(C_n\times C_5^i\times C_4^j\times C_5^k\). Theorem 5. For \(i,j,k\geq 0\) and \(n>5\), \(T(0,i,j,k)\) and \(T(n,i,j,k)\) have nested optimal subsets. An optimum order is given, and it is conjectured that these are the only discrete tori having nested optimal subsets.