[r-t] q-sets

[Philip Saddleton]

Alexander Holroyd said  on 08/09/2006 04:02:
> But does anyone know general conditions under which such a thing is 
> possible (where "such a thing" means roughly: joining an odd number of 
> blocks to form an extent using q-sets of size 3)?  Was it obvious 
> immediately that it would work in this case?  And does anyone know an easy 
> way to find such a joining other than lots of trial and error?
> 
> (Sorry if this isn't very clear, but I don't know exactly what the correct 
> question is!)

We have a graph with each vertex representing a block, and q-sets are 
triangles made up of the three edges that they connect.

For it to be possible to connect all the blocks with the minimum number 
of q-sets (i.e. n for 2n+1 blocks), it is sufficient that the graph 
formed by these q-sets is connected. Clearly we can arbitrarily remove 
one edge from each q-set and the graph will be still be connected. It 
now has 2n edges, and so is a tree.

I don't think that much can be said for the more general case. My guess 
is that would be quite easy to construct an example where it is not 
possible (without imposing any group structure), but can anyone find one 
where the graph is regular? (If you understand what I mean.)

-- 
Regards
Philip
http://www.saddleton.freeuk.com/