Combinatorics/Graphs problem

And by 'graph' I mean graph theory graphs, not bar chart graphs.

You've got n blue vertices and m red vertices. You cannot connect red to red or blue to blue but you can connect as many of one colour to a single vertex of the other colour. How many different connected graphs can you draw?

What if you allow a blue vertex to be connected to itself but not to any other blue vertex?

Given I'm useless at combinatorics like this, I have no idea how I'd go about solving this other than drawing a bucket load and trying to spot some pattern but that wouldn't be a proof, just as conjecture.

Anyone got any ideas the answer? I'm working with a system where n+m=4, which is easy to do with 2 coloured pens and brute force. I'm not interested in subtle hints because I'm not trying to learn graph theory or combinatorics, I'm just interested in the result out of curiosity. Thanks

Please Register or Log in to view the hidden image!

 

Log in or Sign up to hide all adverts.

Do all vertices have to be connected to at least another?

 

Log in or Sign up to hide all adverts.

If you start from a red, you have m choices first. Then n choices to which blue vertex you go to. Then m choices to which red vertex you go to.... and so on. Keep going until you hit the desired number of edges you're permitting your graph to have.

 

Log in or Sign up to hide all adverts.

Yes, that's the 'connected' condition. It means that you cannot have graphs with say n=0, m>2 because the reds would have to join.

As with most of my threads here, it's all to do with Lie algebras and a non-connected graph would be equivalent to a direct sum of algebras. The constraint that red connects to blue only and vice versa descends from Jacobi constraints on generators.

I'll upload something shortly to explain what the heck I'm talking about, for those who know what Lie algebras involve, so I can get comments.

/edit

On seeing Guest's comment I forgot about an additional constraint. You cannot go from a blue to a red and then back to the same blue. One line only connects any two vertices.

 

I think I know what you're on about, but I can't help, I'm just interested.

 

I don't suppose you could give an example of permissible and impermissible graphs could you? If I'm interpreting the scenario correctly, then it's fairly straight forward to give a coarse upper bound, but it's not immediately obvious to me how you could get a tractable, closed form solution. It's late though, and I've been celebrating Hamilton's win, so perhaps my maths has left me...

 

Here's an explanation of what I'm thinking/talking about :

http://www.hep.phys.soton.ac.uk/~g.j.weatherill/image_files/algebra2.jpg
http://www.hep.phys.soton.ac.uk/~g.j.weatherill/image_files/algebra1.jpg
http://www.hep.phys.soton.ac.uk/~g.j.weatherill/image_files/algebra3.jpg
http://www.hep.phys.soton.ac.uk/~g.j.weatherill/image_files/algebra4.jpg

Excuse the terrible handwriting and variety of misspellings or incorrect words.

 

Ooh - this looks interesting. It's a little late now, but I'll hopefully get chance to look at it tomorrow. A small note: it would be easier, from your POV, to separate the blue and red dots if you're hoping to do some graph counting.

 

Let me just throw in a keyword here:

http://en.wikipedia.org/wiki/Bipartite_graph

 

Not counting colored graphs or graphs with nodes connected to each other there are 11 distinct graphs on four nodes, A,B,C,D if the nodes are indistinguishable.

http://keithbriggs.info/images/g4.pdf

For Red-Blue bipartite graphs, any subgraph which is connected must have no odd-numbered cycles. So the way I chose to count we have

Number of distinct ways to two-color: 17
Number of ways to two-color with self-connected blues: 49

Case 1: Disconnected: A,B,C,D
Number of distinct ways to two-color: 5=(1+4)
Number of ways to two-color with self-connected blues: 15=T(5)
Ar,Br,Cr,Dr
Ar,Br,Cr,Db;Ar,Br,Cr,Db*
Ar,Br,Cb,Db;Ar,Br,Cb,Db*;Ar,Br,Cb*,Db*
Ar,Bb,Cb,Db;Ar,Bb,Cb,Db*;Ar,Bb,Cb*,Db*;Ar,Bb*,Cb*,Db*
Ab,Bb,Cb,Db;Ab,Bb,Cb,Db*;Ab,Bb,Cb*,Db*;Ab,Bb*,Cb*,Db*;Ab*,Bb*,Cb*,Db*

