3
$\begingroup$

Consider a $d$-regular, $k$-uniform hypergraph: the elements $S$ of its set $E$ of edges are subsets of $V$ of size $k$, and each vertex $v\in V$ is in $d$ edges. We can then define its adjacency tensor $\mathscr{A} = (a_{i_1\dotsb i_k})$ by $a_{i_1\dotsb i_k}=1$ for $\{i_1,\dotsc,i_k\}\in E$ and $a_{i_1\dotsb i_k}=1$ otherwise.

There is a standard definition of the spectral radius $\rho(\mathscr{A})$ of a tensor $\mathscr{A}$ (see, e.g., https://www.degruyter.com/document/doi/10.1515/math-2020-0143/html). My question is whether one can define an operator norm of $\mathscr{A}$ so that (a) it makes intuitive sense, (b) it is bounded by $\rho(\mathscr{A})$.

Let me ask this question in a precise form. Is it the case that, for any $f_1,\dotsc,f_k:V\to \mathbb{C}$, $$|\sum_{S\in E} \prod_{v\in S} f_i(v)| \leq \frac{\rho(\mathscr{A})}{(k-1)!} |V| \prod_{i=1}^k |f_i|_2,$$

where $|\cdot|_2$ is the $\ell^2$ norm on functions $V\to \mathbb{C}$ with respect to the uniform probability measure on $V$? (Rationale for the factor $(k-1)!$: the example of constant functions gives us $\rho(\mathscr{A})\geq d (k-1)!$, and would also make the inequality tight as stated, if in fact $\rho(\mathscr{A})=d (k-1)!$.) If not, is there a sensible way to modify this inequality so that it holds -- tightly, if possible?

Assuming that the inequality above (modified or not) holds in some overly simple way: what if we replace $\mathscr{A}$ by its restrictions to functions $f_1,\dotsc,f_k:V\to \mathbb{C}$ orthogonal to constant functions, and define $\rho(\mathscr{A})$ accordingly? Is the inequality above still correct (for functions orthogonal to constant functions)?

$\endgroup$
4
  • 1
    $\begingroup$ Did you have a look at a bunch of papers by Shmuel Friedland on the topic of tensor norms and related material? see e.g., ams.org/journals/mcom/2020-89-325/S0025-5718-2020-03525-X/… and also this paper: stat.uchicago.edu/~lekheng/work/nuclear.pdf $\endgroup$
    – Suvrit
    Mar 30, 2021 at 0:44
  • $\begingroup$ Thanks! I didn't find the inequality above as written, but I did find the analogous inequality for the spectral norm $|\mathscr{A}|_\sigma$, which may be defined as $\sup_{\vec{v}\ne 0} |\langle A,\vec{v}^{\otimes k}\rangle|_2/|\vec{v}|_2$: then $|\sum_{S\in E} \prod_{v\in S} f_i(v)| = |\langle A,f_1\otimes \dotsb \otimes f_k\rangle| \leq |\mathscr{A}|_\sigma \prod_{i=1}^k |f_i|_2$. That turns to be an inequality due to Banach. (See also math.tsukuba.ac.jp/~wkbysh/note3.pdf .) $\endgroup$ Mar 30, 2021 at 9:17
  • $\begingroup$ It seems clear that the same inequality applies when we restrict to functions orthogonal to constant functions (since we are then just working with a vector space of dimension one smaller, and the definitions and inequalities above can be expressed in a coordinate-free way). $\endgroup$ Mar 30, 2021 at 9:19
  • $\begingroup$ See also mathoverflow.net/questions/388846/… $\endgroup$ Mar 30, 2021 at 16:33

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.