We consider the problem of the presence of short cycles in the
graphs of nonzero elements of matrices which have sublinear rank
and nonzero entries on the main diagonal, and analyze the connection between
these properties and the rigidity of matrices. In particular, we
exhibit a family of matrices which
shows that sublinear rank does not imply the existence of
triangles. This family can also be used to give a constructive
bound of the order of $k^{3/2}$ on the Ramsey number $R(3,k)$, which matches
the best known bound. On the other hand we show that sublinear
rank implies the existence of 4-cycles. Finally, we prove some
partial results towards establishing lower bounds on matrix
rigidity and consequently on the size of logarithmic depth arithmetic
circuits for computing certain explicit linear transformations.
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 an explicit linear transformation cannot be computed by
linear size and logarithmic depth circuits. We prove some
partial results supporting the conjecture.
Some of the results of the paper have been based on the
'Triangle Conjecture'. Here we show that this conjecture,
in its general form, is false, by describing the construction
of a matrix with ones on the main diagonal, with sublinear rank,
and such that the graph obtained by associating edges to nonzero
entries of the matrix does not have 'transitive triangles'.
As a byproduct of the above result, we find a constructive bound on
the Ramsey number $R(3,n)$. The bound is asymptotically the same as
the one by Alon in "Explicit Ramsey graphs and orthonormal labelings"
(Electronic Journal of Combinatorics 1 (1994), R12), but our
construction is far simpler.