Case 2: Connected(A,B),Disconnected(C,D)
Number of distinct ways to two-color: 3 = 1(1+2)
Number of ways to two-color with self-connected blues: 9=T(4)-T(1)
Ar,Bb,Cr,Dr;Ar,Bb*,Cr,Dr
Ar,Bb,Cr,Db;Ar,Bb*,Cr,Db*;Ar,Bb*,Cr,Db*
Ar,Bb,Cb,Db;Ar,Bb,Cb,Db*;Ar,Bb,Cb*,Db*;Ar,Bb*,Cb*,Db*

Case 3: Star(B;A,C),Disconnected(D) [ or OddChain(A,B,C),Disconnected(D) ]
Number of distinct ways to two-color: 4 = 2(1+1)
Number of ways to two-color with self-connected blues: 12= [T(3)-T(1)]+[T(4)-T(2)]
Ar,Bb,Cr,Dr;Ar,Bb*,Cr,Dr;
Ar,Bb,Cr,Db;Ar,Bb,Cr,Db*;Ar,Bb*,Cr,Db*
Ab,Br,Cb,Dr;Ab,Br,Cb*,Dr;Ab*,Br,Cb*,Dr;
Ab,Br,Cb,Db;Ab,Br,Cb,Db*;Ab,Br,Cb*,Db*;Ab*,Br,Cb*,Db*

Case 4:Star(A;B,C,D),Disconnected()
Number of distinct ways to two-color: 2 = 2(1+0)
Number of ways to two-color with self-connected blues: 6= [T(2)-T(1)]+[T(4)-T(3)]
Ar,Bb,Cb,Db;Ar,Bb,Cb,Db*;Ar,Bb,Cb*,Db*;Ar,Bb*,Cb*,Db*
Ab,Br,Cr,Dr;Ab*,Br,Cr,Dr

Case 5: Connected(A,B),Connected(C,D),Disconnected()
Number of distinct ways to two-color: 1 = 1*1*(1+0)
Number of ways to two-color with self-connected blues: 3= [T(3)-T(2)]
Ar,Bb,Cr,Db;Ar,Bb,Cr,Db*;Ar,Bb*,Cr,Db*

Case 6: EvenChain(A,B,C,D),Disconnected()
Number of distinct ways to two-color: 1 = 1*(1+0)
Number of ways to two-color with self-connected blues: 3= [T(3)-T(2)]
Ar,Bb,Cr,Db;Ar,Bb,Cr,Db*;Ar,Bb*,Cr,Db*

Case7: Connected(A,B,C),Disconnected(D) [or OddCycle(A,B,C),Disconnected(D)]
Number of distinct ways to two-color: 0 = 0*(1+1)
Number of ways to two-color with self-connected blues: 0

Case8: Connected(A,B,C),Connected(A,D),Disconnected()
Number of distinct ways to two-color: 0 = 0*1*(1+0)
Number of ways to two-color with self-connected blues: 0

Case9: EvenCycle(A,B,C,D),Disconnected()
Number of distinct ways to two-color: 1 = 1*(1+0)
Number of ways to two-color with self-connected blues: 3= [T(3)-T(2)]
Ar,Bb,Cr,Db;Ar,Bb,Cr,Db*;Ar,Bb*,Cr,Db*

Case10: Connected(A,B,C),Connected(A,B,D),Disconnected()
Number of distinct ways to two-color: 0 = 0*0*(1+0)
Number of ways to two-color with self-connected blues: 0

Case11: Connected(A,B,C,D),Disconnected()
Number of distinct ways to two-color: 0 = 0*(1+0)
Number of ways to two-color with self-connected blues: 0

