Isoperimetric numbers and bisection widths of double coverings of a complete graph. (Q2715969)

For a finite simple graph \(G=(V,E)\) its isoperimetric number is \(i(G)=\min _X | \partial X| /| X| \) where \(X\subset V\), \(1\leq | X| \leq | V| /2\), and \(\partial X\) are edges having exactly one end in \(X\). The bisection width of \(G\) is \(b(G)=\min _X | \partial X| \) where \(| X| =\lfloor | V| /2\rfloor \). If \(\phi : E\rightarrow \{1,-1\}\) is a signing of \(G\), \(G^{\phi }\) has vertices \(V'=V\times \{1,-1\}\) and \((u,a),(v,b)\in V'\) form an edge in \(G^{\phi }\) iff \(a=\phi (uv)b\). (It is known that every double covering of \(G\) is a \(G^{\phi }\) + the projection to the first coordinate.) Finally, \(d(G,\phi )\) is the smallest number of changes of the edge signs needed to destroy, in \(G\), every cycle with an odd number of \(-1\) signs. The authors prove that (for any signing \(\phi \) of the graph in question) \(i(G^{\phi })\leq \min (i(G),2d(G,\phi )/| V| )\), \(b(K_m^{\phi })=m\cdot i(K_m^{\phi })\), and \(i(K_m^{\phi })=2d(K_m,\phi )/m\). Spectral estimates of \(i(K_m^{\phi })\) and \(d(K_m,\phi )\) are derived. Finally, it is proved in the article that for every \(d\), \(0\leq d\leq \lfloor (m-1)^2/4\rfloor \), there is a signing \(\phi \) of \(K_m\) such that \(d(K_m,\phi )=d\) (or, equivalently, \(i(K_m^{\phi })=2d/m\)).