
PreviousNext
We consider the conjecture stating that a matrix with rank
$o(n)$ and ones on the main diagonal must contain nonzero
entries on a $2\times 2$ submatrix with one entry on the main
diagonal. We show that a slightly stronger conjecture implies
that ...
more >>>
Razborov~\cite{Razborov96} recently proved that polynomial
calculus proofs of the pigeonhole principle $PHP_n^m$ must have
degree at least $\ceiling{n/2}+1$ over any field. We present a
simplified proof of the same result. The main
idea of our proof is the same as in the original proof
of Razborov: we want to describe ...
more >>>
The bandwidth problem is the problem of enumerating
the vertices of a given graph $G$ such that the maximum
difference between the numbers of
adjacent vertices is minimal. The problem has a long
history and a number of applications
and is ...
more >>>
PreviousNext