The Maximimum Monochromatic k-Cliques for Complete Graph











up vote
3
down vote

favorite
1












Show:
For a complete graph $K_{n}$, there is a coloring of the edges with $2$ colors, such that the number of monochromatic $k$-Cliques is a maximum of $binom{n}{k}2^{1-binom{k}{2}}$.



I do not know where to begin on this exercise. As a hint, our professor gave us the following pre-exercise, which I have been able to solve:




Let $n in mathbb N$, and $mathcal{K}$ be the set of permutations
possible for a set ${1,...,n}$. Let $sigma in mathcal{K}, $ such
that $sigma: [n] to [n]$ is a randomly selected permutation. Find
the probability space, define random variable $X$ as the number of
fixed points and find $mathbb E[X]$.




How do the two questions fit together? I am lost.










share|cite|improve this question






















  • I do not know about those random graph and just google about that. And I found people.cs.pitt.edu/~kirk/cs3150spring06/HW6_B.pdf Problem 6.2A has a similar question - which the number there is the expected number of monochromatic clique. But I do not quite follow how is that related to "at most".
    – BGM
    Nov 20 at 16:17















up vote
3
down vote

favorite
1












Show:
For a complete graph $K_{n}$, there is a coloring of the edges with $2$ colors, such that the number of monochromatic $k$-Cliques is a maximum of $binom{n}{k}2^{1-binom{k}{2}}$.



I do not know where to begin on this exercise. As a hint, our professor gave us the following pre-exercise, which I have been able to solve:




Let $n in mathbb N$, and $mathcal{K}$ be the set of permutations
possible for a set ${1,...,n}$. Let $sigma in mathcal{K}, $ such
that $sigma: [n] to [n]$ is a randomly selected permutation. Find
the probability space, define random variable $X$ as the number of
fixed points and find $mathbb E[X]$.




How do the two questions fit together? I am lost.










share|cite|improve this question






















  • I do not know about those random graph and just google about that. And I found people.cs.pitt.edu/~kirk/cs3150spring06/HW6_B.pdf Problem 6.2A has a similar question - which the number there is the expected number of monochromatic clique. But I do not quite follow how is that related to "at most".
    – BGM
    Nov 20 at 16:17













up vote
3
down vote

favorite
1









up vote
3
down vote

favorite
1






1





Show:
For a complete graph $K_{n}$, there is a coloring of the edges with $2$ colors, such that the number of monochromatic $k$-Cliques is a maximum of $binom{n}{k}2^{1-binom{k}{2}}$.



I do not know where to begin on this exercise. As a hint, our professor gave us the following pre-exercise, which I have been able to solve:




Let $n in mathbb N$, and $mathcal{K}$ be the set of permutations
possible for a set ${1,...,n}$. Let $sigma in mathcal{K}, $ such
that $sigma: [n] to [n]$ is a randomly selected permutation. Find
the probability space, define random variable $X$ as the number of
fixed points and find $mathbb E[X]$.




How do the two questions fit together? I am lost.










share|cite|improve this question













Show:
For a complete graph $K_{n}$, there is a coloring of the edges with $2$ colors, such that the number of monochromatic $k$-Cliques is a maximum of $binom{n}{k}2^{1-binom{k}{2}}$.



I do not know where to begin on this exercise. As a hint, our professor gave us the following pre-exercise, which I have been able to solve:




Let $n in mathbb N$, and $mathcal{K}$ be the set of permutations
possible for a set ${1,...,n}$. Let $sigma in mathcal{K}, $ such
that $sigma: [n] to [n]$ is a randomly selected permutation. Find
the probability space, define random variable $X$ as the number of
fixed points and find $mathbb E[X]$.




How do the two questions fit together? I am lost.







probability stochastic-processes permutations






share|cite|improve this question













share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










asked Nov 17 at 15:10









SABOY

484211




484211












  • I do not know about those random graph and just google about that. And I found people.cs.pitt.edu/~kirk/cs3150spring06/HW6_B.pdf Problem 6.2A has a similar question - which the number there is the expected number of monochromatic clique. But I do not quite follow how is that related to "at most".
    – BGM
    Nov 20 at 16:17


















  • I do not know about those random graph and just google about that. And I found people.cs.pitt.edu/~kirk/cs3150spring06/HW6_B.pdf Problem 6.2A has a similar question - which the number there is the expected number of monochromatic clique. But I do not quite follow how is that related to "at most".
    – BGM
    Nov 20 at 16:17
















