counting intersecting cliques of same size - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T00:22:55Z http://mathoverflow.net/feeds/question/107627 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/107627/counting-intersecting-cliques-of-same-size counting intersecting cliques of same size vzn 2012-09-19T23:13:55Z 2012-09-19T23:13:55Z <p>(earlier tried to count the following but came up with a wrong formula so will just ask the direct question without proposing a formula 1st.)</p> <p>given: a graph of \$m\$ vertices, \$\binom{m}{2}\$ edges and a fixed clique of \$\binom{n}{2}\$ edges. </p> <blockquote> <ul> <li>how many other cliques on this graph are there of size \$\binom{n}{2}\$ edges that have at least one edge in common with the first fixed clique? (ie counting two cliques of same size on same graph, one fixed, the other variably-placed, with intersecting/shared edges, not disjoint.)</li> <li>prefer an end formula without binomial coefficient expressions in it. an asymptotic estimate may be ok.</li> <li>has someone seen this formula in a paper or book somewhere? esp interested in uses of it in comp sci refs/books/papers or extremal graph/set theory.</li> </ul> </blockquote> <p>(have a rough idea of how to count this but got messed up in the details.)</p>