Binary matrix with fixed inner product.












2












$begingroup$


Suppose that $m, n$ are two positive integers such that $m<<n$. Let $a, b, c$ be the three positive integers such that $aleq b < c$. Consider a binary matrix $Ain {0,1}^{mtimes n}$, such that for any two differnt columns $u$ and $v$ of matrix $A$, it is the case that,
$$aleqlangle u ,v rangle leq b,$$



and every column should contain at least $c$ numbers of $1's$.



Is it possible to construct such a matrix $A$ given the parameters $m,n, a,b,c$?










share|cite|improve this question











$endgroup$












  • $begingroup$
    The columns are of dimension $m$, right? So, basically you look for $A$ such that all off-diagonal elements of $A^TA$ are in $[a,b]$.
    $endgroup$
    – Berci
    Jan 24 at 10:19








  • 1




    $begingroup$
    This may be a dissatisfying answer, but can't you just pick a binary vector $v in mathbb{R}^m$ so that $a leq langle v, v rangle leq b$ and let each of the columns of $A$ be equal to $v$?
    $endgroup$
    – Eric
    Jan 24 at 10:41










  • $begingroup$
    I edited the question for both of you.
    $endgroup$
    – Shashank Ranjan
    Jan 24 at 11:31
















2












$begingroup$


Suppose that $m, n$ are two positive integers such that $m<<n$. Let $a, b, c$ be the three positive integers such that $aleq b < c$. Consider a binary matrix $Ain {0,1}^{mtimes n}$, such that for any two differnt columns $u$ and $v$ of matrix $A$, it is the case that,
$$aleqlangle u ,v rangle leq b,$$



and every column should contain at least $c$ numbers of $1's$.



Is it possible to construct such a matrix $A$ given the parameters $m,n, a,b,c$?










share|cite|improve this question











$endgroup$












  • $begingroup$
    The columns are of dimension $m$, right? So, basically you look for $A$ such that all off-diagonal elements of $A^TA$ are in $[a,b]$.
    $endgroup$
    – Berci
    Jan 24 at 10:19








  • 1




    $begingroup$
    This may be a dissatisfying answer, but can't you just pick a binary vector $v in mathbb{R}^m$ so that $a leq langle v, v rangle leq b$ and let each of the columns of $A$ be equal to $v$?
    $endgroup$
    – Eric
    Jan 24 at 10:41










  • $begingroup$
    I edited the question for both of you.
    $endgroup$
    – Shashank Ranjan
    Jan 24 at 11:31














2












2








2


1



$begingroup$


Suppose that $m, n$ are two positive integers such that $m<<n$. Let $a, b, c$ be the three positive integers such that $aleq b < c$. Consider a binary matrix $Ain {0,1}^{mtimes n}$, such that for any two differnt columns $u$ and $v$ of matrix $A$, it is the case that,
$$aleqlangle u ,v rangle leq b,$$



and every column should contain at least $c$ numbers of $1's$.



Is it possible to construct such a matrix $A$ given the parameters $m,n, a,b,c$?










share|cite|improve this question











$endgroup$




Suppose that $m, n$ are two positive integers such that $m<<n$. Let $a, b, c$ be the three positive integers such that $aleq b < c$. Consider a binary matrix $Ain {0,1}^{mtimes n}$, such that for any two differnt columns $u$ and $v$ of matrix $A$, it is the case that,
$$aleqlangle u ,v rangle leq b,$$



and every column should contain at least $c$ numbers of $1's$.



Is it possible to construct such a matrix $A$ given the parameters $m,n, a,b,c$?







linear-algebra field-theory extension-field coding-theory finite-geometry






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Jan 24 at 11:30







Shashank Ranjan

















asked Jan 24 at 10:04









Shashank RanjanShashank Ranjan

84




