Bilu–Linial conjecture for arbitrary graphs

Let GG be a graph with maximum degree Δ(G)>1\Delta(G)>1. An edge-signing of GG is a map from E(G)E(G) to {1,1}\{-1,1\}; write GσG^\sigma for the resulting edge-signed graph and let ρ(Gσ)\rho(G^\sigma) be the maximum absolute value of an eigenvalue of its signed adjacency matrix. Bilu–Linial conjecture for arbitrary graphs. There exists an edge-signing σ\sigma of GG such that

ρ(Gσ)2Δ(G)1.\rho(G^\sigma)\leq 2\sqrt{\Delta(G)-1}.

This is presented as a stronger conjecture obtained by omitting regularity from the regular-graph formulation, and is attributed to reference greg. The source gives no resolution status.

Sources & referencesView supporting material

Primary source

Mohsen Alinejad and Sanaz Fulad, “Equitable partitions for Ramanajun graphs”, arXiv:2107.11563 (2021).

Additional references

3 papers in this index state this conjecture (2013–2021). The statement above is taken from the most recent of them; the others are arXiv:1907.04349, arXiv:1311.3268.

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.