9
$\begingroup$

I have a question that involves some ability in combinatorics that I don't have. Any hint could be extremely appreciated.

Take $n>1$ with $n\in \mathbb{N}$.

Let $\mathcal{G}$ be the set of all possible binary matrices of dimension $n\times (n-1)$. $\mathcal{G}$ has cardinality $|\mathcal{G}|=2^{n(n-1)}$.

For example, if $n=2$, then $\mathcal{G}:=\{\begin{pmatrix} 1\\ 1 \end{pmatrix},\begin{pmatrix} 1\\ 0 \end{pmatrix}, \begin{pmatrix} 0\\ 1 \end{pmatrix} , \begin{pmatrix} 0\\ 0 \end{pmatrix}\}$ with $|\mathcal{G}|=4$.

Question: For $M=2,...,|\mathcal{G}|-1$, I want to count all possible sets $C\subset \mathcal{G}$ with cardinality $M$ such that:

there exists a non-empty set $D\subset C$ such that for every pair of matrices, one taken from $D$ and the other taken from $C-D$, the two matrices in the pair considered differ for at least two rows.

Is this counting possible? If not, is there any known upper bound or lower bound?

I have looked at this question whose comments link to bounds for binary constant weight codes, but it does not seem to help.

[$C-D$ denotes the complement of $D$ in $C$].

For example: when $n=2$ the result is $2$. Indeed, for $M=2$, we can have $$ C=\{\begin{pmatrix} 1\\ 1 \end{pmatrix}, \begin{pmatrix} 0\\ 0 \end{pmatrix}\} $$ where $D=\{\overbrace{\begin{pmatrix} 1\\ 1 \end{pmatrix}}^{d_1}\}$, $C-D=\{\overbrace{\begin{pmatrix} 0\\ 0 \end{pmatrix}}^{c_1}\}$, row $1$ of $d_1$ $\neq $ row $1$ of $c_1$, and row $2$ of $d_1$ $\neq $ row $2$ of $c_1$ and $$ C=\{\begin{pmatrix} 0\\ 1 \end{pmatrix}, \begin{pmatrix} 1\\ 0 \end{pmatrix}\} $$ where $D=\{\overbrace{\begin{pmatrix} 0\\ 1 \end{pmatrix}}^{d_1}\}$, $C-D=\{\overbrace{\begin{pmatrix} 1\\ 0 \end{pmatrix}}^{c_1}\}$, row $1$ of $d_1$ $\neq $ row $1$ of $c_1$, and row $2$ of $d_1$ $\neq $ row $2$ of $c_1$

For $M=3$, there is no $C$ satisfying the considered criterion.

Remark: Notice that the order of the rows matter.

$\endgroup$
4
  • 1
    $\begingroup$ Sorry; I completely misunderstood the question. $\endgroup$ – Misha Lavrov May 18 '17 at 15:37
  • $\begingroup$ No problems, thanks for you help, any further hint could be extremely appreciated. $\endgroup$ – TEX May 18 '17 at 15:38
  • $\begingroup$ @bof The second, thanks. Question edited. $\endgroup$ – TEX May 22 '17 at 13:07
  • $\begingroup$ Thanks @san. Could you provide an answer with more explanations? $\endgroup$ – TEX May 31 '17 at 12:12
2
+100
$\begingroup$

For $M=2$ we have to count the number of pairs of matrices that differ at least at 2 rows. For this we have to substract from the total number of pairs of matrices the number $C_2$ of pairs of matrices that differ at exactly one row.

