Timeline for Combinatorial 0-1 vector problem

Current License: CC BY-SA 3.0

15 events

when toggle format	what		by	license	comment
Dec 10, 2017 at 21:51	vote	accept	Penelope Benenati
Dec 10, 2017 at 21:34	vote	accept	Penelope Benenati
Dec 10, 2017 at 21:35
Dec 10, 2017 at 21:24	vote	accept	Penelope Benenati
Dec 10, 2017 at 21:32
Dec 10, 2017 at 20:57	comment	added	fedja		Argh, I answered you in the comments to my post without the at construct, so you, most likely, haven't been notified yet. Ping!
Dec 10, 2017 at 17:04	answer	added	fedja		timeline score: 3
Dec 10, 2017 at 13:17	comment	added	Penelope Benenati		@fedja, thank you a lot for your precious help! I am very surprised by the existence of $n^{1/3}$ vectors having exactly $n/2$ ones such that the pairwise overlap is always strictly smaller than $n/4$. Could you please describe it? I now designed a method to create, when $n=c^m$, $\sum_{i=1}^{m} c^{(c^i)}$ vectors with $n/c$ ones such that the pairwise overlap is exactly $n/c^2$ (perhaps this method lists all vectors satisfying these properties "with the equality"). However I cannot see how to construct a list of vectors when the pairwise overlap is strictly smaller than $n/c^2$.
Dec 10, 2017 at 5:35	comment	added	fedja		Actually every $n\times n$ Hadamard matrix gives an example (if you remove the constant row and replace $-1$ by $0$ in the remaining ones) of $n-1$ vectors with $n/2$ ones and the overlap of any $2$ exactly $n/4$. Of course, you were cunning enough to use $\ge$ instead of $>$ in the definition, but I doubt very much that it matters in the slightest except for making a counterexample ugly instead of neat and clean (I can do a reasonably clean one with $n^{1/3}$ instead of $n-1$ and strict inequalities, as requested, so $\beta>2/3$ definitely gives no gain over the trivial bound of $n+1$).
Dec 10, 2017 at 4:22	comment	added	fedja		That is a bit too optimistic. If $n=c^m$, you can create $cm$ pairwise $c^{-2}$ orthogonal vectors $v_{kp}$ putting $1$'s in the positions having the $k$-th digit equal to $p$ in their $c$-ary representation. Repeat all but one of them $n^\beta$ times and fill the rest of the matrix with the remaining one. This already gives $n-cn^\beta\log_c n$. If it were sets on the interval $[0,1]$, you would be able to go with this forever, but the discrete nature of the problem imposes some restrictions on such games, so, $n-n^{\beta+o(1)}$ may be already correct. Will that be enough for your purposes?
Dec 10, 2017 at 0:56	history	edited	Penelope Benenati	CC BY-SA 3.0	deleted 9 characters in body
Dec 10, 2017 at 0:47	history	edited	Penelope Benenati	CC BY-SA 3.0	deleted 13 characters in body
Dec 10, 2017 at 0:41	history	edited	Penelope Benenati	CC BY-SA 3.0	deleted 13 characters in body
Dec 9, 2017 at 21:52	history	edited	Penelope Benenati	CC BY-SA 3.0	added 3 characters in body
Dec 9, 2017 at 20:34	history	edited	Penelope Benenati	CC BY-SA 3.0	added 4 characters in body
Dec 9, 2017 at 20:28	history	edited	Penelope Benenati	CC BY-SA 3.0	deleted 154 characters in body
Dec 9, 2017 at 19:41	history	asked	Penelope Benenati	CC BY-SA 3.0