Revision #1 Authors: Bruno Codenotti, Pavel Pudlak, Giovanni Resta

Accepted on: 28th August 1998 00:00

Downloads: 1976

Keywords:

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.

TR97-043 Authors: Bruno Codenotti, Pavel Pudlak, Giovanni Resta

Publication: 25th September 1997 18:52

Downloads: 1444

Keywords:

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.

Comment #1 Authors: Bruno Codenotti, Pavel Pudlak, Giovanni Resta

Accepted on: 3rd December 1997 08:33

Downloads: 970

Keywords:

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.