// Added:
Requiring the graphs to be connected means you only have to consider cases 4, 6 and 9.

Number of distinct ways to two-color: 4
Number of ways to two-color with self-connected blues: 12

Requireing each node to be connected a node distinct from itself, means you only have to consided cases 4, 5, 6 and 9.

Number of distinct ways to two-color: 5
Number of ways to two-color with self-connected blues: 15

But, if you require each node to be connected to a node, possibly itself, then this requires all the disconnected nodes to be connected to themselves and therefore blue. So all of 4, 5, 6, and 9 and of the others:

Case 1A) Disconnected: A,B,C,D
Number of distinct ways to two-color, all nodes connected at least once: 1
Ab*,Bb*,Cb*,Db*

Case 2A) Connected(A,B),Disconnected(C,D)
Number of distinct ways to two-color, all nodes connected at least once: 2
Ar,Bb,Cb*,Db*;Ar,Bb*,Cb*,Db*

Case 3A) Star(B;A,C),Disconnected(D) [ or OddChain(A,B,C),Disconnected(D) ]
Number of distinct ways to two-color, all nodes connected at least once: 5
Ar,Bb,Cr,Db*;Ar,Bb*,Cr,Db*
Ab,Br,Cb,Db*;Ab,Br,Cb*,Db*;Ab*,Br,Cb*,Db*

Number of distinct ways to two-color: 8
Number of ways to two-color with self-connected blues: 23

 

Seperating the blue and the red sounds like a good idea. I've been mentally doing that when drawing the graphs, thinking to myself "This blue connects to 3 red and then the other blue can connect to 1, 2 or 3 red". Didn't occur to me to seperate them on the paper too!

Rpenner, I had a feeling this might be something you'd have a go at

Please Register or Log in to view the hidden image!

You say that if we consider 4 vertices then there's 5 graphs if we exclude loops and 15 if we don't. Are you distinguishing between graphs which look the same?

For instance, the second graph in the first row here is only counted once, though if you distinguish between the two blues (ie blue1, blue2) then you can construct a graph which looks exactly the same but has it's su(2) loop on the other blue. It's a bit like Feynman diagrams, you have to take into account the symmetry factors of a graph.

If I'm mistaken and you're only considering topologically distinct graphs which ones am I missing in the case of 4 vertices? I've got 4 loop-less ones and another 9 with loops.

Please Register or Log in to view the hidden image!

As the pictures/pages I linked to in my previous post explain, this is all in an attempt to construct a bunch of valid Lie algebras. Until I realised the 2 chain restriction I was trying to get 'algebras' with graphs like O-O-O-O to work, failing to realise they didn't actually represent proper algebras. No wonder I got empty varieties (ie no solutions)! The graphs are not invariant under a change of basis. If you defined new generators from linear combinations of old generators, the graphs would change, most likely unable to represent the algebra because there'd be non-zero [S,T] terms. Hence it's not trivial that two different graphs represent two different algebras. I'm pretty confident that any two tree graphs represent different algebras because any change of basis from a tree to a tree will effectively be a relabelling of your generators (calling say T's S's and S's T's etc) and the graphs are independent of that. But for the graphs which have loops in them, not su(2) loops but loops involving 4 or more vertices (has to be an even number greater than 2) I am not entirely sure they will be certain to represent new algebras.

It's all fairly academic in the sense I'm working with 4 vertex graphs and I can check those by hand, as before I'm more wondering out of curiosity. It'd be nice if they were distinct algebras. I think it's a nice construction method which makes the subalgebras (ie subgraphs) immediately obvious

Please Register or Log in to view the hidden image!

 

If you have 4 uncolored vertices, there are just 11 distinct ways to make a undirected graph, corresponding to the diagram and the 11 "cases". Not all of these are connected graphs, not all of these have vertices without any edges, and not all of them can be 2-colored.