For this you have to choose first one matrix (so you have $2^{n(n-1)}$ choices, and then you have to choose one row (so you have $n$ choices) and choose then from the possible values of the chosen row one of the $2^{n-1}-1$ remaining possible rows. Since you have repeated every pair, you have to divide by 2. So $$ C_2=2^{n(n-1)}n(2^{n-1}-1)/2=n2^{n^2-n-1}(2^{n-1}-1). $$

Another way to compute $C_2$ is to choose first one row (you have $n$ choices), then choose the possible values of the rows that are equal (you have $2^{(n-1)^2}$ choices) and then pick two possible values of the chosen row (you have $\binom{2^{n-1}}{2}$ choices)and so $$ C_2=n 2^{(n-1)^2}\binom{2^{n-1}}{2}=n2^{n^2-n-1}(2^{n-1}-1). $$

Now substract $C_2$ from the total number of pairs and obtain $$ \#C=\binom{2^{n(n-1)}}{2}-n2^{n^2-n-1}(2^{n-1}-1). $$

For $M=2$ I'm pretty sure about the count. For $M=3$ I have the following reasoning:

A set of three matrices is not admissible if either all three coincide in all but one row, or they coincide in all but two rows. In the first case you have $n$ choices for the row, then $2^{(n-1)^2}$ choices for the coinciding rows, and you have to choose 3 values for the chosen row, so you have $\binom{2^{n-1}}{3}$ choices. This means that you have $$ n2^{(n-1)^2}\binom{2^{n-1}}{3}=2^{n(n-1)}(2^{n-1}-1)(2^{n-2}-1)n/3 $$ of such sets of three matrices.

In the second case you have to choose two rows (that makes $\binom{n}{2}$ choices) choose the values of the coinciding rows (you have $2^{(n-1)(n-2)}$ choices) and then choose two possible values $A_1$ and $A_2$ for the first chosen row (that's $\binom{2^{n-1}}{2}$ choices) and then choose two possible values $B_1$ and $B_2$ for the second chosen row (that's $\binom{2^{n-1}}{2}$ choices).

Then you can construct four possible sets of three matrices with the given data:

I. First matrix: $A_1$, $B_1$

Second matrix: $A_1$, $B_2$

Third matrix: $A_2$, $B_1$

II. First matrix: $A_1$, $B_1$

Second matrix: $A_2$, $B_1$

Third matrix: $A_2$, $B_2$

III. First matrix: $A_1$, $B_1$

Second matrix: $A_1$, $B_2$

Third matrix: $A_2$, $B_2$

IV. First matrix: $A_1$, $B_2$

Second matrix: $A_2$, $B_2$

Third matrix: $A_2$, $B_1$

So the number of sets of three matrices such that the number of the different rows for each possible pair is $\{2,1,1\}$ is given by $$ \binom{n}{2}2^{(n-1)(n-2)}\binom{2^{n-1}}{2}^2\cdot 4=2^{n(n-1)}(2^{n-1}-1)^2\binom{n}{2}. $$ Finally we arrive at $$ \#C=\binom{2^{n(n-1)}}{3}-2^{n(n-1)}(2^{n-1}-1)(2^{n-2}-1)n/3-2^{n(n-1)}(2^{n-1}-1)^2\binom{n}{2}, $$ for $M=3$.

For sets of four matrices it is much more complicated to write down the configurations of matrices that cannot be separated in two sets of distance at least two (define a distance function between matrices simply by setting the distance equal to the number of differing rows) so the formula gets more and more complicated for increasing $M$.

${\bf EDIT:}$

One can see this problem from the viewpoint of graph theory. For each $n$ consider the graph where the vertices are the matrices and there is an edge between two vertices if the matrices coincide in all but one row. Then you want to count the number of disconnected sets (of size $M$). For $n=2$ the graph is very simple (just a square), but for $n=3$ the graph has already $64$ vertices and $288$ edges, so the question is very difficult to answer. It corresponds to a 9-regular, distance-regular graph.

In general the graph is distance-regular, and the main theorem of "The vertex-connectivity of a distance-regular graph" by Andries E. Brouwer and Jack H. Koolen in European Journal of Combinatorics Volume 30, Issue 3, April 2009, Pages 668-673 European Journal of Combinatorics

says that the vertex-connectivity of a distance-regular graph equals its valency. Since the valency is the number of neighbors $k=n(2^{n-1}-1)$, this means that if you have $M> 2^{n(n-1)}-n(2^{n-1}-1)$, then every subset of vertices of cardinality $M$ is connected, and thus cannot have a subset $C$ satisfying the criterion of the OP. This gives a complete proof of the statement in @Jens answer.

Moreover the same theorem says that the only disconnecting sets of vertices of size not more than $k$ are the point neighbourhoods. Hence for $n>2$ and $M=2^{n(n-1)}-n(2^{n-1}-1)$ we have exactly $2^{n(n-1)}$ sets, that are the complements of the point neighborhoods, that are disconnected, and so that is the count for that $M$. (Note that for $n>2$ the point neighborhood uniquely determines the point of which it is the neighborhood).

${\bf SECOND\ EDIT:}$ The following is Definition 2.1 in https://arxiv.org/pdf/1410.6294.pdf

A connected graph $\Gamma$ with diameter $D$ is called distance-regular if there are constants $c_i$, $a_i$, $b_i$ — the so-called intersection numbers — such that for all $i = 0, 1, . . . , D,$ and all vertices $x$ and $y$ at distance $i = d(x, y)$, among the neighbors of $y$, there are $c_i$ at distance $i − 1$ from $x$, $a_i$ at distance $i$, and $b_i$ at distance $i + 1$.

In our case the diameter is $n$. If the matrices $y$ and $x$ have distance $i$ between them, this means that they differ in $i$ rows. Let the matrix $z$ be a neighbor of $y$.

If $z$ has a distance of $i-1$ to $x$, then it has to coincide in all rows with $y$ except in one row, among the distinguished $i$ rows, where it coincides with $x$. Then we have $i$ choices and so $c_i=i$.

If $z$ has a distance of $i$ to $x$, then it has to coincide in all rows with $y$ except in one row, among the distinguished $i$ rows, where it also differs from $x$. Then we have $2^{n-1}-2$ choices, and since we already chose one of the $i$ distinguished rows, we have $a_i=i(2^{n-1}-2)$.

If $z$ has a distance of $i+1$ to $x$, then it has to coincide in all rows with $y$ except in one row, which is not among the distinguished $i$ rows. Then we have $(2^{n-1}-1)$ choices, and since we already chose one of the $n-i$ rows (which are not distinguished), we have $b_i=(n-i)(2^{n-1}-1)$.

Note that $a_i+b_i+c_i=n(2^{n-1}-1)$, which is the number of neighbors of $y$ and so is the valency of the graph.

This proves that the graph is distance-regular for any $n$.

$\endgroup$
9
  • $\begingroup$ Thanks, that's brilliant! Three small clarifications, if I may. (1) My first question is actually a question on the statement of the theorem you are using: why do the authors write "the only disconnecting sets of vertices of size NOT MORE THAN $k$ are the point neighbourhoods"? They have just said that sets of disconnecting vertices have size AT LEAST EQUAL TO $k$. Hence should I interpret this as "the only disconnecting sets of vertices of size EQUAL TO $k$ are the point neighbourhoods"? $\endgroup$ – TEX Jun 2 '17 at 12:13
  • $\begingroup$ (2) My second question is again related to the last claim and why the counting does not apply to $n=2$. Is the following explanation correct: the counting for $n=2$ is $2<2^{n(n-1)}=4$ because there are vertices sharing the same neighbourhood; instead, for $n>2$ there are no vertices sharing the same neighbourhood. If this is correct, is there any way to formally show it? $\endgroup$ – TEX Jun 2 '17 at 12:16
  • $\begingroup$ (3) Is there any way to show that the graph is distance-regular for any $n$? $\endgroup$ – TEX Jun 2 '17 at 12:17
  • $\begingroup$ (1) your interpretation is correct. (2)again, this is correct, and if two points share the same neighborhood, then the distance is two, and then there are exactly two points between them, so the graph is 2-regular and so $n=2$. $\endgroup$ – san Jun 2 '17 at 13:31
  • $\begingroup$ Thanks, regarding (2), I think it should be "... the distance is two, and then there is exactly ONE point between them ... ". Also how can I conclude that the graph is $2$-regular, i.e. the vertex degree is 2? $\endgroup$ – TEX Jun 2 '17 at 13:55
2
$\begingroup$

This is not an answer but an input regarding the maximum of $M$.

Claim:

For $M \gt 2^{n(n-1)}-n(2^{n-1}-1)$ there is no $C$ satisfying the criterion.

Argument:

When pairing matrices, at least two rows must differ. This means the only pairing which isn't allowed is the pairing of matrices which differ in exactly one row. For a given matrix, how many such disallowed pair-mates are there?

If a row has $n-1$ binary digits there are $2^{n-1}$ possible permutations of that row. For a given row and a given matrix, there are thus $2^{n-1}-1$ matrices which differ from the given matrix in only that row. With $n$ rows there are thus $n(2^{n-1}-1)$ matrices which differ from the given matrix in one row.

An example with $n=3$. The given matrix:

$$ \begin{pmatrix} 0 & 0 \\ 0 & 0 \\ 0 & 0 \\ \end{pmatrix} $$

has the following $n(2^{n-1}-1)$ disallowed pair-mates:

$$ \begin{pmatrix} 0 & 1 \\ 0 & 0 \\ 0 & 0 \\ \end{pmatrix}\begin{pmatrix} 1 & 0 \\ 0 & 0 \\ 0 & 0 \\ \end{pmatrix}\begin{pmatrix} 1 & 1 \\ 0 & 0 \\ 0 & 0 \\ \end{pmatrix} $$ $$ \begin{pmatrix} 0 & 0 \\ 0 & 1 \\ 0 & 0 \\ \end{pmatrix}\begin{pmatrix} 0 & 0 \\ 1 & 0 \\ 0 & 0 \\ \end{pmatrix}\begin{pmatrix} 0 & 0 \\ 1 & 1 \\ 0 & 0 \\ \end{pmatrix} $$ $$ \begin{pmatrix} 0 & 0 \\ 0 & 0 \\ 0 & 1 \\ \end{pmatrix}\begin{pmatrix} 0 & 0 \\ 0 & 0 \\ 1 & 0 \\ \end{pmatrix}\begin{pmatrix} 0 & 0 \\ 0 & 0 \\ 1 & 1 \\ \end{pmatrix} $$ This means a given matrix can only be paired with $2^{n(n-1)}-n(2^{n-1}-1)-1$ other matrices (the $-1$ at the end is because a given matrix cannot be paired with itself). A subset $C$, where $D$ consists only of the given matrix, can therefore at most have $|C-D| = 2^{n(n-1)}-n(2^{n-1}-1)-1$ other elements and can therefore at most have cardinality $M = 2^{n(n-1)}-n(2^{n-1}-1)$.

If the sole element of $D$ is the given matrix, we know from above that we cannot add extra matrices in $C-D$, but perhaps we can add extra matrices in $D$, thus increasing $M$?

If we add a disallowed matrix to $D$ (say the upper left matrix in the example above) we see that this new member of $D$ doesn't share $(n-1)(2^{n-1}-1)$ of the disallowed with the given matrix. Since the total number of matrices that a matrix can be paired with remains constant for a given $n$, the number of matrices that both the given matrix and the new member can be paired with, is reduced by $(n-1)(2^{n-1}-1)$. So one extra member of $D$, but a greater reduction in $|C-D|$.

If we add an allowed matrix to $D$, the reduction of $|C-D|$ would be even greater.

Let me know what you think.

$\endgroup$
8
  • $\begingroup$ Thanks, that is a very nice claim but I am not sure about the last step "If we add an allowed matrix to $D$, the reduction $|C-D|$ would be even greater". Consider, for example, $$D:=\{\begin{pmatrix} 0 & 0\\ 0 & 0\\ 0 & 0 \end{pmatrix},\begin{pmatrix} 0 & 1\\ 0 & 1\\ 0 & 0 \end{pmatrix}\}$$ $\endgroup$ – TEX May 31 '17 at 12:15
  • $\begingroup$ Then, the number of matrices that cannot be paired with the second matrix , in addition to those that cannot be paired with the first, is smaller than in the disallowed case. $\endgroup$ – TEX May 31 '17 at 12:16
  • $\begingroup$ Jens am I wrong? Could you help me to clarify this step? $\endgroup$ – TEX Jun 1 '17 at 21:49
  • $\begingroup$ If we add the allowed matrix you suggest to $D$, we immediately reduce $|C-D|$ by one, as that matrix was previously in $C-D$. And the suggested matrix only shares 2 of the disallowed with the given matrix, meaning 7 additional matrices in $C-D$ must be removed. $\endgroup$ – Jens Jun 2 '17 at 0:59
  • $\begingroup$ However, it is true that my argument is not a proof. E.g. I only discussed what happens when I add one disallowed to $D$, not what happens if I add another. And I didn't discuss the allowed cases at all. I'm pretty sure the claim is true, though. I am currently running a program to determine the case for $n=3$. $\endgroup$ – Jens Jun 2 '17 at 1:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.