Using the Zig Zag Theorem












1












$begingroup$


While learning about the Zig Zag Theorem, I noticed that we are able to build an expander family using the $left(d^4, d, frac 14right)$ graph construction. I don't understand why this one actually exists.



My question stems from page 6 in http://www.math.mcgill.ca/goren/667.2010/Neil.pdf.



Thank you.










share|cite|improve this question











$endgroup$












  • $begingroup$
    So, what is your question again? The way you worded your post is really vague.
    $endgroup$
    – Mike
    Jan 10 at 16:43
















1












$begingroup$


While learning about the Zig Zag Theorem, I noticed that we are able to build an expander family using the $left(d^4, d, frac 14right)$ graph construction. I don't understand why this one actually exists.



My question stems from page 6 in http://www.math.mcgill.ca/goren/667.2010/Neil.pdf.



Thank you.










share|cite|improve this question











$endgroup$












  • $begingroup$
    So, what is your question again? The way you worded your post is really vague.
    $endgroup$
    – Mike
    Jan 10 at 16:43














1












1








1





$begingroup$


While learning about the Zig Zag Theorem, I noticed that we are able to build an expander family using the $left(d^4, d, frac 14right)$ graph construction. I don't understand why this one actually exists.



My question stems from page 6 in http://www.math.mcgill.ca/goren/667.2010/Neil.pdf.



Thank you.










share|cite|improve this question











$endgroup$




While learning about the Zig Zag Theorem, I noticed that we are able to build an expander family using the $left(d^4, d, frac 14right)$ graph construction. I don't understand why this one actually exists.



My question stems from page 6 in http://www.math.mcgill.ca/goren/667.2010/Neil.pdf.



Thank you.







graph-theory






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Jan 11 at 13:46









amWhy

1




1










asked Jan 10 at 9:46









נירייב שמואלנירייב שמואל

195




195












  • $begingroup$
    So, what is your question again? The way you worded your post is really vague.
    $endgroup$
    – Mike
    Jan 10 at 16:43


















  • $begingroup$
    So, what is your question again? The way you worded your post is really vague.
    $endgroup$
    – Mike
    Jan 10 at 16:43
















$begingroup$
So, what is your question again? The way you worded your post is really vague.
$endgroup$
– Mike
Jan 10 at 16:43




$begingroup$
So, what is your question again? The way you worded your post is really vague.
$endgroup$
– Mike
Jan 10 at 16:43










1 Answer
1






active

oldest

votes


















0












$begingroup$

If we choose a random $d$-regular graph on $d^4$ vertices, then with positive probability its second eigenvalue is at most $frac d4$. This gives us the $(d^4, d, frac14)$-graph you want.



Actually, we expect the second eigenvalue to be $O(sqrt d)$, but it's harder to prove that.



We choose the random graph by taking the union of $d$ uniformly random matchings on $d^4$ vertices. This might sometimes be a multigraph, but we don't care; triple parallel edges are unlikely to occur, and we can fix all the double edges in a way that only improves expansion.



I'll assume that we can take $d$ sufficiently large for the approximations we want to hold; for small $d$, we have to do more messy calculations, and for very small $d$ we might have to manually look for the graph we want.





This is an application of the "trace method": we estimate the trace of the $k^{text{th}}$ power of the adjacency matrix of a random $d$-regular graph. This has a combinatorial interpretation: it counts closed walks of length $k$. It also gives the sum of the $k^{text{th}}$ powers of the eigenvalues. Here, we'll just take $k=10$.



We have three types of closed walks to care about:




  1. Walks that follow a simple cycle of length $10$.

  2. Walks that backtrack and don't include a cycle at all.

  3. Walks that have a cycle at some point, but have fewer than $10$ distinct edges.


For the first kind: we have a bit under $(d^4)^{10}$ ways to choose which vertices the walk visits. Label the desired edges between them with which matching we want them to come from; this can be done in a bit fewer than $d^{10}$ ways that avoid the same label between multiple vertices. Then the probability that the edges we've asked for are present with probability a bit over $frac{1}{d^4}$ each, giving us $d^{40} cdot d^{10} cdot frac{1}{d^{40}} = d^{10}$ walks of this type in expectation, plus lower order terms.