For four unconnected vertices, there are 5 distinct ways to two-color them, but if the blue ones can optionally self-connect, then there are 15 distinct ways to do that. (Case 1, which assumes no edge connects two verticies). But if every vertex MUST have an edge or self-connection, then you get case 1A where all four vertices must be blue and self-connected.

I'm counting only topologically distinct graphs. (Ar-Bb) is considered the same as (Ab-Br) but distinct from (Ar-Bb*). (* represents self-connection and only appears on blue nodes).

 

I think I forgot to say that in the case of su(2) loops, ie self connecting blues, in order to give an algebra which isn't just the direct sum of su(2) and some lower dimensional algebra, the self connecting blues must also be connected to at least one red, hence making the graph connected overall.

A connected graph without self-connections will be nilpotent (Cartan-Killing metric is exactly zero etc) but the same graph with a self connecting blue will have a C-K metric which isn't exactly zero (but still singular, other than the 1 vertex graph case).

In regard to my previous post and musings about different algebras from different graphs, for those who know about Lie algebras am I right in thinking that the dimension of the centre of an algebra is invariant under generator transformations? If so then it means graphs with different numbers of red vertices (whose generators commute with themselves and everyone else) cannot be isomorphic. Then it reduces the issue to considering loop (though not the su(2) loop) graphs with the same number of red and blue vertices, ie if \(G_{n,m}\) is the set of graphs with n blues and m reds, it is not possible for an element of \(G_{n,m}\) to represent the same algebra as an element of \(G_{n',m'}\) when \(n \not= n'\) or \(m \not= m'\).

 

And we're back.

Just for the case when the 4 vertices aren't connected to each other.

I am counting only up to isomorphism.

That diagram appears exactly once in my list:

Your 4 connected graphs without self-connections ones the first entries of each row in cases 4, 6 and 9. Adding self-connections, I counted only 8 more. Now, I see that I didn't count the middle case of row 2. So I get 9 also.

