# Asymptotic Rank of Complete Graph Tensors

Preprint · Huanyi Zhou

- Archive id: arxiv:2610.34273
- Published: 2026-10-25
- arXiv: https://arxiv.org/abs/2610.34273
- Citations: 0
- Source URL: https://arxiv.org/abs/2610.34273
- PDF: https://arxiv.org/pdf/2610.34273
- Provenance: arxiv

## Abstract

Graph tensors extend the matrix multiplication tensor by placing a two-party identity tensor on every edge of a graph and keeping one tensor leg at every vertex. We study the asymptotic rank of the tensor associated with the complete graph. For every integer $n\\geq 2$, over the complex numbers, we prove \\\[ \\left\\lfloor\\frac{n^2}{4}\\right\\rfloor \\leq \\log\_2\\widetilde R\\bigl(\\mathsf{GT}\_2(K\_n)\\bigr) \\leq \\frac{n^2}{4}. \\\] The upper bound matches the maximum-cut lower bound for every even $n$ and differs from it by only $1/4$ for every odd $n$. In particular, the exponent per edge is below $2/3$ for every $n\\geq5$, answering a question of Christandl, Vrana, and Zuiddam. Our proof extends the polynomial multiplication approach underlying OpenAI's bound $ω\\leq9/4$. The main step separates any fixed number of shared tensor legs simultaneously, using only linearly many direct-sum copies in the number of blocks. This yields an entropy inequality for higher-order tensors. We apply it to the tensor for multiplying $n-1$ polynomials, whose rank is linear in the input length. Discrete concavity and a shifted tripling inequality then force a lower bound on a symmetrized spectral profile. Comparing this growth with polynomial interpolation gives the stated upper bound while preserving all $n$ tensor legs. We also prove an operational barrier for these higher-order polynomial constructions. For $n\\geq3$, the specified formal reduction rules cannot certify an exponent below $n^2/4$ for $\\mathsf{GT}\_2(K\_n)$, even after taking tensor powers and allowing subexponential overhead and common auxiliary factors. This extends the symmetric three-leg barrier of Amanov, van den Berg, and Zuiddam and explains the remaining gap for odd complete graphs within this method.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Algorithms & Complexity Breakthroughs](https://space-kitty.com/topics/algorithms-complexity)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.