Conference rusure::math

F'rinstance, a place to start is to show that a regular edge-but-not-vertex-
transitive graph must be a subgraph, G, of K(n,n), for some n, where G has
2n vertices.

Regards,
Andrew.

	Define edge-transitive, vertex-transitive, and regular. :-)

	I know what you mean by graph and bipartite graph K(a,b):

		graph:	an ordered pair of sets (V,E) where elements
			of E (edges) are unordered pairs of elements
			of V (vertexes or vertices).

		complete graph K(n):	a graph (V,E) where V has n
			elements and E contains every unordered pair
			from V.

		bipartite graph K(n,m):	a graph (V,E) where V is a
			disjoint union of V1 and V2, where V1 has n
			elements, V2 has m elements, and E contains
			every unordered pair of an element of V1 and
			an element of V2 (and only those pairs).

	Dan

>	Define edge-transitive, vertex-transitive, and regular. :-)

	Yessuh.


	A graph is regular iff every vertex has the same degree.   ie, every
vertex is adjacent to the same number of edges, k.


	Given a graph, G, a graph automorphism (AM) is a permutation of the
vertices which preserves the structure of the graph.   ie: � is a
graph AM of G, iff

	for all u,v vertices of G,
	uv is an edge of G <=> �(u)�(v) is an edge of G.

	Loosely, the graph-AM maps vertices to vertices and edges to edges.   
The graph-AMs form a group, naturally.   Call the group A.   A can then be 
regarded as a permutation group, A_v, of the vertices, or it can be regarded 
as a permutation group, A_e, of the edges.

	A permutation group, P, is *transitive* if for any elements a & b of
the set being permuted, there is an element p of P mapping a to b.   
Transitivity is a key concept of permutation groups.

	Returning to the graph context, we say that G is vertex-transitive iff
A_v is transitive, and edge-transitive iff A_e is transitive.


>		bipartite graph K(n,m):	a graph (V,E) where V is a
>			disjoint union of V1 and V2, where V1 has n
>			elements, V2 has m elements, and E contains
>			every unordered pair of an element of V1 and
>			an element of V2 (and only those pairs).

	Not quite.   You've defined the complete bipartite graph, K(n,m).
A general bipartite graph need not contain *all* the edges linking V1 & V2.

Regards,
Andrew.

	Thanks for the definitions and the correction, Andrew.

>>	The bipartite graph K(a,b) is an example of a graph which is edge-
>> transitive but not vertex-transitive.   Can you find a *regular* graph
>> which has this property?   (I'm told there are some.)

	Can you give us a hint?  Like a minimum number of vertexes
	under which we shouldn't bother to look?

	Dan

>	Can you give us a hint?  Like a minimum number of vertexes
>	under which we shouldn't bother to look?

	Well, the first step is to look at .1, which restricts enormously
the kinds of graph that could have this property.   Then it's pretty
obvious that the number of vertices must be at least 12.   I don't know
anything about the solution, except that it is "not at all easy to
find" these graphs.

	I would suggest toying with graphs with additional constraints:
eg: bipartite with vertex set partitioned into L & R, such that each vertex
in L has a twin, also in L, with exactly the same neighbours.   But no
vertex in R has this property.   If you can do this edge-transitively, then
you're home.

Regards,
Andrew.

>	I would suggest toying with graphs with additional constraints:
>eg: bipartite with vertex set partitioned into L & R, such that each vertex
>in L has a twin, also in L, with exactly the same neighbours.   But no
>vertex in R has this property.   If you can do this edge-transitively, then
>you're home.

	Along the lines above, I've come up with *a* solution, on 24 vertices
with degree 4.

	Let the vertices in L be l_1,...,l_6, m_1,...,m_6.   Then let (i,j) 
denote that there is a vertex in R adjacent to l_i, l_j, m_i & m_j.   Our
graph is defined by the list of all 15 possible pairs (i,j) *except*:

	(1,2), (3,4), (5,6)

	This satisfies all the requirements, I think.

	Question: is there an solution on a smaller number of vertices?

Regards,
Andrew.

>	Question: is there an solution on a smaller number of vertices?

	Yes, there's one on 20 vertices, also I've located solutions of
order 32 and 36.

	Let me try to generalize a little the construction that I'm
using here.

	If I have a vertex-transitive *and* edge-transitive graph, G, of order 
g, and degree 4, then I can build an edge-transitive but *not* vertex-transitive
regular graph, G', of order 4*g, and degree 4.

	I label the vertices of G as 1,...,g and the vertices of G' as
l_1,...,l_g, m_1,...,m_g, r_1,...,r_(2*g).   I label the edges of G 1,...,2*g.
Then if edge e of G links i to j, this determines that in G', r_e is adjacent
to l_i, l_j, m_i and m_j.

	Now, building suitable G is not too difficult.

	For g = 5, K5 does the job.
	For g = 6, K(2,2,2) (complete tripartite) gives the solution in -.1
	For g = 7, there is no such graph.
	For g = 8, K(4,4)
	For g = 9, imagine 9 vertices in a 3-by-3 torus.   a links to b iff
they are either in the same row or the same column.

Questions abound:

	(1) can we do better than 20 as the minimum solution?
	(2) can we show there are an infinite number of connected 4-regular 
edge-transitive graphs?
	(3) what about degree 3 graphs?

Regards,
Andrew.