The Chebyshev-distance asymptotic conjecture for hypergraph clique-shadows

At least 3 years old · documented by

For each k≥3k\geq 3, let Δk\Delta_k be the maximum Chebyshev distance between the coordinatewise powers of the principal eigenvectors of a connected kk-graph and its clique-shadow:

Δk:=max⁡H∈H(k)D(y^,x^).\Delta_k:=\max_{H\in\mathcal{H}(k)}D(\hat y,\hat x).

Here D(y^,x^)=max⁡v∣yvk−xv2∣D(\hat y,\hat x)=\max_v|y_v^k-x_v^2|, where yy and xx are the principal eigenvectors of HH and ∂∗(H)\partial^*(H), respectively, and y^=(yvk)v∈V\hat y=(y_v^k)_{v\in V} and x^=(xv2)v∈V\hat x=(x_v^2)_{v\in V}. Chebyshev-distance conjecture.

Δk=12+o(1)\Delta_k=\frac12+o(1)

for all k≥3k\geq 3. The surrounding theorem proves the upper bound D(y^,x^)≤1/2D(\hat y,\hat x)\leq 1/2 and establishes only the asymptotic lower bound lim⁡k→∞Δk=1/2\lim_{k\to\infty}\Delta_k=1/2; the stated uniform asymptotic formula is not resolved in the supplied text.

References

Primary source

Gregory J. Clark, Felipe Thomaz and Andrew Stephen, “On the Effect of Data Dimensionality on Eigenvector Centrality”, arXiv:2201.12034 (2022).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.