Name
Abstract | ||
|---|---|---|
Consider an m×n zero-one matrix A. An s×t submatrix of A is said to be even if the sum of its entries is even. In this paper, we focus on the case m=n and s=t=2. The maximum number M(n) of even 2×2 submatrices of A is clearly ** and corresponds to the matrix A having, e.g., all ones (or zeros). A more interesting question, motivated by Turán numbers and Hadamard matrices, is that of the minimum number m(n) of such matrices. It has recently been shown that ** for some constant B. In this paper we show that if the matrix A=An is considered to be induced by an infinite zero one matrix obtained at random, then ** where En denotes the number of even 2×2 submatrices of An. Results such as these provide us with specific information about the tightness of the concentration of En around its expected value of **. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1007/s00373-004-0585-9 | Graphs and Combinatorics |
Keywords | DocType | Volume |
minimum number m,Hadamard matrix,n number,case m,expected value,interesting question,Random Zero-One Matrix,constant B.,maximum number,specific information | Journal | 20 |
Issue | ISSN | Citations |
4 | 1435-5914 | 0 |
PageRank | References | Authors |
0.34 | 3 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Anant P. Godbole | 1 | 95 | 16.08 |
| Joseph A. Johnson | 2 | 0 | 0.68 |