I do not know about those random graph and just google about that. And I found people.cs.pitt.edu/~kirk/cs3150spring06/HW6_B.pdf Problem 6.2A has a similar question - which the number there is the expected number of monochromatic clique. But I do not quite follow how is that related to "at most".
– BGM
Nov 20 at 16:17




I do not know about those random graph and just google about that. And I found people.cs.pitt.edu/~kirk/cs3150spring06/HW6_B.pdf Problem 6.2A has a similar question - which the number there is the expected number of monochromatic clique. But I do not quite follow how is that related to "at most".
– BGM
Nov 20 at 16:17










1 Answer
1






active

oldest

votes

















up vote
2
down vote



accepted
+50










This problem is a classical problem in probabilistic graph theory due to Erdos and can be found in pretty much any introductory course on probabilistic graph theory.



Denote by $I_{x_1,...,x_k}$ the indicator function of the k-clique of vertices ${x_1,...,x_k}$(for a random coloring of $K_n$). Thus $I_{x_1,...,x_k}$ is 1 if ${x_1,...,x_k}$ is monochromatic or 0 else. Then the total number of monochromatic k-Cliques is equal to $sum_{x_1,...,x_k}I_{x_1,...,x_k}$ where the sum is taken over all ${nchoose k}$ groups of k-vertices in the graph. The expected number of monochromatic k-Cliques is then equal to ${nchoose k}P({x_1,...,x_k}$ is monochromatic $) = {nchoose k}2^{1-{kchoose 2}}$, by linearity of expectation and also by $E(I_A)=P(A)$, for any event set A, so you can find at least one graph with ${nchoose k}2^{1-{kchoose 2}}$ monochromatic k-Cliques.



For completion, note that $P({x_1,...,x_k}$ is monochromatic $) = 2^{1-{kchoose 2}}$ because ${x_1,...,x_k}$ is monochromatic if it is either red or blue(whence the factor of 1 in its exponent and the probability that each of its $k choose 2$ edges is red is exactly $frac{1}{2}$)






