{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-03-09","reactions":{}}