Revised:
Case 6: EvenChain(A,B,C,D),Disconnected()
Number of distinct ways to two-color: 1 = 1*(1+0)
Number of ways to two-color with self-connected blues: 3= [T(3)-T(2)] 4 (formula doesn't work because no automorphism swaps the blues!)
Ar,Bb,Cr,Db;Ar,Bb,Cr,Db*;Ar,Bb*,Cr,Db* + Ar,Bb*,Cr,Db

12 Dimensions with su(2) terms
\(\begin{array}{ccc} \left( {\textrm{Case 4} \\ Ab*,Br,Cr,Dr } \right) & \left( {\textrm{Case 9} \\ Ar,Bb,Cr,Db* } \right) & \left( {\textrm{Case 9} \\ Ar,Bb*,Cr,Db* } \right) \\ \left( {\textrm{Case 6} \\ Ar,Bb,Cr,Db* } \right) & \left( {\textrm{Case 6} \\ Ar,Bb*,Cr,Db } \right) & \left( {\textrm{Case 6} \\ Ar,Bb,Cr,Db* } \right) \\ \left( {\textrm{Case 4} \\ Ar,Bb,Cb,Db* } \right) & \left( {\textrm{Case 4} \\ Ar,Bb,Cb*,Db* } \right) & \left( {\textrm{Case 4} \\ Ar,Bb*,Cb*,Db* } \right) \end{array}\)

// Lesson Learned: While the two-color without self-connections worked, not all blue nodes are equivalent which complicates the counting.

 

So many errors. As before, only cases 4,6 and 9 appear to matter to AlphaNumeric.

Case 1: Disconnected: A,B,C,D
Number of distinct ways to two-color: 5=(1+4)
Number of ways to two-color with self-connected blues: 15=T(5)
Ar,Br,Cr,Dr
Ar,Br,Cr,Db;Ar,Br,Cr,Db*
Ar,Br,Cb,Db;Ar,Br,Cb,Db*;Ar,Br,Cb*,Db*
Ar,Bb,Cb,Db;Ar,Bb,Cb,Db*;Ar,Bb,Cb*,Db*;Ar,Bb*,Cb*,Db*
Ab,Bb,Cb,Db;Ab,Bb,Cb,Db*;Ab,Bb,Cb*,Db*;Ab,Bb*,Cb*,Db*;Ab*,Bb*,Cb*,Db*

Case 2: Connected(A,B),Disconnected(C,D)
Number of distinct ways to two-color: 3 = 1(1+2)
Number of ways to two-color with self-connected blues: 2*T(3)=12
Ar,Bb,Cr,Dr;Ar,Bb*,Cr,Dr
Ar,Bb,Cr,Db;Ar,Bb*,Cr,Db;Ar,Bb,Cr,Db*;Ar,Bb*,Cr,Db*
Ar,Bb,Cb,Db;Ar,Bb,Cb,Db*;Ar,Bb,Cb*,Db*;Ar,Bb*,Cb,Db;Ar,Bb*,Cb,Db*;Ar,Bb*,Cb*,Db*;

Case 3: Star(B;A,C),Disconnected(D) [ or OddChain(A,B,C),Disconnected(D) ]
Number of distinct ways to two-color: 4 = 2(1+1)
Number of ways to two-color with self-connected blues: 15
Ar,Bb,Cr,Dr;Ar,Bb*,Cr,Dr;
Ar,Bb,Cr,Db;Ar,Bb,Cr,Db*;Ar,Bb*,Cr,Db*;Ar,Bb*,Cr,Db
Ab,Br,Cb,Dr;Ab,Br,Cb*,Dr;Ab*,Br,Cb*,Dr
Ab,Br,Cb,Db;Ab,Br,Cb*,Db;Ab*,Br,Cb*,Db;Ab,Br,Cb,Db*;Ab,Br,Cb*,Db*;Ab*,Br,Cb*,Db*

Case 4:Star(A;B,C,D),Disconnected()
Number of distinct ways to two-color: 2 = 2(1+0)
Number of ways to two-color with self-connected blues: 6= [T(2)-T(1)]+[T(4)-T(3)]
Ar,Bb,Cb,Db;Ar,Bb,Cb,Db*;Ar,Bb,Cb*,Db*;Ar,Bb*,Cb*,Db*
Ab,Br,Cr,Dr;Ab*,Br,Cr,Dr

Case 5: Connected(A,B),Connected(C,D),Disconnected()
Number of distinct ways to two-color: 1 = 1*1*(1+0)
Number of ways to two-color with self-connected blues: 3= [T(3)-T(2)]
Ar,Bb,Cr,Db;Ar,Bb,Cr,Db*;Ar,Bb*,Cr,Db*

Case 6: EvenChain(A,B,C,D),Disconnected()
Number of distinct ways to two-color: 1 = 1*(1+0)
Number of ways to two-color with self-connected blues: 4
Ar,Bb,Cr,Db;Ar,Bb,Cr,Db*;Ar,Bb*,Cr,Db*;Ar,Bb*,Cr,Db

Case7: Connected(A,B,C),Disconnected(D) [or OddCycle(A,B,C),Disconnected(D)]
Number of distinct ways to two-color: 0 = 0*(1+1)
Number of ways to two-color with self-connected blues: 0

Case8: Connected(A,B,C),Connected(A,D),Disconnected()
Number of distinct ways to two-color: 0 = 0*1*(1+0)
Number of ways to two-color with self-connected blues: 0

Case9: EvenCycle(A,B,C,D),Disconnected()
Number of distinct ways to two-color: 1 = 1*(1+0)
Number of ways to two-color with self-connected blues: 3= [T(3)-T(2)]
Ar,Bb,Cr,Db;Ar,Bb,Cr,Db*;Ar,Bb*,Cr,Db*

Case10: Connected(A,B,C),Connected(A,B,D),Disconnected()
Number of distinct ways to two-color: 0 = 0*0*(1+0)
Number of ways to two-color with self-connected blues: 0

Case11: Connected(A,B,C,D),Disconnected()
Number of distinct ways to two-color: 0 = 0*(1+0)
Number of ways to two-color with self-connected blues: 0

 

Total number of possible edges is nm. There is a unique graph with this many edges.
Consider nm-a (a<=nm) edges. Then you have nmCa (nm choose a - sorry not Tex today) number of possible graphs.

So total number of graphs is sum from 0 to nm of nmCa. That is 2^nm graphs.

 

I forgot to discount the disconnected graphs. A grapg is disconnected if any vertex has no adjacent vertex.
Delete a vertex from blue (n blues, say). Thats n ways to choose this vertex and n*2^(n-1)m possible graphs left. Delete any red and we have m*2^n(m-1) graphs.

Delete a blues and you have nCa*2^(n-a)m graphs, similarly delete a reds and you have mCa*2^n(m-a) graphs. We need to discount ALL of these, summing a from 0 to n and to m separately.

 

Human, that ignores the fact that some of your graphs will be topologically identical. That multiplicity gets even more significant when you consider putting in the self connections on blue vertices. For instance, the n=3, m=1 graph has a kind of Z_3 symmetry and while there's 3 vertices to choose where to put an su(2) loop they are all the same so you only get one counted, not three.

If the vertices of the same colour were distinct in some way and we weren't restricted to connected graphs then your counting would be correct.

/edit

You posted while I was typing. You've realised about the connected-ness but I think you're still counting multiple topologically identical graphs.

 

I see. Doesnt that simplify it? Well then for each count nmCa ALL the graphs are top. equiv. so just count 1.

So the answer is sum of a from 0 to nm of 1. which is nm+1. Thats before deleting disconnected graphs.

 

I've been doing the n+m=5 and am part of the way through n+m=6 (without su(2) loops) and it seems that the pattern relates to how you partition integers.

For instance, consider n+m=6.

(n,m) = (1,5) has a single diagram.
(n,m) = (2,4) has 6 distinct diagrams. If (A,B) are the number of edges connecting blue1 and blue2 and [a,b,c,d] likewise for red1 to red4 then you have diagrams with :

(1,4)[2,1,1,1]
(2,4)[2,2,1,1]
(3,4)[2,2,2,1]
(4,4)[2,2,2,2]
(2,3)[2,1,1,1]
(3,3)[2,2,1,1]

The ( , ) notation and [ , ] notation are independent of order, ie [a,b] = [b,a] etc because the vertices of the same colour are indistinguishable. It's clear that the numbers in [ , ] cannot exceed the length of ( , ), the sum of their entries must be the same (since every edge attaches to a vertex of each colour) and you only need consider from (n,m) = (1,N) to ( N/2 , N/2 ) (if N, the total number of indices, is odd then upto something like (2,3) when N=5, I can't be arsed to do the Floor function thing) due to the symmetry in exchanging reds and blues.

When n+m<6 there's only one topology for any (n,m) but for n+m>5 you can get more, as I've just realised for n+m=6, ie

(2,2,2)[3,2,1]
(2,2,2)[2,2,2]

Those two are constructed from the red-blue-red-blue-red-blue tree graph by adding another edge between the end red and either one of the remaining blues, giving either a 6 vertex loop or a 4 vertex loop with 'wings'.

This is getting more and more like some kind of GCSE coursework project, drawing dots and lines and counting different ways of making them. Thank goodness there's some underlying concept legitimising all these pictures!

Please Register or Log in to view the hidden image!

/edit

Unfortunately it seems things are not quite that straight forward with that notation because [3,3,1](3,3,1) doesn't exist. [3,3,1] implies 2 blues connect to all reds, yet (3,3,1) means only one blue connects to a particular red. [3,3,1] only pairs with the (3,2,2) partioning of 7 (ie 3+3+1=7=3+2+2). Hence it is not a matter of saying "Let there be E edges" (where E>= n+m-1), working out the non-trivial partitions of E (ie 7 = 6+1 is a non-trivial partition of 7, 7+0 is not).

Ah raspberries!