On the bipartition of graphs (Q796548): Difference between revisions

The isoperimetric constant i(G) of a cubic graph G is \(i(G)=\min | \partial U| /| U|\) where \(|.|\) is cardinality, U runs over all subsets of the vertex set VG satisfying \(| U| \leq {1\over2}| VG|\), and \(| \partial U|\) is the number of edges running from U to the complement V\(G\backslash U\). The spectral theory on Riemann surfaces is used to prove that infinitely many cubic graphs G exist satisfying i(G)\(\geq 1/128\).