The second kind of walk, we count deterministically in any $d$-regular graph. We have $d^4$ ways to choose the starting vertex, and since every edge is walked twice, we have at most $5$ edges to choose. Each new edge we choose can be chosen in fewer than $d$ ways, for $d^5$ choices. The number of shapes for this walk (e.g. walk 5 edges then walk back, or walk back and forth across an edge 5 times, etc.) is constant, so the contribution is $O(d^9)$.



The third kind of walk is counted similarly to the first, but more sloppily. Each of these has at most $9$ edges, and because they contain a cycle, they have at most as many vertices as edges. So for some $kle 9$, we choose the vertices in the walk (in about $d^{4k}$ ways), then label the edges with the matching they come from (in about $d^k$ ways), then find the probability that the resulting walk occurs in the graph (which is about $d^{-4k}$). The expected number of walks of this type is $O(d^k) = O(d^9)$ by multiplying these terms, and the number of different shapes is once again constant.



We conclude that the expected number of closed walks of length $10$ is $d^{10} + O(d^9)$. This means that there must exist a graph for which the number of closed walks of this length is at most this large.



We have $lambda_1^{10} + lambda_2^{10} + dots + lambda_{4d}^{10} le d^{10} + O(d^9)$ for this graph. We know $lambda_1 = d$ and the $lambda_3, dots, lambda_{4d}$ terms are nonnegative, so $lambda_2^{10} le O(d^9)$, or $|lambda_2| = O(d^{9/10})$. Take $d$ large enough, and $lambda_2 le frac d4$.






share|cite|improve this answer











