# Linial, Nathan

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

**Conjecture**If is the adjacency matrix of a -regular graph, then there is a symmetric signing of (i.e. replace some entries by ) so that the resulting matrix has all eigenvalues of magnitude at most .

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

## Linial-Berge path partition duality ★★★

**Conjecture**The minimum -norm of a path partition on a directed graph is no more than the maximal size of an induced -colorable subgraph.

Keywords: coloring; directed path; partition

## The Alon-Tarsi basis conjecture ★★

Author(s): Alon; Linial; Meshulam

**Conjecture**If are invertible matrices with entries in for a prime , then there is a submatrix of so that is an AT-base.

Keywords: additive basis; matrix

## The additive basis conjecture ★★★

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

**Conjecture**For every prime , there is a constant (possibly ) so that the union (as multisets) of any bases of the vector space contains an additive basis.

Keywords: additive basis; matrix