# Linial, Nathan

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

Author(s): Bilu; Linial

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 ★★★

Author(s): Berge; Linial

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.