84












  • $begingroup$
    The columns are of dimension $m$, right? So, basically you look for $A$ such that all off-diagonal elements of $A^TA$ are in $[a,b]$.
    $endgroup$
    – Berci
    Jan 24 at 10:19








  • 1




    $begingroup$
    This may be a dissatisfying answer, but can't you just pick a binary vector $v in mathbb{R}^m$ so that $a leq langle v, v rangle leq b$ and let each of the columns of $A$ be equal to $v$?
    $endgroup$
    – Eric
    Jan 24 at 10:41










  • $begingroup$
    I edited the question for both of you.
    $endgroup$
    – Shashank Ranjan
    Jan 24 at 11:31


















  • $begingroup$
    The columns are of dimension $m$, right? So, basically you look for $A$ such that all off-diagonal elements of $A^TA$ are in $[a,b]$.
    $endgroup$
    – Berci
    Jan 24 at 10:19








  • 1




    $begingroup$
    This may be a dissatisfying answer, but can't you just pick a binary vector $v in mathbb{R}^m$ so that $a leq langle v, v rangle leq b$ and let each of the columns of $A$ be equal to $v$?
    $endgroup$
    – Eric
    Jan 24 at 10:41










  • $begingroup$
    I edited the question for both of you.
    $endgroup$
    – Shashank Ranjan
    Jan 24 at 11:31
















$begingroup$
The columns are of dimension $m$, right? So, basically you look for $A$ such that all off-diagonal elements of $A^TA$ are in $[a,b]$.
$endgroup$
– Berci
Jan 24 at 10:19






$begingroup$
The columns are of dimension $m$, right? So, basically you look for $A$ such that all off-diagonal elements of $A^TA$ are in $[a,b]$.
$endgroup$
– Berci
Jan 24 at 10:19






1




1




$begingroup$
This may be a dissatisfying answer, but can't you just pick a binary vector $v in mathbb{R}^m$ so that $a leq langle v, v rangle leq b$ and let each of the columns of $A$ be equal to $v$?
$endgroup$
– Eric
Jan 24 at 10:41




$begingroup$
This may be a dissatisfying answer, but can't you just pick a binary vector $v in mathbb{R}^m$ so that $a leq langle v, v rangle leq b$ and let each of the columns of $A$ be equal to $v$?
$endgroup$
– Eric
Jan 24 at 10:41












$begingroup$
I edited the question for both of you.
$endgroup$
– Shashank Ranjan
Jan 24 at 11:31




$begingroup$
I edited the question for both of you.
$endgroup$
– Shashank Ranjan
Jan 24 at 11:31










2 Answers
2






active

oldest

votes


















0












$begingroup$

This is not a full answer but is a too long for a comment. It depends on how $n,c,m$ are chosen.



If $n > {{m}choose{c}}$ then two of the columns of $A$ must be equal. The inner product between these two columns is $c$ which is not between $a$ and $b$.



The answer for $n leq {{m}choose{c}}$ depends on the gap between $b$ and $c$ and also on $a$. For example if $b=c-1$ and $a=0$ and $n leq {{m}choose{c}}$ then the answer is yes. This is because you can pick the columns of $c$ such that any two columns disagree on at least one position where a $1$ occurs. Hence the inner product of any two columns would be bounded above by $c-1$.



However if $n= {{m}choose{c}}$ and $b=c-2$ the answer is no. In this case you must have two columns of $A$ which disagree at no more than one position where a one occurs. The inner product between these two columns is $c-1$.



The dependence on $a$ comes in because after choosing your first column of $A$, the remaining columns must have at least $a$ ones in positions which are ones in the the first columns. This cuts down on the number of your ${{m}choose{c}}$ options which are valid. If $a leq 2c-m$, then a doesn't put any restriction on the problem, since any two columns with $c$ ones must have at least $min {2c-m,0}$ common ones. For a larger than $2c-m$ you do have a real restriction in place.



Much more than that requires more combinatorics that I can manage.






share|cite|improve this answer











