Finding the spanning subgraphs of a complete bipartite graph
$begingroup$
Let $K_{(m,n)}$ be the complete bipartite graph with $m$ and $n$ being the number of vertices in each partition. Is there an efficient way to list down or construct all its spanning subgraphs up to isomorphism?
I tried finding the spanning subgraphs for small $m$ and $n$ and what I am doing is I start by distributing edges. The number of edges is greater than or equal to $0$ and less than or equal to $mn$. There is only one spanning subgraph with $0$ and $mn$ edges. There is only one spanning subgraph with $1$ edge also. For $2$ edges there are two if $m+ngeq 4$ and only one otherwise. Then I proceed until I have used up all the possible number of edges. This is quite tedious.
Can anyone suggest an alternative method? I figured some programs might be able to enumerate all the spanning subgraphs fast so there must be a way on how they do it.
Any help or idea is appreciated. Thank you!
UPDATE:
I'm also interested on the number of these graphs. How many spanning subgraphs does $K_{(m,n)}$ have? I've read somewhere that I should use Polya's Enumeration Theorem. I'm not yet familiar on how to use that. I'd be really thankful if someone could give a hint and point me to the right direction. Thanks!
graph-theory bipartite-graph
$endgroup$
add a comment |
$begingroup$
Let $K_{(m,n)}$ be the complete bipartite graph with $m$ and $n$ being the number of vertices in each partition. Is there an efficient way to list down or construct all its spanning subgraphs up to isomorphism?
I tried finding the spanning subgraphs for small $m$ and $n$ and what I am doing is I start by distributing edges. The number of edges is greater than or equal to $0$ and less than or equal to $mn$. There is only one spanning subgraph with $0$ and $mn$ edges. There is only one spanning subgraph with $1$ edge also. For $2$ edges there are two if $m+ngeq 4$ and only one otherwise. Then I proceed until I have used up all the possible number of edges. This is quite tedious.
Can anyone suggest an alternative method? I figured some programs might be able to enumerate all the spanning subgraphs fast so there must be a way on how they do it.
Any help or idea is appreciated. Thank you!
UPDATE:
I'm also interested on the number of these graphs. How many spanning subgraphs does $K_{(m,n)}$ have? I've read somewhere that I should use Polya's Enumeration Theorem. I'm not yet familiar on how to use that. I'd be really thankful if someone could give a hint and point me to the right direction. Thanks!
graph-theory bipartite-graph
$endgroup$
add a comment |
$begingroup$
Let $K_{(m,n)}$ be the complete bipartite graph with $m$ and $n$ being the number of vertices in each partition. Is there an efficient way to list down or construct all its spanning subgraphs up to isomorphism?
I tried finding the spanning subgraphs for small $m$ and $n$ and what I am doing is I start by distributing edges. The number of edges is greater than or equal to $0$ and less than or equal to $mn$. There is only one spanning subgraph with $0$ and $mn$ edges. There is only one spanning subgraph with $1$ edge also. For $2$ edges there are two if $m+ngeq 4$ and only one otherwise. Then I proceed until I have used up all the possible number of edges. This is quite tedious.
Can anyone suggest an alternative method? I figured some programs might be able to enumerate all the spanning subgraphs fast so there must be a way on how they do it.
Any help or idea is appreciated. Thank you!
UPDATE:
I'm also interested on the number of these graphs. How many spanning subgraphs does $K_{(m,n)}$ have? I've read somewhere that I should use Polya's Enumeration Theorem. I'm not yet familiar on how to use that. I'd be really thankful if someone could give a hint and point me to the right direction. Thanks!
graph-theory bipartite-graph
$endgroup$
Let $K_{(m,n)}$ be the complete bipartite graph with $m$ and $n$ being the number of vertices in each partition. Is there an efficient way to list down or construct all its spanning subgraphs up to isomorphism?
I tried finding the spanning subgraphs for small $m$ and $n$ and what I am doing is I start by distributing edges. The number of edges is greater than or equal to $0$ and less than or equal to $mn$. There is only one spanning subgraph with $0$ and $mn$ edges. There is only one spanning subgraph with $1$ edge also. For $2$ edges there are two if $m+ngeq 4$ and only one otherwise. Then I proceed until I have used up all the possible number of edges. This is quite tedious.
Can anyone suggest an alternative method? I figured some programs might be able to enumerate all the spanning subgraphs fast so there must be a way on how they do it.
Any help or idea is appreciated. Thank you!
UPDATE:
I'm also interested on the number of these graphs. How many spanning subgraphs does $K_{(m,n)}$ have? I've read somewhere that I should use Polya's Enumeration Theorem. I'm not yet familiar on how to use that. I'd be really thankful if someone could give a hint and point me to the right direction. Thanks!
graph-theory bipartite-graph
graph-theory bipartite-graph
edited Feb 17 '15 at 12:48
chowching
asked Feb 17 '15 at 3:19
chowchingchowching
390117
390117
add a comment |
add a comment |
4 Answers
4
active
oldest
votes
$begingroup$
Introductory remark. The following discussion uses two different
definition of spanning subgraphs of $K_{n,m}$, one being subgraphs
with the same vertex set and the second subgraphs with the same vertex
set where there are no isolated vertices. The first of these is
equivalent to coloring the graph with two colors. Call these two model
$Q$ and model $P$ respectively.
The goal here is to enumerate spanning subgraphs of $K_{n,m}$ where we
will treat the simple case where even if $n=m$ there are no flips
above a central vertical axis i.e. no reflections. We can do much
better than NAUTY as we are only counting these graphs as opposed to
enumerating them. We use the Polya Enumeration Theorem (PET) to obtain
the count of all non-isomorphic subgraphs of $K_{n,m}$ (model $Q$) and
the principle of inclusion-exclusion (PIE) to extract the count of the
spanning subgraphs (model $P$).
We will consult NAUTY just the same to get sample data to match
against in our mathematical analysis. The following Perl script was
used.
#! /usr/bin/perl -w
#
sub decode_graph {
my ($str) = @_;
sub R {
my (@args) = map {
sprintf "%06b", $_;
} @_;
join '', @args;
}
my (@ents) = map {
ord($_) - 63
} split //, $str;
my $n = shift @ents;
my @adj_data = split //, R(@ents);
my $adj = ; my $pos = 0;
for(my $ind2 = 1; $ind2 < $n; $ind2++){
for(my $ind1 = 0; $ind1 < $ind2; $ind1++){
$adj->[$ind1]->[$ind2] = $adj_data[$pos];
$adj->[$ind2]->[$ind1] = $adj_data[$pos];
$pos++;
}
}
return $adj;
}
MAIN: {
my $mx = shift || 3;
die "out of range for GENBG: $mx"
if 2*$mx < 2 || 2*$mx > 32;
for(my $comp_a = 1; $comp_a <= $mx; $comp_a++){
for(my $comp_b = 1; $comp_b <= $mx; $comp_b++){
my $vcount = $comp_a + $comp_b;
my $cmd = sprintf "./genbg %d %d",
$comp_a, $comp_b;
my $count = 0;
open GENBG, "$cmd 2>/dev/null|";
while(my $bp = <GENBG>){
chomp $bp; my $adj = decode_graph $bp;
for($v = 0; $v < $vcount; $v++){
my $deg = 0;
for(my $w = 0; $w < $vcount; $w++){
my $ent = $adj->[$v]->[$w];
$deg++ if defined($ent) && $ent == 1;
}
last if $deg == 0;
}
$count++ if $v == $vcount;
}
close GENBG;
printf " " if $comp_b > 1;
printf "%06d", $count;
}
printf "n";
};
}
This gave the following table:
$ ./scripts/bipartite.pl 6
000001 000001 000001 000001 000001 000001
000001 000003 000005 000008 000011 000015
000001 000005 000017 000042 000091 000180
000001 000008 000042 000179 000633 002001
000001 000011 000091 000633 003835 020755
000001 000015 000180 002001 020755 200082
Now for the mathematics. We use the Polya Enumeration Theorem as
conjectured by the OP. To do this we need the cycle index of the
action on the edges of the group that permutes the vertices in
partition $A$ of size $n$ according to the symmetric group $S_n$ and
the vertices in partition $B$ of size $m$ according to $S_m.$
These cycle indices are easy to compute and we do not need to iterate
over all $n!times m!$ pairs of permutations (acting on $A$ and $B$)
but instead it is sufficient to iterate over pairs of terms from the
cycle indices $Z(S_n)$ and $Z(S_m)$ of the symmetric groups $S_n$ and
$S_m$ according to their multiplicities to obtain the cycle index
$Z(Q_{n,m})$ of the combined action on $A$ and $B$. The number of
terms here is the much better count of the number of partitions of $n$
and $m$ (upper bound).
The classic approach to the calculation of these cycle indices is
based on the simple observation that for two cycles, one of length
$l_1$ from a permutation $alpha$ of $A$ and another of length $l_2$
from a column permutation $beta$ of $B$ their contribution to the
disjoint cycle decomposition product for $(alpha,beta)$ in the cycle
index $Z(Q_{n,m})$ is by inspection
$$a_{mathrm{lcm}(l_1, l_2)}^{l_1 l_2 / mathrm{lcm}(l_1, l_2)}
= a_{mathrm{lcm}(l_1, l_2)}^{gcd(l_1, l_2)}.$$
Once we have the cycle indices we evaluate
$$Z(Q_{n,m})(1+z)$$
which is the standard substitution to produce the OGF. If we are only
looking to obtain the count, we may use
$$Z(Q_{n,m})_{Large a_1=a_2=a_3=cdots=2}.$$
Here is an example:
$$Z(Q_{3,4}) =
{frac {{a_{{1}}}^{12}}{144}}+1/24,{a_{{2}}}^{3}{a_{{1}}}^{6}+1/18,{a_{{3
}}}^{3}{a_{{1}}}^{3}+1/12,{a_{{2}}}^{6}+1/6,{a_{{4}}}^{3}
\+1/48,{a_{{2}}}
^{4}{a_{{1}}}^{4}+1/8,{a_{{1}}}^{2}{a_{{2}}}^{5}+1/6,a_{{1}}a_{{2}}a_{{3}
}a_{{6}}+1/8,{a_{{3}}}^{4}
\+1/12,{a_{{3}}}^{2}a_{{6}}+1/24,{a_{{6}}}^{2}+
1/12,a_{{12}}.$$
The substituted cycle index becomes
$$Z(Q_{3,4})(1+z) =
{z}^{12}+{z}^{11}+3,{z}^{10}+6,{z}^{9}+11,{z}^{8}
\ +13,{z}^{7}+17,{z}^{6
}+13,{z}^{5}+11,{z}^{4}+6,{z}^{3}+3,{z}^{2}+z+1.$$
At this point we have just about everything we need, the only problem
as is evident from the substituted cycle index (indexed by edge count)
is that we are counting all subgraphs including those that obviously
cannot span $K_{3,4}.$ Observe however that $Z(Q_{3,4})$ includes the
count from all graphs $K_{a,b}$ where $1le a le 3$ and $1le b le
4$ and this observation holds for the $Z(Q_{a,b})$ as well. The way to
identify a spanning subgraph of $K_{3,4}$ is that every vertex in the
vertex set has degree at least one, which means these are just the
graphs that cannot possibly be counted by $Z(Q_{a,b})$ with $(a,b)ne
(3,4)$ because of the missing vertices. Therefore we apply PIE to the
poset where the nodes corresponding to the $(a,b)$ is the set of
graphs counted by the corresponding substituted cycle index. We have
by inspection that this poset is isomorphic to the divisor poset of
$2^{n-1}times 3^{m-1}$ so that we may use the ordinary Möbius
function from number theory as our Möbius function for the PIE
computation. (We are not including the empty graph in the sets at the
nodes from the poset.)
This is implemented in the following Maple program.
with(numtheory);
pet_cycleind_symm :=
proc(n)
option remember;
if n=0 then return 1; fi;
expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;
pet_varinto_cind :=
proc(poly, ind)
local subs1, subsl, polyvars, indvars, v, pot;
polyvars := indets(poly);
indvars := indets(ind);
subsl := ;
for v in indvars do
pot := op(1, v);
subs1 :=
[seq(polyvars[k]=polyvars[k]^pot,
k=1..nops(polyvars))];
subsl := [op(subsl), v=subs(subs1, poly)];
od;
subs(subsl, ind);
end;
pet_cycleind_knm :=
proc(n, m)
option remember;
local cind, sind1, sind2, t1, t2, q,
v1, v2, len, len1, len2;
cind := 0;
if n=1 then
sind1 := [a[1]];
else
sind1 := pet_cycleind_symm(n);
fi;
if m=1 then
sind2 := [a[1]];
else
sind2 := pet_cycleind_symm(m);
fi;
for t1 in sind1 do
for t2 in sind2 do
q := 1;
for v1 in indets(t1) do
len1 := op(1, v1);
for v2 in indets(t2) do
len2 := op(1, v2);
len := lcm(len1, len2);
q := q *
a[len]^((len1*len2/len) *
degree(t1, v1)*degree(t2, v2));
od;
od;
cind := cind +
lcoeff(t1)*lcoeff(t2)*q;
od;
od;
cind;
end;
v_pre_pie :=
proc(n, m)
option remember;
local cind;
cind := pet_cycleind_knm(n, m);
subs([seq(a[v]=2, v=1..n*m)], cind);
end;
v :=
proc(n, m)
local q, a, b, res;
q := 2^(n-1)*3^(m-1);
res := 0;
for a to n do
for b to m do
res := res +
mobius(q/2^(a-1)/3^(b-1))*
(v_pre_pie(a, b)-1);
od;
od;
res;
end;
print_table :=
proc(mx)
local n, m;
for n to mx do
for m to mx do
if m>1 then printf(" ") fi;
printf("%06d", v(n, m));
od;
printf("n");
od;
end;
The above Maple code produces the following table:
> print_table(6);
000001 000001 000001 000001 000001 000001
000001 000003 000005 000008 000011 000015
000001 000005 000017 000042 000091 000180
000001 000008 000042 000179 000633 002001
000001 000011 000091 000633 003835 020755
000001 000015 000180 002001 020755 200082
It can calculate values that are completely out of reach for NAUTY
like the sequence of non-isomorphic spanning subgraphs of $K_{n,n}$
which is
$$1, 3, 17, 179, 3835, 200082, 29610804, 13702979132, \
20677458750966, 103609939177198046, 1745061194503344181714, \
99860890306900024150675406,ldots$$
which points us to OEIS A054976
where we find confirmation of the above calculation and a slightly
different interpretation of the problem statement.
The function v in the Maple program implements model $P$ and the
function v_pre_pie implements model $Q.$
For bicolored versions of $K_{n,n}$ model $Q$ gives the sequence
$$2, 7, 36, 317, 5624, 251610, 33642660, 14685630688, \
21467043671008, 105735224248507784, 1764356230257807614296, \
100455994644460412263071692,ldots$$
which points us to OEIS A002724,
where the calculation is confirmed.
This MSE Meta Link
has many more PET computations by various users.
Thanks go to the authors of the NAUTY package.
$endgroup$
$begingroup$
Excellent! Thanks for taking the time to answer. I'm studying it right now. Quick question about 'the sequence of non-isomorphic spanning subgraphs of $K_{(n,n)}$. If I take $n=2$ I found that there are $6$ spanning subgraphs of $K_{(2,2)}$ namely: the empty graph of four vertices, $P_2cup {a}cup{b}, P_2cup P_2, P_3cup {a}, P_4, K_{(2,2)}$. Thank you!
$endgroup$
– chowching
Feb 25 '15 at 6:12
$begingroup$
We already discussed this at your other MSE question. There seven bicolored graphs on $K_{2,2}$ but a bicolored graph is not the same as a spanning subgraph. Please consult the discussion on the other question. E.g. the empty graph does not span $K_{2,2}.$ This Wikipedia entry is the definition of a spanning subgraph. The above program also counts bicolored graphs. Note that v_pre_pi(2,2)=7 and v(2,2)=3.
$endgroup$
– Marko Riedel
Feb 25 '15 at 18:50
$begingroup$
I see what you mean now, I have added a comment.
$endgroup$
– Marko Riedel
Feb 25 '15 at 19:05
$begingroup$
I'm not impressed to have yet another impressing anwer from you.
$endgroup$
– Jorge Fernández Hidalgo
Feb 26 '15 at 1:31
add a comment |
$begingroup$
The following data augment those in the first answer, namely we treat
the problem of computing $Z(Q_{n})$ for $K_{n,n}$ where we include reflections. The
algorithm here is slightly different from Harary and Palmer. Clearly
all permutations from the first answer represented in $Z(Q_{n,n})$
contribute as well. Now for the reflections, which are simple,
fortunately. These (the vertex permutations) can be obtained from the
permutations in $S_n$ by placing vertices from component $A$
alternating with component $B$ on a cycle with twice the length of a
cycle contained in a permutation $gamma$ of $S_n.$ The
induced action on the set of edges is the contribution to $Z(Q_n).$ In
the following we have used an algorithmic approach rather than the
formula from Harary and Palmer, namely we construct a canonical
representative of each permutation shape from the cycle index $Z(S_n)$
that doubles the length of every cycle and alternates elements from
the two components. We let that act on the set of edges and factor the
result.
This gives the following cycle indices, the first of which matches the
result given by Harary and Palmer.
For $n=3$,
$$Z(Q_3) =
{frac {{a_{{1}}}^{9}}{72}}+1/6,{a_{{2}}}^{3}{a_{{1}}}^{3}
\+1/9,{a_{{3}}}^{3}
+1/8,{a_{{2}}}^{4}a_{{1}}+1/3,a_{{3}}a_{{6}}+1/4,a_{{1}}{a_{{4}}}^{2}
,$$
for $n=4$,
$$Z(Q_4) =
{frac {{a_{{1}}}^{16}}{1152}}+{frac {{a_{{1}}}^{8}{a_{{2}}}^{4}}{96}}+{
frac {{a_{{3}}}^{4}{a_{{1}}}^{4}}{72}}\
+{frac {17,{a_{{2}}}^{8}}{384}}+{
frac {19,{a_{{4}}}^{4}}{96}}+{frac {5,{a_{{1}}}^{4}{a_{{2}}}^{6}}{96}}+1/
12,{a_{{3}}}^{2}{a_{{1}}}^{2}a_{{2}}a_{{6}}+1/18,{a_{{3}}}^{5}a_{{1}}
\+1/24,
{a_{{2}}}^{2}{a_{{6}}}^{2}+1/12,a_{{4}}a_{{12}}+1/8,{a_{{1}}}^{2}a_{{2}}{a_{
{4}}}^{3}+1/6,a_{{1}}{a_{{6}}}^{2}a_{{3}}+1/8,{a_{{8}}}^{2}
,$$
and for $n=5$,
$$Z(Q_5) =
1/12,{a_{{1}}}^{2}a_{{2}}{a_{{6}}}^{3}a_{{3}}+1/24,{a_{{1}}}^{3}{a_{{2}}}^{3
}{a_{{4}}}^{4}+{frac {{a_{{1}}}^{25}}{28800}}+{frac {13,{a_{{5}}}^{5}}{600}
}+{frac {{a_{{5}}}^{3}a_{{10}}}{60}}\
+1/48,{a_{{2}}}^{4}{a_{{1}}}^{2}a_{{3}}{
a_{{6}}}^{2}+{frac {{a_{{1}}}^{6}{a_{{3}}}^{3}{a_{{2}}}^{2}a_{{6}}}{72}}+1/48
,{a_{{4}}}^{5}{a_{{1}}}^{3}a_{{2}}+1/24,{a_{{4}}}^{2}{a_{{1}}}^{2}a_{{3}}a_{
{12}}\
+1/36,{a_{{2}}}^{2}{a_{{3}}}^{5}a_{{6}}+1/32,{a_{{4}}}^{5}a_{{1}}{a_{{2
}}}^{2}+1/48,{a_{{2}}}^{5}a_{{3}}{a_{{6}}}^{2}+1/24,a_{{2}}a_{{3}}{a_{{4}}}^
{2}a_{{12}}\
+1/8,a_{{1}}{a_{{8}}}^{3}+1/12,a_{{4}}a_{{12}}a_{{6}}a_{{3}}+{
frac {{a_{{1}}}^{15}{a_{{2}}}^{5}}{1440}}+{frac {{a_{{1}}}^{10}{a_{{3}}}^{5}
}{720}}+{frac {{a_{{1}}}^{5}{a_{{2}}}^{10}}{192}}\
+{frac {{a_{{4}}}^{5}{a_{{1
}}}^{5}}{480}}+{frac {{a_{{2}}}^{5}{a_{{3}}}^{5}}{720}}+{frac {{a_{{1}}}^{9}
{a_{{2}}}^{8}}{288}}+{frac {{a_{{2}}}^{11}{a_{{1}}}^{3}}{96}}+{frac {{a_{{2}
}}^{5}{a_{{3}}}^{3}a_{{6}}}{72}}+{frac {{a_{{3}}}^{7}{a_{{1}}}^{4}}{72}}
\ +1/30
,{a_{{5}}}^{2}a_{{15}}+1/20,a_{{5}}a_{{20}}+1/30,a_{{10}}a_{{15}}+{frac {{
a_{{2}}}^{12}a_{{1}}}{128}}+1/8,a_{{5}}{a_{{10}}}^{2}
\+{frac {3,a_{{1}}{a_{{
4}}}^{6}}{32}}+{frac {{a_{{2}}}^{2}{a_{{6}}}^{2}{a_{{3}}}^{3}}{72}}
.$$
These cycle indices can be calculated for large $n$ but the pattern
should be clear. The count of these graphs gives the sequence
$$2, 6, 26, 192, 3014, 127757, 16853750, \ 7343780765, 10733574184956,
52867617324773592,\882178116079222400788, 50227997322550920824045262,
ldots $$
which points us to OEIS A007139 where
we find confirmation of this calculation.
This was the Maple code used to obtain these values.
with(numtheory);
pet_cycleind_symm :=
proc(n)
local p, s;
option remember;
if n=0 then return 1; fi;
expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;
pet_autom2cycles :=
proc(src, aut)
local numa, numsubs;
local marks, pos, cycs, cpos, clen;
numsubs := [seq(src[k]=k, k=1..nops(src))];
numa := subs(numsubs, aut);
marks := Array([seq(true, pos=1..nops(aut))]);
cycs := ; pos := 1;
while pos <= nops(aut) do
if marks[pos] then
clen := 0; cpos := pos;
while marks[cpos] do
marks[cpos] := false;
cpos := numa[cpos];
clen := clen+1;
od;
cycs := [op(cycs), clen];
fi;
pos := pos+1;
od;
return mul(a[cycs[k]], k=1..nops(cycs));
end;
pet_varinto_cind :=
proc(poly, ind)
local subs1, subs2, polyvars, indvars, v, pot, res;
res := ind;
polyvars := indets(poly);
indvars := indets(ind);
for v in indvars do
pot := op(1, v);
subs1 :=
[seq(polyvars[k]=polyvars[k]^pot,
k=1..nops(polyvars))];
subs2 := [v=subs(subs1, poly)];
res := subs(subs2, res);
od;
res;
end;
pet_flatten_term :=
proc(varp)
local terml, d, cf, v;
terml := ;
cf := varp;
for v in indets(varp) do
d := degree(varp, v);
terml := [op(terml), seq(v, k=1..d)];
cf := cf/v^d;
od;
[cf, terml];
end;
pet_flat2rep_cyc :=
proc(f)
local p, q, res, cyc, t, len;
q := 1; res := ;
for t in f do
len := op(1, t);
cyc := [seq(p, p=q+1..q+len-1), q];
res := [op(res), cyc];
q := q+len;
od;
res;
end;
pet_cycs2table :=
proc(cycs)
local pairs, cyc, p, ent;
pairs := ;
for cyc in cycs do
pairs :=
[op(pairs),
seq([cyc[p], cyc[1 + (p mod nops(cyc))]],
p = 1 .. nops(cyc))];
od;
map(ent->ent[2], sort(pairs, (a,b)->a[1] < b[1]));
end;
pet_cycleind_knn :=
proc(n)
option remember;
local cindA, cindB, sind, t1, t2, p, q, cyc1, cyc2,
flat1, flat2, len, len1, len2,
edges, edgeperm, rep, cycsA, cycsB, cycsrc, cyc;
if n=1 then
sind := [a[1]];
else
sind := pet_cycleind_symm(n);
fi;
cindA := 0;
for t1 in sind do
flat1 := pet_flatten_term(t1);
for t2 in sind do
flat2 := pet_flatten_term(t2);
q := 1;
for cyc1 in flat1[2] do
len1 := op(1, cyc1);
for cyc2 in flat2[2] do
len2 := op(1, cyc2);
len := lcm(len1, len2);
q := q * a[len]^(len1*len2/len);
od;
od;
cindA := cindA + flat1[1]*flat2[1]*q;
od;
od;
edges := [seq(seq({p, q+n}, q=1..n), p=1..n)];
cindB := 0;
for t1 in sind do
flat1 := pet_flatten_term(t1);
cycsA := pet_flat2rep_cyc(flat1[2]);
cycsB := ;
for cycsrc in cycsA do
cyc := ;
for q in cycsrc do
cyc := [op(cyc), q, q+n];
od;
cycsB := [op(cycsB), cyc];
od;
rep := pet_cycs2table(cycsB);
edgeperm :=
subs([seq(q=rep[q], q=1..2*n)], edges);
cindB := cindB + flat1[1]*
pet_autom2cycles(edges, edgeperm);
od;
(cindA+cindB)/2;
end;
v_pre_pie :=
proc(n)
option remember;
local cind, gf;
cind := pet_cycleind_knn(n);
gf := pet_varinto_cind(1+z, cind);
subs(z=1, gf);
end;
$endgroup$
add a comment |
$begingroup$
The question is equivalent to finding all non-isomorphic bipartite graphs with bi-partitions of sizes $n$ and $m$ respectively and is hard to solve in general. In particular there is no simple characterization of such graphs.
If you need the sequence for the number of such graphs then you can take a look at this oeis entry http://oeis.org/A033995.
If you need to compute such graphs (up to a reasonable number) then your best choice is the tool genbg which you can find in McKay's nauty package. In some sense genbg is currently the most efficient way to construct such graphs and hence answers your question.
$endgroup$
$begingroup$
Yeah I need to find all those non-isomorphic bipartite graphs with sizes $m$ and $n$ in each partition. The sequence above is for the number of bipartite graphs of $n$ vertices. But that number is greater than the number of graphs that I am trying to find. For example if I have four vertices, there are $7$ bipartite graphs but if I'm only taking all the spanning subgraphs of $K_{(2,2)}$ then there are just $6$ of them. The other bipartite graph is a claw which is bipartite with sizes 1 and 3 in each partition.
$endgroup$
– chowching
Feb 17 '15 at 12:43
$begingroup$
@chowching You should be more specific about what you're looking for. Note that in general there is no closed formula for the number of bipartite graphs with bipartitions of cardinality n and m.
$endgroup$
– Jernej
Feb 17 '15 at 13:00
$begingroup$
Thanks for the reply. I'm studying Polya Enumeration Theorem now to see if I can apply it to find how many such graphs are there given a certain $n$ and $m$.
$endgroup$
– chowching
Feb 17 '15 at 13:00
$begingroup$
@chowching You can but the formula will most likely require using computer computations.
$endgroup$
– Jernej
Feb 17 '15 at 13:01
$begingroup$
@chowching I suggest that for a start you look at Harary's and Palmer's book called "graphical enumeration"
$endgroup$
– Jernej
Feb 17 '15 at 13:02
|
show 1 more comment
$begingroup$
Adding another answer after receiving a pointer from a reader of this
thread. We treat the case of spanning subgraphs of $K_{n,n}$ including
reflections. The algorithm has been greatly simplified. There are two
types of symmetries, namely shuffles within the two sets of vertices
and reflections that map one to the other. The first type has been
simplified as follows: we continue to iterate over pairs of
permutation shapes from $S_n$ but the contribution to the cycle index
$Z(Q_n)$ is now computed by iterating over pairs of cycle types (same
length) rather than single cycles. The second type (reflections) has
been replaced in its entirety. We continue to produce contributions
by building factorized permutations consisting of cycles that
alternate between the two classes of vertices (a precondition of this
problem) but whereas in the first version we would construct a
representative of the factored permutation, apply it to the edges, and
factor the result into cycles, the new version does not construct
representatives and does no factorization and builds the terms for the
cycle index from first principles, namely that we enumerate the cycles
of edges (two-sets of vertices) that are obtained from a vertex
permutation by choosing pairs of vertices, counting these, and
computing the lengths of the cycles on which they reside. These
optimizations make for a faster and much more compact program. This
was the code:
pet_cycleind_symm :=
proc(n)
option remember;
if n=0 then return 1; fi;
expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;
pet_varinto_cind :=
proc(poly, ind)
local subs1, subs2, polyvars, indvars, v, pot, res;
res := ind;
polyvars := indets(poly);
indvars := indets(ind);
for v in indvars do
pot := op(1, v);
subs1 :=
[seq(polyvars[k]=polyvars[k]^pot,
k=1..nops(polyvars))];
subs2 := [v=subs(subs1, poly)];
res := subs(subs2, res);
od;
res;
end;
pet_flatten_termA :=
proc(varp)
local terml, d, cf, v;
terml := ;
cf := varp;
for v in indets(varp) do
d := degree(varp, v);
terml := [op(terml), [op(1,v), d]];
cf := cf/v^d;
od;
[cf, terml];
end;
pet_cycleind_knn :=
proc(n)
option remember;
local cindA, cindB, sind, t1, t2, term, res,
flat, flat1, flat2, len, l1, l2, cycs, uidx, vidx,
u, v, inst1;
if n=1 then
sind := [a[1]];
else
sind := pet_cycleind_symm(n);
fi;
cindA := 0;
for t1 in sind do
flat1 := pet_flatten_termA(t1);
for t2 in sind do
flat2 := pet_flatten_termA(t2);
res := 1;
for u in flat1[2] do
l1 := op(1, u);
for v in flat2[2] do
l2 := op(1, v);
len := lcm(l1, l2);
res := res *
a[len]^(op(2, u)*op(2, v)
*l1*l2/len);
od;
od;
cindA := cindA + flat1[1]*flat2[1]*res;
od;
od;
cindB := 0;
for term in sind do
flat := pet_flatten_termA(term);
cycs := map(cyc -> [2*cyc[1], cyc[2]], flat[2]);
res := 1;
# edges on different cycles of different sizes
for uidx to nops(cycs) do
u := cycs[uidx];
for vidx from uidx+1 to nops(cycs) do
v := cycs[vidx];
l1 := op(1, u); l2 := op(1, v);
res := res *
a[lcm(l1, l2)]^((l1*l2/2/lcm(l1, l2))*
op(2, u)*op(2, v));
od;
od;
# edges on different cycles of the same size
for uidx to nops(cycs) do
u := cycs[uidx];
l1 := op(1, u); inst1 := op(2, u);
# a[l1]^(1/2*inst1*(inst1-1)*l1*l1/2/l1)
res := res *
a[l1]^(1/2*inst1*(inst1-1)*l1/2);
od;
# edges on identical cycles of some size
for uidx to nops(cycs) do
u := cycs[uidx];
l1 := op(1, u); inst1 := op(2, u);
if type(l1/2, even) then
# a[l1]^((l1/2)^2/l1);
res := res *
(a[l1]^(l1/4))^inst1;
else
# a[l1/2]^(l1/2/(l1/2))*a[l1]^(((l1/2)^2-l1/2)/l1)
res := res *
(a[l1/2]*a[l1]^(l1/4-1/2))^inst1;
fi;
od;
cindB := cindB + flat[1]*res;
od;
(cindA+cindB)/2;
end;
v_pre_pie :=
proc(n)
option remember;
local cind, gf;
cind := pet_cycleind_knn(n);
gf := pet_varinto_cind(1+z, cind);
subs(z=1, gf);
end;
This will produce the following data for the non-isomorphic spanning
subgraphs of $K_{6,6}$ including reflections classified according to
the number of edges:
$${z}^{36}+{z}^{35}+2,{z}^{34}+4,{z}^{33}+10,{z}^{32}
+20,{z}^{31}+50,{z}^{30}+99,{z}^{29}+227,{z}^{28}
\ +458,{z}^{27}+934,{z}^{26}+
1711,{z}^{25}+3057,{z}^{24}+4889,{z}^{23}+7400,{z}^{22}
\ +10071,{z}^{21}+12755,{z}^{20}+14524,{z}^{19}
+15331,{z}^{18}+14524,{z}^{17}+12755,{z}^{16}
\+10071,{z}^{15}+7400,{z}^{14}+4889,{z}^{13}+
3057,{z}^{12}+1711,{z}^{11}+934,{z}^{10}
\ +458,{z}^{9}+227,{z}^{8}+99,{z}^{7}+50,{z}^{6}+20,{z}^{5}
+10,{z}^{4}+4,{z}^{3}+2,{z}^{2}+z+1.$$
i.e. the value four for three edges counts, first, a set of three
edges, not connected, second, two edges sharing a vertex and a single
edge, third, three edges emanating from the same vertex and fourth, a
path of three edges.
Addendum. We may use Burnside as shown below if we are not
interested in classifying according to the number of edges and require
only the total count. This gives:
Q :=
proc(n)
option remember;
local cind;
cind := pet_cycleind_knn(n);
subs([seq(a[p]=2, p=1..n*n)], cind);
end;
The routine that substitutes polynomials into cycle indices is no
longer needed in this case. Observe that further simplification at the
expense of readability is possible by not computing the cycle index at
all and setting all $a[p]$ to two during the computation of what used
to be the cycle index.
$endgroup$
add a comment |
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
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1151538%2ffinding-the-spanning-subgraphs-of-a-complete-bipartite-graph%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Introductory remark. The following discussion uses two different
definition of spanning subgraphs of $K_{n,m}$, one being subgraphs
with the same vertex set and the second subgraphs with the same vertex
set where there are no isolated vertices. The first of these is
equivalent to coloring the graph with two colors. Call these two model
$Q$ and model $P$ respectively.
The goal here is to enumerate spanning subgraphs of $K_{n,m}$ where we
will treat the simple case where even if $n=m$ there are no flips
above a central vertical axis i.e. no reflections. We can do much
better than NAUTY as we are only counting these graphs as opposed to
enumerating them. We use the Polya Enumeration Theorem (PET) to obtain
the count of all non-isomorphic subgraphs of $K_{n,m}$ (model $Q$) and
the principle of inclusion-exclusion (PIE) to extract the count of the
spanning subgraphs (model $P$).
We will consult NAUTY just the same to get sample data to match
against in our mathematical analysis. The following Perl script was
used.
#! /usr/bin/perl -w
#
sub decode_graph {
my ($str) = @_;
sub R {
my (@args) = map {
sprintf "%06b", $_;
} @_;
join '', @args;
}
my (@ents) = map {
ord($_) - 63
} split //, $str;
my $n = shift @ents;
my @adj_data = split //, R(@ents);
my $adj = ; my $pos = 0;
for(my $ind2 = 1; $ind2 < $n; $ind2++){
for(my $ind1 = 0; $ind1 < $ind2; $ind1++){
$adj->[$ind1]->[$ind2] = $adj_data[$pos];
$adj->[$ind2]->[$ind1] = $adj_data[$pos];
$pos++;
}
}
return $adj;
}
MAIN: {
my $mx = shift || 3;
die "out of range for GENBG: $mx"
if 2*$mx < 2 || 2*$mx > 32;
for(my $comp_a = 1; $comp_a <= $mx; $comp_a++){
for(my $comp_b = 1; $comp_b <= $mx; $comp_b++){
my $vcount = $comp_a + $comp_b;
my $cmd = sprintf "./genbg %d %d",
$comp_a, $comp_b;
my $count = 0;
open GENBG, "$cmd 2>/dev/null|";
while(my $bp = <GENBG>){
chomp $bp; my $adj = decode_graph $bp;
for($v = 0; $v < $vcount; $v++){
my $deg = 0;
for(my $w = 0; $w < $vcount; $w++){
my $ent = $adj->[$v]->[$w];
$deg++ if defined($ent) && $ent == 1;
}
last if $deg == 0;
}
$count++ if $v == $vcount;
}
close GENBG;
printf " " if $comp_b > 1;
printf "%06d", $count;
}
printf "n";
};
}
This gave the following table:
$ ./scripts/bipartite.pl 6
000001 000001 000001 000001 000001 000001
000001 000003 000005 000008 000011 000015
000001 000005 000017 000042 000091 000180
000001 000008 000042 000179 000633 002001
000001 000011 000091 000633 003835 020755
000001 000015 000180 002001 020755 200082
Now for the mathematics. We use the Polya Enumeration Theorem as
conjectured by the OP. To do this we need the cycle index of the
action on the edges of the group that permutes the vertices in
partition $A$ of size $n$ according to the symmetric group $S_n$ and
the vertices in partition $B$ of size $m$ according to $S_m.$
These cycle indices are easy to compute and we do not need to iterate
over all $n!times m!$ pairs of permutations (acting on $A$ and $B$)
but instead it is sufficient to iterate over pairs of terms from the
cycle indices $Z(S_n)$ and $Z(S_m)$ of the symmetric groups $S_n$ and
$S_m$ according to their multiplicities to obtain the cycle index
$Z(Q_{n,m})$ of the combined action on $A$ and $B$. The number of
terms here is the much better count of the number of partitions of $n$
and $m$ (upper bound).
The classic approach to the calculation of these cycle indices is
based on the simple observation that for two cycles, one of length
$l_1$ from a permutation $alpha$ of $A$ and another of length $l_2$
from a column permutation $beta$ of $B$ their contribution to the
disjoint cycle decomposition product for $(alpha,beta)$ in the cycle
index $Z(Q_{n,m})$ is by inspection
$$a_{mathrm{lcm}(l_1, l_2)}^{l_1 l_2 / mathrm{lcm}(l_1, l_2)}
= a_{mathrm{lcm}(l_1, l_2)}^{gcd(l_1, l_2)}.$$
Once we have the cycle indices we evaluate
$$Z(Q_{n,m})(1+z)$$
which is the standard substitution to produce the OGF. If we are only
looking to obtain the count, we may use
$$Z(Q_{n,m})_{Large a_1=a_2=a_3=cdots=2}.$$
Here is an example:
$$Z(Q_{3,4}) =
{frac {{a_{{1}}}^{12}}{144}}+1/24,{a_{{2}}}^{3}{a_{{1}}}^{6}+1/18,{a_{{3
}}}^{3}{a_{{1}}}^{3}+1/12,{a_{{2}}}^{6}+1/6,{a_{{4}}}^{3}
\+1/48,{a_{{2}}}
^{4}{a_{{1}}}^{4}+1/8,{a_{{1}}}^{2}{a_{{2}}}^{5}+1/6,a_{{1}}a_{{2}}a_{{3}
}a_{{6}}+1/8,{a_{{3}}}^{4}
\+1/12,{a_{{3}}}^{2}a_{{6}}+1/24,{a_{{6}}}^{2}+
1/12,a_{{12}}.$$
The substituted cycle index becomes
$$Z(Q_{3,4})(1+z) =
{z}^{12}+{z}^{11}+3,{z}^{10}+6,{z}^{9}+11,{z}^{8}
\ +13,{z}^{7}+17,{z}^{6
}+13,{z}^{5}+11,{z}^{4}+6,{z}^{3}+3,{z}^{2}+z+1.$$
At this point we have just about everything we need, the only problem
as is evident from the substituted cycle index (indexed by edge count)
is that we are counting all subgraphs including those that obviously
cannot span $K_{3,4}.$ Observe however that $Z(Q_{3,4})$ includes the
count from all graphs $K_{a,b}$ where $1le a le 3$ and $1le b le
4$ and this observation holds for the $Z(Q_{a,b})$ as well. The way to
identify a spanning subgraph of $K_{3,4}$ is that every vertex in the
vertex set has degree at least one, which means these are just the
graphs that cannot possibly be counted by $Z(Q_{a,b})$ with $(a,b)ne
(3,4)$ because of the missing vertices. Therefore we apply PIE to the
poset where the nodes corresponding to the $(a,b)$ is the set of
graphs counted by the corresponding substituted cycle index. We have
by inspection that this poset is isomorphic to the divisor poset of
$2^{n-1}times 3^{m-1}$ so that we may use the ordinary Möbius
function from number theory as our Möbius function for the PIE
computation. (We are not including the empty graph in the sets at the
nodes from the poset.)
This is implemented in the following Maple program.
with(numtheory);
pet_cycleind_symm :=
proc(n)
option remember;
if n=0 then return 1; fi;
expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;
pet_varinto_cind :=
proc(poly, ind)
local subs1, subsl, polyvars, indvars, v, pot;
polyvars := indets(poly);
indvars := indets(ind);
subsl := ;
for v in indvars do
pot := op(1, v);
subs1 :=
[seq(polyvars[k]=polyvars[k]^pot,
k=1..nops(polyvars))];
subsl := [op(subsl), v=subs(subs1, poly)];
od;
subs(subsl, ind);
end;
pet_cycleind_knm :=
proc(n, m)
option remember;
local cind, sind1, sind2, t1, t2, q,
v1, v2, len, len1, len2;
cind := 0;
if n=1 then
sind1 := [a[1]];
else
sind1 := pet_cycleind_symm(n);
fi;
if m=1 then
sind2 := [a[1]];
else
sind2 := pet_cycleind_symm(m);
fi;
for t1 in sind1 do
for t2 in sind2 do
q := 1;
for v1 in indets(t1) do
len1 := op(1, v1);
for v2 in indets(t2) do
len2 := op(1, v2);
len := lcm(len1, len2);
q := q *
a[len]^((len1*len2/len) *
degree(t1, v1)*degree(t2, v2));
od;
od;
cind := cind +
lcoeff(t1)*lcoeff(t2)*q;
od;
od;
cind;
end;
v_pre_pie :=
proc(n, m)
option remember;
local cind;
cind := pet_cycleind_knm(n, m);
subs([seq(a[v]=2, v=1..n*m)], cind);
end;
v :=
proc(n, m)
local q, a, b, res;
q := 2^(n-1)*3^(m-1);
res := 0;
for a to n do
for b to m do
res := res +
mobius(q/2^(a-1)/3^(b-1))*
(v_pre_pie(a, b)-1);
od;
od;
res;
end;
print_table :=
proc(mx)
local n, m;
for n to mx do
for m to mx do
if m>1 then printf(" ") fi;
printf("%06d", v(n, m));
od;
printf("n");
od;
end;
The above Maple code produces the following table:
> print_table(6);
000001 000001 000001 000001 000001 000001
000001 000003 000005 000008 000011 000015
000001 000005 000017 000042 000091 000180
000001 000008 000042 000179 000633 002001
000001 000011 000091 000633 003835 020755
000001 000015 000180 002001 020755 200082
It can calculate values that are completely out of reach for NAUTY
like the sequence of non-isomorphic spanning subgraphs of $K_{n,n}$
which is
$$1, 3, 17, 179, 3835, 200082, 29610804, 13702979132, \
20677458750966, 103609939177198046, 1745061194503344181714, \
99860890306900024150675406,ldots$$
which points us to OEIS A054976
where we find confirmation of the above calculation and a slightly
different interpretation of the problem statement.
The function v in the Maple program implements model $P$ and the
function v_pre_pie implements model $Q.$
For bicolored versions of $K_{n,n}$ model $Q$ gives the sequence
$$2, 7, 36, 317, 5624, 251610, 33642660, 14685630688, \
21467043671008, 105735224248507784, 1764356230257807614296, \
100455994644460412263071692,ldots$$
which points us to OEIS A002724,
where the calculation is confirmed.
This MSE Meta Link
has many more PET computations by various users.
Thanks go to the authors of the NAUTY package.
$endgroup$
$begingroup$
Excellent! Thanks for taking the time to answer. I'm studying it right now. Quick question about 'the sequence of non-isomorphic spanning subgraphs of $K_{(n,n)}$. If I take $n=2$ I found that there are $6$ spanning subgraphs of $K_{(2,2)}$ namely: the empty graph of four vertices, $P_2cup {a}cup{b}, P_2cup P_2, P_3cup {a}, P_4, K_{(2,2)}$. Thank you!
$endgroup$
– chowching
Feb 25 '15 at 6:12
$begingroup$
We already discussed this at your other MSE question. There seven bicolored graphs on $K_{2,2}$ but a bicolored graph is not the same as a spanning subgraph. Please consult the discussion on the other question. E.g. the empty graph does not span $K_{2,2}.$ This Wikipedia entry is the definition of a spanning subgraph. The above program also counts bicolored graphs. Note that v_pre_pi(2,2)=7 and v(2,2)=3.
$endgroup$
– Marko Riedel
Feb 25 '15 at 18:50
$begingroup$
I see what you mean now, I have added a comment.
$endgroup$
– Marko Riedel
Feb 25 '15 at 19:05
$begingroup$
I'm not impressed to have yet another impressing anwer from you.
$endgroup$
– Jorge Fernández Hidalgo
Feb 26 '15 at 1:31
add a comment |
$begingroup$
Introductory remark. The following discussion uses two different
definition of spanning subgraphs of $K_{n,m}$, one being subgraphs
with the same vertex set and the second subgraphs with the same vertex
set where there are no isolated vertices. The first of these is
equivalent to coloring the graph with two colors. Call these two model
$Q$ and model $P$ respectively.
The goal here is to enumerate spanning subgraphs of $K_{n,m}$ where we
will treat the simple case where even if $n=m$ there are no flips
above a central vertical axis i.e. no reflections. We can do much
better than NAUTY as we are only counting these graphs as opposed to
enumerating them. We use the Polya Enumeration Theorem (PET) to obtain
the count of all non-isomorphic subgraphs of $K_{n,m}$ (model $Q$) and
the principle of inclusion-exclusion (PIE) to extract the count of the
spanning subgraphs (model $P$).
We will consult NAUTY just the same to get sample data to match
against in our mathematical analysis. The following Perl script was
used.
#! /usr/bin/perl -w
#
sub decode_graph {
my ($str) = @_;
sub R {
my (@args) = map {
sprintf "%06b", $_;
} @_;
join '', @args;
}
my (@ents) = map {
ord($_) - 63
} split //, $str;
my $n = shift @ents;
my @adj_data = split //, R(@ents);
my $adj = ; my $pos = 0;
for(my $ind2 = 1; $ind2 < $n; $ind2++){
for(my $ind1 = 0; $ind1 < $ind2; $ind1++){
$adj->[$ind1]->[$ind2] = $adj_data[$pos];
$adj->[$ind2]->[$ind1] = $adj_data[$pos];
$pos++;
}
}
return $adj;
}
MAIN: {
my $mx = shift || 3;
die "out of range for GENBG: $mx"
if 2*$mx < 2 || 2*$mx > 32;
for(my $comp_a = 1; $comp_a <= $mx; $comp_a++){
for(my $comp_b = 1; $comp_b <= $mx; $comp_b++){
my $vcount = $comp_a + $comp_b;
my $cmd = sprintf "./genbg %d %d",
$comp_a, $comp_b;
my $count = 0;
open GENBG, "$cmd 2>/dev/null|";
while(my $bp = <GENBG>){
chomp $bp; my $adj = decode_graph $bp;
for($v = 0; $v < $vcount; $v++){
my $deg = 0;
for(my $w = 0; $w < $vcount; $w++){
my $ent = $adj->[$v]->[$w];
$deg++ if defined($ent) && $ent == 1;
}
last if $deg == 0;
}
$count++ if $v == $vcount;
}
close GENBG;
printf " " if $comp_b > 1;
printf "%06d", $count;
}
printf "n";
};
}
This gave the following table:
$ ./scripts/bipartite.pl 6
000001 000001 000001 000001 000001 000001
000001 000003 000005 000008 000011 000015
000001 000005 000017 000042 000091 000180
000001 000008 000042 000179 000633 002001
000001 000011 000091 000633 003835 020755
000001 000015 000180 002001 020755 200082
Now for the mathematics. We use the Polya Enumeration Theorem as
conjectured by the OP. To do this we need the cycle index of the
action on the edges of the group that permutes the vertices in
partition $A$ of size $n$ according to the symmetric group $S_n$ and
the vertices in partition $B$ of size $m$ according to $S_m.$
These cycle indices are easy to compute and we do not need to iterate
over all $n!times m!$ pairs of permutations (acting on $A$ and $B$)
but instead it is sufficient to iterate over pairs of terms from the
cycle indices $Z(S_n)$ and $Z(S_m)$ of the symmetric groups $S_n$ and
$S_m$ according to their multiplicities to obtain the cycle index
$Z(Q_{n,m})$ of the combined action on $A$ and $B$. The number of
terms here is the much better count of the number of partitions of $n$
and $m$ (upper bound).
The classic approach to the calculation of these cycle indices is
based on the simple observation that for two cycles, one of length
$l_1$ from a permutation $alpha$ of $A$ and another of length $l_2$
from a column permutation $beta$ of $B$ their contribution to the
disjoint cycle decomposition product for $(alpha,beta)$ in the cycle
index $Z(Q_{n,m})$ is by inspection
$$a_{mathrm{lcm}(l_1, l_2)}^{l_1 l_2 / mathrm{lcm}(l_1, l_2)}
= a_{mathrm{lcm}(l_1, l_2)}^{gcd(l_1, l_2)}.$$
Once we have the cycle indices we evaluate
$$Z(Q_{n,m})(1+z)$$
which is the standard substitution to produce the OGF. If we are only
looking to obtain the count, we may use
$$Z(Q_{n,m})_{Large a_1=a_2=a_3=cdots=2}.$$
Here is an example:
$$Z(Q_{3,4}) =
{frac {{a_{{1}}}^{12}}{144}}+1/24,{a_{{2}}}^{3}{a_{{1}}}^{6}+1/18,{a_{{3
}}}^{3}{a_{{1}}}^{3}+1/12,{a_{{2}}}^{6}+1/6,{a_{{4}}}^{3}
\+1/48,{a_{{2}}}
^{4}{a_{{1}}}^{4}+1/8,{a_{{1}}}^{2}{a_{{2}}}^{5}+1/6,a_{{1}}a_{{2}}a_{{3}
}a_{{6}}+1/8,{a_{{3}}}^{4}
\+1/12,{a_{{3}}}^{2}a_{{6}}+1/24,{a_{{6}}}^{2}+
1/12,a_{{12}}.$$
The substituted cycle index becomes
$$Z(Q_{3,4})(1+z) =
{z}^{12}+{z}^{11}+3,{z}^{10}+6,{z}^{9}+11,{z}^{8}
\ +13,{z}^{7}+17,{z}^{6
}+13,{z}^{5}+11,{z}^{4}+6,{z}^{3}+3,{z}^{2}+z+1.$$
At this point we have just about everything we need, the only problem
as is evident from the substituted cycle index (indexed by edge count)
is that we are counting all subgraphs including those that obviously
cannot span $K_{3,4}.$ Observe however that $Z(Q_{3,4})$ includes the
count from all graphs $K_{a,b}$ where $1le a le 3$ and $1le b le
4$ and this observation holds for the $Z(Q_{a,b})$ as well. The way to
identify a spanning subgraph of $K_{3,4}$ is that every vertex in the
vertex set has degree at least one, which means these are just the
graphs that cannot possibly be counted by $Z(Q_{a,b})$ with $(a,b)ne
(3,4)$ because of the missing vertices. Therefore we apply PIE to the
poset where the nodes corresponding to the $(a,b)$ is the set of
graphs counted by the corresponding substituted cycle index. We have
by inspection that this poset is isomorphic to the divisor poset of
$2^{n-1}times 3^{m-1}$ so that we may use the ordinary Möbius
function from number theory as our Möbius function for the PIE
computation. (We are not including the empty graph in the sets at the
nodes from the poset.)
This is implemented in the following Maple program.
with(numtheory);
pet_cycleind_symm :=
proc(n)
option remember;
if n=0 then return 1; fi;
expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;
pet_varinto_cind :=
proc(poly, ind)
local subs1, subsl, polyvars, indvars, v, pot;
polyvars := indets(poly);
indvars := indets(ind);
subsl := ;
for v in indvars do
pot := op(1, v);
subs1 :=
[seq(polyvars[k]=polyvars[k]^pot,
k=1..nops(polyvars))];
subsl := [op(subsl), v=subs(subs1, poly)];
od;
subs(subsl, ind);
end;
pet_cycleind_knm :=
proc(n, m)
option remember;
local cind, sind1, sind2, t1, t2, q,
v1, v2, len, len1, len2;
cind := 0;
if n=1 then
sind1 := [a[1]];
else
sind1 := pet_cycleind_symm(n);
fi;
if m=1 then
sind2 := [a[1]];
else
sind2 := pet_cycleind_symm(m);
fi;
for t1 in sind1 do
for t2 in sind2 do
q := 1;
for v1 in indets(t1) do
len1 := op(1, v1);
for v2 in indets(t2) do
len2 := op(1, v2);
len := lcm(len1, len2);
q := q *
a[len]^((len1*len2/len) *
degree(t1, v1)*degree(t2, v2));
od;
od;
cind := cind +
lcoeff(t1)*lcoeff(t2)*q;
od;
od;
cind;
end;
v_pre_pie :=
proc(n, m)
option remember;
local cind;
cind := pet_cycleind_knm(n, m);
subs([seq(a[v]=2, v=1..n*m)], cind);
end;
v :=
proc(n, m)
local q, a, b, res;
q := 2^(n-1)*3^(m-1);
res := 0;
for a to n do
for b to m do
res := res +
mobius(q/2^(a-1)/3^(b-1))*
(v_pre_pie(a, b)-1);
od;
od;
res;
end;
print_table :=
proc(mx)
local n, m;
for n to mx do
for m to mx do
if m>1 then printf(" ") fi;
printf("%06d", v(n, m));
od;
printf("n");
od;
end;
The above Maple code produces the following table:
> print_table(6);
000001 000001 000001 000001 000001 000001
000001 000003 000005 000008 000011 000015
000001 000005 000017 000042 000091 000180
000001 000008 000042 000179 000633 002001
000001 000011 000091 000633 003835 020755
000001 000015 000180 002001 020755 200082
It can calculate values that are completely out of reach for NAUTY
like the sequence of non-isomorphic spanning subgraphs of $K_{n,n}$
which is
$$1, 3, 17, 179, 3835, 200082, 29610804, 13702979132, \
20677458750966, 103609939177198046, 1745061194503344181714, \
99860890306900024150675406,ldots$$
which points us to OEIS A054976
where we find confirmation of the above calculation and a slightly
different interpretation of the problem statement.
The function v in the Maple program implements model $P$ and the
function v_pre_pie implements model $Q.$
For bicolored versions of $K_{n,n}$ model $Q$ gives the sequence
$$2, 7, 36, 317, 5624, 251610, 33642660, 14685630688, \
21467043671008, 105735224248507784, 1764356230257807614296, \
100455994644460412263071692,ldots$$
which points us to OEIS A002724,
where the calculation is confirmed.
This MSE Meta Link
has many more PET computations by various users.
Thanks go to the authors of the NAUTY package.
$endgroup$
$begingroup$
Excellent! Thanks for taking the time to answer. I'm studying it right now. Quick question about 'the sequence of non-isomorphic spanning subgraphs of $K_{(n,n)}$. If I take $n=2$ I found that there are $6$ spanning subgraphs of $K_{(2,2)}$ namely: the empty graph of four vertices, $P_2cup {a}cup{b}, P_2cup P_2, P_3cup {a}, P_4, K_{(2,2)}$. Thank you!
$endgroup$
– chowching
Feb 25 '15 at 6:12
$begingroup$
We already discussed this at your other MSE question. There seven bicolored graphs on $K_{2,2}$ but a bicolored graph is not the same as a spanning subgraph. Please consult the discussion on the other question. E.g. the empty graph does not span $K_{2,2}.$ This Wikipedia entry is the definition of a spanning subgraph. The above program also counts bicolored graphs. Note that v_pre_pi(2,2)=7 and v(2,2)=3.
$endgroup$
– Marko Riedel
Feb 25 '15 at 18:50
$begingroup$
I see what you mean now, I have added a comment.
$endgroup$
– Marko Riedel
Feb 25 '15 at 19:05
$begingroup$
I'm not impressed to have yet another impressing anwer from you.
$endgroup$
– Jorge Fernández Hidalgo
Feb 26 '15 at 1:31
add a comment |
$begingroup$
Introductory remark. The following discussion uses two different
definition of spanning subgraphs of $K_{n,m}$, one being subgraphs
with the same vertex set and the second subgraphs with the same vertex
set where there are no isolated vertices. The first of these is
equivalent to coloring the graph with two colors. Call these two model
$Q$ and model $P$ respectively.
The goal here is to enumerate spanning subgraphs of $K_{n,m}$ where we
will treat the simple case where even if $n=m$ there are no flips
above a central vertical axis i.e. no reflections. We can do much
better than NAUTY as we are only counting these graphs as opposed to
enumerating them. We use the Polya Enumeration Theorem (PET) to obtain
the count of all non-isomorphic subgraphs of $K_{n,m}$ (model $Q$) and
the principle of inclusion-exclusion (PIE) to extract the count of the
spanning subgraphs (model $P$).
We will consult NAUTY just the same to get sample data to match
against in our mathematical analysis. The following Perl script was
used.
#! /usr/bin/perl -w
#
sub decode_graph {
my ($str) = @_;
sub R {
my (@args) = map {
sprintf "%06b", $_;
} @_;
join '', @args;
}
my (@ents) = map {
ord($_) - 63
} split //, $str;
my $n = shift @ents;
my @adj_data = split //, R(@ents);
my $adj = ; my $pos = 0;
for(my $ind2 = 1; $ind2 < $n; $ind2++){
for(my $ind1 = 0; $ind1 < $ind2; $ind1++){
$adj->[$ind1]->[$ind2] = $adj_data[$pos];
$adj->[$ind2]->[$ind1] = $adj_data[$pos];
$pos++;
}
}
return $adj;
}
MAIN: {
my $mx = shift || 3;
die "out of range for GENBG: $mx"
if 2*$mx < 2 || 2*$mx > 32;
for(my $comp_a = 1; $comp_a <= $mx; $comp_a++){
for(my $comp_b = 1; $comp_b <= $mx; $comp_b++){
my $vcount = $comp_a + $comp_b;
my $cmd = sprintf "./genbg %d %d",
$comp_a, $comp_b;
my $count = 0;
open GENBG, "$cmd 2>/dev/null|";
while(my $bp = <GENBG>){
chomp $bp; my $adj = decode_graph $bp;
for($v = 0; $v < $vcount; $v++){
my $deg = 0;
for(my $w = 0; $w < $vcount; $w++){
my $ent = $adj->[$v]->[$w];
$deg++ if defined($ent) && $ent == 1;
}
last if $deg == 0;
}
$count++ if $v == $vcount;
}
close GENBG;
printf " " if $comp_b > 1;
printf "%06d", $count;
}
printf "n";
};
}
This gave the following table:
$ ./scripts/bipartite.pl 6
000001 000001 000001 000001 000001 000001
000001 000003 000005 000008 000011 000015
000001 000005 000017 000042 000091 000180
000001 000008 000042 000179 000633 002001
000001 000011 000091 000633 003835 020755
000001 000015 000180 002001 020755 200082
Now for the mathematics. We use the Polya Enumeration Theorem as
conjectured by the OP. To do this we need the cycle index of the
action on the edges of the group that permutes the vertices in
partition $A$ of size $n$ according to the symmetric group $S_n$ and
the vertices in partition $B$ of size $m$ according to $S_m.$
These cycle indices are easy to compute and we do not need to iterate
over all $n!times m!$ pairs of permutations (acting on $A$ and $B$)
but instead it is sufficient to iterate over pairs of terms from the
cycle indices $Z(S_n)$ and $Z(S_m)$ of the symmetric groups $S_n$ and
$S_m$ according to their multiplicities to obtain the cycle index
$Z(Q_{n,m})$ of the combined action on $A$ and $B$. The number of
terms here is the much better count of the number of partitions of $n$
and $m$ (upper bound).
The classic approach to the calculation of these cycle indices is
based on the simple observation that for two cycles, one of length
$l_1$ from a permutation $alpha$ of $A$ and another of length $l_2$
from a column permutation $beta$ of $B$ their contribution to the
disjoint cycle decomposition product for $(alpha,beta)$ in the cycle
index $Z(Q_{n,m})$ is by inspection
$$a_{mathrm{lcm}(l_1, l_2)}^{l_1 l_2 / mathrm{lcm}(l_1, l_2)}
= a_{mathrm{lcm}(l_1, l_2)}^{gcd(l_1, l_2)}.$$
Once we have the cycle indices we evaluate
$$Z(Q_{n,m})(1+z)$$
which is the standard substitution to produce the OGF. If we are only
looking to obtain the count, we may use
$$Z(Q_{n,m})_{Large a_1=a_2=a_3=cdots=2}.$$
Here is an example:
$$Z(Q_{3,4}) =
{frac {{a_{{1}}}^{12}}{144}}+1/24,{a_{{2}}}^{3}{a_{{1}}}^{6}+1/18,{a_{{3
}}}^{3}{a_{{1}}}^{3}+1/12,{a_{{2}}}^{6}+1/6,{a_{{4}}}^{3}
\+1/48,{a_{{2}}}
^{4}{a_{{1}}}^{4}+1/8,{a_{{1}}}^{2}{a_{{2}}}^{5}+1/6,a_{{1}}a_{{2}}a_{{3}
}a_{{6}}+1/8,{a_{{3}}}^{4}
\+1/12,{a_{{3}}}^{2}a_{{6}}+1/24,{a_{{6}}}^{2}+
1/12,a_{{12}}.$$
The substituted cycle index becomes
$$Z(Q_{3,4})(1+z) =
{z}^{12}+{z}^{11}+3,{z}^{10}+6,{z}^{9}+11,{z}^{8}
\ +13,{z}^{7}+17,{z}^{6
}+13,{z}^{5}+11,{z}^{4}+6,{z}^{3}+3,{z}^{2}+z+1.$$
At this point we have just about everything we need, the only problem
as is evident from the substituted cycle index (indexed by edge count)
is that we are counting all subgraphs including those that obviously
cannot span $K_{3,4}.$ Observe however that $Z(Q_{3,4})$ includes the
count from all graphs $K_{a,b}$ where $1le a le 3$ and $1le b le
4$ and this observation holds for the $Z(Q_{a,b})$ as well. The way to
identify a spanning subgraph of $K_{3,4}$ is that every vertex in the
vertex set has degree at least one, which means these are just the
graphs that cannot possibly be counted by $Z(Q_{a,b})$ with $(a,b)ne
(3,4)$ because of the missing vertices. Therefore we apply PIE to the
poset where the nodes corresponding to the $(a,b)$ is the set of
graphs counted by the corresponding substituted cycle index. We have
by inspection that this poset is isomorphic to the divisor poset of
$2^{n-1}times 3^{m-1}$ so that we may use the ordinary Möbius
function from number theory as our Möbius function for the PIE
computation. (We are not including the empty graph in the sets at the
nodes from the poset.)
This is implemented in the following Maple program.
with(numtheory);
pet_cycleind_symm :=
proc(n)
option remember;
if n=0 then return 1; fi;
expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;
pet_varinto_cind :=
proc(poly, ind)
local subs1, subsl, polyvars, indvars, v, pot;
polyvars := indets(poly);
indvars := indets(ind);
subsl := ;
for v in indvars do
pot := op(1, v);
subs1 :=
[seq(polyvars[k]=polyvars[k]^pot,
k=1..nops(polyvars))];
subsl := [op(subsl), v=subs(subs1, poly)];
od;
subs(subsl, ind);
end;
pet_cycleind_knm :=
proc(n, m)
option remember;
local cind, sind1, sind2, t1, t2, q,
v1, v2, len, len1, len2;
cind := 0;
if n=1 then
sind1 := [a[1]];
else
sind1 := pet_cycleind_symm(n);
fi;
if m=1 then
sind2 := [a[1]];
else
sind2 := pet_cycleind_symm(m);
fi;
for t1 in sind1 do
for t2 in sind2 do
q := 1;
for v1 in indets(t1) do
len1 := op(1, v1);
for v2 in indets(t2) do
len2 := op(1, v2);
len := lcm(len1, len2);
q := q *
a[len]^((len1*len2/len) *
degree(t1, v1)*degree(t2, v2));
od;
od;
cind := cind +
lcoeff(t1)*lcoeff(t2)*q;
od;
od;
cind;
end;
v_pre_pie :=
proc(n, m)
option remember;
local cind;
cind := pet_cycleind_knm(n, m);
subs([seq(a[v]=2, v=1..n*m)], cind);
end;
v :=
proc(n, m)
local q, a, b, res;
q := 2^(n-1)*3^(m-1);
res := 0;
for a to n do
for b to m do
res := res +
mobius(q/2^(a-1)/3^(b-1))*
(v_pre_pie(a, b)-1);
od;
od;
res;
end;
print_table :=
proc(mx)
local n, m;
for n to mx do
for m to mx do
if m>1 then printf(" ") fi;
printf("%06d", v(n, m));
od;
printf("n");
od;
end;
The above Maple code produces the following table:
> print_table(6);
000001 000001 000001 000001 000001 000001
000001 000003 000005 000008 000011 000015
000001 000005 000017 000042 000091 000180
000001 000008 000042 000179 000633 002001
000001 000011 000091 000633 003835 020755
000001 000015 000180 002001 020755 200082
It can calculate values that are completely out of reach for NAUTY
like the sequence of non-isomorphic spanning subgraphs of $K_{n,n}$
which is
$$1, 3, 17, 179, 3835, 200082, 29610804, 13702979132, \
20677458750966, 103609939177198046, 1745061194503344181714, \
99860890306900024150675406,ldots$$
which points us to OEIS A054976
where we find confirmation of the above calculation and a slightly
different interpretation of the problem statement.
The function v in the Maple program implements model $P$ and the
function v_pre_pie implements model $Q.$
For bicolored versions of $K_{n,n}$ model $Q$ gives the sequence
$$2, 7, 36, 317, 5624, 251610, 33642660, 14685630688, \
21467043671008, 105735224248507784, 1764356230257807614296, \
100455994644460412263071692,ldots$$
which points us to OEIS A002724,
where the calculation is confirmed.
This MSE Meta Link
has many more PET computations by various users.
Thanks go to the authors of the NAUTY package.
$endgroup$
Introductory remark. The following discussion uses two different
definition of spanning subgraphs of $K_{n,m}$, one being subgraphs
with the same vertex set and the second subgraphs with the same vertex
set where there are no isolated vertices. The first of these is
equivalent to coloring the graph with two colors. Call these two model
$Q$ and model $P$ respectively.
The goal here is to enumerate spanning subgraphs of $K_{n,m}$ where we
will treat the simple case where even if $n=m$ there are no flips
above a central vertical axis i.e. no reflections. We can do much
better than NAUTY as we are only counting these graphs as opposed to
enumerating them. We use the Polya Enumeration Theorem (PET) to obtain
the count of all non-isomorphic subgraphs of $K_{n,m}$ (model $Q$) and
the principle of inclusion-exclusion (PIE) to extract the count of the
spanning subgraphs (model $P$).
We will consult NAUTY just the same to get sample data to match
against in our mathematical analysis. The following Perl script was
used.
#! /usr/bin/perl -w
#
sub decode_graph {
my ($str) = @_;
sub R {
my (@args) = map {
sprintf "%06b", $_;
} @_;
join '', @args;
}
my (@ents) = map {
ord($_) - 63
} split //, $str;
my $n = shift @ents;
my @adj_data = split //, R(@ents);
my $adj = ; my $pos = 0;
for(my $ind2 = 1; $ind2 < $n; $ind2++){
for(my $ind1 = 0; $ind1 < $ind2; $ind1++){
$adj->[$ind1]->[$ind2] = $adj_data[$pos];
$adj->[$ind2]->[$ind1] = $adj_data[$pos];
$pos++;
}
}
return $adj;
}
MAIN: {
my $mx = shift || 3;
die "out of range for GENBG: $mx"
if 2*$mx < 2 || 2*$mx > 32;
for(my $comp_a = 1; $comp_a <= $mx; $comp_a++){
for(my $comp_b = 1; $comp_b <= $mx; $comp_b++){
my $vcount = $comp_a + $comp_b;
my $cmd = sprintf "./genbg %d %d",
$comp_a, $comp_b;
my $count = 0;
open GENBG, "$cmd 2>/dev/null|";
while(my $bp = <GENBG>){
chomp $bp; my $adj = decode_graph $bp;
for($v = 0; $v < $vcount; $v++){
my $deg = 0;
for(my $w = 0; $w < $vcount; $w++){
my $ent = $adj->[$v]->[$w];
$deg++ if defined($ent) && $ent == 1;
}
last if $deg == 0;
}
$count++ if $v == $vcount;
}
close GENBG;
printf " " if $comp_b > 1;
printf "%06d", $count;
}
printf "n";
};
}
This gave the following table:
$ ./scripts/bipartite.pl 6
000001 000001 000001 000001 000001 000001
000001 000003 000005 000008 000011 000015
000001 000005 000017 000042 000091 000180
000001 000008 000042 000179 000633 002001
000001 000011 000091 000633 003835 020755
000001 000015 000180 002001 020755 200082
Now for the mathematics. We use the Polya Enumeration Theorem as
conjectured by the OP. To do this we need the cycle index of the
action on the edges of the group that permutes the vertices in
partition $A$ of size $n$ according to the symmetric group $S_n$ and
the vertices in partition $B$ of size $m$ according to $S_m.$
These cycle indices are easy to compute and we do not need to iterate
over all $n!times m!$ pairs of permutations (acting on $A$ and $B$)
but instead it is sufficient to iterate over pairs of terms from the
cycle indices $Z(S_n)$ and $Z(S_m)$ of the symmetric groups $S_n$ and
$S_m$ according to their multiplicities to obtain the cycle index
$Z(Q_{n,m})$ of the combined action on $A$ and $B$. The number of
terms here is the much better count of the number of partitions of $n$
and $m$ (upper bound).
The classic approach to the calculation of these cycle indices is
based on the simple observation that for two cycles, one of length
$l_1$ from a permutation $alpha$ of $A$ and another of length $l_2$
from a column permutation $beta$ of $B$ their contribution to the
disjoint cycle decomposition product for $(alpha,beta)$ in the cycle
index $Z(Q_{n,m})$ is by inspection
$$a_{mathrm{lcm}(l_1, l_2)}^{l_1 l_2 / mathrm{lcm}(l_1, l_2)}
= a_{mathrm{lcm}(l_1, l_2)}^{gcd(l_1, l_2)}.$$
Once we have the cycle indices we evaluate
$$Z(Q_{n,m})(1+z)$$
which is the standard substitution to produce the OGF. If we are only
looking to obtain the count, we may use
$$Z(Q_{n,m})_{Large a_1=a_2=a_3=cdots=2}.$$
Here is an example:
$$Z(Q_{3,4}) =
{frac {{a_{{1}}}^{12}}{144}}+1/24,{a_{{2}}}^{3}{a_{{1}}}^{6}+1/18,{a_{{3
}}}^{3}{a_{{1}}}^{3}+1/12,{a_{{2}}}^{6}+1/6,{a_{{4}}}^{3}
\+1/48,{a_{{2}}}
^{4}{a_{{1}}}^{4}+1/8,{a_{{1}}}^{2}{a_{{2}}}^{5}+1/6,a_{{1}}a_{{2}}a_{{3}
}a_{{6}}+1/8,{a_{{3}}}^{4}
\+1/12,{a_{{3}}}^{2}a_{{6}}+1/24,{a_{{6}}}^{2}+
1/12,a_{{12}}.$$
The substituted cycle index becomes
$$Z(Q_{3,4})(1+z) =
{z}^{12}+{z}^{11}+3,{z}^{10}+6,{z}^{9}+11,{z}^{8}
\ +13,{z}^{7}+17,{z}^{6
}+13,{z}^{5}+11,{z}^{4}+6,{z}^{3}+3,{z}^{2}+z+1.$$
At this point we have just about everything we need, the only problem
as is evident from the substituted cycle index (indexed by edge count)
is that we are counting all subgraphs including those that obviously
cannot span $K_{3,4}.$ Observe however that $Z(Q_{3,4})$ includes the
count from all graphs $K_{a,b}$ where $1le a le 3$ and $1le b le
4$ and this observation holds for the $Z(Q_{a,b})$ as well. The way to
identify a spanning subgraph of $K_{3,4}$ is that every vertex in the
vertex set has degree at least one, which means these are just the
graphs that cannot possibly be counted by $Z(Q_{a,b})$ with $(a,b)ne
(3,4)$ because of the missing vertices. Therefore we apply PIE to the
poset where the nodes corresponding to the $(a,b)$ is the set of
graphs counted by the corresponding substituted cycle index. We have
by inspection that this poset is isomorphic to the divisor poset of
$2^{n-1}times 3^{m-1}$ so that we may use the ordinary Möbius
function from number theory as our Möbius function for the PIE
computation. (We are not including the empty graph in the sets at the
nodes from the poset.)
This is implemented in the following Maple program.
with(numtheory);
pet_cycleind_symm :=
proc(n)
option remember;
if n=0 then return 1; fi;
expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;
pet_varinto_cind :=
proc(poly, ind)
local subs1, subsl, polyvars, indvars, v, pot;
polyvars := indets(poly);
indvars := indets(ind);
subsl := ;
for v in indvars do
pot := op(1, v);
subs1 :=
[seq(polyvars[k]=polyvars[k]^pot,
k=1..nops(polyvars))];
subsl := [op(subsl), v=subs(subs1, poly)];
od;
subs(subsl, ind);
end;
pet_cycleind_knm :=
proc(n, m)
option remember;
local cind, sind1, sind2, t1, t2, q,
v1, v2, len, len1, len2;
cind := 0;
if n=1 then
sind1 := [a[1]];
else
sind1 := pet_cycleind_symm(n);
fi;
if m=1 then
sind2 := [a[1]];
else
sind2 := pet_cycleind_symm(m);
fi;
for t1 in sind1 do
for t2 in sind2 do
q := 1;
for v1 in indets(t1) do
len1 := op(1, v1);
for v2 in indets(t2) do
len2 := op(1, v2);
len := lcm(len1, len2);
q := q *
a[len]^((len1*len2/len) *
degree(t1, v1)*degree(t2, v2));
od;
od;
cind := cind +
lcoeff(t1)*lcoeff(t2)*q;
od;
od;
cind;
end;
v_pre_pie :=
proc(n, m)
option remember;
local cind;
cind := pet_cycleind_knm(n, m);
subs([seq(a[v]=2, v=1..n*m)], cind);
end;
v :=
proc(n, m)
local q, a, b, res;
q := 2^(n-1)*3^(m-1);
res := 0;
for a to n do
for b to m do
res := res +
mobius(q/2^(a-1)/3^(b-1))*
(v_pre_pie(a, b)-1);
od;
od;
res;
end;
print_table :=
proc(mx)
local n, m;
for n to mx do
for m to mx do
if m>1 then printf(" ") fi;
printf("%06d", v(n, m));
od;
printf("n");
od;
end;
The above Maple code produces the following table:
> print_table(6);
000001 000001 000001 000001 000001 000001
000001 000003 000005 000008 000011 000015
000001 000005 000017 000042 000091 000180
000001 000008 000042 000179 000633 002001
000001 000011 000091 000633 003835 020755
000001 000015 000180 002001 020755 200082
It can calculate values that are completely out of reach for NAUTY
like the sequence of non-isomorphic spanning subgraphs of $K_{n,n}$
which is
$$1, 3, 17, 179, 3835, 200082, 29610804, 13702979132, \
20677458750966, 103609939177198046, 1745061194503344181714, \
99860890306900024150675406,ldots$$
which points us to OEIS A054976
where we find confirmation of the above calculation and a slightly
different interpretation of the problem statement.
The function v in the Maple program implements model $P$ and the
function v_pre_pie implements model $Q.$
For bicolored versions of $K_{n,n}$ model $Q$ gives the sequence
$$2, 7, 36, 317, 5624, 251610, 33642660, 14685630688, \
21467043671008, 105735224248507784, 1764356230257807614296, \
100455994644460412263071692,ldots$$
which points us to OEIS A002724,
where the calculation is confirmed.
This MSE Meta Link
has many more PET computations by various users.
Thanks go to the authors of the NAUTY package.
edited Jan 4 at 15:41
answered Feb 25 '15 at 2:29
Marko RiedelMarko Riedel
41.1k340111
41.1k340111
$begingroup$
Excellent! Thanks for taking the time to answer. I'm studying it right now. Quick question about 'the sequence of non-isomorphic spanning subgraphs of $K_{(n,n)}$. If I take $n=2$ I found that there are $6$ spanning subgraphs of $K_{(2,2)}$ namely: the empty graph of four vertices, $P_2cup {a}cup{b}, P_2cup P_2, P_3cup {a}, P_4, K_{(2,2)}$. Thank you!
$endgroup$
– chowching
Feb 25 '15 at 6:12
$begingroup$
We already discussed this at your other MSE question. There seven bicolored graphs on $K_{2,2}$ but a bicolored graph is not the same as a spanning subgraph. Please consult the discussion on the other question. E.g. the empty graph does not span $K_{2,2}.$ This Wikipedia entry is the definition of a spanning subgraph. The above program also counts bicolored graphs. Note that v_pre_pi(2,2)=7 and v(2,2)=3.
$endgroup$
– Marko Riedel
Feb 25 '15 at 18:50
$begingroup$
I see what you mean now, I have added a comment.
$endgroup$
– Marko Riedel
Feb 25 '15 at 19:05
$begingroup$
I'm not impressed to have yet another impressing anwer from you.
$endgroup$
– Jorge Fernández Hidalgo
Feb 26 '15 at 1:31
add a comment |
$begingroup$
Excellent! Thanks for taking the time to answer. I'm studying it right now. Quick question about 'the sequence of non-isomorphic spanning subgraphs of $K_{(n,n)}$. If I take $n=2$ I found that there are $6$ spanning subgraphs of $K_{(2,2)}$ namely: the empty graph of four vertices, $P_2cup {a}cup{b}, P_2cup P_2, P_3cup {a}, P_4, K_{(2,2)}$. Thank you!
$endgroup$
– chowching
Feb 25 '15 at 6:12
$begingroup$
We already discussed this at your other MSE question. There seven bicolored graphs on $K_{2,2}$ but a bicolored graph is not the same as a spanning subgraph. Please consult the discussion on the other question. E.g. the empty graph does not span $K_{2,2}.$ This Wikipedia entry is the definition of a spanning subgraph. The above program also counts bicolored graphs. Note that v_pre_pi(2,2)=7 and v(2,2)=3.
$endgroup$
– Marko Riedel
Feb 25 '15 at 18:50
$begingroup$
I see what you mean now, I have added a comment.
$endgroup$
– Marko Riedel
Feb 25 '15 at 19:05
$begingroup$
I'm not impressed to have yet another impressing anwer from you.
$endgroup$
– Jorge Fernández Hidalgo
Feb 26 '15 at 1:31
$begingroup$
Excellent! Thanks for taking the time to answer. I'm studying it right now. Quick question about 'the sequence of non-isomorphic spanning subgraphs of $K_{(n,n)}$. If I take $n=2$ I found that there are $6$ spanning subgraphs of $K_{(2,2)}$ namely: the empty graph of four vertices, $P_2cup {a}cup{b}, P_2cup P_2, P_3cup {a}, P_4, K_{(2,2)}$. Thank you!
$endgroup$
– chowching
Feb 25 '15 at 6:12
$begingroup$
Excellent! Thanks for taking the time to answer. I'm studying it right now. Quick question about 'the sequence of non-isomorphic spanning subgraphs of $K_{(n,n)}$. If I take $n=2$ I found that there are $6$ spanning subgraphs of $K_{(2,2)}$ namely: the empty graph of four vertices, $P_2cup {a}cup{b}, P_2cup P_2, P_3cup {a}, P_4, K_{(2,2)}$. Thank you!
$endgroup$
– chowching
Feb 25 '15 at 6:12
$begingroup$
We already discussed this at your other MSE question. There seven bicolored graphs on $K_{2,2}$ but a bicolored graph is not the same as a spanning subgraph. Please consult the discussion on the other question. E.g. the empty graph does not span $K_{2,2}.$ This Wikipedia entry is the definition of a spanning subgraph. The above program also counts bicolored graphs. Note that v_pre_pi(2,2)=7 and v(2,2)=3.
$endgroup$
– Marko Riedel
Feb 25 '15 at 18:50
$begingroup$
We already discussed this at your other MSE question. There seven bicolored graphs on $K_{2,2}$ but a bicolored graph is not the same as a spanning subgraph. Please consult the discussion on the other question. E.g. the empty graph does not span $K_{2,2}.$ This Wikipedia entry is the definition of a spanning subgraph. The above program also counts bicolored graphs. Note that v_pre_pi(2,2)=7 and v(2,2)=3.
$endgroup$
– Marko Riedel
Feb 25 '15 at 18:50
$begingroup$
I see what you mean now, I have added a comment.
$endgroup$
– Marko Riedel
Feb 25 '15 at 19:05
$begingroup$
I see what you mean now, I have added a comment.
$endgroup$
– Marko Riedel
Feb 25 '15 at 19:05
$begingroup$
I'm not impressed to have yet another impressing anwer from you.
$endgroup$
– Jorge Fernández Hidalgo
Feb 26 '15 at 1:31
$begingroup$
I'm not impressed to have yet another impressing anwer from you.
$endgroup$
– Jorge Fernández Hidalgo
Feb 26 '15 at 1:31
add a comment |
$begingroup$
The following data augment those in the first answer, namely we treat
the problem of computing $Z(Q_{n})$ for $K_{n,n}$ where we include reflections. The
algorithm here is slightly different from Harary and Palmer. Clearly
all permutations from the first answer represented in $Z(Q_{n,n})$
contribute as well. Now for the reflections, which are simple,
fortunately. These (the vertex permutations) can be obtained from the
permutations in $S_n$ by placing vertices from component $A$
alternating with component $B$ on a cycle with twice the length of a
cycle contained in a permutation $gamma$ of $S_n.$ The
induced action on the set of edges is the contribution to $Z(Q_n).$ In
the following we have used an algorithmic approach rather than the
formula from Harary and Palmer, namely we construct a canonical
representative of each permutation shape from the cycle index $Z(S_n)$
that doubles the length of every cycle and alternates elements from
the two components. We let that act on the set of edges and factor the
result.
This gives the following cycle indices, the first of which matches the
result given by Harary and Palmer.
For $n=3$,
$$Z(Q_3) =
{frac {{a_{{1}}}^{9}}{72}}+1/6,{a_{{2}}}^{3}{a_{{1}}}^{3}
\+1/9,{a_{{3}}}^{3}
+1/8,{a_{{2}}}^{4}a_{{1}}+1/3,a_{{3}}a_{{6}}+1/4,a_{{1}}{a_{{4}}}^{2}
,$$
for $n=4$,
$$Z(Q_4) =
{frac {{a_{{1}}}^{16}}{1152}}+{frac {{a_{{1}}}^{8}{a_{{2}}}^{4}}{96}}+{
frac {{a_{{3}}}^{4}{a_{{1}}}^{4}}{72}}\
+{frac {17,{a_{{2}}}^{8}}{384}}+{
frac {19,{a_{{4}}}^{4}}{96}}+{frac {5,{a_{{1}}}^{4}{a_{{2}}}^{6}}{96}}+1/
12,{a_{{3}}}^{2}{a_{{1}}}^{2}a_{{2}}a_{{6}}+1/18,{a_{{3}}}^{5}a_{{1}}
\+1/24,
{a_{{2}}}^{2}{a_{{6}}}^{2}+1/12,a_{{4}}a_{{12}}+1/8,{a_{{1}}}^{2}a_{{2}}{a_{
{4}}}^{3}+1/6,a_{{1}}{a_{{6}}}^{2}a_{{3}}+1/8,{a_{{8}}}^{2}
,$$
and for $n=5$,
$$Z(Q_5) =
1/12,{a_{{1}}}^{2}a_{{2}}{a_{{6}}}^{3}a_{{3}}+1/24,{a_{{1}}}^{3}{a_{{2}}}^{3
}{a_{{4}}}^{4}+{frac {{a_{{1}}}^{25}}{28800}}+{frac {13,{a_{{5}}}^{5}}{600}
}+{frac {{a_{{5}}}^{3}a_{{10}}}{60}}\
+1/48,{a_{{2}}}^{4}{a_{{1}}}^{2}a_{{3}}{
a_{{6}}}^{2}+{frac {{a_{{1}}}^{6}{a_{{3}}}^{3}{a_{{2}}}^{2}a_{{6}}}{72}}+1/48
,{a_{{4}}}^{5}{a_{{1}}}^{3}a_{{2}}+1/24,{a_{{4}}}^{2}{a_{{1}}}^{2}a_{{3}}a_{
{12}}\
+1/36,{a_{{2}}}^{2}{a_{{3}}}^{5}a_{{6}}+1/32,{a_{{4}}}^{5}a_{{1}}{a_{{2
}}}^{2}+1/48,{a_{{2}}}^{5}a_{{3}}{a_{{6}}}^{2}+1/24,a_{{2}}a_{{3}}{a_{{4}}}^
{2}a_{{12}}\
+1/8,a_{{1}}{a_{{8}}}^{3}+1/12,a_{{4}}a_{{12}}a_{{6}}a_{{3}}+{
frac {{a_{{1}}}^{15}{a_{{2}}}^{5}}{1440}}+{frac {{a_{{1}}}^{10}{a_{{3}}}^{5}
}{720}}+{frac {{a_{{1}}}^{5}{a_{{2}}}^{10}}{192}}\
+{frac {{a_{{4}}}^{5}{a_{{1
}}}^{5}}{480}}+{frac {{a_{{2}}}^{5}{a_{{3}}}^{5}}{720}}+{frac {{a_{{1}}}^{9}
{a_{{2}}}^{8}}{288}}+{frac {{a_{{2}}}^{11}{a_{{1}}}^{3}}{96}}+{frac {{a_{{2}
}}^{5}{a_{{3}}}^{3}a_{{6}}}{72}}+{frac {{a_{{3}}}^{7}{a_{{1}}}^{4}}{72}}
\ +1/30
,{a_{{5}}}^{2}a_{{15}}+1/20,a_{{5}}a_{{20}}+1/30,a_{{10}}a_{{15}}+{frac {{
a_{{2}}}^{12}a_{{1}}}{128}}+1/8,a_{{5}}{a_{{10}}}^{2}
\+{frac {3,a_{{1}}{a_{{
4}}}^{6}}{32}}+{frac {{a_{{2}}}^{2}{a_{{6}}}^{2}{a_{{3}}}^{3}}{72}}
.$$
These cycle indices can be calculated for large $n$ but the pattern
should be clear. The count of these graphs gives the sequence
$$2, 6, 26, 192, 3014, 127757, 16853750, \ 7343780765, 10733574184956,
52867617324773592,\882178116079222400788, 50227997322550920824045262,
ldots $$
which points us to OEIS A007139 where
we find confirmation of this calculation.
This was the Maple code used to obtain these values.
with(numtheory);
pet_cycleind_symm :=
proc(n)
local p, s;
option remember;
if n=0 then return 1; fi;
expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;
pet_autom2cycles :=
proc(src, aut)
local numa, numsubs;
local marks, pos, cycs, cpos, clen;
numsubs := [seq(src[k]=k, k=1..nops(src))];
numa := subs(numsubs, aut);
marks := Array([seq(true, pos=1..nops(aut))]);
cycs := ; pos := 1;
while pos <= nops(aut) do
if marks[pos] then
clen := 0; cpos := pos;
while marks[cpos] do
marks[cpos] := false;
cpos := numa[cpos];
clen := clen+1;
od;
cycs := [op(cycs), clen];
fi;
pos := pos+1;
od;
return mul(a[cycs[k]], k=1..nops(cycs));
end;
pet_varinto_cind :=
proc(poly, ind)
local subs1, subs2, polyvars, indvars, v, pot, res;
res := ind;
polyvars := indets(poly);
indvars := indets(ind);
for v in indvars do
pot := op(1, v);
subs1 :=
[seq(polyvars[k]=polyvars[k]^pot,
k=1..nops(polyvars))];
subs2 := [v=subs(subs1, poly)];
res := subs(subs2, res);
od;
res;
end;
pet_flatten_term :=
proc(varp)
local terml, d, cf, v;
terml := ;
cf := varp;
for v in indets(varp) do
d := degree(varp, v);
terml := [op(terml), seq(v, k=1..d)];
cf := cf/v^d;
od;
[cf, terml];
end;
pet_flat2rep_cyc :=
proc(f)
local p, q, res, cyc, t, len;
q := 1; res := ;
for t in f do
len := op(1, t);
cyc := [seq(p, p=q+1..q+len-1), q];
res := [op(res), cyc];
q := q+len;
od;
res;
end;
pet_cycs2table :=
proc(cycs)
local pairs, cyc, p, ent;
pairs := ;
for cyc in cycs do
pairs :=
[op(pairs),
seq([cyc[p], cyc[1 + (p mod nops(cyc))]],
p = 1 .. nops(cyc))];
od;
map(ent->ent[2], sort(pairs, (a,b)->a[1] < b[1]));
end;
pet_cycleind_knn :=
proc(n)
option remember;
local cindA, cindB, sind, t1, t2, p, q, cyc1, cyc2,
flat1, flat2, len, len1, len2,
edges, edgeperm, rep, cycsA, cycsB, cycsrc, cyc;
if n=1 then
sind := [a[1]];
else
sind := pet_cycleind_symm(n);
fi;
cindA := 0;
for t1 in sind do
flat1 := pet_flatten_term(t1);
for t2 in sind do
flat2 := pet_flatten_term(t2);
q := 1;
for cyc1 in flat1[2] do
len1 := op(1, cyc1);
for cyc2 in flat2[2] do
len2 := op(1, cyc2);
len := lcm(len1, len2);
q := q * a[len]^(len1*len2/len);
od;
od;
cindA := cindA + flat1[1]*flat2[1]*q;
od;
od;
edges := [seq(seq({p, q+n}, q=1..n), p=1..n)];
cindB := 0;
for t1 in sind do
flat1 := pet_flatten_term(t1);
cycsA := pet_flat2rep_cyc(flat1[2]);
cycsB := ;
for cycsrc in cycsA do
cyc := ;
for q in cycsrc do
cyc := [op(cyc), q, q+n];
od;
cycsB := [op(cycsB), cyc];
od;
rep := pet_cycs2table(cycsB);
edgeperm :=
subs([seq(q=rep[q], q=1..2*n)], edges);
cindB := cindB + flat1[1]*
pet_autom2cycles(edges, edgeperm);
od;
(cindA+cindB)/2;
end;
v_pre_pie :=
proc(n)
option remember;
local cind, gf;
cind := pet_cycleind_knn(n);
gf := pet_varinto_cind(1+z, cind);
subs(z=1, gf);
end;
$endgroup$
add a comment |
$begingroup$
The following data augment those in the first answer, namely we treat
the problem of computing $Z(Q_{n})$ for $K_{n,n}$ where we include reflections. The
algorithm here is slightly different from Harary and Palmer. Clearly
all permutations from the first answer represented in $Z(Q_{n,n})$
contribute as well. Now for the reflections, which are simple,
fortunately. These (the vertex permutations) can be obtained from the
permutations in $S_n$ by placing vertices from component $A$
alternating with component $B$ on a cycle with twice the length of a
cycle contained in a permutation $gamma$ of $S_n.$ The
induced action on the set of edges is the contribution to $Z(Q_n).$ In
the following we have used an algorithmic approach rather than the
formula from Harary and Palmer, namely we construct a canonical
representative of each permutation shape from the cycle index $Z(S_n)$
that doubles the length of every cycle and alternates elements from
the two components. We let that act on the set of edges and factor the
result.
This gives the following cycle indices, the first of which matches the
result given by Harary and Palmer.
For $n=3$,
$$Z(Q_3) =
{frac {{a_{{1}}}^{9}}{72}}+1/6,{a_{{2}}}^{3}{a_{{1}}}^{3}
\+1/9,{a_{{3}}}^{3}
+1/8,{a_{{2}}}^{4}a_{{1}}+1/3,a_{{3}}a_{{6}}+1/4,a_{{1}}{a_{{4}}}^{2}
,$$
for $n=4$,
$$Z(Q_4) =
{frac {{a_{{1}}}^{16}}{1152}}+{frac {{a_{{1}}}^{8}{a_{{2}}}^{4}}{96}}+{
frac {{a_{{3}}}^{4}{a_{{1}}}^{4}}{72}}\
+{frac {17,{a_{{2}}}^{8}}{384}}+{
frac {19,{a_{{4}}}^{4}}{96}}+{frac {5,{a_{{1}}}^{4}{a_{{2}}}^{6}}{96}}+1/
12,{a_{{3}}}^{2}{a_{{1}}}^{2}a_{{2}}a_{{6}}+1/18,{a_{{3}}}^{5}a_{{1}}
\+1/24,
{a_{{2}}}^{2}{a_{{6}}}^{2}+1/12,a_{{4}}a_{{12}}+1/8,{a_{{1}}}^{2}a_{{2}}{a_{
{4}}}^{3}+1/6,a_{{1}}{a_{{6}}}^{2}a_{{3}}+1/8,{a_{{8}}}^{2}
,$$
and for $n=5$,
$$Z(Q_5) =
1/12,{a_{{1}}}^{2}a_{{2}}{a_{{6}}}^{3}a_{{3}}+1/24,{a_{{1}}}^{3}{a_{{2}}}^{3
}{a_{{4}}}^{4}+{frac {{a_{{1}}}^{25}}{28800}}+{frac {13,{a_{{5}}}^{5}}{600}
}+{frac {{a_{{5}}}^{3}a_{{10}}}{60}}\
+1/48,{a_{{2}}}^{4}{a_{{1}}}^{2}a_{{3}}{
a_{{6}}}^{2}+{frac {{a_{{1}}}^{6}{a_{{3}}}^{3}{a_{{2}}}^{2}a_{{6}}}{72}}+1/48
,{a_{{4}}}^{5}{a_{{1}}}^{3}a_{{2}}+1/24,{a_{{4}}}^{2}{a_{{1}}}^{2}a_{{3}}a_{
{12}}\
+1/36,{a_{{2}}}^{2}{a_{{3}}}^{5}a_{{6}}+1/32,{a_{{4}}}^{5}a_{{1}}{a_{{2
}}}^{2}+1/48,{a_{{2}}}^{5}a_{{3}}{a_{{6}}}^{2}+1/24,a_{{2}}a_{{3}}{a_{{4}}}^
{2}a_{{12}}\
+1/8,a_{{1}}{a_{{8}}}^{3}+1/12,a_{{4}}a_{{12}}a_{{6}}a_{{3}}+{
frac {{a_{{1}}}^{15}{a_{{2}}}^{5}}{1440}}+{frac {{a_{{1}}}^{10}{a_{{3}}}^{5}
}{720}}+{frac {{a_{{1}}}^{5}{a_{{2}}}^{10}}{192}}\
+{frac {{a_{{4}}}^{5}{a_{{1
}}}^{5}}{480}}+{frac {{a_{{2}}}^{5}{a_{{3}}}^{5}}{720}}+{frac {{a_{{1}}}^{9}
{a_{{2}}}^{8}}{288}}+{frac {{a_{{2}}}^{11}{a_{{1}}}^{3}}{96}}+{frac {{a_{{2}
}}^{5}{a_{{3}}}^{3}a_{{6}}}{72}}+{frac {{a_{{3}}}^{7}{a_{{1}}}^{4}}{72}}
\ +1/30
,{a_{{5}}}^{2}a_{{15}}+1/20,a_{{5}}a_{{20}}+1/30,a_{{10}}a_{{15}}+{frac {{
a_{{2}}}^{12}a_{{1}}}{128}}+1/8,a_{{5}}{a_{{10}}}^{2}
\+{frac {3,a_{{1}}{a_{{
4}}}^{6}}{32}}+{frac {{a_{{2}}}^{2}{a_{{6}}}^{2}{a_{{3}}}^{3}}{72}}
.$$
These cycle indices can be calculated for large $n$ but the pattern
should be clear. The count of these graphs gives the sequence
$$2, 6, 26, 192, 3014, 127757, 16853750, \ 7343780765, 10733574184956,
52867617324773592,\882178116079222400788, 50227997322550920824045262,
ldots $$
which points us to OEIS A007139 where
we find confirmation of this calculation.
This was the Maple code used to obtain these values.
with(numtheory);
pet_cycleind_symm :=
proc(n)
local p, s;
option remember;
if n=0 then return 1; fi;
expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;
pet_autom2cycles :=
proc(src, aut)
local numa, numsubs;
local marks, pos, cycs, cpos, clen;
numsubs := [seq(src[k]=k, k=1..nops(src))];
numa := subs(numsubs, aut);
marks := Array([seq(true, pos=1..nops(aut))]);
cycs := ; pos := 1;
while pos <= nops(aut) do
if marks[pos] then
clen := 0; cpos := pos;
while marks[cpos] do
marks[cpos] := false;
cpos := numa[cpos];
clen := clen+1;
od;
cycs := [op(cycs), clen];
fi;
pos := pos+1;
od;
return mul(a[cycs[k]], k=1..nops(cycs));
end;
pet_varinto_cind :=
proc(poly, ind)
local subs1, subs2, polyvars, indvars, v, pot, res;
res := ind;
polyvars := indets(poly);
indvars := indets(ind);
for v in indvars do
pot := op(1, v);
subs1 :=
[seq(polyvars[k]=polyvars[k]^pot,
k=1..nops(polyvars))];
subs2 := [v=subs(subs1, poly)];
res := subs(subs2, res);
od;
res;
end;
pet_flatten_term :=
proc(varp)
local terml, d, cf, v;
terml := ;
cf := varp;
for v in indets(varp) do
d := degree(varp, v);
terml := [op(terml), seq(v, k=1..d)];
cf := cf/v^d;
od;
[cf, terml];
end;
pet_flat2rep_cyc :=
proc(f)
local p, q, res, cyc, t, len;
q := 1; res := ;
for t in f do
len := op(1, t);
cyc := [seq(p, p=q+1..q+len-1), q];
res := [op(res), cyc];
q := q+len;
od;
res;
end;
pet_cycs2table :=
proc(cycs)
local pairs, cyc, p, ent;
pairs := ;
for cyc in cycs do
pairs :=
[op(pairs),
seq([cyc[p], cyc[1 + (p mod nops(cyc))]],
p = 1 .. nops(cyc))];
od;
map(ent->ent[2], sort(pairs, (a,b)->a[1] < b[1]));
end;
pet_cycleind_knn :=
proc(n)
option remember;
local cindA, cindB, sind, t1, t2, p, q, cyc1, cyc2,
flat1, flat2, len, len1, len2,
edges, edgeperm, rep, cycsA, cycsB, cycsrc, cyc;
if n=1 then
sind := [a[1]];
else
sind := pet_cycleind_symm(n);
fi;
cindA := 0;
for t1 in sind do
flat1 := pet_flatten_term(t1);
for t2 in sind do
flat2 := pet_flatten_term(t2);
q := 1;
for cyc1 in flat1[2] do
len1 := op(1, cyc1);
for cyc2 in flat2[2] do
len2 := op(1, cyc2);
len := lcm(len1, len2);
q := q * a[len]^(len1*len2/len);
od;
od;
cindA := cindA + flat1[1]*flat2[1]*q;
od;
od;
edges := [seq(seq({p, q+n}, q=1..n), p=1..n)];
cindB := 0;
for t1 in sind do
flat1 := pet_flatten_term(t1);
cycsA := pet_flat2rep_cyc(flat1[2]);
cycsB := ;
for cycsrc in cycsA do
cyc := ;
for q in cycsrc do
cyc := [op(cyc), q, q+n];
od;
cycsB := [op(cycsB), cyc];
od;
rep := pet_cycs2table(cycsB);
edgeperm :=
subs([seq(q=rep[q], q=1..2*n)], edges);
cindB := cindB + flat1[1]*
pet_autom2cycles(edges, edgeperm);
od;
(cindA+cindB)/2;
end;
v_pre_pie :=
proc(n)
option remember;
local cind, gf;
cind := pet_cycleind_knn(n);
gf := pet_varinto_cind(1+z, cind);
subs(z=1, gf);
end;
$endgroup$
add a comment |
$begingroup$
The following data augment those in the first answer, namely we treat
the problem of computing $Z(Q_{n})$ for $K_{n,n}$ where we include reflections. The
algorithm here is slightly different from Harary and Palmer. Clearly
all permutations from the first answer represented in $Z(Q_{n,n})$
contribute as well. Now for the reflections, which are simple,
fortunately. These (the vertex permutations) can be obtained from the
permutations in $S_n$ by placing vertices from component $A$
alternating with component $B$ on a cycle with twice the length of a
cycle contained in a permutation $gamma$ of $S_n.$ The
induced action on the set of edges is the contribution to $Z(Q_n).$ In
the following we have used an algorithmic approach rather than the
formula from Harary and Palmer, namely we construct a canonical
representative of each permutation shape from the cycle index $Z(S_n)$
that doubles the length of every cycle and alternates elements from
the two components. We let that act on the set of edges and factor the
result.
This gives the following cycle indices, the first of which matches the
result given by Harary and Palmer.
For $n=3$,
$$Z(Q_3) =
{frac {{a_{{1}}}^{9}}{72}}+1/6,{a_{{2}}}^{3}{a_{{1}}}^{3}
\+1/9,{a_{{3}}}^{3}
+1/8,{a_{{2}}}^{4}a_{{1}}+1/3,a_{{3}}a_{{6}}+1/4,a_{{1}}{a_{{4}}}^{2}
,$$
for $n=4$,
$$Z(Q_4) =
{frac {{a_{{1}}}^{16}}{1152}}+{frac {{a_{{1}}}^{8}{a_{{2}}}^{4}}{96}}+{
frac {{a_{{3}}}^{4}{a_{{1}}}^{4}}{72}}\
+{frac {17,{a_{{2}}}^{8}}{384}}+{
frac {19,{a_{{4}}}^{4}}{96}}+{frac {5,{a_{{1}}}^{4}{a_{{2}}}^{6}}{96}}+1/
12,{a_{{3}}}^{2}{a_{{1}}}^{2}a_{{2}}a_{{6}}+1/18,{a_{{3}}}^{5}a_{{1}}
\+1/24,
{a_{{2}}}^{2}{a_{{6}}}^{2}+1/12,a_{{4}}a_{{12}}+1/8,{a_{{1}}}^{2}a_{{2}}{a_{
{4}}}^{3}+1/6,a_{{1}}{a_{{6}}}^{2}a_{{3}}+1/8,{a_{{8}}}^{2}
,$$
and for $n=5$,
$$Z(Q_5) =
1/12,{a_{{1}}}^{2}a_{{2}}{a_{{6}}}^{3}a_{{3}}+1/24,{a_{{1}}}^{3}{a_{{2}}}^{3
}{a_{{4}}}^{4}+{frac {{a_{{1}}}^{25}}{28800}}+{frac {13,{a_{{5}}}^{5}}{600}
}+{frac {{a_{{5}}}^{3}a_{{10}}}{60}}\
+1/48,{a_{{2}}}^{4}{a_{{1}}}^{2}a_{{3}}{
a_{{6}}}^{2}+{frac {{a_{{1}}}^{6}{a_{{3}}}^{3}{a_{{2}}}^{2}a_{{6}}}{72}}+1/48
,{a_{{4}}}^{5}{a_{{1}}}^{3}a_{{2}}+1/24,{a_{{4}}}^{2}{a_{{1}}}^{2}a_{{3}}a_{
{12}}\
+1/36,{a_{{2}}}^{2}{a_{{3}}}^{5}a_{{6}}+1/32,{a_{{4}}}^{5}a_{{1}}{a_{{2
}}}^{2}+1/48,{a_{{2}}}^{5}a_{{3}}{a_{{6}}}^{2}+1/24,a_{{2}}a_{{3}}{a_{{4}}}^
{2}a_{{12}}\
+1/8,a_{{1}}{a_{{8}}}^{3}+1/12,a_{{4}}a_{{12}}a_{{6}}a_{{3}}+{
frac {{a_{{1}}}^{15}{a_{{2}}}^{5}}{1440}}+{frac {{a_{{1}}}^{10}{a_{{3}}}^{5}
}{720}}+{frac {{a_{{1}}}^{5}{a_{{2}}}^{10}}{192}}\
+{frac {{a_{{4}}}^{5}{a_{{1
}}}^{5}}{480}}+{frac {{a_{{2}}}^{5}{a_{{3}}}^{5}}{720}}+{frac {{a_{{1}}}^{9}
{a_{{2}}}^{8}}{288}}+{frac {{a_{{2}}}^{11}{a_{{1}}}^{3}}{96}}+{frac {{a_{{2}
}}^{5}{a_{{3}}}^{3}a_{{6}}}{72}}+{frac {{a_{{3}}}^{7}{a_{{1}}}^{4}}{72}}
\ +1/30
,{a_{{5}}}^{2}a_{{15}}+1/20,a_{{5}}a_{{20}}+1/30,a_{{10}}a_{{15}}+{frac {{
a_{{2}}}^{12}a_{{1}}}{128}}+1/8,a_{{5}}{a_{{10}}}^{2}
\+{frac {3,a_{{1}}{a_{{
4}}}^{6}}{32}}+{frac {{a_{{2}}}^{2}{a_{{6}}}^{2}{a_{{3}}}^{3}}{72}}
.$$
These cycle indices can be calculated for large $n$ but the pattern
should be clear. The count of these graphs gives the sequence
$$2, 6, 26, 192, 3014, 127757, 16853750, \ 7343780765, 10733574184956,
52867617324773592,\882178116079222400788, 50227997322550920824045262,
ldots $$
which points us to OEIS A007139 where
we find confirmation of this calculation.
This was the Maple code used to obtain these values.
with(numtheory);
pet_cycleind_symm :=
proc(n)
local p, s;
option remember;
if n=0 then return 1; fi;
expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;
pet_autom2cycles :=
proc(src, aut)
local numa, numsubs;
local marks, pos, cycs, cpos, clen;
numsubs := [seq(src[k]=k, k=1..nops(src))];
numa := subs(numsubs, aut);
marks := Array([seq(true, pos=1..nops(aut))]);
cycs := ; pos := 1;
while pos <= nops(aut) do
if marks[pos] then
clen := 0; cpos := pos;
while marks[cpos] do
marks[cpos] := false;
cpos := numa[cpos];
clen := clen+1;
od;
cycs := [op(cycs), clen];
fi;
pos := pos+1;
od;
return mul(a[cycs[k]], k=1..nops(cycs));
end;
pet_varinto_cind :=
proc(poly, ind)
local subs1, subs2, polyvars, indvars, v, pot, res;
res := ind;
polyvars := indets(poly);
indvars := indets(ind);
for v in indvars do
pot := op(1, v);
subs1 :=
[seq(polyvars[k]=polyvars[k]^pot,
k=1..nops(polyvars))];
subs2 := [v=subs(subs1, poly)];
res := subs(subs2, res);
od;
res;
end;
pet_flatten_term :=
proc(varp)
local terml, d, cf, v;
terml := ;
cf := varp;
for v in indets(varp) do
d := degree(varp, v);
terml := [op(terml), seq(v, k=1..d)];
cf := cf/v^d;
od;
[cf, terml];
end;
pet_flat2rep_cyc :=
proc(f)
local p, q, res, cyc, t, len;
q := 1; res := ;
for t in f do
len := op(1, t);
cyc := [seq(p, p=q+1..q+len-1), q];
res := [op(res), cyc];
q := q+len;
od;
res;
end;
pet_cycs2table :=
proc(cycs)
local pairs, cyc, p, ent;
pairs := ;
for cyc in cycs do
pairs :=
[op(pairs),
seq([cyc[p], cyc[1 + (p mod nops(cyc))]],
p = 1 .. nops(cyc))];
od;
map(ent->ent[2], sort(pairs, (a,b)->a[1] < b[1]));
end;
pet_cycleind_knn :=
proc(n)
option remember;
local cindA, cindB, sind, t1, t2, p, q, cyc1, cyc2,
flat1, flat2, len, len1, len2,
edges, edgeperm, rep, cycsA, cycsB, cycsrc, cyc;
if n=1 then
sind := [a[1]];
else
sind := pet_cycleind_symm(n);
fi;
cindA := 0;
for t1 in sind do
flat1 := pet_flatten_term(t1);
for t2 in sind do
flat2 := pet_flatten_term(t2);
q := 1;
for cyc1 in flat1[2] do
len1 := op(1, cyc1);
for cyc2 in flat2[2] do
len2 := op(1, cyc2);
len := lcm(len1, len2);
q := q * a[len]^(len1*len2/len);
od;
od;
cindA := cindA + flat1[1]*flat2[1]*q;
od;
od;
edges := [seq(seq({p, q+n}, q=1..n), p=1..n)];
cindB := 0;
for t1 in sind do
flat1 := pet_flatten_term(t1);
cycsA := pet_flat2rep_cyc(flat1[2]);
cycsB := ;
for cycsrc in cycsA do
cyc := ;
for q in cycsrc do
cyc := [op(cyc), q, q+n];
od;
cycsB := [op(cycsB), cyc];
od;
rep := pet_cycs2table(cycsB);
edgeperm :=
subs([seq(q=rep[q], q=1..2*n)], edges);
cindB := cindB + flat1[1]*
pet_autom2cycles(edges, edgeperm);
od;
(cindA+cindB)/2;
end;
v_pre_pie :=
proc(n)
option remember;
local cind, gf;
cind := pet_cycleind_knn(n);
gf := pet_varinto_cind(1+z, cind);
subs(z=1, gf);
end;
$endgroup$
The following data augment those in the first answer, namely we treat
the problem of computing $Z(Q_{n})$ for $K_{n,n}$ where we include reflections. The
algorithm here is slightly different from Harary and Palmer. Clearly
all permutations from the first answer represented in $Z(Q_{n,n})$
contribute as well. Now for the reflections, which are simple,
fortunately. These (the vertex permutations) can be obtained from the
permutations in $S_n$ by placing vertices from component $A$
alternating with component $B$ on a cycle with twice the length of a
cycle contained in a permutation $gamma$ of $S_n.$ The
induced action on the set of edges is the contribution to $Z(Q_n).$ In
the following we have used an algorithmic approach rather than the
formula from Harary and Palmer, namely we construct a canonical
representative of each permutation shape from the cycle index $Z(S_n)$
that doubles the length of every cycle and alternates elements from
the two components. We let that act on the set of edges and factor the
result.
This gives the following cycle indices, the first of which matches the
result given by Harary and Palmer.
For $n=3$,
$$Z(Q_3) =
{frac {{a_{{1}}}^{9}}{72}}+1/6,{a_{{2}}}^{3}{a_{{1}}}^{3}
\+1/9,{a_{{3}}}^{3}
+1/8,{a_{{2}}}^{4}a_{{1}}+1/3,a_{{3}}a_{{6}}+1/4,a_{{1}}{a_{{4}}}^{2}
,$$
for $n=4$,
$$Z(Q_4) =
{frac {{a_{{1}}}^{16}}{1152}}+{frac {{a_{{1}}}^{8}{a_{{2}}}^{4}}{96}}+{
frac {{a_{{3}}}^{4}{a_{{1}}}^{4}}{72}}\
+{frac {17,{a_{{2}}}^{8}}{384}}+{
frac {19,{a_{{4}}}^{4}}{96}}+{frac {5,{a_{{1}}}^{4}{a_{{2}}}^{6}}{96}}+1/
12,{a_{{3}}}^{2}{a_{{1}}}^{2}a_{{2}}a_{{6}}+1/18,{a_{{3}}}^{5}a_{{1}}
\+1/24,
{a_{{2}}}^{2}{a_{{6}}}^{2}+1/12,a_{{4}}a_{{12}}+1/8,{a_{{1}}}^{2}a_{{2}}{a_{
{4}}}^{3}+1/6,a_{{1}}{a_{{6}}}^{2}a_{{3}}+1/8,{a_{{8}}}^{2}
,$$
and for $n=5$,
$$Z(Q_5) =
1/12,{a_{{1}}}^{2}a_{{2}}{a_{{6}}}^{3}a_{{3}}+1/24,{a_{{1}}}^{3}{a_{{2}}}^{3
}{a_{{4}}}^{4}+{frac {{a_{{1}}}^{25}}{28800}}+{frac {13,{a_{{5}}}^{5}}{600}
}+{frac {{a_{{5}}}^{3}a_{{10}}}{60}}\
+1/48,{a_{{2}}}^{4}{a_{{1}}}^{2}a_{{3}}{
a_{{6}}}^{2}+{frac {{a_{{1}}}^{6}{a_{{3}}}^{3}{a_{{2}}}^{2}a_{{6}}}{72}}+1/48
,{a_{{4}}}^{5}{a_{{1}}}^{3}a_{{2}}+1/24,{a_{{4}}}^{2}{a_{{1}}}^{2}a_{{3}}a_{
{12}}\
+1/36,{a_{{2}}}^{2}{a_{{3}}}^{5}a_{{6}}+1/32,{a_{{4}}}^{5}a_{{1}}{a_{{2
}}}^{2}+1/48,{a_{{2}}}^{5}a_{{3}}{a_{{6}}}^{2}+1/24,a_{{2}}a_{{3}}{a_{{4}}}^
{2}a_{{12}}\
+1/8,a_{{1}}{a_{{8}}}^{3}+1/12,a_{{4}}a_{{12}}a_{{6}}a_{{3}}+{
frac {{a_{{1}}}^{15}{a_{{2}}}^{5}}{1440}}+{frac {{a_{{1}}}^{10}{a_{{3}}}^{5}
}{720}}+{frac {{a_{{1}}}^{5}{a_{{2}}}^{10}}{192}}\
+{frac {{a_{{4}}}^{5}{a_{{1
}}}^{5}}{480}}+{frac {{a_{{2}}}^{5}{a_{{3}}}^{5}}{720}}+{frac {{a_{{1}}}^{9}
{a_{{2}}}^{8}}{288}}+{frac {{a_{{2}}}^{11}{a_{{1}}}^{3}}{96}}+{frac {{a_{{2}
}}^{5}{a_{{3}}}^{3}a_{{6}}}{72}}+{frac {{a_{{3}}}^{7}{a_{{1}}}^{4}}{72}}
\ +1/30
,{a_{{5}}}^{2}a_{{15}}+1/20,a_{{5}}a_{{20}}+1/30,a_{{10}}a_{{15}}+{frac {{
a_{{2}}}^{12}a_{{1}}}{128}}+1/8,a_{{5}}{a_{{10}}}^{2}
\+{frac {3,a_{{1}}{a_{{
4}}}^{6}}{32}}+{frac {{a_{{2}}}^{2}{a_{{6}}}^{2}{a_{{3}}}^{3}}{72}}
.$$
These cycle indices can be calculated for large $n$ but the pattern
should be clear. The count of these graphs gives the sequence
$$2, 6, 26, 192, 3014, 127757, 16853750, \ 7343780765, 10733574184956,
52867617324773592,\882178116079222400788, 50227997322550920824045262,
ldots $$
which points us to OEIS A007139 where
we find confirmation of this calculation.
This was the Maple code used to obtain these values.
with(numtheory);
pet_cycleind_symm :=
proc(n)
local p, s;
option remember;
if n=0 then return 1; fi;
expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;
pet_autom2cycles :=
proc(src, aut)
local numa, numsubs;
local marks, pos, cycs, cpos, clen;
numsubs := [seq(src[k]=k, k=1..nops(src))];
numa := subs(numsubs, aut);
marks := Array([seq(true, pos=1..nops(aut))]);
cycs := ; pos := 1;
while pos <= nops(aut) do
if marks[pos] then
clen := 0; cpos := pos;
while marks[cpos] do
marks[cpos] := false;
cpos := numa[cpos];
clen := clen+1;
od;
cycs := [op(cycs), clen];
fi;
pos := pos+1;
od;
return mul(a[cycs[k]], k=1..nops(cycs));
end;
pet_varinto_cind :=
proc(poly, ind)
local subs1, subs2, polyvars, indvars, v, pot, res;
res := ind;
polyvars := indets(poly);
indvars := indets(ind);
for v in indvars do
pot := op(1, v);
subs1 :=
[seq(polyvars[k]=polyvars[k]^pot,
k=1..nops(polyvars))];
subs2 := [v=subs(subs1, poly)];
res := subs(subs2, res);
od;
res;
end;
pet_flatten_term :=
proc(varp)
local terml, d, cf, v;
terml := ;
cf := varp;
for v in indets(varp) do
d := degree(varp, v);
terml := [op(terml), seq(v, k=1..d)];
cf := cf/v^d;
od;
[cf, terml];
end;
pet_flat2rep_cyc :=
proc(f)
local p, q, res, cyc, t, len;
q := 1; res := ;
for t in f do
len := op(1, t);
cyc := [seq(p, p=q+1..q+len-1), q];
res := [op(res), cyc];
q := q+len;
od;
res;
end;
pet_cycs2table :=
proc(cycs)
local pairs, cyc, p, ent;
pairs := ;
for cyc in cycs do
pairs :=
[op(pairs),
seq([cyc[p], cyc[1 + (p mod nops(cyc))]],
p = 1 .. nops(cyc))];
od;
map(ent->ent[2], sort(pairs, (a,b)->a[1] < b[1]));
end;
pet_cycleind_knn :=
proc(n)
option remember;
local cindA, cindB, sind, t1, t2, p, q, cyc1, cyc2,
flat1, flat2, len, len1, len2,
edges, edgeperm, rep, cycsA, cycsB, cycsrc, cyc;
if n=1 then
sind := [a[1]];
else
sind := pet_cycleind_symm(n);
fi;
cindA := 0;
for t1 in sind do
flat1 := pet_flatten_term(t1);
for t2 in sind do
flat2 := pet_flatten_term(t2);
q := 1;
for cyc1 in flat1[2] do
len1 := op(1, cyc1);
for cyc2 in flat2[2] do
len2 := op(1, cyc2);
len := lcm(len1, len2);
q := q * a[len]^(len1*len2/len);
od;
od;
cindA := cindA + flat1[1]*flat2[1]*q;
od;
od;
edges := [seq(seq({p, q+n}, q=1..n), p=1..n)];
cindB := 0;
for t1 in sind do
flat1 := pet_flatten_term(t1);
cycsA := pet_flat2rep_cyc(flat1[2]);
cycsB := ;
for cycsrc in cycsA do
cyc := ;
for q in cycsrc do
cyc := [op(cyc), q, q+n];
od;
cycsB := [op(cycsB), cyc];
od;
rep := pet_cycs2table(cycsB);
edgeperm :=
subs([seq(q=rep[q], q=1..2*n)], edges);
cindB := cindB + flat1[1]*
pet_autom2cycles(edges, edgeperm);
od;
(cindA+cindB)/2;
end;
v_pre_pie :=
proc(n)
option remember;
local cind, gf;
cind := pet_cycleind_knn(n);
gf := pet_varinto_cind(1+z, cind);
subs(z=1, gf);
end;
edited Feb 26 '15 at 1:54
answered Feb 26 '15 at 1:10
Marko RiedelMarko Riedel
41.1k340111
41.1k340111
add a comment |
add a comment |
$begingroup$
The question is equivalent to finding all non-isomorphic bipartite graphs with bi-partitions of sizes $n$ and $m$ respectively and is hard to solve in general. In particular there is no simple characterization of such graphs.
If you need the sequence for the number of such graphs then you can take a look at this oeis entry http://oeis.org/A033995.
If you need to compute such graphs (up to a reasonable number) then your best choice is the tool genbg which you can find in McKay's nauty package. In some sense genbg is currently the most efficient way to construct such graphs and hence answers your question.
$endgroup$
$begingroup$
Yeah I need to find all those non-isomorphic bipartite graphs with sizes $m$ and $n$ in each partition. The sequence above is for the number of bipartite graphs of $n$ vertices. But that number is greater than the number of graphs that I am trying to find. For example if I have four vertices, there are $7$ bipartite graphs but if I'm only taking all the spanning subgraphs of $K_{(2,2)}$ then there are just $6$ of them. The other bipartite graph is a claw which is bipartite with sizes 1 and 3 in each partition.
$endgroup$
– chowching
Feb 17 '15 at 12:43
$begingroup$
@chowching You should be more specific about what you're looking for. Note that in general there is no closed formula for the number of bipartite graphs with bipartitions of cardinality n and m.
$endgroup$
– Jernej
Feb 17 '15 at 13:00
$begingroup$
Thanks for the reply. I'm studying Polya Enumeration Theorem now to see if I can apply it to find how many such graphs are there given a certain $n$ and $m$.
$endgroup$
– chowching
Feb 17 '15 at 13:00
$begingroup$
@chowching You can but the formula will most likely require using computer computations.
$endgroup$
– Jernej
Feb 17 '15 at 13:01
$begingroup$
@chowching I suggest that for a start you look at Harary's and Palmer's book called "graphical enumeration"
$endgroup$
– Jernej
Feb 17 '15 at 13:02
|
show 1 more comment
$begingroup$
The question is equivalent to finding all non-isomorphic bipartite graphs with bi-partitions of sizes $n$ and $m$ respectively and is hard to solve in general. In particular there is no simple characterization of such graphs.
If you need the sequence for the number of such graphs then you can take a look at this oeis entry http://oeis.org/A033995.
If you need to compute such graphs (up to a reasonable number) then your best choice is the tool genbg which you can find in McKay's nauty package. In some sense genbg is currently the most efficient way to construct such graphs and hence answers your question.
$endgroup$
$begingroup$
Yeah I need to find all those non-isomorphic bipartite graphs with sizes $m$ and $n$ in each partition. The sequence above is for the number of bipartite graphs of $n$ vertices. But that number is greater than the number of graphs that I am trying to find. For example if I have four vertices, there are $7$ bipartite graphs but if I'm only taking all the spanning subgraphs of $K_{(2,2)}$ then there are just $6$ of them. The other bipartite graph is a claw which is bipartite with sizes 1 and 3 in each partition.
$endgroup$
– chowching
Feb 17 '15 at 12:43
$begingroup$
@chowching You should be more specific about what you're looking for. Note that in general there is no closed formula for the number of bipartite graphs with bipartitions of cardinality n and m.
$endgroup$
– Jernej
Feb 17 '15 at 13:00
$begingroup$
Thanks for the reply. I'm studying Polya Enumeration Theorem now to see if I can apply it to find how many such graphs are there given a certain $n$ and $m$.
$endgroup$
– chowching
Feb 17 '15 at 13:00
$begingroup$
@chowching You can but the formula will most likely require using computer computations.
$endgroup$
– Jernej
Feb 17 '15 at 13:01
$begingroup$
@chowching I suggest that for a start you look at Harary's and Palmer's book called "graphical enumeration"
$endgroup$
– Jernej
Feb 17 '15 at 13:02
|
show 1 more comment
$begingroup$
The question is equivalent to finding all non-isomorphic bipartite graphs with bi-partitions of sizes $n$ and $m$ respectively and is hard to solve in general. In particular there is no simple characterization of such graphs.
If you need the sequence for the number of such graphs then you can take a look at this oeis entry http://oeis.org/A033995.
If you need to compute such graphs (up to a reasonable number) then your best choice is the tool genbg which you can find in McKay's nauty package. In some sense genbg is currently the most efficient way to construct such graphs and hence answers your question.
$endgroup$
The question is equivalent to finding all non-isomorphic bipartite graphs with bi-partitions of sizes $n$ and $m$ respectively and is hard to solve in general. In particular there is no simple characterization of such graphs.
If you need the sequence for the number of such graphs then you can take a look at this oeis entry http://oeis.org/A033995.
If you need to compute such graphs (up to a reasonable number) then your best choice is the tool genbg which you can find in McKay's nauty package. In some sense genbg is currently the most efficient way to construct such graphs and hence answers your question.
answered Feb 17 '15 at 7:58
JernejJernej
2,8312041
2,8312041
$begingroup$
Yeah I need to find all those non-isomorphic bipartite graphs with sizes $m$ and $n$ in each partition. The sequence above is for the number of bipartite graphs of $n$ vertices. But that number is greater than the number of graphs that I am trying to find. For example if I have four vertices, there are $7$ bipartite graphs but if I'm only taking all the spanning subgraphs of $K_{(2,2)}$ then there are just $6$ of them. The other bipartite graph is a claw which is bipartite with sizes 1 and 3 in each partition.
$endgroup$
– chowching
Feb 17 '15 at 12:43
$begingroup$
@chowching You should be more specific about what you're looking for. Note that in general there is no closed formula for the number of bipartite graphs with bipartitions of cardinality n and m.
$endgroup$
– Jernej
Feb 17 '15 at 13:00
$begingroup$
Thanks for the reply. I'm studying Polya Enumeration Theorem now to see if I can apply it to find how many such graphs are there given a certain $n$ and $m$.
$endgroup$
– chowching
Feb 17 '15 at 13:00
$begingroup$
@chowching You can but the formula will most likely require using computer computations.
$endgroup$
– Jernej
Feb 17 '15 at 13:01
$begingroup$
@chowching I suggest that for a start you look at Harary's and Palmer's book called "graphical enumeration"
$endgroup$
– Jernej
Feb 17 '15 at 13:02
|
show 1 more comment
$begingroup$
Yeah I need to find all those non-isomorphic bipartite graphs with sizes $m$ and $n$ in each partition. The sequence above is for the number of bipartite graphs of $n$ vertices. But that number is greater than the number of graphs that I am trying to find. For example if I have four vertices, there are $7$ bipartite graphs but if I'm only taking all the spanning subgraphs of $K_{(2,2)}$ then there are just $6$ of them. The other bipartite graph is a claw which is bipartite with sizes 1 and 3 in each partition.
$endgroup$
– chowching
Feb 17 '15 at 12:43
$begingroup$
@chowching You should be more specific about what you're looking for. Note that in general there is no closed formula for the number of bipartite graphs with bipartitions of cardinality n and m.
$endgroup$
– Jernej
Feb 17 '15 at 13:00
$begingroup$
Thanks for the reply. I'm studying Polya Enumeration Theorem now to see if I can apply it to find how many such graphs are there given a certain $n$ and $m$.
$endgroup$
– chowching
Feb 17 '15 at 13:00
$begingroup$
@chowching You can but the formula will most likely require using computer computations.
$endgroup$
– Jernej
Feb 17 '15 at 13:01
$begingroup$
@chowching I suggest that for a start you look at Harary's and Palmer's book called "graphical enumeration"
$endgroup$
– Jernej
Feb 17 '15 at 13:02
$begingroup$
Yeah I need to find all those non-isomorphic bipartite graphs with sizes $m$ and $n$ in each partition. The sequence above is for the number of bipartite graphs of $n$ vertices. But that number is greater than the number of graphs that I am trying to find. For example if I have four vertices, there are $7$ bipartite graphs but if I'm only taking all the spanning subgraphs of $K_{(2,2)}$ then there are just $6$ of them. The other bipartite graph is a claw which is bipartite with sizes 1 and 3 in each partition.
$endgroup$
– chowching
Feb 17 '15 at 12:43
$begingroup$
Yeah I need to find all those non-isomorphic bipartite graphs with sizes $m$ and $n$ in each partition. The sequence above is for the number of bipartite graphs of $n$ vertices. But that number is greater than the number of graphs that I am trying to find. For example if I have four vertices, there are $7$ bipartite graphs but if I'm only taking all the spanning subgraphs of $K_{(2,2)}$ then there are just $6$ of them. The other bipartite graph is a claw which is bipartite with sizes 1 and 3 in each partition.
$endgroup$
– chowching
Feb 17 '15 at 12:43
$begingroup$
@chowching You should be more specific about what you're looking for. Note that in general there is no closed formula for the number of bipartite graphs with bipartitions of cardinality n and m.
$endgroup$
– Jernej
Feb 17 '15 at 13:00
$begingroup$
@chowching You should be more specific about what you're looking for. Note that in general there is no closed formula for the number of bipartite graphs with bipartitions of cardinality n and m.
$endgroup$
– Jernej
Feb 17 '15 at 13:00
$begingroup$
Thanks for the reply. I'm studying Polya Enumeration Theorem now to see if I can apply it to find how many such graphs are there given a certain $n$ and $m$.
$endgroup$
– chowching
Feb 17 '15 at 13:00
$begingroup$
Thanks for the reply. I'm studying Polya Enumeration Theorem now to see if I can apply it to find how many such graphs are there given a certain $n$ and $m$.
$endgroup$
– chowching
Feb 17 '15 at 13:00
$begingroup$
@chowching You can but the formula will most likely require using computer computations.
$endgroup$
– Jernej
Feb 17 '15 at 13:01
$begingroup$
@chowching You can but the formula will most likely require using computer computations.
$endgroup$
– Jernej
Feb 17 '15 at 13:01
$begingroup$
@chowching I suggest that for a start you look at Harary's and Palmer's book called "graphical enumeration"
$endgroup$
– Jernej
Feb 17 '15 at 13:02
$begingroup$
@chowching I suggest that for a start you look at Harary's and Palmer's book called "graphical enumeration"
$endgroup$
– Jernej
Feb 17 '15 at 13:02
|
show 1 more comment
$begingroup$
Adding another answer after receiving a pointer from a reader of this
thread. We treat the case of spanning subgraphs of $K_{n,n}$ including
reflections. The algorithm has been greatly simplified. There are two
types of symmetries, namely shuffles within the two sets of vertices
and reflections that map one to the other. The first type has been
simplified as follows: we continue to iterate over pairs of
permutation shapes from $S_n$ but the contribution to the cycle index
$Z(Q_n)$ is now computed by iterating over pairs of cycle types (same
length) rather than single cycles. The second type (reflections) has
been replaced in its entirety. We continue to produce contributions
by building factorized permutations consisting of cycles that
alternate between the two classes of vertices (a precondition of this
problem) but whereas in the first version we would construct a
representative of the factored permutation, apply it to the edges, and
factor the result into cycles, the new version does not construct
representatives and does no factorization and builds the terms for the
cycle index from first principles, namely that we enumerate the cycles
of edges (two-sets of vertices) that are obtained from a vertex
permutation by choosing pairs of vertices, counting these, and
computing the lengths of the cycles on which they reside. These
optimizations make for a faster and much more compact program. This
was the code:
pet_cycleind_symm :=
proc(n)
option remember;
if n=0 then return 1; fi;
expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;
pet_varinto_cind :=
proc(poly, ind)
local subs1, subs2, polyvars, indvars, v, pot, res;
res := ind;
polyvars := indets(poly);
indvars := indets(ind);
for v in indvars do
pot := op(1, v);
subs1 :=
[seq(polyvars[k]=polyvars[k]^pot,
k=1..nops(polyvars))];
subs2 := [v=subs(subs1, poly)];
res := subs(subs2, res);
od;
res;
end;
pet_flatten_termA :=
proc(varp)
local terml, d, cf, v;
terml := ;
cf := varp;
for v in indets(varp) do
d := degree(varp, v);
terml := [op(terml), [op(1,v), d]];
cf := cf/v^d;
od;
[cf, terml];
end;
pet_cycleind_knn :=
proc(n)
option remember;
local cindA, cindB, sind, t1, t2, term, res,
flat, flat1, flat2, len, l1, l2, cycs, uidx, vidx,
u, v, inst1;
if n=1 then
sind := [a[1]];
else
sind := pet_cycleind_symm(n);
fi;
cindA := 0;
for t1 in sind do
flat1 := pet_flatten_termA(t1);
for t2 in sind do
flat2 := pet_flatten_termA(t2);
res := 1;
for u in flat1[2] do
l1 := op(1, u);
for v in flat2[2] do
l2 := op(1, v);
len := lcm(l1, l2);
res := res *
a[len]^(op(2, u)*op(2, v)
*l1*l2/len);
od;
od;
cindA := cindA + flat1[1]*flat2[1]*res;
od;
od;
cindB := 0;
for term in sind do
flat := pet_flatten_termA(term);
cycs := map(cyc -> [2*cyc[1], cyc[2]], flat[2]);
res := 1;
# edges on different cycles of different sizes
for uidx to nops(cycs) do
u := cycs[uidx];
for vidx from uidx+1 to nops(cycs) do
v := cycs[vidx];
l1 := op(1, u); l2 := op(1, v);
res := res *
a[lcm(l1, l2)]^((l1*l2/2/lcm(l1, l2))*
op(2, u)*op(2, v));
od;
od;
# edges on different cycles of the same size
for uidx to nops(cycs) do
u := cycs[uidx];
l1 := op(1, u); inst1 := op(2, u);
# a[l1]^(1/2*inst1*(inst1-1)*l1*l1/2/l1)
res := res *
a[l1]^(1/2*inst1*(inst1-1)*l1/2);
od;
# edges on identical cycles of some size
for uidx to nops(cycs) do
u := cycs[uidx];
l1 := op(1, u); inst1 := op(2, u);
if type(l1/2, even) then
# a[l1]^((l1/2)^2/l1);
res := res *
(a[l1]^(l1/4))^inst1;
else
# a[l1/2]^(l1/2/(l1/2))*a[l1]^(((l1/2)^2-l1/2)/l1)
res := res *
(a[l1/2]*a[l1]^(l1/4-1/2))^inst1;
fi;
od;
cindB := cindB + flat[1]*res;
od;
(cindA+cindB)/2;
end;
v_pre_pie :=
proc(n)
option remember;
local cind, gf;
cind := pet_cycleind_knn(n);
gf := pet_varinto_cind(1+z, cind);
subs(z=1, gf);
end;
This will produce the following data for the non-isomorphic spanning
subgraphs of $K_{6,6}$ including reflections classified according to
the number of edges:
$${z}^{36}+{z}^{35}+2,{z}^{34}+4,{z}^{33}+10,{z}^{32}
+20,{z}^{31}+50,{z}^{30}+99,{z}^{29}+227,{z}^{28}
\ +458,{z}^{27}+934,{z}^{26}+
1711,{z}^{25}+3057,{z}^{24}+4889,{z}^{23}+7400,{z}^{22}
\ +10071,{z}^{21}+12755,{z}^{20}+14524,{z}^{19}
+15331,{z}^{18}+14524,{z}^{17}+12755,{z}^{16}
\+10071,{z}^{15}+7400,{z}^{14}+4889,{z}^{13}+
3057,{z}^{12}+1711,{z}^{11}+934,{z}^{10}
\ +458,{z}^{9}+227,{z}^{8}+99,{z}^{7}+50,{z}^{6}+20,{z}^{5}
+10,{z}^{4}+4,{z}^{3}+2,{z}^{2}+z+1.$$
i.e. the value four for three edges counts, first, a set of three
edges, not connected, second, two edges sharing a vertex and a single
edge, third, three edges emanating from the same vertex and fourth, a
path of three edges.
Addendum. We may use Burnside as shown below if we are not
interested in classifying according to the number of edges and require
only the total count. This gives:
Q :=
proc(n)
option remember;
local cind;
cind := pet_cycleind_knn(n);
subs([seq(a[p]=2, p=1..n*n)], cind);
end;
The routine that substitutes polynomials into cycle indices is no
longer needed in this case. Observe that further simplification at the
expense of readability is possible by not computing the cycle index at
all and setting all $a[p]$ to two during the computation of what used
to be the cycle index.
$endgroup$
add a comment |
$begingroup$
Adding another answer after receiving a pointer from a reader of this
thread. We treat the case of spanning subgraphs of $K_{n,n}$ including
reflections. The algorithm has been greatly simplified. There are two
types of symmetries, namely shuffles within the two sets of vertices
and reflections that map one to the other. The first type has been
simplified as follows: we continue to iterate over pairs of
permutation shapes from $S_n$ but the contribution to the cycle index
$Z(Q_n)$ is now computed by iterating over pairs of cycle types (same
length) rather than single cycles. The second type (reflections) has
been replaced in its entirety. We continue to produce contributions
by building factorized permutations consisting of cycles that
alternate between the two classes of vertices (a precondition of this
problem) but whereas in the first version we would construct a
representative of the factored permutation, apply it to the edges, and
factor the result into cycles, the new version does not construct
representatives and does no factorization and builds the terms for the
cycle index from first principles, namely that we enumerate the cycles
of edges (two-sets of vertices) that are obtained from a vertex
permutation by choosing pairs of vertices, counting these, and
computing the lengths of the cycles on which they reside. These
optimizations make for a faster and much more compact program. This
was the code:
pet_cycleind_symm :=
proc(n)
option remember;
if n=0 then return 1; fi;
expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;
pet_varinto_cind :=
proc(poly, ind)
local subs1, subs2, polyvars, indvars, v, pot, res;
res := ind;
polyvars := indets(poly);
indvars := indets(ind);
for v in indvars do
pot := op(1, v);
subs1 :=
[seq(polyvars[k]=polyvars[k]^pot,
k=1..nops(polyvars))];
subs2 := [v=subs(subs1, poly)];
res := subs(subs2, res);
od;
res;
end;
pet_flatten_termA :=
proc(varp)
local terml, d, cf, v;
terml := ;
cf := varp;
for v in indets(varp) do
d := degree(varp, v);
terml := [op(terml), [op(1,v), d]];
cf := cf/v^d;
od;
[cf, terml];
end;
pet_cycleind_knn :=
proc(n)
option remember;
local cindA, cindB, sind, t1, t2, term, res,
flat, flat1, flat2, len, l1, l2, cycs, uidx, vidx,
u, v, inst1;
if n=1 then
sind := [a[1]];
else
sind := pet_cycleind_symm(n);
fi;
cindA := 0;
for t1 in sind do
flat1 := pet_flatten_termA(t1);
for t2 in sind do
flat2 := pet_flatten_termA(t2);
res := 1;
for u in flat1[2] do
l1 := op(1, u);
for v in flat2[2] do
l2 := op(1, v);
len := lcm(l1, l2);
res := res *
a[len]^(op(2, u)*op(2, v)
*l1*l2/len);
od;
od;
cindA := cindA + flat1[1]*flat2[1]*res;
od;
od;
cindB := 0;
for term in sind do
flat := pet_flatten_termA(term);
cycs := map(cyc -> [2*cyc[1], cyc[2]], flat[2]);
res := 1;
# edges on different cycles of different sizes
for uidx to nops(cycs) do
u := cycs[uidx];
for vidx from uidx+1 to nops(cycs) do
v := cycs[vidx];
l1 := op(1, u); l2 := op(1, v);
res := res *
a[lcm(l1, l2)]^((l1*l2/2/lcm(l1, l2))*
op(2, u)*op(2, v));
od;
od;
# edges on different cycles of the same size
for uidx to nops(cycs) do
u := cycs[uidx];
l1 := op(1, u); inst1 := op(2, u);
# a[l1]^(1/2*inst1*(inst1-1)*l1*l1/2/l1)
res := res *
a[l1]^(1/2*inst1*(inst1-1)*l1/2);
od;
# edges on identical cycles of some size
for uidx to nops(cycs) do
u := cycs[uidx];
l1 := op(1, u); inst1 := op(2, u);
if type(l1/2, even) then
# a[l1]^((l1/2)^2/l1);
res := res *
(a[l1]^(l1/4))^inst1;
else
# a[l1/2]^(l1/2/(l1/2))*a[l1]^(((l1/2)^2-l1/2)/l1)
res := res *
(a[l1/2]*a[l1]^(l1/4-1/2))^inst1;
fi;
od;
cindB := cindB + flat[1]*res;
od;
(cindA+cindB)/2;
end;
v_pre_pie :=
proc(n)
option remember;
local cind, gf;
cind := pet_cycleind_knn(n);
gf := pet_varinto_cind(1+z, cind);
subs(z=1, gf);
end;
This will produce the following data for the non-isomorphic spanning
subgraphs of $K_{6,6}$ including reflections classified according to
the number of edges:
$${z}^{36}+{z}^{35}+2,{z}^{34}+4,{z}^{33}+10,{z}^{32}
+20,{z}^{31}+50,{z}^{30}+99,{z}^{29}+227,{z}^{28}
\ +458,{z}^{27}+934,{z}^{26}+
1711,{z}^{25}+3057,{z}^{24}+4889,{z}^{23}+7400,{z}^{22}
\ +10071,{z}^{21}+12755,{z}^{20}+14524,{z}^{19}
+15331,{z}^{18}+14524,{z}^{17}+12755,{z}^{16}
\+10071,{z}^{15}+7400,{z}^{14}+4889,{z}^{13}+
3057,{z}^{12}+1711,{z}^{11}+934,{z}^{10}
\ +458,{z}^{9}+227,{z}^{8}+99,{z}^{7}+50,{z}^{6}+20,{z}^{5}
+10,{z}^{4}+4,{z}^{3}+2,{z}^{2}+z+1.$$
i.e. the value four for three edges counts, first, a set of three
edges, not connected, second, two edges sharing a vertex and a single
edge, third, three edges emanating from the same vertex and fourth, a
path of three edges.
Addendum. We may use Burnside as shown below if we are not
interested in classifying according to the number of edges and require
only the total count. This gives:
Q :=
proc(n)
option remember;
local cind;
cind := pet_cycleind_knn(n);
subs([seq(a[p]=2, p=1..n*n)], cind);
end;
The routine that substitutes polynomials into cycle indices is no
longer needed in this case. Observe that further simplification at the
expense of readability is possible by not computing the cycle index at
all and setting all $a[p]$ to two during the computation of what used
to be the cycle index.
$endgroup$
add a comment |
$begingroup$
Adding another answer after receiving a pointer from a reader of this
thread. We treat the case of spanning subgraphs of $K_{n,n}$ including
reflections. The algorithm has been greatly simplified. There are two
types of symmetries, namely shuffles within the two sets of vertices
and reflections that map one to the other. The first type has been
simplified as follows: we continue to iterate over pairs of
permutation shapes from $S_n$ but the contribution to the cycle index
$Z(Q_n)$ is now computed by iterating over pairs of cycle types (same
length) rather than single cycles. The second type (reflections) has
been replaced in its entirety. We continue to produce contributions
by building factorized permutations consisting of cycles that
alternate between the two classes of vertices (a precondition of this
problem) but whereas in the first version we would construct a
representative of the factored permutation, apply it to the edges, and
factor the result into cycles, the new version does not construct
representatives and does no factorization and builds the terms for the
cycle index from first principles, namely that we enumerate the cycles
of edges (two-sets of vertices) that are obtained from a vertex
permutation by choosing pairs of vertices, counting these, and
computing the lengths of the cycles on which they reside. These
optimizations make for a faster and much more compact program. This
was the code:
pet_cycleind_symm :=
proc(n)
option remember;
if n=0 then return 1; fi;
expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;
pet_varinto_cind :=
proc(poly, ind)
local subs1, subs2, polyvars, indvars, v, pot, res;
res := ind;
polyvars := indets(poly);
indvars := indets(ind);
for v in indvars do
pot := op(1, v);
subs1 :=
[seq(polyvars[k]=polyvars[k]^pot,
k=1..nops(polyvars))];
subs2 := [v=subs(subs1, poly)];
res := subs(subs2, res);
od;
res;
end;
pet_flatten_termA :=
proc(varp)
local terml, d, cf, v;
terml := ;
cf := varp;
for v in indets(varp) do
d := degree(varp, v);
terml := [op(terml), [op(1,v), d]];
cf := cf/v^d;
od;
[cf, terml];
end;
pet_cycleind_knn :=
proc(n)
option remember;
local cindA, cindB, sind, t1, t2, term, res,
flat, flat1, flat2, len, l1, l2, cycs, uidx, vidx,
u, v, inst1;
if n=1 then
sind := [a[1]];
else
sind := pet_cycleind_symm(n);
fi;
cindA := 0;
for t1 in sind do
flat1 := pet_flatten_termA(t1);
for t2 in sind do
flat2 := pet_flatten_termA(t2);
res := 1;
for u in flat1[2] do
l1 := op(1, u);
for v in flat2[2] do
l2 := op(1, v);
len := lcm(l1, l2);
res := res *
a[len]^(op(2, u)*op(2, v)
*l1*l2/len);
od;
od;
cindA := cindA + flat1[1]*flat2[1]*res;
od;
od;
cindB := 0;
for term in sind do
flat := pet_flatten_termA(term);
cycs := map(cyc -> [2*cyc[1], cyc[2]], flat[2]);
res := 1;
# edges on different cycles of different sizes
for uidx to nops(cycs) do
u := cycs[uidx];
for vidx from uidx+1 to nops(cycs) do
v := cycs[vidx];
l1 := op(1, u); l2 := op(1, v);
res := res *
a[lcm(l1, l2)]^((l1*l2/2/lcm(l1, l2))*
op(2, u)*op(2, v));
od;
od;
# edges on different cycles of the same size
for uidx to nops(cycs) do
u := cycs[uidx];
l1 := op(1, u); inst1 := op(2, u);
# a[l1]^(1/2*inst1*(inst1-1)*l1*l1/2/l1)
res := res *
a[l1]^(1/2*inst1*(inst1-1)*l1/2);
od;
# edges on identical cycles of some size
for uidx to nops(cycs) do
u := cycs[uidx];
l1 := op(1, u); inst1 := op(2, u);
if type(l1/2, even) then
# a[l1]^((l1/2)^2/l1);
res := res *
(a[l1]^(l1/4))^inst1;
else
# a[l1/2]^(l1/2/(l1/2))*a[l1]^(((l1/2)^2-l1/2)/l1)
res := res *
(a[l1/2]*a[l1]^(l1/4-1/2))^inst1;
fi;
od;
cindB := cindB + flat[1]*res;
od;
(cindA+cindB)/2;
end;
v_pre_pie :=
proc(n)
option remember;
local cind, gf;
cind := pet_cycleind_knn(n);
gf := pet_varinto_cind(1+z, cind);
subs(z=1, gf);
end;
This will produce the following data for the non-isomorphic spanning
subgraphs of $K_{6,6}$ including reflections classified according to
the number of edges:
$${z}^{36}+{z}^{35}+2,{z}^{34}+4,{z}^{33}+10,{z}^{32}
+20,{z}^{31}+50,{z}^{30}+99,{z}^{29}+227,{z}^{28}
\ +458,{z}^{27}+934,{z}^{26}+
1711,{z}^{25}+3057,{z}^{24}+4889,{z}^{23}+7400,{z}^{22}
\ +10071,{z}^{21}+12755,{z}^{20}+14524,{z}^{19}
+15331,{z}^{18}+14524,{z}^{17}+12755,{z}^{16}
\+10071,{z}^{15}+7400,{z}^{14}+4889,{z}^{13}+
3057,{z}^{12}+1711,{z}^{11}+934,{z}^{10}
\ +458,{z}^{9}+227,{z}^{8}+99,{z}^{7}+50,{z}^{6}+20,{z}^{5}
+10,{z}^{4}+4,{z}^{3}+2,{z}^{2}+z+1.$$
i.e. the value four for three edges counts, first, a set of three
edges, not connected, second, two edges sharing a vertex and a single
edge, third, three edges emanating from the same vertex and fourth, a
path of three edges.
Addendum. We may use Burnside as shown below if we are not
interested in classifying according to the number of edges and require
only the total count. This gives:
Q :=
proc(n)
option remember;
local cind;
cind := pet_cycleind_knn(n);
subs([seq(a[p]=2, p=1..n*n)], cind);
end;
The routine that substitutes polynomials into cycle indices is no
longer needed in this case. Observe that further simplification at the
expense of readability is possible by not computing the cycle index at
all and setting all $a[p]$ to two during the computation of what used
to be the cycle index.
$endgroup$
Adding another answer after receiving a pointer from a reader of this
thread. We treat the case of spanning subgraphs of $K_{n,n}$ including
reflections. The algorithm has been greatly simplified. There are two
types of symmetries, namely shuffles within the two sets of vertices
and reflections that map one to the other. The first type has been
simplified as follows: we continue to iterate over pairs of
permutation shapes from $S_n$ but the contribution to the cycle index
$Z(Q_n)$ is now computed by iterating over pairs of cycle types (same
length) rather than single cycles. The second type (reflections) has
been replaced in its entirety. We continue to produce contributions
by building factorized permutations consisting of cycles that
alternate between the two classes of vertices (a precondition of this
problem) but whereas in the first version we would construct a
representative of the factored permutation, apply it to the edges, and
factor the result into cycles, the new version does not construct
representatives and does no factorization and builds the terms for the
cycle index from first principles, namely that we enumerate the cycles
of edges (two-sets of vertices) that are obtained from a vertex
permutation by choosing pairs of vertices, counting these, and
computing the lengths of the cycles on which they reside. These
optimizations make for a faster and much more compact program. This
was the code:
pet_cycleind_symm :=
proc(n)
option remember;
if n=0 then return 1; fi;
expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;
pet_varinto_cind :=
proc(poly, ind)
local subs1, subs2, polyvars, indvars, v, pot, res;
res := ind;
polyvars := indets(poly);
indvars := indets(ind);
for v in indvars do
pot := op(1, v);
subs1 :=
[seq(polyvars[k]=polyvars[k]^pot,
k=1..nops(polyvars))];
subs2 := [v=subs(subs1, poly)];
res := subs(subs2, res);
od;
res;
end;
pet_flatten_termA :=
proc(varp)
local terml, d, cf, v;
terml := ;
cf := varp;
for v in indets(varp) do
d := degree(varp, v);
terml := [op(terml), [op(1,v), d]];
cf := cf/v^d;
od;
[cf, terml];
end;
pet_cycleind_knn :=
proc(n)
option remember;
local cindA, cindB, sind, t1, t2, term, res,
flat, flat1, flat2, len, l1, l2, cycs, uidx, vidx,
u, v, inst1;
if n=1 then
sind := [a[1]];
else
sind := pet_cycleind_symm(n);
fi;
cindA := 0;
for t1 in sind do
flat1 := pet_flatten_termA(t1);
for t2 in sind do
flat2 := pet_flatten_termA(t2);
res := 1;
for u in flat1[2] do
l1 := op(1, u);
for v in flat2[2] do
l2 := op(1, v);
len := lcm(l1, l2);
res := res *
a[len]^(op(2, u)*op(2, v)
*l1*l2/len);
od;
od;
cindA := cindA + flat1[1]*flat2[1]*res;
od;
od;
cindB := 0;
for term in sind do
flat := pet_flatten_termA(term);
cycs := map(cyc -> [2*cyc[1], cyc[2]], flat[2]);
res := 1;
# edges on different cycles of different sizes
for uidx to nops(cycs) do
u := cycs[uidx];
for vidx from uidx+1 to nops(cycs) do
v := cycs[vidx];
l1 := op(1, u); l2 := op(1, v);
res := res *
a[lcm(l1, l2)]^((l1*l2/2/lcm(l1, l2))*
op(2, u)*op(2, v));
od;
od;
# edges on different cycles of the same size
for uidx to nops(cycs) do
u := cycs[uidx];
l1 := op(1, u); inst1 := op(2, u);
# a[l1]^(1/2*inst1*(inst1-1)*l1*l1/2/l1)
res := res *
a[l1]^(1/2*inst1*(inst1-1)*l1/2);
od;
# edges on identical cycles of some size
for uidx to nops(cycs) do
u := cycs[uidx];
l1 := op(1, u); inst1 := op(2, u);
if type(l1/2, even) then
# a[l1]^((l1/2)^2/l1);
res := res *
(a[l1]^(l1/4))^inst1;
else
# a[l1/2]^(l1/2/(l1/2))*a[l1]^(((l1/2)^2-l1/2)/l1)
res := res *
(a[l1/2]*a[l1]^(l1/4-1/2))^inst1;
fi;
od;
cindB := cindB + flat[1]*res;
od;
(cindA+cindB)/2;
end;
v_pre_pie :=
proc(n)
option remember;
local cind, gf;
cind := pet_cycleind_knn(n);
gf := pet_varinto_cind(1+z, cind);
subs(z=1, gf);
end;
This will produce the following data for the non-isomorphic spanning
subgraphs of $K_{6,6}$ including reflections classified according to
the number of edges:
$${z}^{36}+{z}^{35}+2,{z}^{34}+4,{z}^{33}+10,{z}^{32}
+20,{z}^{31}+50,{z}^{30}+99,{z}^{29}+227,{z}^{28}
\ +458,{z}^{27}+934,{z}^{26}+
1711,{z}^{25}+3057,{z}^{24}+4889,{z}^{23}+7400,{z}^{22}
\ +10071,{z}^{21}+12755,{z}^{20}+14524,{z}^{19}
+15331,{z}^{18}+14524,{z}^{17}+12755,{z}^{16}
\+10071,{z}^{15}+7400,{z}^{14}+4889,{z}^{13}+
3057,{z}^{12}+1711,{z}^{11}+934,{z}^{10}
\ +458,{z}^{9}+227,{z}^{8}+99,{z}^{7}+50,{z}^{6}+20,{z}^{5}
+10,{z}^{4}+4,{z}^{3}+2,{z}^{2}+z+1.$$
i.e. the value four for three edges counts, first, a set of three
edges, not connected, second, two edges sharing a vertex and a single
edge, third, three edges emanating from the same vertex and fourth, a
path of three edges.
Addendum. We may use Burnside as shown below if we are not
interested in classifying according to the number of edges and require
only the total count. This gives:
Q :=
proc(n)
option remember;
local cind;
cind := pet_cycleind_knn(n);
subs([seq(a[p]=2, p=1..n*n)], cind);
end;
The routine that substitutes polynomials into cycle indices is no
longer needed in this case. Observe that further simplification at the
expense of readability is possible by not computing the cycle index at
all and setting all $a[p]$ to two during the computation of what used
to be the cycle index.
edited Jun 20 '17 at 20:03
answered Jun 14 '17 at 23:12
Marko RiedelMarko Riedel
41.1k340111
41.1k340111
add a comment |
add a comment |
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1151538%2ffinding-the-spanning-subgraphs-of-a-complete-bipartite-graph%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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