4
$\begingroup$

Let $q$ be an odd number...

consider $0-1$ strings of length $2q$ with $q$ ones. [with total number of $C(2q,q)$]

I want to find an upper bound for a set of these strings such that the number of mutual ones in any two of them be an odd number...

i already wrote a code in MATLAB and it seems this number is not very big... (about $2q$)

can someone help me to find any efficient (OR NOT!) upper bound?

[if it helps you can think of even intersection strings as well]

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ It is certainly exponential in $q$. Indeed, take $Q=3$. Then you can do $2$ strings. Now, for $q=RQ$ with odd $R$, you can choose one of those $2$ strings independently in each $6$-block giving you $2^R=2^{q/3}$ choices. On the other hand, they are exponentially fewer than the total number of strings. I doubt anybody can tell you the exact exponent (so that the example and the upper bound match), but I will be happy to be proved wrong. $\endgroup$
    – fedja
    Commented Sep 26, 2016 at 12:48
  • $\begingroup$ @fedja Thanks for your helpful comment... i did not understand the agument of your last sentence... $\endgroup$
    – MR_BD
    Commented Sep 26, 2016 at 14:06
  • $\begingroup$ This problem is in flavor of Odd/Even-towns discretemath.imp.fu-berlin.de/DMII-2011-12/linalgmethod.pdf $\endgroup$
    – Max Alekseyev
    Commented Sep 26, 2016 at 14:16

2 Answers 2

Reset to default
6
$\begingroup$

The answer is $2^{q+o(q)}$ (well, there are rooms for improvement).

Example: consider all strings with $1$ at the last position and $(q-1)/2$ pairs of one's chosen from possible pairs of positions $(1,2)$, $(3,4),\dots$, $(2q-3,2q-2)$. It is a family consisting of $\binom{q-1}{(q-1)/2}$ strings.

For the estimate, choose index $j$ so that at least half of your strings has 1 at position $j$. Consider only them and remove this position from them. We have $2q-1$ positions, and intersection of any two strings is even. There may be at most $2^{q-1}$ such strings, this is already well known. Indeed, consider the space generated by these strings over $\mathbb{F}_2$. This space is contained in its own orthogonal complement, hence its dimension does not exceed $q-1$.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Being proved wrong has never been such a pleasure :-). $\endgroup$
    – fedja
    Commented Sep 26, 2016 at 23:22
2
$\begingroup$

If q is odd and you want even intersection, then this is the Frankl-Wilson Theorem (and indeed the upper bound is 2q). For odd intersection it seems it can be exponential. See https://www.dpmms.cam.ac.uk/~dce27/chapter1version2.pdf Theorem 4 and remark following.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .