Skip to main content
deleted 319 characters in body
Source Link
verret
  • 3.3k
  • 1
  • 22
  • 30

If bothEDIT $m$: I've edited the argument to make it stronger Suppose that $m\geq 3$ and $n$ are at least 5, then$n\geq 5$ so that there is a 3x5 submatrix A. I show that the number of such matricespossibilities is 0zero in this case.

IndeedIn A, there must beare at three lines containingleast two rows with at least threethere $1$'s each (up to relabeling the symbols). It is then easy to see that two of those lines must have two $1$'s in the same position (it is impossible toSince we cannot have three 3-subsets of a 5-set such that each pairwise intersection has cardinality at most one.)

Here is a similar argument to show that if $m\geq 3$ and $n\geq 7$constant 2x2 submatrix, then the number of such matrices if 0. Considering onlywe may assume that the first two rows, we get seven ordered pairs of $\{0,1\}$. Wethe matrix are only allowed to have $(0,0)$ [11100] and $(1,1)$ appear once each, so that there are at least five other pairs [00111]. In particular there are at least three of one of the other two possibilities

To avoid a 2x2 contant submatrix, say $(1,0)$. Consider only the three columns where we have $(1,0)$ in the first two rows. In at least twoentries of these columns, the third row must repeat itselfbe different, andbut then, whatever choice we make for the third one, we will get a constant 2x2 sub-matrixsubmatrix in the first and third row.

The answer for $m=1$ and $m=2$ is not hard to calculate explicitly, and.

Together with the argumentanswer above, this reduces the questionproblem to a finite number of otherchecking the following cases (which is not too hard): 3x3,3x4,3x5,3x6,4x4,4x5,4x6.

If both $m$ and $n$ are at least 5, then the number of such matrices is 0.

Indeed, there must be at three lines containing at least three $1$'s each (up to relabeling the symbols). It is then easy to see that two of those lines must have two $1$'s in the same position (it is impossible to have three 3-subsets of a 5-set such that each pairwise intersection has cardinality at most one.)

Here is a similar argument to show that if $m\geq 3$ and $n\geq 7$, then the number of such matrices if 0. Considering only the first two rows, we get seven ordered pairs of $\{0,1\}$. We are only allowed to have $(0,0)$ and $(1,1)$ appear once each, so that there are at least five other pairs. In particular there are at least three of one of the other two possibilities, say $(1,0)$. Consider only the three columns where we have $(1,0)$ in the first two rows. In at least two of these columns, the third row must repeat itself, and we get a constant 2x2 sub-matrix.

The answer for $m=1$ and $m=2$ is not hard to calculate explicitly, and the argument above reduces the question to a finite number of other cases : 3x3,3x4,3x5,3x6,4x4,4x5,4x6.

EDIT : I've edited the argument to make it stronger Suppose that $m\geq 3$ and $n\geq 5$ so that there is a 3x5 submatrix A. I show that the number of possibilities is zero in this case.

In A, there are at least two rows with at least there $1$'s each (up to relabeling the symbols). Since we cannot have a constant 2x2 submatrix, we may assume that the first two rows of the matrix are [11100] and [00111].

To avoid a 2x2 contant submatrix, the first two entries of the third row must be different, but then, whatever choice we make for the third one, we will get a constant 2x2-submatrix in the first and third row.

The answer for $m=1$ and $m=2$ is not hard to calculate explicitly.

Together with the answer above, this reduces the problem to checking the following cases (which is not too hard): 3x3,3x4,4x4.

added 631 characters in body; deleted 34 characters in body; added 6 characters in body; deleted 1 characters in body
Source Link
verret
  • 3.3k
  • 1
  • 22
  • 30

This is not a complete answer but ifIf both $m$ and $n$ are at least 5, then the number of such matrices is 0.

Indeed, there must be at three lines containing at least three $1$'s each (up to relabeling the symbols). It is then easy to see that two of those lines must have two $1$'s in the same position (it is impossible to have three 3-subsets of a 5-set such that each pairwise intersection has cardinality at most one.)

IfHere is a similar argument to show that if $m\geq 3$ and $n\geq 7$, then the number of such matrices if 0. Considering only the first two rows, we get seven ordered pairs of $\{0,1\}$. We are only allowed to have $(0,0)$ and $(1,1)$ appear once each, so that there are at least five other pairs. In particular there are at least three of one of the other two possibilities, say $m$ or$(1,0)$. Consider only the three columns where we have $n$ is$(1,0)$ in the first two rows. In at most 2least two of these columns, it is pretty easy to find an explicit numberthe third row must repeat itself, and we get a constant 2x2 sub-matrix. Maybe it is also possible

The answer for 3$m=1$ and 4$m=2$ is not hard to calculate explicitly, and the argument above reduces the question to a finite number of other cases : 3x3,3x4,3x5,3x6,4x4,4x5,4x6.

This is not a complete answer but if both $m$ and $n$ are at least 5, then the number of such matrices is 0.

Indeed, there must be at three lines containing at least three $1$'s each (up to relabeling the symbols). It is then easy to see that two of those lines must have two $1$'s in the same position (it is impossible to have three 3-subsets of a 5-set such that each pairwise intersection has cardinality at most one.)

If one of $m$ or $n$ is at most 2, it is pretty easy to find an explicit number. Maybe it is also possible for 3 and 4.

If both $m$ and $n$ are at least 5, then the number of such matrices is 0.

Indeed, there must be at three lines containing at least three $1$'s each (up to relabeling the symbols). It is then easy to see that two of those lines must have two $1$'s in the same position (it is impossible to have three 3-subsets of a 5-set such that each pairwise intersection has cardinality at most one.)

Here is a similar argument to show that if $m\geq 3$ and $n\geq 7$, then the number of such matrices if 0. Considering only the first two rows, we get seven ordered pairs of $\{0,1\}$. We are only allowed to have $(0,0)$ and $(1,1)$ appear once each, so that there are at least five other pairs. In particular there are at least three of one of the other two possibilities, say $(1,0)$. Consider only the three columns where we have $(1,0)$ in the first two rows. In at least two of these columns, the third row must repeat itself, and we get a constant 2x2 sub-matrix.

The answer for $m=1$ and $m=2$ is not hard to calculate explicitly, and the argument above reduces the question to a finite number of other cases : 3x3,3x4,3x5,3x6,4x4,4x5,4x6.

Source Link
verret
  • 3.3k
  • 1
  • 22
  • 30

This is not a complete answer but if both $m$ and $n$ are at least 5, then the number of such matrices is 0.

Indeed, there must be at three lines containing at least three $1$'s each (up to relabeling the symbols). It is then easy to see that two of those lines must have two $1$'s in the same position (it is impossible to have three 3-subsets of a 5-set such that each pairwise intersection has cardinality at most one.)

If one of $m$ or $n$ is at most 2, it is pretty easy to find an explicit number. Maybe it is also possible for 3 and 4.