3
$\begingroup$

Let $V$ be a set of ordered vertices such that $|V|=n$. There are $2^{n^2}$ possible directed graphs on $V$. Let $U\subset V$ such that $|U|=k$, any such subset again has $2^{k^2}$ possible directed graphs on it. We label any graph on the subset $U$ as $n_i$, where $i$ is the $i^{th}$ graph in an enumeration of the possible $2^{k^2}$ graphs. Now given an instance of a graph $(V,E)$, I can associate a monomial to this graph as follows: $$M = \prod_{U\subset V \\ |U|=k} n_{i}^{\alpha_i}$$ Basically, $\alpha_i$ is the number of times the $k-sized$ subgraph labelled $n_i$ appears in the graph (upto isomorphism).

Now, if I were to sum all such monomials for all $2^{n^2}$ graphs, I will get the following polynomial:

$$P(V) = \sum_{\bf{\alpha}} C_{\alpha}\prod_{U\subset V\\|U|=k}n_{i}^{\alpha}$$

Where $\alpha = <\alpha_1 ...\alpha_{2^{k^2}}>$, is the vector of cardinality of such subgraphs.

Is there any efficient way to generate $P(V)$ ? Is there any literature on this problem ?

Notice that these polynomials are always homogeneous with degree $n \choose k$

PS: Please leave a comment if the question is not clear


My definition of subgraph on a subset $U \subset V$ of a directed graph $(V,E)$ is: $(U,E')$ such that $E'$ are all the edges in $(V,E)$, which were defined on $U$.

$\endgroup$
10
  • $\begingroup$ Aren't there $2^{n^2-n}$ graphs? $\endgroup$
    – Kenta S
    Commented Feb 4, 2021 at 16:53
  • $\begingroup$ I allow a node to be connected to itself. So you have two choices for each ordered pair of nodes in the possible $n^2$ ordered pairs $\endgroup$
    – SagarM
    Commented Feb 4, 2021 at 16:55
  • $\begingroup$ Ok, that makes sense. $\endgroup$
    – Kenta S
    Commented Feb 4, 2021 at 16:56
  • 1
    $\begingroup$ When $k > \sqrt{\log n}$ or so, the number of possible monomials is going to be greater than the number of graphs, and we might expect the number of distinct monomials that appear to be not much smaller than the number of graphs, in which case merely writing down this polynomial would not take much less time than simply enumerating all the graphs. Are you interested, then, only in very small values of $k$? $\endgroup$
    – Will Sawin
    Commented Mar 3, 2021 at 21:50
  • 1
    $\begingroup$ I have no reference. My only thoughts are (1) I definitely think in this case there is a solution faster than enumeration (2) it's clear an approximate solution is available by the moment method (3) it might be possible to do a little faster than enumeration by some dynamic programming algorithm, but I haven't figured out how yet $\endgroup$
    – Will Sawin
    Commented Mar 5, 2021 at 19:40

1 Answer 1

1
$\begingroup$

To approximately estimate $C_\alpha$, it is convenient to view $C_\alpha/ 2^{n^2}$ as the probability that a random complete directed graph / tournament on $V$ has subgraph cardinalities $\alpha_1,\dots, \alpha_{2^{k^2}}$.

A first step is compute the moments, for a vector of exponents $e_1,\dots, e_{2^{k^2}}$, $$\sum_\alpha \frac{C_\alpha}{2^{n^2}} \prod_{i=1}^{2^{k^2}} \left(\alpha_i- \frac{ \binom{n}{k}} { 2^{k^2}}\right)^{e_i}.$$

One can think of these as certain derivatives of your polynomial. Here I subtracted the expectation $\frac{ \binom{n}{k}} { 2^{k^2}}$ of $\alpha_i$ to get the most interesting moments.

Let $1_i(U)$ be the random variable that equals $1$ if the graph restricted to $U$ is the $i$th graph and $0$ otherwise. Then $\alpha_i = \sum_U 1_i(U)$ so $$\alpha_i - \frac{ \binom{n}{k}} { 2^{k^2}} = \sum_U \left(1_i (U) - \frac{1}{2^{k^2} } \right).$$

Thus we can expand this moment out as

$$ \sum_{ \substack{U_{1,1},\dots, U_{1,e_1}, U_{2,1}, \dots, U_{2^k, e^{2^k}} \subset V \\ | U_{i,j} | = k}} \frac{1}{ 2^{n^2}} \sum_{\alpha} \prod_{i=1}^{2^k} \prod_{j=1}^{e_i} \left( 1_i (U_{i,j}) - \frac{1}{2^{k^2}} \right).$$

Now if there is any $U_{i,j}$ which doesn't share a vertex with the other $U_{i',j'}$, the inner sum over $\alpha$ will vanish because $1_i ( U_{i,j})- \frac{1}{2^{k^2}}$ will be independent of the other variables and since its expectation is $0$ this will force the sum to cancel.

The number of remaining terms is $O_{k,e} ( n^{ (k-1/2) \sum_i e_i})$ because we have $k \sum_i e_i$ elements of the $U_{i,j}$ to choose but there must be at least $ \sum_i e_i/2$ pairs that share a vertex, so $n^{ (k-1/2) \sum_i e_i})$ independent vertices in total.

Since for each fixed tuple of $U_{i,j}$, the sum over $\alpha$ contributes at most $1$, the largest contributions will come from the sets $U_{i,j}$ where each $U_{i,j}$ shares exactly one vertex with one other $U_{i,j}$.

Using this, I think, but am not completely sure, that one can show that as $n$ goes to $\infty$, the moment divided by $ n^{ (k-1/2) \sum_i e_i}$ converges to the moments of a Gaussian random variable with a variance-covariance matrix that can be calculate by considering the correlations between $\alpha_i (U_{i,j})$ and $\alpha_{i'} (U_{i',j'})$ when $U_{i,j}$ and $U_{i',j'}$ share exactly one vertex.

If this is true, then the normalized deviations $$ \frac{\alpha_i - \frac{ \binom{n}{k}} { 2^{k^2}}}{n^{ k- \frac{1}{2}}}$$ will converge as $n$ goes to $\infty$ to a Gaussian random variable with the same mean and covariance matrix.

This should give the largest-scale behavior of this polynomial.

$\endgroup$

You must log in to answer this question.

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