Skip to main content
added 72 characters in body
Source Link
Dustin G. Mixon
  • 7.6k
  • 2
  • 31
  • 56

It'sIf you further assume that the diagonal of your matrices are all zeros, it's natural to view your matrices as adjacency matrices of graphs. With this identification, your sum condition means the graph is $d$-regular, and the distinct-row condition means the graph is reduced (see for example this paper).

In fact, that same paper considers a function $m(r)$, defined to be the number of vertices in the largest reduced graph of rank $r$. Note that upper bounds on $m(r)$ provide upper bounds for your second question. Kotlov and Lovasz's result in the beginning of section 4 gives that $m(r)=O(2^{r/2})$, and this is tight by Proposition 5.

Section 5 of the paper discusses how rank is related to other parameters of the graph (e.g., number of components, clique number, etc.), but the minimum/maximum degree does not appear to be considered.

It's natural to view your matrices as adjacency matrices of graphs. With this identification, your sum condition means the graph is $d$-regular, and the distinct-row condition means the graph is reduced (see for example this paper).

In fact, that same paper considers a function $m(r)$, defined to be the number of vertices in the largest reduced graph of rank $r$. Note that upper bounds on $m(r)$ provide upper bounds for your second question. Kotlov and Lovasz's result in the beginning of section 4 gives that $m(r)=O(2^{r/2})$, and this is tight by Proposition 5.

Section 5 of the paper discusses how rank is related to other parameters of the graph (e.g., number of components, clique number, etc.), but the minimum/maximum degree does not appear to be considered.

If you further assume that the diagonal of your matrices are all zeros, it's natural to view your matrices as adjacency matrices of graphs. With this identification, your sum condition means the graph is $d$-regular, and the distinct-row condition means the graph is reduced (see for example this paper).

In fact, that same paper considers a function $m(r)$, defined to be the number of vertices in the largest reduced graph of rank $r$. Note that upper bounds on $m(r)$ provide upper bounds for your second question. Kotlov and Lovasz's result in the beginning of section 4 gives that $m(r)=O(2^{r/2})$, and this is tight by Proposition 5.

Section 5 of the paper discusses how rank is related to other parameters of the graph (e.g., number of components, clique number, etc.), but the minimum/maximum degree does not appear to be considered.

Source Link
Dustin G. Mixon
  • 7.6k
  • 2
  • 31
  • 56

It's natural to view your matrices as adjacency matrices of graphs. With this identification, your sum condition means the graph is $d$-regular, and the distinct-row condition means the graph is reduced (see for example this paper).

In fact, that same paper considers a function $m(r)$, defined to be the number of vertices in the largest reduced graph of rank $r$. Note that upper bounds on $m(r)$ provide upper bounds for your second question. Kotlov and Lovasz's result in the beginning of section 4 gives that $m(r)=O(2^{r/2})$, and this is tight by Proposition 5.

Section 5 of the paper discusses how rank is related to other parameters of the graph (e.g., number of components, clique number, etc.), but the minimum/maximum degree does not appear to be considered.