Id: arxiv/2603.08876 Url: https://arxiv.org/abs/2603.08876 Tags: math.CO, cs.DM, math.OC Score: 0 Title: Hierarchical threshold structure in Max-Cut with geometric edge weights Domain: math.CO Source: arxiv Authors: Nevena Marić Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-03-09 Page: https://delphi.science/r/arxiv/2603.08876 We study a family of weighted Max-Cut instances on the complete graph $K_n$ in which edge weights decrease geometrically in lexicographic order: the $i$-th edge has weight $r^{N-i}$ where $N=\binom{n}{2}$. For $r\ge 2$, the lexicographically first cut is optimal; for $r=1$, all edges have equal weight and the balanced partition wins. In this paper we study the intermediate regime $1< r <2$. The geometric weighting makes early edges dominant and singles out the $k$-isolated cuts $C_k=\{1,\dots,k\}\mid\{k+1,\dots,n\}$ as natural candidates for optimality. For each $n$ and $k\le\lfloor…