DIMACS Discrete Mathematics Seminar


The rank of the intersection of free groups and a conjecture in graph theory


Gabor Tardos
Mathematical Institute of Hungary


CoRE Building, Room 431
Busch Campus, Rutgers University


4:30 PM
Tuesday, September 19, 1995


The talk is on partial results about a graph-theoretic conjecture that is equivalent to the 40 year old Hanna Neumann Conjecture on the intersection of free groups.

By the Nielsen-Schreier theorem any subgroup of a free group is free. Let us take two subgroups of a free group now. Clearly both of them and also the intersection is free and therefore characterised up to isomorphism by their rank (number of free generators). Suppose the two subgroups have finite ranks k+1 and l+1 what can be the rank of the intersection. Hanna Neumann conjectured that kl+1 is an upper bound but was only able to prove that the rank is at most 2kl+1. This upper bound has been hardly improved since.

While connection to graph theory was noted earlier, W. Dicks has recently proved that the following Amalgamated Graph Conjecture is equivalent to a strengthened form the Hanna Neumann Conjecture.

By graph we mean two-colored simple bipartite graphs, that is the two-coloring is also given with the graph and oppositely colored graphs are not considered isomorphic (unless they are symmetric).

The Amalgamated Graph Conjecture states:

Let us take three graphs G_1, G_2 and G_3, such that G_1 \cap G_2 = G_2 \cap G_3 = G_3 \cap G_1 = G and suppose that the connected components of the three graphs G_1 \cup G_2 and G_2 \cup G_3 and G_3 \cup G_1 are isomorphic in pairs. The conjecture states that in this case G has at most half as many edges "as it could have" i.e. the number of edges is at most half the product of the number of vertices on one side times the number of vertices on the other side.

In the talk I will focus on the special cases of the conjecture solved and time permits, I will sketch the equivalence to the group theoretic question as well.

Document last modified on September 15, 1995