Analytic methods for uniform hypergraphs

NEW

Problem: Reconstructed statement: for a finite simple $r$-uniform hypergraph $G=(V,E)$, $r\ge2$, define

$$P_G(x)=r!\sum_{e\in E}\prod_{i\in e}x_i,\qquad \lambda^{(p)}(G)=\max_{\sum_i |x_i|^p=1}P_G(x),\quad p\ge1.$$

Nikiforov’s Question 2.12 asks whether $p\mapsto\lambda^{(p)}(G)$ is $C^1$ on $(r,\infty)$, and more strongly on $(1,\infty)\setminus\{2,\dots,r\}$. This is the standard $p$-spectral radius notation for ordinary nonnegative $r$-graphs.

Result: The first question has answer yes: $\lambda^{(p)}(G)$ is in fact real analytic for $p>r$. The second question has answer no, already for ordinary graphs.

Proof for $p>r$. Since $P_G(|x|)\ge P_G(x)$, maximize over $x_i\ge0$. Put $y_i=x_i^p$, so $\sum y_i=1$, and

$$\lambda^{(p)}(G)=r!\max_{y\in\Delta}\sum_{e\in E}\prod_{i\in e} y_i^{1/p}.$$

Ignore isolated vertices; if $E=\varnothing$, the function is identically $0$.

For $p>r$, each monomial $m_e(y)=\prod_{i\in e}y_i^{1/p}$ has total degree $r/p<1$. On the positive orthant,

$$D^2m_e(y)[h,h] =m_e(y)\left[\frac1{p^2}\Big(\sum_{i\in e}\frac{h_i}{y_i}\Big)^2 -\frac1p\sum_{i\in e}\Big(\frac{h_i}{y_i}\Big)^2\right]<0$$

whenever $h$ is nonzero on $e$, by Cauchy and $r/p<1$. Since every non-isolated vertex lies in some edge, the full objective is strictly concave on the positive simplex.

A maximizer cannot lie on the boundary: adding small mass to a missing edge or to missing vertices in an edge gives a gain of order $\varepsilon^{k/p}$ with $k\le r$, while losses are only $O(\varepsilon)$, and $k/p<1$. Hence the unique maximizer $y(p)$ is interior.

The Lagrange equations

$$\nabla_y F(p,y)=\mu \mathbf 1,\qquad \sum_i y_i=1$$

have nonsingular bordered Hessian because the Hessian of $F$ is negative definite. Since $F$ is real analytic in $(p,y)$ for $p>r$ and $y_i>0$, the implicit function theorem gives real-analytic $y(p)$, hence real-analytic $\lambda^{(p)}(G)=F(p,y(p))$.

Counterexample to the stronger question. Let $r=2$ and let

$$G=K_3\ \sqcup\ K_{1,5}.$$

For $1<p<2$, a disjoint union satisfies

$$\lambda^{(p)}(G)=\max_i \lambda^{(p)}(G_i),$$

because if component $i$ has $p$-norm $t_i$, then

$$P_G(x)\le \sum_i \lambda^{(p)}(G_i)t_i^2 \le \max_i\lambda^{(p)}(G_i)\sum_i t_i^p =\max_i\lambda^{(p)}(G_i).$$

Direct computation gives

$$\lambda^{(p)}(K_3)=2\cdot 3^{1-2/p},$$

and, for the star with five leaves,

$$\lambda^{(p)}(K_{1,5})=2^{1-2/p}5^{1-1/p}.$$

Their logarithmic ratio is

$$D(p)=\log\frac{\lambda^{(p)}(K_{1,5})}{\lambda^{(p)}(K_3)} =\log(5/3)-\frac1p\log(20/9).$$

Thus $D(p_0)=0$ at

$$p_0=\frac{\log(20/9)}{\log(5/3)}\in(1,2),$$

and $D'(p_0)>0$. Therefore near $p_0$, $\lambda^{(p)}(G)$ is the $K_3$ branch on the left and the star branch on the right, with unequal derivatives. Hence $\lambda^{(p)}(G)$ is not differentiable at the non-integer point $p_0\ne2$.

Verification audit: the proof uses exactly the standard finite unweighted $r$-graph definition. The positive result covers all $G$ for $p>r$, including disconnected graphs and isolated vertices. The counterexample is a legitimate member of $G^2$ and disproves the broader $p\ne2,\dots,r$ assertion.

Citation: Question/notation: Vladimir Nikiforov, “Analytic methods for uniform hypergraphs,” Linear Algebra Appl. 457 (2014), 455–535, Question 2.12. No external resolution is used above.