# Linial, Nathan

## Signing a graph to have small magnitude eigenvalues ★★

\begin{conjecture} If $A$ is the adjacency matrix of a $d$-regular graph, then there is a symmetric signing of $A$ (i.e. replace some $+1$ entries by $-1$) so that the resulting matrix has all eigenvalues of magnitude at most $2 \sqrt{d-1}$. \end{conjecture}

Keywords: eigenvalue; expander; Ramanujan graph; signed graph; signing

## Linial-Berge path partition duality ★★★

\begin{conjecture} The minimum $k$-norm of a path partition on a directed graph $D$ is no more than the maximal size of an induced $k$-colorable subgraph. \end{conjecture}

Keywords: coloring; directed path; partition

## The Alon-Tarsi basis conjecture ★★

Author(s): Alon; Linial; Meshulam

\begin{conjecture} If $B_1,B_2,\ldots B_p$ are invertible $n \times n$ matrices with entries in ${\mathbb Z}_p$ for a prime $p$, then there is a $n \times (p-1)n$ submatrix $A$ of $[B_1 B_2 \ldots B_p]$ so that $A$ is an AT-base. \end{conjecture}

Keywords: additive basis; matrix

## The additive basis conjecture ★★★

Author(s): Jaeger; Linial; Payan; Tarsi

\begin{conjecture} For every prime $p$, there is a constant $c(p)$ (possibly $c(p)=p$) so that the union (as multisets) of any $c(p)$ bases of the vector space $({\mathbb Z}_p)^n$ contains an additive basis. \end{conjecture}

Keywords: additive basis; matrix