10 Lectures and 42 Open Problems — Random k-lifts of graphs

Definitions and mathematical statement

For a random $N\times N$ matrix $A$ over ${\mathbb{R}}$ or ${\mathbb{C}}$ and a positive integer $k$, the tensor power is the random operator $A^{\otimes k}$ on the $k$-fold tensor product, with entries \[ (A^{\otimes k})_{(i_1,\ldots,i_k),(j_1,\ldots,j_k)} =\prod_{s=1}^k A_{i_sj_s}. \] Every factor uses the same realization of $A$, not independent copies. The target quantity in the source is \[ {\mathbb{E}}\left\|A^{\otimes k}-{\mathbb{E}}[A^{\otimes k}]\right\|. \] The centering is the expectation of the tensor power, not generally $({\mathbb{E}} A)^{\otimes k}$. Under the usual spectral-norm interpretation, the norm is the operator norm for the Euclidean tensor-product inner product; the extract does not specify its norm convention. The expectations require the corresponding moments to exist, for example under the sufficient condition ${\mathbb{E}}\|A\|^k<\infty$ in this convention.

Bandeira asks for a tight upper bound on this expected norm, in the random-graph-lift setting indicated by the title. The record does not define $A$, its probability law, normalization, base graph, lift size, dimension, or the role and range of $k$ relative to those parameters. In particular, it does not identify $A$ as a particular adjacency operator or specify that tensor order and lift degree coincide. No ensemble or independence assumptions are invented here.

A meaningful bound must state its dependence on those missing parameters and what tightness means, such as a sharp leading term or matching scale. Without any law or normalization there can be no numerical uniform bound over all random matrices; rescaling $A$ rescales the displayed quantity by the corresponding $k$th power. The task is therefore an underspecified ensemble-dependent estimate, not a universal assertion over arbitrary matrices.

The supplied partial-progress summary mentions random-lift new-eigenvalue bounds at the $2\sqrt{\Delta-1}$ scale, general lift norm estimates, and Bordenave--Collins tensor-product and quantum-expander work. It gives no exact hypotheses or theorem identifying the requested centered tensor expectation, and expressly says a tight bound for the literal quantity was not certified. These are attributed contextual claims, not a verified bound for this problem.

Short English statement

Find a sharp expected operator-norm bound for the centered tensor power of the random matrix intended by the graph-lift source. The same matrix occurs in every tensor factor. Its law, normalization, dimensions, and parameter regime are missing, so no source-specific numerical estimate can yet be stated. Related lift-spectrum results are reported but not identified with this quantity.

Sources

• Local source registry: data/unsolvedmath/problems.json, permanent UnsolvedMath ID $2800405$, source code catalogue entry, proposed by Afonso S. Bandeira in 2015, including the supplied PARTIAL-PROGRESS summary. Dataset attribution: Ulam AI and UnsolvedMath Contributors; original-source attribution and rights are retained.
• Bandeira, source-list title 42 Open Problems in Data Science (2016), Open Problem 4.5, registry title 10 Lectures and 42 Open Problems --- Random k-lifts of graphs: https://afonsobandeira.wordpress.com/2015/10/25/10l42concentration/. Metadata reports HTML access on July 29, 2026, with status and rights review flags. The 2015 proposer date and 2016 list date are retained separately.
• The summary names Bordenave--Collins work on tensor products and quantum expanders and general random-lift spectral results, but supplies no complete citations or theorem matching the displayed expectation. No linked source was inspected for this draft.