share|cite|improve this answer























    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',
    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%2f3002457%2fthe-maximimum-monochromatic-k-cliques-for-complete-graph%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








    up vote
    2
    down vote



    accepted
    +50










    This problem is a classical problem in probabilistic graph theory due to Erdos and can be found in pretty much any introductory course on probabilistic graph theory.



    Denote by $I_{x_1,...,x_k}$ the indicator function of the k-clique of vertices ${x_1,...,x_k}$(for a random coloring of $K_n$). Thus $I_{x_1,...,x_k}$ is 1 if ${x_1,...,x_k}$ is monochromatic or 0 else. Then the total number of monochromatic k-Cliques is equal to $sum_{x_1,...,x_k}I_{x_1,...,x_k}$ where the sum is taken over all ${nchoose k}$ groups of k-vertices in the graph. The expected number of monochromatic k-Cliques is then equal to ${nchoose k}P({x_1,...,x_k}$ is monochromatic $) = {nchoose k}2^{1-{kchoose 2}}$, by linearity of expectation and also by $E(I_A)=P(A)$, for any event set A, so you can find at least one graph with ${nchoose k}2^{1-{kchoose 2}}$ monochromatic k-Cliques.



    For completion, note that $P({x_1,...,x_k}$ is monochromatic $) = 2^{1-{kchoose 2}}$ because ${x_1,...,x_k}$ is monochromatic if it is either red or blue(whence the factor of 1 in its exponent and the probability that each of its $k choose 2$ edges is red is exactly $frac{1}{2}$)






    share|cite|improve this answer



























      up vote
      2
      down vote



      accepted
      +50










      This problem is a classical problem in probabilistic graph theory due to Erdos and can be found in pretty much any introductory course on probabilistic graph theory.



      Denote by $I_{x_1,...,x_k}$ the indicator function of the k-clique of vertices ${x_1,...,x_k}$(for a random coloring of $K_n$). Thus $I_{x_1,...,x_k}$ is 1 if ${x_1,...,x_k}$ is monochromatic or 0 else. Then the total number of monochromatic k-Cliques is equal to $sum_{x_1,...,x_k}I_{x_1,...,x_k}$ where the sum is taken over all ${nchoose k}$ groups of k-vertices in the graph. The expected number of monochromatic k-Cliques is then equal to ${nchoose k}P({x_1,...,x_k}$ is monochromatic $) = {nchoose k}2^{1-{kchoose 2}}$, by linearity of expectation and also by $E(I_A)=P(A)$, for any event set A, so you can find at least one graph with ${nchoose k}2^{1-{kchoose 2}}$ monochromatic k-Cliques.



      For completion, note that $P({x_1,...,x_k}$ is monochromatic $) = 2^{1-{kchoose 2}}$ because ${x_1,...,x_k}$ is monochromatic if it is either red or blue(whence the factor of 1 in its exponent and the probability that each of its $k choose 2$ edges is red is exactly $frac{1}{2}$)






      share|cite|improve this answer

























        up vote
        2
        down vote



        accepted
        +50







        up vote
        2
        down vote



        accepted
        +50




        +50




        This problem is a classical problem in probabilistic graph theory due to Erdos and can be found in pretty much any introductory course on probabilistic graph theory.



        Denote by $I_{x_1,...,x_k}$ the indicator function of the k-clique of vertices ${x_1,...,x_k}$(for a random coloring of $K_n$). Thus $I_{x_1,...,x_k}$ is 1 if ${x_1,...,x_k}$ is monochromatic or 0 else. Then the total number of monochromatic k-Cliques is equal to $sum_{x_1,...,x_k}I_{x_1,...,x_k}$ where the sum is taken over all ${nchoose k}$ groups of k-vertices in the graph. The expected number of monochromatic k-Cliques is then equal to ${nchoose k}P({x_1,...,x_k}$ is monochromatic $) = {nchoose k}2^{1-{kchoose 2}}$, by linearity of expectation and also by $E(I_A)=P(A)$, for any event set A, so you can find at least one graph with ${nchoose k}2^{1-{kchoose 2}}$ monochromatic k-Cliques.



        For completion, note that $P({x_1,...,x_k}$ is monochromatic $) = 2^{1-{kchoose 2}}$ because ${x_1,...,x_k}$ is monochromatic if it is either red or blue(whence the factor of 1 in its exponent and the probability that each of its $k choose 2$ edges is red is exactly $frac{1}{2}$)






        share|cite|improve this answer














        This problem is a classical problem in probabilistic graph theory due to Erdos and can be found in pretty much any introductory course on probabilistic graph theory.



        Denote by $I_{x_1,...,x_k}$ the indicator function of the k-clique of vertices ${x_1,...,x_k}$(for a random coloring of $K_n$). Thus $I_{x_1,...,x_k}$ is 1 if ${x_1,...,x_k}$ is monochromatic or 0 else. Then the total number of monochromatic k-Cliques is equal to $sum_{x_1,...,x_k}I_{x_1,...,x_k}$ where the sum is taken over all ${nchoose k}$ groups of k-vertices in the graph. The expected number of monochromatic k-Cliques is then equal to ${nchoose k}P({x_1,...,x_k}$ is monochromatic $) = {nchoose k}2^{1-{kchoose 2}}$, by linearity of expectation and also by $E(I_A)=P(A)$, for any event set A, so you can find at least one graph with ${nchoose k}2^{1-{kchoose 2}}$ monochromatic k-Cliques.



        For completion, note that $P({x_1,...,x_k}$ is monochromatic $) = 2^{1-{kchoose 2}}$ because ${x_1,...,x_k}$ is monochromatic if it is either red or blue(whence the factor of 1 in its exponent and the probability that each of its $k choose 2$ edges is red is exactly $frac{1}{2}$)







        share|cite|improve this answer














        share|cite|improve this answer



        share|cite|improve this answer








        edited Nov 27 at 20:28

























        answered Nov 21 at 10:43









        Sorin Tirc

        76210




        76210






























            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.





            Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


            Please pay close attention to the following guidance:


            • 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.


            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%2f3002457%2fthe-maximimum-monochromatic-k-cliques-for-complete-graph%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

            AnyDesk - Fatal Program Failure

            How to calibrate 16:9 built-in touch-screen to a 4:3 resolution?

            QoS: MAC-Priority for clients behind a repeater