$endgroup$













    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%2f3068442%2fusing-the-zig-zag-theorem%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    1 Answer
    1






    active

    oldest

    votes








    1 Answer
    1






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    0












    $begingroup$

    If we choose a random $d$-regular graph on $d^4$ vertices, then with positive probability its second eigenvalue is at most $frac d4$. This gives us the $(d^4, d, frac14)$-graph you want.



    Actually, we expect the second eigenvalue to be $O(sqrt d)$, but it's harder to prove that.



    We choose the random graph by taking the union of $d$ uniformly random matchings on $d^4$ vertices. This might sometimes be a multigraph, but we don't care; triple parallel edges are unlikely to occur, and we can fix all the double edges in a way that only improves expansion.



    I'll assume that we can take $d$ sufficiently large for the approximations we want to hold; for small $d$, we have to do more messy calculations, and for very small $d$ we might have to manually look for the graph we want.





    This is an application of the "trace method": we estimate the trace of the $k^{text{th}}$ power of the adjacency matrix of a random $d$-regular graph. This has a combinatorial interpretation: it counts closed walks of length $k$. It also gives the sum of the $k^{text{th}}$ powers of the eigenvalues. Here, we'll just take $k=10$.



    We have three types of closed walks to care about:




    1. Walks that follow a simple cycle of length $10$.

    2. Walks that backtrack and don't include a cycle at all.

    3. Walks that have a cycle at some point, but have fewer than $10$ distinct edges.


    For the first kind: we have a bit under $(d^4)^{10}$ ways to choose which vertices the walk visits. Label the desired edges between them with which matching we want them to come from; this can be done in a bit fewer than $d^{10}$ ways that avoid the same label between multiple vertices. Then the probability that the edges we've asked for are present with probability a bit over $frac{1}{d^4}$ each, giving us $d^{40} cdot d^{10} cdot frac{1}{d^{40}} = d^{10}$ walks of this type in expectation, plus lower order terms.



    The second kind of walk, we count deterministically in any $d$-regular graph. We have $d^4$ ways to choose the starting vertex, and since every edge is walked twice, we have at most $5$ edges to choose. Each new edge we choose can be chosen in fewer than $d$ ways, for $d^5$ choices. The number of shapes for this walk (e.g. walk 5 edges then walk back, or walk back and forth across an edge 5 times, etc.) is constant, so the contribution is $O(d^9)$.



    The third kind of walk is counted similarly to the first, but more sloppily. Each of these has at most $9$ edges, and because they contain a cycle, they have at most as many vertices as edges. So for some $kle 9$, we choose the vertices in the walk (in about $d^{4k}$ ways), then label the edges with the matching they come from (in about $d^k$ ways), then find the probability that the resulting walk occurs in the graph (which is about $d^{-4k}$). The expected number of walks of this type is $O(d^k) = O(d^9)$ by multiplying these terms, and the number of different shapes is once again constant.



    We conclude that the expected number of closed walks of length $10$ is $d^{10} + O(d^9)$. This means that there must exist a graph for which the number of closed walks of this length is at most this large.



    We have $lambda_1^{10} + lambda_2^{10} + dots + lambda_{4d}^{10} le d^{10} + O(d^9)$ for this graph. We know $lambda_1 = d$ and the $lambda_3, dots, lambda_{4d}$ terms are nonnegative, so $lambda_2^{10} le O(d^9)$, or $|lambda_2| = O(d^{9/10})$. Take $d$ large enough, and $lambda_2 le frac d4$.






    share|cite|improve this answer











    $endgroup$


















      0












      $begingroup$

      If we choose a random $d$-regular graph on $d^4$ vertices, then with positive probability its second eigenvalue is at most $frac d4$. This gives us the $(d^4, d, frac14)$-graph you want.



      Actually, we expect the second eigenvalue to be $O(sqrt d)$, but it's harder to prove that.



      We choose the random graph by taking the union of $d$ uniformly random matchings on $d^4$ vertices. This might sometimes be a multigraph, but we don't care; triple parallel edges are unlikely to occur, and we can fix all the double edges in a way that only improves expansion.



      I'll assume that we can take $d$ sufficiently large for the approximations we want to hold; for small $d$, we have to do more messy calculations, and for very small $d$ we might have to manually look for the graph we want.





      This is an application of the "trace method": we estimate the trace of the $k^{text{th}}$ power of the adjacency matrix of a random $d$-regular graph. This has a combinatorial interpretation: it counts closed walks of length $k$. It also gives the sum of the $k^{text{th}}$ powers of the eigenvalues. Here, we'll just take $k=10$.



      We have three types of closed walks to care about:




      1. Walks that follow a simple cycle of length $10$.

      2. Walks that backtrack and don't include a cycle at all.

      3. Walks that have a cycle at some point, but have fewer than $10$ distinct edges.


      For the first kind: we have a bit under $(d^4)^{10}$ ways to choose which vertices the walk visits. Label the desired edges between them with which matching we want them to come from; this can be done in a bit fewer than $d^{10}$ ways that avoid the same label between multiple vertices. Then the probability that the edges we've asked for are present with probability a bit over $frac{1}{d^4}$ each, giving us $d^{40} cdot d^{10} cdot frac{1}{d^{40}} = d^{10}$ walks of this type in expectation, plus lower order terms.



      The second kind of walk, we count deterministically in any $d$-regular graph. We have $d^4$ ways to choose the starting vertex, and since every edge is walked twice, we have at most $5$ edges to choose. Each new edge we choose can be chosen in fewer than $d$ ways, for $d^5$ choices. The number of shapes for this walk (e.g. walk 5 edges then walk back, or walk back and forth across an edge 5 times, etc.) is constant, so the contribution is $O(d^9)$.



      The third kind of walk is counted similarly to the first, but more sloppily. Each of these has at most $9$ edges, and because they contain a cycle, they have at most as many vertices as edges. So for some $kle 9$, we choose the vertices in the walk (in about $d^{4k}$ ways), then label the edges with the matching they come from (in about $d^k$ ways), then find the probability that the resulting walk occurs in the graph (which is about $d^{-4k}$). The expected number of walks of this type is $O(d^k) = O(d^9)$ by multiplying these terms, and the number of different shapes is once again constant.



      We conclude that the expected number of closed walks of length $10$ is $d^{10} + O(d^9)$. This means that there must exist a graph for which the number of closed walks of this length is at most this large.



      We have $lambda_1^{10} + lambda_2^{10} + dots + lambda_{4d}^{10} le d^{10} + O(d^9)$ for this graph. We know $lambda_1 = d$ and the $lambda_3, dots, lambda_{4d}$ terms are nonnegative, so $lambda_2^{10} le O(d^9)$, or $|lambda_2| = O(d^{9/10})$. Take $d$ large enough, and $lambda_2 le frac d4$.






      share|cite|improve this answer











      $endgroup$
















        0












        0








        0





        $begingroup$

        If we choose a random $d$-regular graph on $d^4$ vertices, then with positive probability its second eigenvalue is at most $frac d4$. This gives us the $(d^4, d, frac14)$-graph you want.



        Actually, we expect the second eigenvalue to be $O(sqrt d)$, but it's harder to prove that.



        We choose the random graph by taking the union of $d$ uniformly random matchings on $d^4$ vertices. This might sometimes be a multigraph, but we don't care; triple parallel edges are unlikely to occur, and we can fix all the double edges in a way that only improves expansion.



        I'll assume that we can take $d$ sufficiently large for the approximations we want to hold; for small $d$, we have to do more messy calculations, and for very small $d$ we might have to manually look for the graph we want.





        This is an application of the "trace method": we estimate the trace of the $k^{text{th}}$ power of the adjacency matrix of a random $d$-regular graph. This has a combinatorial interpretation: it counts closed walks of length $k$. It also gives the sum of the $k^{text{th}}$ powers of the eigenvalues. Here, we'll just take $k=10$.



        We have three types of closed walks to care about:




        1. Walks that follow a simple cycle of length $10$.

        2. Walks that backtrack and don't include a cycle at all.

        3. Walks that have a cycle at some point, but have fewer than $10$ distinct edges.


        For the first kind: we have a bit under $(d^4)^{10}$ ways to choose which vertices the walk visits. Label the desired edges between them with which matching we want them to come from; this can be done in a bit fewer than $d^{10}$ ways that avoid the same label between multiple vertices. Then the probability that the edges we've asked for are present with probability a bit over $frac{1}{d^4}$ each, giving us $d^{40} cdot d^{10} cdot frac{1}{d^{40}} = d^{10}$ walks of this type in expectation, plus lower order terms.



        The second kind of walk, we count deterministically in any $d$-regular graph. We have $d^4$ ways to choose the starting vertex, and since every edge is walked twice, we have at most $5$ edges to choose. Each new edge we choose can be chosen in fewer than $d$ ways, for $d^5$ choices. The number of shapes for this walk (e.g. walk 5 edges then walk back, or walk back and forth across an edge 5 times, etc.) is constant, so the contribution is $O(d^9)$.



        The third kind of walk is counted similarly to the first, but more sloppily. Each of these has at most $9$ edges, and because they contain a cycle, they have at most as many vertices as edges. So for some $kle 9$, we choose the vertices in the walk (in about $d^{4k}$ ways), then label the edges with the matching they come from (in about $d^k$ ways), then find the probability that the resulting walk occurs in the graph (which is about $d^{-4k}$). The expected number of walks of this type is $O(d^k) = O(d^9)$ by multiplying these terms, and the number of different shapes is once again constant.



        We conclude that the expected number of closed walks of length $10$ is $d^{10} + O(d^9)$. This means that there must exist a graph for which the number of closed walks of this length is at most this large.



        We have $lambda_1^{10} + lambda_2^{10} + dots + lambda_{4d}^{10} le d^{10} + O(d^9)$ for this graph. We know $lambda_1 = d$ and the $lambda_3, dots, lambda_{4d}$ terms are nonnegative, so $lambda_2^{10} le O(d^9)$, or $|lambda_2| = O(d^{9/10})$. Take $d$ large enough, and $lambda_2 le frac d4$.






        share|cite|improve this answer











        $endgroup$



        If we choose a random $d$-regular graph on $d^4$ vertices, then with positive probability its second eigenvalue is at most $frac d4$. This gives us the $(d^4, d, frac14)$-graph you want.



        Actually, we expect the second eigenvalue to be $O(sqrt d)$, but it's harder to prove that.



        We choose the random graph by taking the union of $d$ uniformly random matchings on $d^4$ vertices. This might sometimes be a multigraph, but we don't care; triple parallel edges are unlikely to occur, and we can fix all the double edges in a way that only improves expansion.



        I'll assume that we can take $d$ sufficiently large for the approximations we want to hold; for small $d$, we have to do more messy calculations, and for very small $d$ we might have to manually look for the graph we want.





        This is an application of the "trace method": we estimate the trace of the $k^{text{th}}$ power of the adjacency matrix of a random $d$-regular graph. This has a combinatorial interpretation: it counts closed walks of length $k$. It also gives the sum of the $k^{text{th}}$ powers of the eigenvalues. Here, we'll just take $k=10$.



        We have three types of closed walks to care about:




        1. Walks that follow a simple cycle of length $10$.

        2. Walks that backtrack and don't include a cycle at all.

        3. Walks that have a cycle at some point, but have fewer than $10$ distinct edges.


        For the first kind: we have a bit under $(d^4)^{10}$ ways to choose which vertices the walk visits. Label the desired edges between them with which matching we want them to come from; this can be done in a bit fewer than $d^{10}$ ways that avoid the same label between multiple vertices. Then the probability that the edges we've asked for are present with probability a bit over $frac{1}{d^4}$ each, giving us $d^{40} cdot d^{10} cdot frac{1}{d^{40}} = d^{10}$ walks of this type in expectation, plus lower order terms.



        The second kind of walk, we count deterministically in any $d$-regular graph. We have $d^4$ ways to choose the starting vertex, and since every edge is walked twice, we have at most $5$ edges to choose. Each new edge we choose can be chosen in fewer than $d$ ways, for $d^5$ choices. The number of shapes for this walk (e.g. walk 5 edges then walk back, or walk back and forth across an edge 5 times, etc.) is constant, so the contribution is $O(d^9)$.



        The third kind of walk is counted similarly to the first, but more sloppily. Each of these has at most $9$ edges, and because they contain a cycle, they have at most as many vertices as edges. So for some $kle 9$, we choose the vertices in the walk (in about $d^{4k}$ ways), then label the edges with the matching they come from (in about $d^k$ ways), then find the probability that the resulting walk occurs in the graph (which is about $d^{-4k}$). The expected number of walks of this type is $O(d^k) = O(d^9)$ by multiplying these terms, and the number of different shapes is once again constant.



        We conclude that the expected number of closed walks of length $10$ is $d^{10} + O(d^9)$. This means that there must exist a graph for which the number of closed walks of this length is at most this large.



        We have $lambda_1^{10} + lambda_2^{10} + dots + lambda_{4d}^{10} le d^{10} + O(d^9)$ for this graph. We know $lambda_1 = d$ and the $lambda_3, dots, lambda_{4d}$ terms are nonnegative, so $lambda_2^{10} le O(d^9)$, or $|lambda_2| = O(d^{9/10})$. Take $d$ large enough, and $lambda_2 le frac d4$.







        share|cite|improve this answer














        share|cite|improve this answer



        share|cite|improve this answer








        edited Jan 10 at 18:02

























        answered Jan 10 at 17:53









        Misha LavrovMisha Lavrov

        47k657107




        47k657107






























            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%2f3068442%2fusing-the-zig-zag-theorem%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

            Human spaceflight

            Can not write log (Is /dev/pts mounted?) - openpty in Ubuntu-on-Windows?

            張江高科駅