![](/files/happy5.png)
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
.
![$ A $](/files/tex/7a8d9782350e8eb5a84c149576d83160492cbdd3.png)
![$ d $](/files/tex/aeba4a4076fc495e8b5df04d874f2911a838883a.png)
![$ A $](/files/tex/7a8d9782350e8eb5a84c149576d83160492cbdd3.png)
![$ +1 $](/files/tex/155fca3c17d66548c323f203be786f9387842fe4.png)
![$ -1 $](/files/tex/26833acbe5abb13c40595cebdee81f595c59a397.png)
![$ 2 \sqrt{d-1} $](/files/tex/40581c05b66d632e7bdb2bcb852e63443663853a.png)
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.
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
![$ D $](/files/tex/b8653a25aff72e3dacd3642492c24c2241f0058c.png)
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
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.
![$ B_1,B_2,\ldots B_p $](/files/tex/d7626d3626b2054ebc198940785a7861d2fae9c2.png)
![$ n \times n $](/files/tex/fd981d449b91b1f4889d87406e6aa7d8acfb5d68.png)
![$ {\mathbb Z}_p $](/files/tex/e8c94ceb5a9d688bff114c12f7fe9fe47ef955fc.png)
![$ p $](/files/tex/928cd9d544fdea62f88a627aaee28c416c4366c0.png)
![$ n \times (p-1)n $](/files/tex/18102393d42ad781eb0253bf9bee94b60757ed23.png)
![$ A $](/files/tex/7a8d9782350e8eb5a84c149576d83160492cbdd3.png)
![$ [B_1 B_2 \ldots B_p] $](/files/tex/86661dc2948aeca789b4392c2e2a9cbf7d96f735.png)
![$ A $](/files/tex/7a8d9782350e8eb5a84c149576d83160492cbdd3.png)
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.
![$ p $](/files/tex/928cd9d544fdea62f88a627aaee28c416c4366c0.png)
![$ c(p) $](/files/tex/996da72e7b0b6591ec8cc40dcbe46964d764e211.png)
![$ c(p)=p $](/files/tex/b1a6c0fbe5cae8582d2ef00c5f0f5158c9d9d4be.png)
![$ c(p) $](/files/tex/996da72e7b0b6591ec8cc40dcbe46964d764e211.png)
![$ ({\mathbb Z}_p)^n $](/files/tex/ea205f9e138abfc9a2c6a35332ecc6694ebe6419.png)
Keywords: additive basis; matrix
![Syndicate content Syndicate content](/misc/feed.png)