Return to Question

Given $A\in\{0,1\}^{n\times n}$ with $rank(A)=r=2^{O((\log_2n)^{\frac{1}{c+1}})}$.

Denote $\mathsf{1_n}\in\{0,1\}^n$ as vector with $1$s.

Does $$\lim_{n\rightarrow\infty}\mathsf{P_{A\in\{0,1\}^{n\times n}}}\Bigg(\mathsf{1_n}'A\mathsf{1_n}>\frac{(r-1)r^{(\log_2r)^c}}{2\log_2r}\Bigg)=1\quad?$$

Infact is there a matrix (family) such that $$\mathsf{1_n}'A\mathsf{1_n}<\frac{(r-1)r^{(\log_2r)^c}}{2\log_2r}\quad?$$

$c\geq1$ fixed.

Given $A\in\{0,1\}^{n\times n}$ with $\operatorname{rank}(A)=r=2^{O((\log_2n)^{\frac{1}{c+1}})}$.

Denote $\mathsf{1_n}\in\{0,1\}^n$ as vector with $1$s.

Does $$\lim_{n\rightarrow\infty}\mathsf{P_{A\in\{0,1\}^{n\times n}}}\Bigg(\mathsf{1_n}'A\mathsf{1_n}>\frac{(r-1)r^{(\log_2r)^c}}{2\log_2r}\Bigg)=1\quad?$$

Infact is there a matrix (family) such that $$\mathsf{1_n}'A\mathsf{1_n}<\frac{(r-1)r^{(\log_2r)^c}}{2\log_2r}\quad?$$

$c\geq1$ fixed.

Given $A\in\{0,1\}^{n\times n}$ with $rank(A)=r=2^{O((\log_2n)^{\frac{1}{c+1}})}$.

Denote $\mathsf{1_n}\in\{0,1\}^n$ as vector with $1$s.

Does $$\lim_{n\rightarrow\infty}\mathsf{P_{A\in\{0,1\}^{n\times n}}}\Bigg(\mathsf{1_n}'A\mathsf{1_n}>\frac{(r-1)r^{(\log_2r)^c}}{2\log_2r}\Bigg)=1\quad?$$

Infact is there a matrix (family) such that $$\mathsf{1_n}'A\mathsf{1_n}<\frac{(r-1)r^{(\log_2r)^c}}{2\log_2r}\quad?$$

$c>1$ fixed.

Given $A\in\{0,1\}^{n\times n}$ with $rank(A)=r=2^{O((\log_2n)^{\frac{1}{c+1}})}$.

Denote $\mathsf{1_n}\in\{0,1\}^n$ as vector with $1$s.

Does $$\lim_{n\rightarrow\infty}\mathsf{P_{A\in\{0,1\}^{n\times n}}}\Bigg(\mathsf{1_n}'A\mathsf{1_n}>\frac{(r-1)r^{(\log_2r)^c}}{2\log_2r}\Bigg)=1\quad?$$

Infact is there a matrix (family) such that $$\mathsf{1_n}'A\mathsf{1_n}<\frac{(r-1)r^{(\log_2r)^c}}{2\log_2r}\quad?$$

$c\geq1$ fixed.

Given $A\in\{0,1\}^{n\times n}$ with $rank(A)=r=2^{O(\sqrt{\log_2n})}$.

Denote $\mathsf{1_n}\in\{0,1\}^n$ as vector with $1$s.

Does $$\lim_{n\rightarrow\infty}\mathsf{P_{A\in\{0,1\}^{n\times n}}}\Bigg(\mathsf{1_n}'A\mathsf{1_n}>\frac{(r-1)r^{(\log_2r)^c}}{2\log_2r}\Bigg)=1\quad?$$

Infact is there a matrix (family) such that $$\mathsf{1_n}'A\mathsf{1_n}<\frac{(r-1)r^{(\log_2r)^c}}{2\log_2r}\quad?$$

$c>1$ fixed.

Given $A\in\{0,1\}^{n\times n}$ with $rank(A)=r=2^{O((\log_2n)^{\frac{1}{c+1}})}$.

Denote $\mathsf{1_n}\in\{0,1\}^n$ as vector with $1$s.

Does $$\lim_{n\rightarrow\infty}\mathsf{P_{A\in\{0,1\}^{n\times n}}}\Bigg(\mathsf{1_n}'A\mathsf{1_n}>\frac{(r-1)r^{(\log_2r)^c}}{2\log_2r}\Bigg)=1\quad?$$

Infact is there a matrix (family) such that $$\mathsf{1_n}'A\mathsf{1_n}<\frac{(r-1)r^{(\log_2r)^c}}{2\log_2r}\quad?$$

$c>1$ fixed.