OAI.UniformSparsestCut.mainGap

The theorem states that there exists a real constant c > 0 and, for each natural number j, a size n_j ≥ 2 together with a capacity C_j on n_j points (a nonnegative, symmetric function cap on pairs of indices in Fin n_j with zero diagonal), such that n_j tends to infinity as j → ∞, the value glValue(C_j) defined below is strictly positive for every j, and for all sufficiently large j the ratio OPT(C_j)/glValue(C_j) is at least c·√(log n_j)/(log log n_j)^3. Here OPT(C) is the infimum, over nonempty proper subsets B of the points, of the cut ratio: the total capacity across the cut between B and its complement divided by |B|(n − |B|). glValue(C) is the infimum of Σ_{i<j} cap(i,j)·d(i,j) over feasible d, where feasible means d is of negative type (d(i,j) = ‖x_i − x_j‖² for some vectors x_i in Euclidean space of dimension n, and d satisfies the triangle inequality d(i,k) ≤ d(i,j) + d(j,k)) and the sum of d(i,j) over pairs i<j equals 1. The statement is existential and is admitted without proof.