$endgroup$





















    0












    $begingroup$

    Sets with restricted intersection is what you want, the vector is the characteristic function of a subset of
    ${1,ldots,n}.$



    So if row $k$ is $$(a_{k,j})_{1leq jleq n}$$ the $k^{th}$ subset contains element $$j in {1,ldots,n},$$ if and only if $a_{i,j}=1.$



    A collection $cal A$ of subsets of
    ${1,ldots,n}$
    is $L$-intersecting, if
    for any two sets $A,B:$



    $$Acap B in L$$
    holds. Only the cardinality $s=|L|$ matters. Clearly $Lsubset {1,ldots,n}.$



    If the intersecting family $cal A$ is uniform (all its sets have fixed size) then
    $$
    |cal A| leq binom{n}{s}
    $$

    otherwise
    $$
    |cal A| leq sum_{i=0}^s binom{n}{i}.
    $$

    For you $s=b-a+1.$



    See the paper of Keevash for background and more: http://people.maths.ox.ac.uk/keevash/papers/cross-intersections-journal.pdf



    Edit: In general, good lower bounds are much harder to come by.



    For fixed $s=|L|,$ and fixed $k$ if we pick the set of intersections as $L={0,1,ldots,s-1},$ for all $kgeq sgeq 1,$ and $ngeq 2k^2,$ there exists a $k-$uniform family $cal A$ (all sets have cardinality $k$) with
    $$
    |cal A| geq (n/2k)^s,
    $$

    on ${1,ldots,n},$ such that $|Acap B|leq s-1$ for all distinct pairs $A,Bin {cal A}.$






    share|cite|improve this answer











    $endgroup$













    • $begingroup$
      can you please provide lower bound on the cardinality of A ?
      $endgroup$
      – Shashank Ranjan
      Jan 28 at 17:10












    • $begingroup$
      Please see modified answer and upvote if the answer is satisfactory.
      $endgroup$
      – kodlu
      Jan 28 at 22:27










    • $begingroup$
      @kondu Can you please provide the reference for the lower bound on |A| which you have mentioned in the above answer?
      $endgroup$
      – Shashank Ranjan
      Jan 29 at 19:09










    • $begingroup$
      It is described in the lecture notes by Babai & Frankl available at matthewkahle.org/download/file/fid/499. See page 87.
      $endgroup$
      – kodlu
      Jan 29 at 20:48










    • $begingroup$
      Thanks a lot. I have upvoted your answer but it will not be displayed as I have reputation less than 15.
      $endgroup$
      – Shashank Ranjan
      Jan 29 at 22:30











    Your Answer





    StackExchange.ifUsing("editor", function () {
    return StackExchange.using("mathjaxEditing", function () {
    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
    });
    });
    }, "mathjax-editing");

    StackExchange.ready(function() {
    var channelOptions = {
    tags: "".split(" "),
    id: "69"
    };
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function() {
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled) {
    StackExchange.using("snippets", function() {
    createEditor();
    });
    }
    else {
    createEditor();
    }
    });

    function createEditor() {
    StackExchange.prepareEditor({
    heartbeatType: 'answer',
    autoActivateHeartbeat: false,
    convertImagesToLinks: true,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: 10,
    bindNavPrevention: true,
    postfix: "",
    imageUploader: {
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    },
    noCode: true, onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    });


    }
    });














    draft saved

    draft discarded


















    StackExchange.ready(
    function () {
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3085688%2fbinary-matrix-with-fixed-inner-product%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    2 Answers
    2






    active

    oldest

    votes








    2 Answers
    2






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    0












    $begingroup$

    This is not a full answer but is a too long for a comment. It depends on how $n,c,m$ are chosen.



    If $n > {{m}choose{c}}$ then two of the columns of $A$ must be equal. The inner product between these two columns is $c$ which is not between $a$ and $b$.



    The answer for $n leq {{m}choose{c}}$ depends on the gap between $b$ and $c$ and also on $a$. For example if $b=c-1$ and $a=0$ and $n leq {{m}choose{c}}$ then the answer is yes. This is because you can pick the columns of $c$ such that any two columns disagree on at least one position where a $1$ occurs. Hence the inner product of any two columns would be bounded above by $c-1$.



    However if $n= {{m}choose{c}}$ and $b=c-2$ the answer is no. In this case you must have two columns of $A$ which disagree at no more than one position where a one occurs. The inner product between these two columns is $c-1$.



    The dependence on $a$ comes in because after choosing your first column of $A$, the remaining columns must have at least $a$ ones in positions which are ones in the the first columns. This cuts down on the number of your ${{m}choose{c}}$ options which are valid. If $a leq 2c-m$, then a doesn't put any restriction on the problem, since any two columns with $c$ ones must have at least $min {2c-m,0}$ common ones. For a larger than $2c-m$ you do have a real restriction in place.



    Much more than that requires more combinatorics that I can manage.






    share|cite|improve this answer











    $endgroup$


















      0












      $begingroup$

      This is not a full answer but is a too long for a comment. It depends on how $n,c,m$ are chosen.



      If $n > {{m}choose{c}}$ then two of the columns of $A$ must be equal. The inner product between these two columns is $c$ which is not between $a$ and $b$.



      The answer for $n leq {{m}choose{c}}$ depends on the gap between $b$ and $c$ and also on $a$. For example if $b=c-1$ and $a=0$ and $n leq {{m}choose{c}}$ then the answer is yes. This is because you can pick the columns of $c$ such that any two columns disagree on at least one position where a $1$ occurs. Hence the inner product of any two columns would be bounded above by $c-1$.



      However if $n= {{m}choose{c}}$ and $b=c-2$ the answer is no. In this case you must have two columns of $A$ which disagree at no more than one position where a one occurs. The inner product between these two columns is $c-1$.



      The dependence on $a$ comes in because after choosing your first column of $A$, the remaining columns must have at least $a$ ones in positions which are ones in the the first columns. This cuts down on the number of your ${{m}choose{c}}$ options which are valid. If $a leq 2c-m$, then a doesn't put any restriction on the problem, since any two columns with $c$ ones must have at least $min {2c-m,0}$ common ones. For a larger than $2c-m$ you do have a real restriction in place.



      Much more than that requires more combinatorics that I can manage.






      share|cite|improve this answer











      $endgroup$
















        0












        0








        0





        $begingroup$

        This is not a full answer but is a too long for a comment. It depends on how $n,c,m$ are chosen.



        If $n > {{m}choose{c}}$ then two of the columns of $A$ must be equal. The inner product between these two columns is $c$ which is not between $a$ and $b$.



        The answer for $n leq {{m}choose{c}}$ depends on the gap between $b$ and $c$ and also on $a$. For example if $b=c-1$ and $a=0$ and $n leq {{m}choose{c}}$ then the answer is yes. This is because you can pick the columns of $c$ such that any two columns disagree on at least one position where a $1$ occurs. Hence the inner product of any two columns would be bounded above by $c-1$.



        However if $n= {{m}choose{c}}$ and $b=c-2$ the answer is no. In this case you must have two columns of $A$ which disagree at no more than one position where a one occurs. The inner product between these two columns is $c-1$.



        The dependence on $a$ comes in because after choosing your first column of $A$, the remaining columns must have at least $a$ ones in positions which are ones in the the first columns. This cuts down on the number of your ${{m}choose{c}}$ options which are valid. If $a leq 2c-m$, then a doesn't put any restriction on the problem, since any two columns with $c$ ones must have at least $min {2c-m,0}$ common ones. For a larger than $2c-m$ you do have a real restriction in place.



        Much more than that requires more combinatorics that I can manage.






        share|cite|improve this answer











        $endgroup$



        This is not a full answer but is a too long for a comment. It depends on how $n,c,m$ are chosen.



        If $n > {{m}choose{c}}$ then two of the columns of $A$ must be equal. The inner product between these two columns is $c$ which is not between $a$ and $b$.



        The answer for $n leq {{m}choose{c}}$ depends on the gap between $b$ and $c$ and also on $a$. For example if $b=c-1$ and $a=0$ and $n leq {{m}choose{c}}$ then the answer is yes. This is because you can pick the columns of $c$ such that any two columns disagree on at least one position where a $1$ occurs. Hence the inner product of any two columns would be bounded above by $c-1$.



        However if $n= {{m}choose{c}}$ and $b=c-2$ the answer is no. In this case you must have two columns of $A$ which disagree at no more than one position where a one occurs. The inner product between these two columns is $c-1$.



        The dependence on $a$ comes in because after choosing your first column of $A$, the remaining columns must have at least $a$ ones in positions which are ones in the the first columns. This cuts down on the number of your ${{m}choose{c}}$ options which are valid. If $a leq 2c-m$, then a doesn't put any restriction on the problem, since any two columns with $c$ ones must have at least $min {2c-m,0}$ common ones. For a larger than $2c-m$ you do have a real restriction in place.



        Much more than that requires more combinatorics that I can manage.







        share|cite|improve this answer














        share|cite|improve this answer



        share|cite|improve this answer








        edited Jan 24 at 15:01

























        answered Jan 24 at 13:34









        EricEric

        3319




        3319























            0












            $begingroup$

            Sets with restricted intersection is what you want, the vector is the characteristic function of a subset of
            ${1,ldots,n}.$



            So if row $k$ is $$(a_{k,j})_{1leq jleq n}$$ the $k^{th}$ subset contains element $$j in {1,ldots,n},$$ if and only if $a_{i,j}=1.$



            A collection $cal A$ of subsets of
            ${1,ldots,n}$
            is $L$-intersecting, if
            for any two sets $A,B:$



            $$Acap B in L$$
            holds. Only the cardinality $s=|L|$ matters. Clearly $Lsubset {1,ldots,n}.$



            If the intersecting family $cal A$ is uniform (all its sets have fixed size) then
            $$
            |cal A| leq binom{n}{s}
            $$

            otherwise
            $$
            |cal A| leq sum_{i=0}^s binom{n}{i}.
            $$

            For you $s=b-a+1.$



            See the paper of Keevash for background and more: http://people.maths.ox.ac.uk/keevash/papers/cross-intersections-journal.pdf



            Edit: In general, good lower bounds are much harder to come by.



            For fixed $s=|L|,$ and fixed $k$ if we pick the set of intersections as $L={0,1,ldots,s-1},$ for all $kgeq sgeq 1,$ and $ngeq 2k^2,$ there exists a $k-$uniform family $cal A$ (all sets have cardinality $k$) with
            $$
            |cal A| geq (n/2k)^s,
            $$

            on ${1,ldots,n},$ such that $|Acap B|leq s-1$ for all distinct pairs $A,Bin {cal A}.$






            share|cite|improve this answer











            $endgroup$













            • $begingroup$
              can you please provide lower bound on the cardinality of A ?
              $endgroup$
              – Shashank Ranjan
              Jan 28 at 17:10












            • $begingroup$
              Please see modified answer and upvote if the answer is satisfactory.
              $endgroup$
              – kodlu
              Jan 28 at 22:27










            • $begingroup$
              @kondu Can you please provide the reference for the lower bound on |A| which you have mentioned in the above answer?
              $endgroup$
              – Shashank Ranjan
              Jan 29 at 19:09










            • $begingroup$
              It is described in the lecture notes by Babai & Frankl available at matthewkahle.org/download/file/fid/499. See page 87.
              $endgroup$
              – kodlu
              Jan 29 at 20:48










            • $begingroup$
              Thanks a lot. I have upvoted your answer but it will not be displayed as I have reputation less than 15.
              $endgroup$
              – Shashank Ranjan
              Jan 29 at 22:30
















            0












            $begingroup$

            Sets with restricted intersection is what you want, the vector is the characteristic function of a subset of
            ${1,ldots,n}.$



            So if row $k$ is $$(a_{k,j})_{1leq jleq n}$$ the $k^{th}$ subset contains element $$j in {1,ldots,n},$$ if and only if $a_{i,j}=1.$



            A collection $cal A$ of subsets of
            ${1,ldots,n}$
            is $L$-intersecting, if
            for any two sets $A,B:$



            $$Acap B in L$$
            holds. Only the cardinality $s=|L|$ matters. Clearly $Lsubset {1,ldots,n}.$



            If the intersecting family $cal A$ is uniform (all its sets have fixed size) then
            $$
            |cal A| leq binom{n}{s}
            $$

            otherwise
            $$
            |cal A| leq sum_{i=0}^s binom{n}{i}.
            $$

            For you $s=b-a+1.$



            See the paper of Keevash for background and more: http://people.maths.ox.ac.uk/keevash/papers/cross-intersections-journal.pdf



            Edit: In general, good lower bounds are much harder to come by.



            For fixed $s=|L|,$ and fixed $k$ if we pick the set of intersections as $L={0,1,ldots,s-1},$ for all $kgeq sgeq 1,$ and $ngeq 2k^2,$ there exists a $k-$uniform family $cal A$ (all sets have cardinality $k$) with
            $$
            |cal A| geq (n/2k)^s,
            $$

            on ${1,ldots,n},$ such that $|Acap B|leq s-1$ for all distinct pairs $A,Bin {cal A}.$






            share|cite|improve this answer











            $endgroup$













            • $begingroup$
              can you please provide lower bound on the cardinality of A ?
              $endgroup$
              – Shashank Ranjan
              Jan 28 at 17:10












            • $begingroup$
              Please see modified answer and upvote if the answer is satisfactory.
              $endgroup$
              – kodlu
              Jan 28 at 22:27










            • $begingroup$
              @kondu Can you please provide the reference for the lower bound on |A| which you have mentioned in the above answer?
              $endgroup$
              – Shashank Ranjan
              Jan 29 at 19:09










            • $begingroup$
              It is described in the lecture notes by Babai & Frankl available at matthewkahle.org/download/file/fid/499. See page 87.
              $endgroup$
              – kodlu
              Jan 29 at 20:48










            • $begingroup$
              Thanks a lot. I have upvoted your answer but it will not be displayed as I have reputation less than 15.
              $endgroup$
              – Shashank Ranjan
              Jan 29 at 22:30














            0












            0








            0





            $begingroup$

            Sets with restricted intersection is what you want, the vector is the characteristic function of a subset of
            ${1,ldots,n}.$



            So if row $k$ is $$(a_{k,j})_{1leq jleq n}$$ the $k^{th}$ subset contains element $$j in {1,ldots,n},$$ if and only if $a_{i,j}=1.$



            A collection $cal A$ of subsets of
            ${1,ldots,n}$
            is $L$-intersecting, if
            for any two sets $A,B:$



            $$Acap B in L$$
            holds. Only the cardinality $s=|L|$ matters. Clearly $Lsubset {1,ldots,n}.$



            If the intersecting family $cal A$ is uniform (all its sets have fixed size) then
            $$
            |cal A| leq binom{n}{s}
            $$

            otherwise
            $$
            |cal A| leq sum_{i=0}^s binom{n}{i}.
            $$

            For you $s=b-a+1.$



            See the paper of Keevash for background and more: http://people.maths.ox.ac.uk/keevash/papers/cross-intersections-journal.pdf



            Edit: In general, good lower bounds are much harder to come by.



            For fixed $s=|L|,$ and fixed $k$ if we pick the set of intersections as $L={0,1,ldots,s-1},$ for all $kgeq sgeq 1,$ and $ngeq 2k^2,$ there exists a $k-$uniform family $cal A$ (all sets have cardinality $k$) with
            $$
            |cal A| geq (n/2k)^s,
            $$

            on ${1,ldots,n},$ such that $|Acap B|leq s-1$ for all distinct pairs $A,Bin {cal A}.$






            share|cite|improve this answer











            $endgroup$



            Sets with restricted intersection is what you want, the vector is the characteristic function of a subset of
            ${1,ldots,n}.$



            So if row $k$ is $$(a_{k,j})_{1leq jleq n}$$ the $k^{th}$ subset contains element $$j in {1,ldots,n},$$ if and only if $a_{i,j}=1.$



            A collection $cal A$ of subsets of
            ${1,ldots,n}$
            is $L$-intersecting, if
            for any two sets $A,B:$



            $$Acap B in L$$
            holds. Only the cardinality $s=|L|$ matters. Clearly $Lsubset {1,ldots,n}.$



            If the intersecting family $cal A$ is uniform (all its sets have fixed size) then
            $$
            |cal A| leq binom{n}{s}
            $$

            otherwise
            $$
            |cal A| leq sum_{i=0}^s binom{n}{i}.
            $$

            For you $s=b-a+1.$



            See the paper of Keevash for background and more: http://people.maths.ox.ac.uk/keevash/papers/cross-intersections-journal.pdf



            Edit: In general, good lower bounds are much harder to come by.



            For fixed $s=|L|,$ and fixed $k$ if we pick the set of intersections as $L={0,1,ldots,s-1},$ for all $kgeq sgeq 1,$ and $ngeq 2k^2,$ there exists a $k-$uniform family $cal A$ (all sets have cardinality $k$) with
            $$
            |cal A| geq (n/2k)^s,
            $$

            on ${1,ldots,n},$ such that $|Acap B|leq s-1$ for all distinct pairs $A,Bin {cal A}.$







            share|cite|improve this answer














            share|cite|improve this answer



            share|cite|improve this answer








            edited Jan 28 at 22:26

























            answered Jan 26 at 21:48









            kodlukodlu

            3,390716




            3,390716












            • $begingroup$
              can you please provide lower bound on the cardinality of A ?
              $endgroup$
              – Shashank Ranjan
              Jan 28 at 17:10












            • $begingroup$
              Please see modified answer and upvote if the answer is satisfactory.
              $endgroup$
              – kodlu
              Jan 28 at 22:27










            • $begingroup$
              @kondu Can you please provide the reference for the lower bound on |A| which you have mentioned in the above answer?
              $endgroup$
              – Shashank Ranjan
              Jan 29 at 19:09










            • $begingroup$
              It is described in the lecture notes by Babai & Frankl available at matthewkahle.org/download/file/fid/499. See page 87.
              $endgroup$
              – kodlu
              Jan 29 at 20:48










            • $begingroup$
              Thanks a lot. I have upvoted your answer but it will not be displayed as I have reputation less than 15.
              $endgroup$
              – Shashank Ranjan
              Jan 29 at 22:30


















            • $begingroup$
              can you please provide lower bound on the cardinality of A ?
              $endgroup$
              – Shashank Ranjan
              Jan 28 at 17:10












            • $begingroup$
              Please see modified answer and upvote if the answer is satisfactory.
              $endgroup$
              – kodlu
              Jan 28 at 22:27










            • $begingroup$
              @kondu Can you please provide the reference for the lower bound on |A| which you have mentioned in the above answer?
              $endgroup$
              – Shashank Ranjan
              Jan 29 at 19:09










            • $begingroup$
              It is described in the lecture notes by Babai & Frankl available at matthewkahle.org/download/file/fid/499. See page 87.
              $endgroup$
              – kodlu
              Jan 29 at 20:48










            • $begingroup$
              Thanks a lot. I have upvoted your answer but it will not be displayed as I have reputation less than 15.
              $endgroup$
              – Shashank Ranjan
              Jan 29 at 22:30
















            $begingroup$
            can you please provide lower bound on the cardinality of A ?
            $endgroup$
            – Shashank Ranjan
            Jan 28 at 17:10






            $begingroup$
            can you please provide lower bound on the cardinality of A ?
            $endgroup$
            – Shashank Ranjan
            Jan 28 at 17:10














            $begingroup$
            Please see modified answer and upvote if the answer is satisfactory.
            $endgroup$
            – kodlu
            Jan 28 at 22:27




            $begingroup$
            Please see modified answer and upvote if the answer is satisfactory.
            $endgroup$
            – kodlu
            Jan 28 at 22:27












            $begingroup$
            @kondu Can you please provide the reference for the lower bound on |A| which you have mentioned in the above answer?
            $endgroup$
            – Shashank Ranjan
            Jan 29 at 19:09




            $begingroup$
            @kondu Can you please provide the reference for the lower bound on |A| which you have mentioned in the above answer?
            $endgroup$
            – Shashank Ranjan
            Jan 29 at 19:09












            $begingroup$
            It is described in the lecture notes by Babai & Frankl available at matthewkahle.org/download/file/fid/499. See page 87.
            $endgroup$
            – kodlu
            Jan 29 at 20:48




            $begingroup$
            It is described in the lecture notes by Babai & Frankl available at matthewkahle.org/download/file/fid/499. See page 87.
            $endgroup$
            – kodlu
            Jan 29 at 20:48












            $begingroup$
            Thanks a lot. I have upvoted your answer but it will not be displayed as I have reputation less than 15.
            $endgroup$
            – Shashank Ranjan
            Jan 29 at 22:30




            $begingroup$
            Thanks a lot. I have upvoted your answer but it will not be displayed as I have reputation less than 15.
            $endgroup$
            – Shashank Ranjan
            Jan 29 at 22:30


















            draft saved

            draft discarded




















































            Thanks for contributing an answer to Mathematics Stack Exchange!


            • Please be sure to answer the question. Provide details and share your research!

            But avoid



            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.


            Use MathJax to format equations. MathJax reference.


            To learn more, see our tips on writing great answers.




            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3085688%2fbinary-matrix-with-fixed-inner-product%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown







            Popular posts from this blog

            Mario Kart Wii

            Partial Derivative Guidance.

            Understanding the size os this class of aleatory events