Timeline for Count of binary matrices that avoids a certain sub-matrix
Current License: CC BY-SA 2.5
2 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 3, 2010 at 18:36 | comment | added | Kevin P. Costello | One other lower bound that may be of use...If you $n=p^2+p+1$ and the incidence matrix of a projective plane you get a matrix with about $n^{3/2}$ nonzero entries satisfying the property (an all-$1$ submatrix would correspond to two lines intersecting in two points). Replacing any subset of the $1$ by $0$ still works, so you have $2^{n^{3/2}}$, which unfortunately grows very quickly with $n$. This example comes from the lower bound to the $O(n^{3/2})$ bound mentioned in Pettie's paper. I'm not sure the original source for it. | |
| Jul 3, 2010 at 7:09 | history | answered | Suresh Venkat | CC BY-SA 2.5 |